Открыть сервисСервис
Главная → Блог → Метод последовательных приближений

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

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

История

Идея последовательных приближений восходит к работам математиков 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 \) в окрестности корня.

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

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

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

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

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

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

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

Применение

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

Метод последовательных приближений является основным инструментом для численного решения уравнений вида \( 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.

Похожие материалы

Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru