Namespaces
Variants
Actions

Difference between revisions of "Seidel method"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (typo)
 
(One intermediate revision by one other user not shown)
Line 16: Line 16:
  
 
$$  
 
$$  
x  ^ {(} k)  =  ( x _ {1}  ^ {(} k) \dots x _ {n}  ^ {(} k) ) ,
+
x  ^ {(k)} =  ( x _ {1}  ^ {(k)} \dots x _ {n}  ^ {(k)} ) ,
 
$$
 
$$
  
Line 22: Line 22:
  
 
$$ \tag{* }
 
$$ \tag{* }
x _ {i}  ^ {(} k)  =  - \sum _ { j= } 1 ^ { i- }  1
+
x _ {i}  ^ {( k)} =  - \sum _ { j=1 } ^ { i-1 }   
 
 
\frac{a _ ij}{a _ ii}
+
\frac{a _ {ij}}{a _ {ii}}
 
   x _ {j} ( k) - \sum _ { j = i+ 1 } ^ { n }   
 
   x _ {j} ( k) - \sum _ { j = i+ 1 } ^ { n }   
 
 
\frac{a _ ij}{a _ ii }  x _ {j}  ^ {(} k- 1) +  
+
\frac{a _ {ij}}{a _ {ii} }  x _ {j}  ^ {( k- 1)} +  
 
 
\frac{b _ i}{a _ ii}
+
\frac{b _ i}{a _ {ii}}
 
   ,
 
   ,
 
$$
 
$$
Line 43: Line 43:
 
and the diagonal entries of  $  A $
 
and the diagonal entries of  $  A $
 
are assumed to be  $  \neq 0 $.  
 
are assumed to be  $  \neq 0 $.  
The use of (*) differs from the [[Simple-iteration method|simple-iteration method]] only in the fact that, at step  $  k $,  
+
The use of (*) differs from the [[simple-iteration method]] only in the fact that, at step  $  k $,  
computation of the  $  i $-
+
computation of the  $  i $-th component utilizes the previously computed  $  k $-th approximations of the first  $  i- 1 $
th component utilizes the previously computed  $  k $-
 
th approximations of the first  $  i- 1 $
 
 
components.
 
components.
  
Line 77: Line 75:
 
$$
 
$$
  
then formula (*) in matrix notation is  $  x  ^ {(} k) = - B  ^ {-} 1 Cx  ^ {(} k- 1) + B  ^ {-} 1 b $.  
+
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 $,  
+
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 $
+
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, or, equivalently, if all roots of the equation  $  \mathop{\rm det}  ( C + B \lambda ) = 0 $
 
are less than 1 in absolute value.
 
are less than 1 in absolute value.
Line 90: Line 88:
  
 
$$  
 
$$  
\| x  ^ {(} k) - x  ^ {*} \| _ {1}  \leq  q  \| x  ^ {(} k- 1) - x  ^ {*} \| ,\  \| x \| _ {1}  =  \max _ {1 \leq  i \leq  n }  | x _ {i} | .
+
\| x  ^ {( k)} - x  ^ {*} \| _ {1}  \leq  q  \| x  ^ {( k- 1)} - x  ^ {*} \| ,\  \| x \| _ {1}  =  \max _ {1 \leq  i \leq  n }  | x _ {i} | .
 
$$
 
$$
  
Line 96: Line 94:
 
is a positive-definite Hermitian matrix, then the Seidel method is convergent.
 
is a positive-definite Hermitian matrix, then the Seidel method is convergent.
  
The method falls into the category of relaxation methods (cf. [[Relaxation method|Relaxation method]]), the most widely used of which is the [[Hyperrelaxation method|hyperrelaxation method]].
+
The method falls into the category of relaxation methods (cf. [[Relaxation method|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 $(
 
Among the available modifications of the Seidel method are methods that employ preliminary transformation of the system into an equivalent system  $  x = Mx + f $(

Latest revision as of 16:24, 21 June 2020


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
How to Cite This Entry:
Seidel method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Seidel_method&oldid=49577
This article was adapted from an original article by G.D. Kim (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article