Метод простой итерации — это один из численных методов для решения линейных уравнений, который может быть использован для решения уравнения вида Ax = b, где A — матрица коэффициентов, x — вектор неизвестных, а b — вектор правых частей.

Алгоритм метода простой итерации

Представление уравнения: Привести уравнение Ax = b к форме x = T(x) + c, где T — оператор, описывающий итерационный процесс, а c — вектор, связанный с правой частью.

Инициализация: Задать начальное приближение x₀.

Итерации:

Для k = 0, 1, 2, ...:
Вычислить xₖ₊₁ = T(xₖ) + c.

Условие остановки: Проверять, удовлетворяет ли ||xₖ₊₁ - xₖ|| < ε для заданной точности ε или достигнут максимальный номер итерации.

Доказательство сходимости

Сходимость метода простой итерации основана на свойствах оператора T:

Собственное значение: Рассмотрим, что матрица A может быть преобразована в оператор T с помощью подходящей нормализации. Например, если A можно представить в виде T = I - B, где I — единичная матрица, а B — некоторая матрица с малой нормой.

Линейный оператор: Метод сходимости основан на том, что оператор T является сжимающим преобразованием в нормированном пространстве. Это значит, что для любых x₁ и x₂ выполняется неравенство ||T(x₁) - T(x₂)|| ≤ k ||x₁ - x₂||, где 0 ≤ k < 1 — коэффициент сжатия.

Использование критерия сжатия: Если k < 1, то последовательность итераций будет сходиться к фиксированной точке, которая является решением уравнения Ax = b.

Оценка скорости сходимости

Скорость сходимости определяется коэффициентом сжатия k:

Если ||xₖ₊₁ - x|| ≤ k ||xₖ - x||, где x — точное решение, тогда после n итераций мы имеем:
[
||x_n - x|| ≤ k^n ||x_0 - x*||.
]
Таким образом, если k меньше 1, то сходимость будет экспоненциальной, и расстояние до решения уменьшается пропорционально k^n, что означает, что количество необходимых итераций для достижения заданной точности зависит от логарифма отношения начальной ошибки к желаемой.

Таким образом, метод простой итерации сходится, если оператор T является сжимающим, и скорость сходимости зависит от значения коэффициента сжатия k. Если k близок к 0, сходимость будет быстрой, а если k близко к 1, сходимость будет медленной.