Метод последовательных приближений¶

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

¶История

Идея последовательных приближений восходит к работам математиков XVII—XVIII веков. В частности, Исаак Ньютон в 1669 году предложил метод (ныне известный как метод Ньютона или метод касательных) для нахождения корней уравнений, который является частным случаем метода последовательных приближений. В XIX веке Огюстен Луи Коши и Леонард Эйлер развили теорию сходимости итерационных процессов. В 1870-х годах шведский математик Эрик Ивар Фредгольм применил метод для решения интегральных уравнений. В XX веке, с развитием вычислительной техники, метод последовательных приближений стал одним из основных инструментов численного анализа, особенно в задачах, где аналитическое решение невозможно или трудоёмко.

¶Математическая формулировка

Пусть требуется решить уравнение вида \( x = \varphi(x) \), где \( \varphi \) — некоторая функция. Метод последовательных приближений заключается в построении последовательности: \[ x_{n+1} = \varphi(x_n), \quad n = 0, 1, 2, \dots \] где \( x_0 \) — начальное приближение. Если последовательность сходится к некоторому пределу \( x^ \), то при непрерывности функции \( \varphi \) этот предел является решением исходного уравнения: \( x^ = \varphi(x^*) \).

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

Для сходимости метода необходимы определённые условия. В простейшем случае, если функция \( \varphi \) определена на отрезке \( [a, b] \), принимает значения на этом же отрезке и удовлетворяет условию Липшица с константой \( q < 1 \): \[ |\varphi(x) - \varphi(y)| \leq q |x - y| \quad \forall x, y \in [a, b], \] то последовательность сходится к единственному решению \( x^* \) на этом отрезке, причём скорость сходимости линейна (геометрическая прогрессия). В случае дифференцируемости функции условие сходимости часто формулируется как \( |\varphi'(x)| < 1 \) в окрестности корня.

¶Классификация методов

Методы последовательных приближений можно классифицировать по различным признакам:

¶По типу решаемой задачи

• Решение нелинейных уравнений: метод простой итерации, метод Ньютона (касательных), метод секущих.
• Решение систем линейных уравнений: метод Якоби, метод Гаусса—Зейделя, метод релаксации.
• Решение дифференциальных уравнений: метод Пикара (последовательных приближений) для обыкновенных дифференциальных уравнений, метод коллокаций.
• Решение интегральных уравнений: метод последовательных приближений Фредгольма.
• Оптимизация: метод градиентного спуска, метод Ньютона для оптимизации.

¶По способу построения итерации

• Стационарные методы: итерационная формула не меняется от шага к шагу (например, метод простой итерации).
• Нестационарные методы: параметры итерации изменяются (например, метод Ньютона, где на каждом шаге вычисляется производная).

¶По скорости сходимости

• Линейная сходимость: ошибка уменьшается примерно в геометрической прогрессии (метод простой итерации при \( q < 1 \)).
• Квадратичная сходимость: ошибка на каждом шаге пропорциональна квадрату предыдущей ошибки (метод Ньютона).
• Сверхлинейная сходимость: скорость выше линейной, но ниже квадратичной (метод секущих).

¶Применение

¶Решение нелинейных уравнений

Метод последовательных приближений является основным инструментом для численного решения уравнений вида \( f(x) = 0 \). Например, для уравнения \( x = \cos(x) \) можно выбрать начальное приближение \( x_0 = 0 \) и итерационно вычислять \( x_{n+1} = \cos(x_n) \). Последовательность сходится к корню \( x \approx 0.739085 \). Метод Ньютона, использующий формулу \( x_{n+1} = x_n - f(x_n)/f'(x_n) \), сходится быстрее, но требует вычисления производной.

¶Решение систем линейных уравнений

В вычислительной математике для решения больших разреженных систем линейных уравнений \( A x = b \) часто применяются итерационные методы. Например, метод Якоби: \[ x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j \neq i} a_{ij} x_j^{(k)} \right), \quad i = 1, \dots, n. \] Эти методы эффективны для матриц с диагональным преобладанием или положительно определённых матриц.

¶Решение дифференциальных уравнений

Метод Пикара используется для доказательства существования и единственности решения задачи Коши для обыкновенных дифференциальных уравнений. Он также применяется для численного построения приближённого решения в виде ряда. Например, для уравнения \( y' = f(x, y) \) с начальным условием \( y(x_0) = y_0 \) последовательность приближений строится как: \[ y_{n+1}(x) = y_0 + \int_{x_0}^x f(t, y_n(t)) \, dt. \]

¶Оптимизация

В задачах безусловной оптимизации метод градиентного спуска является частным случаем метода последовательных приближений: \[ x_{n+1} = x_n - \alpha \nabla f(x_n), \] где \( \alpha \) — шаг спуска. Метод Ньютона в оптимизации использует вторые производные (матрицу Гессе) для более быстрой сходимости.

¶Примеры

¶Пример 1: Решение уравнения методом простой итерации

Рассмотрим уравнение \( x = \ln(x + 2) \). Приведём его к виду \( x = \varphi(x) \) с \( \varphi(x) = \ln(x + 2) \). Выберем начальное приближение \( x_0 = 1 \). Вычисления:

• \( x_1 = \ln(1 + 2) = \ln 3 \approx 1.0986 \)
• \( x_2 = \ln(1.0986 + 2) = \ln 3.0986 \approx 1.1309 \)
• \( x_3 = \ln(1.1309 + 2) = \ln 3.1309 \approx 1.1410 \)
• \( x_4 = \ln(1.1410 + 2) = \ln 3.1410 \approx 1.1447 \)

Последовательность сходится к корню \( x \approx 1.1462 \). Скорость сходимости линейна, так как \( \varphi'(x) = 1/(x+2) \approx 0.32 < 1 \).

¶Пример 2: Метод Ньютона для уравнения \( x^3 - 2x - 5 = 0 \)

Функция \( f(x) = x^3 - 2x - 5 \), производная \( f'(x) = 3x^2 - 2 \). Начальное приближение \( x_0 = 2 \):

• \( x_1 = 2 - (8 - 4 - 5)/(12 - 2) = 2 - (-1)/10 = 2.1 \)
• \( x_2 = 2.1 - (9.261 - 4.2 - 5)/(13.23 - 2) = 2.1 - (0.061)/11.23 \approx 2.0946 \)
• \( x_3 = 2.0946 - (9.191 - 4.189 - 5)/(13.16 - 2) = 2.0946 - (0.002)/11.16 \approx 2.0944 \)

Корень найден с высокой точностью за три итерации (квадратичная сходимость).

¶Критика и ограничения

Метод последовательных приближений не всегда применим. Основные ограничения:

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

¶Интересные факты

• Метод Ньютона был независимо открыт Джозефом Рафсоном в 1690 году, поэтому в англоязычной литературе он часто называется методом Ньютона—Рафсона.
• В некоторых случаях метод последовательных приближений может сходиться к решению, даже если условия сходимости формально не выполнены, но это требует дополнительного анализа.
• Итерационные методы решения систем линейных уравнений (например, метод сопряжённых градиентов) являются основой современных вычислительных пакетов (MATLAB, SciPy, LAPACK).
• В теории динамических систем метод последовательных приближений используется для построения аттракторов и изучения бифуркаций.

¶Источники

• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином, 2008.
• Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
• Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. — М.: Мир, 1975.
• Хейгеман Л., Янг Д. Прикладные итерационные методы. — М.: Мир, 1986.