Математика / Численный поиск корней

Метод Стеффенсена: ускорение простой итерации

Метод Стеффенсена ускоряет поиск неподвижной точки без вычисления производной. Он выполняет два шага простой итерации и применяет к полученной тройке преобразование Эйткена.

Опубликовано: 7 ноября 2026 г.Обновлено: 7 ноября 2026 г.

Формула

y=g(x_n),\quad z=g(y),\quad x_{n+1}=x_n-\frac{(y-x_n)^2}{z-2y+x_n}

Схема Один цикл ускорения

Пример g(x)=(x+6)/3: обычные шаги 0→2→8/3; преобразование тройки даёт x₁=3 с нулевой невязкой.

Обозначения

$g$: функция исходной неподвижной итерации, сохраняет единицы x
$xₙ$: текущее ускоренное приближение, единицы неизвестной
$y,z$: два последовательных значения g(xₙ) и g(g(xₙ)), единицы неизвестной
$xₙ₊₁$: следующая ускоренная точка, единицы неизвестной

Условия применения

Функция g должна быть определена в текущей точке и в промежуточной точке g(x). Знаменатель z−2y+x должен быть ненулевым. Для стандартного локального утверждения о квадратичной сходимости требуется достаточная гладкость около неподвижной точки α и g′(α)≠1.

Ограничения

Глобальная сходимость из произвольной стартовой точки не гарантируется. Ускоренный шаг может выйти из области определения g. Близкий к нулю знаменатель усиливает ошибки; если y=x с нужной точностью, сначала фиксируют сходимость и прекращают вычисления, а не применяют вырожденную формулу.

Подробное объяснение

Исходное уравнение записывают как x=g(x). Из текущего ускоренного приближения x выполняют два обычных перехода: y=g(x), затем z=g(y). Эти три точки образуют локальную последовательность, к которой можно применить Δ²-преобразование Эйткена.

Полученную ускоренную оценку используют как новое начало. На следующем цикле вычисляют именно g(xₙ₊₁) и g(g(xₙ₊₁)), а не продолжают прежний ряд y,z. Такой перезапуск отличает метод Стеффенсена от простого преобразования всех троек одной исходной последовательности.

Вблизи неподвижной точки гладкую функцию можно линеаризовать: ошибка следующего обычного шага примерно равна g′(α) текущей ошибке. Преобразование Эйткена устраняет этот ведущий геометрический член. При невырожденных условиях оставшаяся ошибка имеет второй порядок по исходной.

Результат зависит от выбранной функции g. Одно уравнение допускает разные представления в виде неподвижной точки; у них различаются области определения, масштабы промежуточных значений и устойчивость ускорения. Отсутствие производной в алгоритме не отменяет необходимости анализировать эти свойства.

Остановку проверяют по невязке |g(x)−x| и величине ускоренного шага. Только маленький шаг может оказаться следствием округления. Если заранее известно, что g сжимает расстояния с коэффициентом q<1, оценка |x−α|≤|g(x)−x|/(1−q) даёт дополнительный контроль ошибки.

Как пользоваться формулой

Запишите уравнение в виде x=g(x), выберите старт в области определения и задайте точность невязки, а не только изменения точки.
Вычислите y=g(x), проверьте остановку по |y−x|, затем найдите z=g(y), сохранив полную рабочую точность значений.
Проверьте знаменатель z−2y+x на вырождение и вычислите ускоренную точку x−(y−x)²/(z−2y+x), если деление устойчиво.
Начните следующий цикл с ускоренной точки; контролируйте область определения, невязку и величину шага до достижения точности.

Историческая справка

Метод Стеффенсена относится к семейству способов ускорения неподвижных итераций. Его связь с преобразованием Эйткена отражена в университетских курсах численного анализа Оттавы 2011 года и Дарема 2018 года: два обычных шага образуют тройку для экстраполяции, затем процесс перезапускается. Поэтому речь идёт о способе организации вычислений, а не о новой алгебраической форме исходного уравнения.

Исторический контекст направления — поиск более быстрой сходимости без обязательного вычисления производных. Общая теория ускорения последовательностей и методы решения нелинейных уравнений развивались совместно; современное изложение различает постобработку последовательности и построение нового итерационного метода. В данной статье использована именно перезапускаемая версия для x=g(x).

Историческая линия формулы

Эпоним Стеффенсена относится к ускоренному итерационному процессу, использующему Δ²-преобразование. Современная формула объединяет два вычисления g и экстраполяцию по трём точкам; атрибуция не означает универсальной сходимости и не переносит условия Ньютона на произвольную g.

Пример

Решим x=(x+6)/3, начав с x₀=0. Точное решение пока не используем в ускорении. Функция g(x)=(x+6)/3 определена на всей числовой прямой и имеет производную 1/3. Два обычных шага: y=g(0)=2, z=g(2)=8/3. Знаменатель z−2y+x₀=8/3−4=−4/3. Ускоренная точка x₁=0−(2−0)²/(−4/3)=3. Проверка невязки: g(3)−3=9/3−3=0. После этого дальнейшее деление выполнять не нужно. Независимо решаем линейное уравнение: 3x=x+6, откуда x=3. Обычная итерация из нуля дала бы 2;8/3;26/9 и лишь постепенно приближалась к трём. Одношаговая точность ускорения объясняется тем, что у этой аффинной функции ошибка строго геометрическая. Все числа в примере безразмерны.

Частая ошибка

Не продолжайте старую цепочку обычных итераций после ускоренного шага: требуется перезапуск от новой точки. Не делите на нуль в уже найденном корне. Не объявляйте квадратичную сходимость глобальной гарантией для любой g. Не ограничивайтесь проверкой малого шага: вычислите также невязку исходного уравнения.

Практика

Задачи с решением

Другая стартовая точка

Условие. Для g(x)=(x+6)/3 начните с x=6. Найдите один ускоренный шаг.

Решение. y=4, z=10/3. Знаменатель 10/3−8+6=4/3. Новая точка 6−(4−6)²/(4/3)=3.

Ответ. 3.

Линейная невязка

Условие. Для g(x)=(x+6)/3 в точке x=2,99 найдите невязку и оценку ошибки при q=1/3.

Решение. g(x)=8,99/3. Модуль g(x)−x=1/150≈0,00666667. Деление на 1−q=2/3 даёт оценку 0,01, совпадающую с расстоянием до корня 3.

Ответ. Невязка 1/150; ошибка не больше 0,01.

Дополнительные источники

https://www.maths.dur.ac.uk/users/anthony.yeates/NOTES/na17.pdf
https://www.site.uottawa.ca/~remi/ode
https://dlmf.nist.gov/3.9

Связанные формулы

Математика

Процесс Эйткена Δ²: ускорение сходящейся последовательности

$\widehat s_n=s_n-\frac{(s_{n+1}-s_n)^2}{s_{n+2}-2s_{n+1}+s_n}$

Процесс Эйткена Δ² строит оценку предела по трём последовательным членам. Он точно устраняет одну геометрическую составляющую ошибки и может ускорить линейную сходимость.

Математика

Метод простой итерации для поиска корня уравнения

$x_{k+1}=g(x_k),\quad x=g(x)$

Метод простой итерации заменяет уравнение f(x)=0 равносильным уравнением x=g(x) и строит последовательность приближений. Условие сжатия отображения даёт проверяемую гарантию сходимости к единственной неподвижной точке.

Математика

Метод Ньютона: приближение корня по касательной

$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$

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