Seidel method

An iterative method for solving a system of linear algebraic equations $ Ax = b $. The solution $ x ^ {*} $ is found as the limit of a sequence

$$ x ^ {(k)} = ( x _ {1} ^ {(k)} \dots x _ {n} ^ {(k)} ) , $$

the terms of which are computed from the formula

$$ \tag{* } x _ {i} ^ {( k)} = - \sum _ { j=1 } ^ { i-1 } \frac{a _ {ij}}{a _ {ii}} x _ {j} ( k) - \sum _ { j = i+ 1 } ^ { n } \frac{a _ {ij}}{a _ {ii} } x _ {j} ^ {( k- 1)} + \frac{b _ i}{a _ {ii}} , $$

$$ i = 1 \dots n , $$

where the $ a _ {ij} $ are the entries of the matrix $ A $, $ b _ {i} $ the components of the vector $ b $, and the diagonal entries of $ A $ are assumed to be $ \neq 0 $. The use of (*) differs from the simple-iteration method only in the fact that, at step $ k $, computation of the $ i $-th component utilizes the previously computed $ k $-th approximations of the first $ i- 1 $ components.

The Seidel method can be expressed in matrix notation as follows. If $ A = B + C $, where

$$ B = \ \left \| \begin{array}{llll} a _ {11} & 0 &\dots & 0 \\ a _ {21} &a _ {22} &\dots & 0 \\ \dots &\dots &\dots &\dots \\ a _ {n1} &a _ {n2} &\dots &a _ {nn} \\ \end{array} \right \| , $$

$$ C = \left \| \begin{array}{lllll} 0 &a _ {12} &a _ {13} &\dots &a _ {1n} \\ 0 & 0 &a _ {23} &\dots &a _ {2n} \\ \dots &\dots &\dots &\dots &\dots \\ \dots &\dots &\dots &\dots &\dots \\ 0 & 0 & 0 &\dots & 0 \\ \end{array} \right \| , $$

then formula (*) in matrix notation is $ x ^ {( k)} = - B ^ {-1} Cx ^ {( k- 1)} + B ^ {-1} b $. The Seidel method is equivalent to simple iteration applied to the system $ x = - B ^ {-1} Cx + B ^ {-1} b $, which is equivalent to the initial system. The method is convergent if and only if all the eigenvalues of the matrix $ B ^ {-1} C $ are less than 1 in absolute value, or, equivalently, if all roots of the equation $ \mathop{\rm det} ( C + B \lambda ) = 0 $ are less than 1 in absolute value.

In practical work, the following sufficient conditions for convergence are more convenient. 1) Suppose that $ \sum _ {i \neq j } | a _ {ij} | \leq q | a _ {ii} | $, $ q < 1 $, for all $ i $, $ 1 \leq i < n $; then the Seidel method is convergent and the following estimate holds for the rate of convergence:

$$ \| x ^ {( k)} - x ^ {*} \| _ {1} \leq q \| x ^ {( k- 1)} - x ^ {*} \| ,\ \| x \| _ {1} = \max _ {1 \leq i \leq n } | x _ {i} | . $$

2) If $ A $ is a positive-definite Hermitian matrix, then the Seidel method is convergent.

The method falls into the category of relaxation methods (cf. Relaxation method), the most widely used of which is the hyperrelaxation method.

Among the available modifications of the Seidel method are methods that employ preliminary transformation of the system into an equivalent system $ x = Mx + f $( see [4]).

The method was proposed by L. Seidel in [1].

References

[1]	L. Seidel, Abh. Bayer. Akad. Wiss. Math.-Naturwiss. Kl. , 11 : 3 (1874) pp. 81–108
[2]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[3]	I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian)
[4]	D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra" , Freeman (1963) (Translated from Russian)

Comments

In the West this method is usually referred to as the Gauss–Seidel method, [a1]–[a4].

References

[a1]	C.-E. Fröberg, "Introduction to numerical analysis" , Addison-Wesley (1965) pp. §4.5
[a2]	W.H. Press, B.P. Flannery, S.A. Teukolsky, W.T. Vetterling, "Numerical recipes" , Cambridge Univ. Press (1986) pp. §17.5
[a3]	D.M. Young, R.T. Gregory, "A survey of numerical mathematics" , II , Dover, reprint (1988) pp. §16.5
[a4]	F.B. Hildebrand, "Introduction to numerical analysis" , Dover, reprint (1987) pp. §10.5