Writing the error as

e_{k} = x_{k} - x^{*}

gives

e_{k + 1} = H e_{k}

provided the fixed-point consistency condition

x^{*} = H x^{*} + v

holds. Convergence for every starting vector is therefore equivalent to

H^{k} \to 0

, which in finite dimensions is equivalent to

ρ (H) < 1.

These two conditions are necessary and sufficient.

ii

Solution

Let

D = diag (A)

x_{k + 1} = (I - D^{- 1} A) x_{k} + D^{- 1} b,

H = I - D^{- 1} A

and

v = D^{- 1} b

. If

A

is strictly diagonally dominant, every Gershgorin disc of

H

is centered at zero and has radius

\sum_{j \neq = i} \frac{∣ a _{ij} ∣}{∣ a _{ii} ∣} < 1.

Every eigenvalue therefore has modulus below one, so

ρ (H) < 1

and part (i) proves convergence.

There are no discussions about this article yet.

There are currently no matching articles.