Русская Википедия:Метод итерации
Метод итерации или метод простой итерации — численный метод решения системы линейных алгебраических уравнений. Суть метода заключается в нахождении по приближённому значению величины следующего приближения, являющегося более точным.
Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (в результате итерационного процесса). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня.
Описание метода
Пусть СЛАУ представлена в виде:
- <math>x = Bx+g </math>
Выбирается начальное приближение <math>x^{(0)}</math>. На каждом шаге считается новое приближение <math>x^{(k+1)}</math> из старого <math>x^{(k)}</math> по формуле
- <math>x^{(k+1)} = Bx^{(k)}+g</math>
или в координатной форме
- <math>
\begin{array}{rcl} x_1^{(k+1)} = & b_{11}x_1^{(k)} + \ldots + b_{1n}x_n^{(k)} + g_1\\ \ldots \\ x_n^{(k+1)} = & b_{n1}x_1^{(k)} + \ldots + b_{nn}x_{n}^{(k)} + g_n \end{array}</math>. Приближения продолжают считаться до того, пока не достигнут нужной степени точности. Достигло ли приближение нужной степени точности или нет проверяется при помощи условия остановки, которые могут отличаться в разных реализациях.
Приведение СЛАУ к нужному виду
Пусть дана СЛАУ
- <math>Ax = b </math>
Для того, чтобы воспользоваться методом простой итерации, необходимо привести её к виду <math>x = Bx+g </math>. Представим матрицу <math>A</math> в виде <math>A=M-N</math>, где <math>M</math> — обратима. Тогда система приводится к виду <math>x = Bx+g </math> следующим образом:
- <math>(M-N)x=b</math>
- <math>Mx=Nx+b</math>
- <math>x=M^{-1}Nx+M^{-1}b</math>
Матрицы <math>M</math> и <math>N</math> могут быть выбраны различными способами; в зависимости от конкретного способа получаются различные разновидности метода. Обозначим далее за <math>L</math> — строго нижнюю треугольную часть <math>A</math>, за <math>D</math> — диагональную часть <math>A</math>, за <math>U</math> — строго верхнюю треугольную часть <math>A</math>. Получающиеся таким способом разновидности эквиваленты следующим методам:
- <math>M=\frac{1}{\omega}E</math> — метод Ричардсона;
- <math>M=D</math> — метод Якоби;
- <math>M=\frac{1}{\omega}D</math> — взвешенный метод Якоби;
- <math>M=D+L</math> — метод Гаусса — Зейделя;
- <math>M=\frac{1}{\omega}D+L</math> — метод релаксации;
- <math>M(\omega)={\omega\over{2-\omega}} \left ( {1\over\omega} D + L \right ) D^{-1} \left ( {1\over\omega} D + L\right)^\mathsf{T}</math> — метод симметричной релаксации.
Здесь эквивалентность понимается в смысле равенства последовательностей приближений <math>x^{(k)}</math> при равенстве начальных приближений <math>x^{(0)}</math>.
Условия сходимости процесса
Необходимое и достаточное условие сходимости: <math>\rho(\alpha) < 1</math>, где — <math>\rho(\alpha)</math> спектральный радиус <math>\alpha</math>Шаблон:Sfn.
Достаточное условие сходимости: <math>\Vert\alpha\Vert < 1</math>Шаблон:Sfn.
В частности при выборе нормы, подчинённой векторной <math> \| x \|_{\infty} = \max\limits_{1 \le i \le n} |x_i| </math> условие сходимости приобретает вид <math>\max_{j=1}^n\vert\alpha_{ij}\vert<1</math> (где <math>i=1,2,\dots,n</math>).
При выборе нормы <math> \| x \|_1 = \sum_{i = 1}^n |x_i| </math> условие приобретает вид <math>\sum_{i=1\atop i\neq j}^n\vert\alpha_{ij}\vert<1</math> (где <math>j=1,2,\dots,n</math>), что называют условием диагонального преобладания исходной матрицы <math>A</math>.
Оценка погрешности
Пусть <math>x</math> — вектор точного решения. Тогда можно получить следующие оценки погрешности приближённого решения <math>x^{(k)}</math> на <math>k</math>-м шаге алгоритмаШаблон:Sfn:
- априорная:
- <math>\Vert x-x^{(k)}\Vert \le ||\alpha||^k ||x^{(0)}|| + \frac{\Vert\alpha\Vert^k }{1-\Vert\alpha\Vert} \Vert\beta\Vert. </math>
- апостериорная:
- <math>\Vert x-x^{(k)}\Vert \le \frac{\Vert\alpha\Vert}{1-\Vert\alpha\Vert}\Vert x^{(k)}-x^{(k-1)}\Vert. </math>
Примечания
Литература
