Namespaces
Variants
Actions

Difference between revisions of "Simple-iteration method"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
(latex details)
 
Line 13: Line 13:
 
A method for approximately solving a system of linear algebraic equations  $  Ax = b $
 
A method for approximately solving a system of linear algebraic equations  $  Ax = b $
 
that can be transformed to the form  $  x = Bx + c $
 
that can be transformed to the form  $  x = Bx + c $
and whose solution is looked for as the limit of a sequence  $  x  ^ {k+} 1 = B x  ^ {k} + c $,  
+
and whose solution is looked for as the limit of a sequence  $  x  ^ {k+1} = B x  ^ {k} + c $,  
 
$  k = 0 , 1 \dots $
 
$  k = 0 , 1 \dots $
 
where  $  x  ^ {0} $
 
where  $  x  ^ {0} $
Line 33: Line 33:
 
is fulfilled if
 
is fulfilled if
  
1)  $  \sum _ {j=} 1 ^ {n} | b _ {ij} | \leq  \rho $,  
+
1)  $  \sum _ {j=1}  ^ {n} | b _ {ij} | \leq  \rho $,  
 
$  i = 1 \dots n $;
 
$  i = 1 \dots n $;
  
2)  $  \sum _ {i=} 1 ^ {n} | b _ {ij} | \leq  \rho $,  
+
2)  $  \sum _ {i=1}  ^ {n} | b _ {ij} | \leq  \rho $,  
 
$  j = 1 \dots n $;
 
$  j = 1 \dots n $;
  
Line 45: Line 45:
 
is the identity matrix, for  $  B $.  
 
is the identity matrix, for  $  B $.  
 
If all diagonal entries of  $  A $
 
If all diagonal entries of  $  A $
are non-zero, then, choosing  $  b = D  ^ {-} 1 ( D - A ) $
+
are non-zero, then, choosing  $  b = D  ^ {-1} ( D - A ) $
and  $  c = D  ^ {-} 1 b $,  
+
and  $  c = D  ^ {-1} b $,  
 
where  $  D $
 
where  $  D $
 
is the diagonal matrix with as diagonal entries those of  $  A $,  
 
is the diagonal matrix with as diagonal entries those of  $  A $,  
Line 73: Line 73:
  
 
$$  
 
$$  
x _ {i}  ^ {k+} 1 =  x _ {i}  ^ {k} - \tau \phi _ {i} ( x  ^ {k} ) ,\  1 \leq  
+
x _ {i}  ^ {k+1}  =  x _ {i}  ^ {k} - \tau \phi _ {i} ( x  ^ {k} ) ,\  1 \leq  
 
i \leq  n ,\  k \geq  0 .
 
i \leq  n ,\  k \geq  0 .
 
$$
 
$$

Latest revision as of 20:21, 10 January 2024


A method for approximately solving a system of linear algebraic equations $ Ax = b $ that can be transformed to the form $ x = Bx + c $ and whose solution is looked for as the limit of a sequence $ x ^ {k+1} = B x ^ {k} + c $, $ k = 0 , 1 \dots $ where $ x ^ {0} $ is an initial approximation. In order that the simple-iteration method converges for any initial approximation $ x ^ {0} $ it is necessary and sufficient that all eigenvalues of $ B $ are less than one in modulus; it is sufficient that some norm of $ B $ is less than one. If in some norm, compatible with the norm of a vector $ x $, $ B $ satisfies $ \| B \| \leq \rho < 1 $, then the simple-iteration method converges at the rate of a geometric series and the estimate

$$ \| x ^ {m} - x \| \leq \rho ^ {m} \| x ^ {0} - x \| $$

holds for its error.

In the case of a cubic, octahedral or spherical vector norm, the condition $ \| B \| \leq \rho $ is fulfilled if

1) $ \sum _ {j=1} ^ {n} | b _ {ij} | \leq \rho $, $ i = 1 \dots n $;

2) $ \sum _ {i=1} ^ {n} | b _ {ij} | \leq \rho $, $ j = 1 \dots n $;

3) $ \sum _ {i , j = 1 } ^ {n} b _ {ij} ^ {2} \leq \rho ^ {2} $.

The simplest version of the method corresponds to the case when one takes $ I - A $, where $ I $ is the identity matrix, for $ B $. If all diagonal entries of $ A $ are non-zero, then, choosing $ b = D ^ {-1} ( D - A ) $ and $ c = D ^ {-1} b $, where $ D $ is the diagonal matrix with as diagonal entries those of $ A $, one obtains the Jacobi method or the method of simultaneous displacement.

A particular case of the simple-iteration method is the method with $ B = I - \tau A $ and $ c = \tau b $, where $ \tau $ is an iteration parameter, chosen from the condition that the norm of $ I - \tau A $ is minimal with respect to $ \tau $. If $ \gamma _ {1} $ and $ \gamma _ {2} $ are the minimal and maximal eigenvalues of a symmetric positive-definite matrix $ A $ and $ \tau = 2 / ( \gamma _ {1} + \gamma _ {2} ) $, then one has for the matrix $ B $ in the spherical norm the estimate $ \| B \| \leq \rho $, with $ \rho = ( \gamma _ {2} - \gamma _ {1} ) / ( \gamma _ {2} + \gamma _ {1} ) < 1 $.

For a system of non-linear algebraic equations

$$ \phi _ {i} ( x) = 0 ,\ 1 \leq i \leq n ,\ x = ( x _ {1} \dots x _ {n} ) , $$

the simple-iteration method has the form

$$ x _ {i} ^ {k+1} = x _ {i} ^ {k} - \tau \phi _ {i} ( x ^ {k} ) ,\ 1 \leq i \leq n ,\ k \geq 0 . $$

The problem of choosing the iteration parameter $ \tau $ is solved in dependence on the differentiability properties of the $ \phi _ {i} $. Often it is subjected to the requirement that the method converges locally in a neighbourhood of a solution.

References

[1] D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra" , Freeman (1963) (Translated from Russian)
[2] I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian)
[3] J.M. Ortega, W.C. Rheinboldt, "Iterative solution of non-linear equations in several variables" , Acad. Press (1970)
[4] A.A. Samarskii, E.S. Nikolaev, "Numerical methods for grid equations" , 1–2 , Birkhäuser (1989) (Translated from Russian)
How to Cite This Entry:
Simple-iteration method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Simple-iteration_method&oldid=54970
This article was adapted from an original article by E.S. Nikolaev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article