Метод простой итерации

Метод простой итерации (также известный как метод последовательных приближений или метод Якоби для решения систем линейных уравнений) — это численный метод решения уравнений и систем уравнений, основанный на построении сходящейся последовательности приближений к точному решению. Относится к классу итерационных методов, в которых каждое следующее приближение вычисляется на основе предыдущего с помощью некоторой рекуррентной формулы. Применяется для решения нелинейных уравнений, систем линейных алгебраических уравнений (СЛАУ) и дифференциальных уравнений.

История

Метод простой итерации имеет длинную историю, восходящую к работам математиков XVII—XVIII веков. Идея последовательных приближений встречается у Исаака Ньютона (метод Ньютона, хотя он является частным случаем с более быстрой сходимостью) и Жозефа Луи Лагранжа. В современном виде метод был формализован в XIX веке в работах Огюстена Луи Коши, который исследовал условия сходимости итерационных процессов. Для систем линейных уравнений метод получил название метода Якоби в честь немецкого математика Карла Густава Якоба Якоби, который опубликовал его в 1845 году. В XX веке, с развитием вычислительной техники, метод простой итерации стал одним из базовых алгоритмов для численного решения задач на ЭВМ.

Постановка задачи

Пусть требуется решить уравнение вида:

\[ x = \varphi(x) \]

где \(\varphi(x)\) — некоторая функция, заданная на отрезке \([a, b]\). Такая форма записи называется приведённой к виду, удобному для итераций. Исходное уравнение \(f(x) = 0\) всегда можно преобразовать к такому виду, например, добавив \(x\) к обеим частям: \(x = x + f(x)\), или умножив на константу.

Для систем линейных уравнений \(Ax = b\) метод простой итерации (метод Якоби) записывается в матричной форме:

\[ x^{(k+1)} = D^{-1}(b - (L+U)x^{(k)}) \]

где \(D\) — диагональная матрица, \(L\) — нижняя треугольная матрица, \(U\) — верхняя треугольная матрица (разложение \(A = D + L + U\)).

Алгоритм

1. Выбрать начальное приближение \(x^{(0)}\).
2. Для \(k = 0, 1, 2, \dots\) вычислять:

\[ x^{(k+1)} = \varphi(x^{(k)}) \]

1. Прекратить итерации, когда выполнится условие остановки:

\[ |x^{(k+1)} - x^{(k)}| < \varepsilon \] где \(\varepsilon\) — заданная точность.

Для систем линейных уравнений алгоритм аналогичен: каждое уравнение системы решается относительно соответствующей переменной, и вычисления проводятся покомпонентно.

Условия сходимости

Для нелинейных уравнений

Сходимость метода простой итерации гарантируется, если функция \(\varphi(x)\) является сжимающим отображением на отрезке \([a, b]\). Формально, если существует константа \(q \in [0, 1)\) такая, что для любых \(x_1, x_2 \in [a, b]\) выполняется:

\[ |\varphi(x_1) - \varphi(x_2)| \leq q |x_1 - x_2| \]

то итерационный процесс сходится к единственному решению \(x^*\) на этом отрезке. На практике часто используют достаточное условие: если \(|\varphi'(x)| \leq q < 1\) на \([a, b]\), то метод сходится.

Для систем линейных уравнений

Для метода Якоби сходимость гарантируется, если матрица \(A\) имеет диагональное преобладание, то есть для каждой строки:

\[ |a_{ii}| > \sum_{j \neq i} |a_{ij}| \]

В более общем случае сходимость определяется спектральным радиусом итерационной матрицы \(B = D^{-1}(L+U)\): метод сходится, если \(\rho(B) < 1\).

Скорость сходимости

Метод простой итерации имеет линейную скорость сходимости (первого порядка). Это означает, что ошибка на каждом шаге уменьшается примерно в \(q\) раз, где \(q\) — константа сжатия. Чем меньше \(q\), тем быстрее сходимость. Для систем линейных уравнений скорость сходимости определяется спектральным радиусом матрицы \(B\).

Модификации

Метод Зейделя

Метод Зейделя (или метод Гаусса — Зейделя) является модификацией метода простой итерации для систем линейных уравнений, в которой при вычислении \(i\)-й компоненты вектора \(x^{(k+1)}\) используются уже вычисленные компоненты того же шага:

\[ x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)} \right) \]

Это часто ускоряет сходимость по сравнению с методом Якоби.

Метод релаксации

Метод релаксации (SOR — Successive Over-Relaxation) вводит параметр релаксации \(\omega\) для ускорения сходимости:

\[ x_i^{(k+1)} = (1 - \omega) x_i^{(k)} + \frac{\omega}{a_{ii}} \left( b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)} \right) \]

При \(\omega = 1\) получается метод Зейделя, при \(\omega > 1\) — метод верхней релаксации, при \(\omega < 1\) — нижней.

Применение

Метод простой итерации широко применяется в вычислительной математике, физике, инженерных расчётах и экономике. Основные области применения:

• Решение нелинейных уравнений: нахождение корней уравнений, которые не решаются аналитически (например, трансцендентные уравнения).
• Решение систем линейных уравнений: особенно для разреженных матриц большого размера, где прямые методы (например, метод Гаусса) неэффективны из-за вычислительной сложности.
• Численное решение дифференциальных уравнений: в методах конечных разностей и конечных элементов для решения краевых задач.
• Оптимизация: в методах градиентного спуска и итеративных алгоритмах поиска минимума функции.
• Обработка сигналов и изображений: в задачах восстановления и фильтрации.

Пример

Рассмотрим уравнение \(x = \cos(x)\) на отрезке \([0, 1]\). Выберем начальное приближение \(x^{(0)} = 0.5\). Выполним несколько итераций:

• \(x^{(1)} = \cos(0.5) \approx 0.8776\)
• \(x^{(2)} = \cos(0.8776) \approx 0.6390\)
• \(x^{(3)} = \cos(0.6390) \approx 0.8027\)
• \(x^{(4)} = \cos(0.8027) \approx 0.6948\)
• \(x^{(5)} = \cos(0.6948) \approx 0.7688\)

Процесс сходится к решению \(x^* \approx 0.7391\) (точное решение уравнения \(x = \cos x\)).

Достоинства и недостатки

Достоинства

• Простота реализации и понимания.
• Низкие требования к памяти (не требуется хранить всю матрицу для систем с разреженными матрицами).
• Возможность распараллеливания (особенно для метода Якоби).
• Устойчивость к ошибкам округления.

Недостатки

• Медленная сходимость (линейная) по сравнению с методами второго порядка (например, метод Ньютона).
• Сходимость не гарантирована для произвольных систем (требуется выполнение условий сжатия или диагонального преобладания).
• Чувствительность к выбору начального приближения.

Сравнение с другими методами

Метод простой итерации уступает по скорости сходимости методу Ньютона (квадратичная сходимость), но выигрывает в простоте и устойчивости. Для систем линейных уравнений метод Якоби часто медленнее, чем метод Зейделя или метод сопряжённых градиентов, но проще в реализации. Для задач с большими разреженными матрицами метод простой итерации может быть предпочтительнее прямых методов из-за меньшей вычислительной сложности на одну итерацию.

Источники

1. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином. Лаборатория знаний, 2006.
2. Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
3. Демидович Б. П., Марон И. А. Основы вычислительной математики. — М.: Наука, 1970.
4. Крылов В. И., Бобков В. В., Монастырный П. И. Вычислительные методы. — М.: Наука, 1976.