Математика / Численный поиск корней
Метод простой итерации для поиска корня уравнения
Метод простой итерации заменяет уравнение f(x)=0 равносильным уравнением x=g(x) и строит последовательность приближений. Условие сжатия отображения даёт проверяемую гарантию сходимости к единственной неподвижной точке.
Формула
Коричневая прямая y=x и синяя кривая g(x)=x−(x²−2)/4 пересекаются при √2. Шкалы x и y указаны отдельно.
Обозначения
- $x_k$
- приближение корня на итерации k, единица x
- $g$
- отображение, неподвижные точки которого решают уравнение, единица x
- $q$
- граница модуля производной g на выбранном интервале, безразмерный
Условия применения
Для гарантии достаточно замкнутого интервала I, такого что g(I)⊆I, и числа q<1, для которого |g′(x)|≤q на всём I. Тогда в I есть единственная неподвижная точка и любая начальная точка внутри интервала сходится к ней. Равносильность исходного уравнения и x=g(x) проверяют отдельно.
Ограничения
Условие сжатия достаточно, но не необходимо: недоказанное q<1 не означает автоматическую расходимость. Если |g′| близко к единице, прогресс медленный; если больше единицы, ошибки могут расти. Разные перестановки дают разные алгоритмы. Малое изменение соседних чисел не гарантирует малую ошибку без оценки сходимости и проверки резидуала f(x).
Подробное объяснение
Неподвижная точка x* удовлетворяет g(x*)=x*. Поэтому искать корень можно, если выбранная запись x=g(x) равносильна исходному уравнению. Начав с x₀, алгоритм подставляет последнее значение в g и получает следующую оценку.
Если g сжимает расстояния, погрешность следующего шага уменьшается. Оценка |g′|≤q<1 на всём интервале обеспечивает это по теореме о среднем. Условие g(I)⊆I столь же важно: последовательность остаётся там, где доказана оценка. Это строгая гарантия, а не наблюдение по первым нескольким числам.
Для x²−2=0 можно взять g(x)=x−(x²−2)/4. На I=[1;1,5] производная 1−x/2 лежит между 0,25 и 0,5, значит q=0,5; образ интервала остаётся внутри него. Другая запись g(x)=2/x тоже имеет тот же положительный корень, но её итерации надо анализировать отдельно.
Остановку задают по допуску на шаг |xₖ₊₁−xₖ| и по лимиту итераций. Исходный остаток |f(xₖ)| показывает, действительно ли найдено решение. При известном q апостериорная оценка имеет вид |xₖ−x*|≤q|xₖ−xₖ₋₁|/(1−q).
Векторный вариант заменяет скалярное отображение на G и использует норму. Условие сжатия должно выполняться для всей области и одной выбранной нормы. Производная может не требоваться в вычислениях, но часто нужна для доказательства сходимости.
Как пользоваться формулой
- Преобразуйте f(x)=0 к x=g(x), сохраните равносильность и отметьте запрещённые значения.
- Выберите интервал I и начальное x₀; проверьте, что g переводит выбранный интервал в себя.
- Докажите на всём интервале оценку |g′(x)|≤q<1 или используйте другую обоснованную оценку сжатия.
- Последовательно вычисляйте xₖ₊₁=g(xₖ), записывая шаги и контролируя выход за I.
- Остановитесь по допуску, проверьте резидуал исходного уравнения и оцените ошибку последнего приближения.
Историческая справка
Последовательные приближения использовали при вычислении корней до современной теории итераций. В 1922 году Стефан Банах доказал принцип сжимающих отображений: сжимающее отображение полного пространства имеет единственную неподвижную точку, а последовательное применение отображения сходится к ней. Теорема формализовала общую гарантию, но не придумала каждую частную схему поиска корней.
В XX веке численный анализ оформил запись xₖ₊₁=g(xₖ) как стандартный способ описывать итерационные алгоритмы. Учебники сравнивают его с бисекцией и методом Ньютона по скорости, гарантии и стоимости вычисления. Практика добавила критерии остановки, проверку резидуала и защиту от стагнации.
Историческая линия формулы
У метода нет единственного автора: последовательные подстановки применялись в разных вычислительных задачах. Банах в 1922 году сформулировал общий принцип сжимающих отображений, который доказывает единственность и сходимость. Эта атрибуция относится к теореме, а не ко всему семейству итерационных алгоритмов.
Пример
Решим x²−2=0 с g(x)=x−(x²−2)/4, интервалом I=[1;1,5] и x₀=1. На всём интервале g′(x)=1−x/2, поэтому 0,25≤g′≤0,5; отображение не покидает I и сжимает расстояния с коэффициентом q=0,5. Итерации: x₁=1,25; x₂=1,359375; x₃=1,3973999; x₄≈1,4092183. Они приближаются к √2≈1,414214. После второго шага остаток f(x₂)=1,359375²−2≈−0,15210, а при продолжении его модуль уменьшается. Это учебный расчёт в безразмерной переменной; если x — длина, каждая итерация и искомый корень выражаются в той же единице. Сжатие гарантирует предел, но число показанных знаков ответа зависит от допуска и округления.
Частая ошибка
Не считайте любую запись x=g(x) сходящейся: эквивалентность определяет корни, сжатие — поведение итерации. Не проверяйте |g′| только в предполагаемом корне, если нужна гарантия на интервале. Не делите на выражение, которое может быть нулём. Не прекращайте расчёт только по неизменившимся отображаемым цифрам: проверьте остаток исходной функции и влияние округления.
Практика
Задачи с решением
Четыре шага
Условие. Для уравнения x²−2=0, отображения g(x)=x−(x²−2)/4 и начального x₀=1 вычислите первые два обновления.
Решение. x₁=1−(1−2)/4=1,25. Затем x₂=1,25−(1,5625−2)/4=1,359375.
Ответ. x₁=1,25; x₂=1,359375.
Оценка сжатия
Условие. Для g(x)=x−(x²−2)/4 на I=[1;1,5] найдите производную и укажите подходящую верхнюю границу коэффициента сжатия.
Решение. g′(x)=1−x/2; на этом интервале значения лежат между 0,25 и 0,5.
Ответ. Можно взять q=0,5<1; оценка сжатия выполнена.
Дополнительные источники
- https://persson.berkeley.edu/math128a/lecture_notes/math128a_lecture_notes_chapter_2.html
- https://web.stanford.edu/class/math114/decks/rootfinding/fixed_point3.html
- https://mathshistory.st-andrews.ac.uk/Biographies/Banach/
Связанные формулы
Математика
Метод бисекции: корень и гарантированная точность
Метод бисекции ищет корень непрерывной функции делением отрезка пополам. Разные знаки на концах дают гарантию существования корня, а длина отрезка — оценку ошибки.
Математика
Метод Ньютона: приближение корня по касательной
Метод Ньютона заменяет функцию касательной в текущем приближении и берёт нуль этой прямой как следующий шаг. Вблизи простого корня сходимость может быть квадратичной.
Математика
Метод секущих: поиск корня без вычисления производной
Метод секущих строит прямую по двум последним точкам графика и использует её пересечение с осью для нового приближения корня. Производная заменяется разностным наклоном.