Total-Step and Successive Overrelaxation Methods for LCP-Problems with Interval Data
Götz E. Alefeld · 1999
Let there be given an (n, n) matrix M and a vector q ∈ Rn. The linear complementarity problem (LCP-problem) consists in finding a vector x ∗ ≥ 0 such that Mx ∗ + q ≥ 0 and x∗T (Mx ∗ + q) = 0, (LCP) or to show that no such vector exists. This problem has many applications; see [1] and [2], for example. In this talk, we are starting with an (n, n) interval matrix [M] and an interval vector [q] with n components. Using the total-step method and the successive overrelaxation method, respectively, we compute interval vectors [xk] which (under certain conditions on [M] and [x0]) contain the solutions of (LCP) for all M ∈ [M] and all q ∈ [q]. Furthermore the convergence of {[xk]} to some limit [x∗] is shown. Applications to this problem can be found in [3]. Some