Метод Стеффенсенса - Википедия - Steffensens method

В числовой анализ, Метод Стеффенсена это метод поиска корней названный в честь Йохан Фредерик Стеффенсен что похоже на Метод Ньютона. Метод Стеффенсена также достигает квадратичная сходимость, но без использования производные в качестве Метод Ньютона делает.

Простое описание

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

Учитывая адекватное начальное значение , последовательность значений может быть сгенерирован по формуле ниже. Когда это работает, каждое значение в последовательности намного ближе к решению. чем предыдущее значение. Значение с текущего шага генерирует значение для следующего шага по этой формуле:[1]

за п = 0, 1, 2, 3, ... , где функция наклона является составной частью исходной функции дается следующей формулой:

или эквивалентно

куда .

Функция - среднее значение наклона функции между последней точкой последовательности и вспомогательная точка , с шагом . Его еще называют разделенная разница первого порядка из между этими двумя точками.

Это только с целью найти для этой вспомогательной точки значение функции должно быть адекватным исправлением, чтобы приблизиться к собственному решению, и по этой причине выполнять требование, что . Для всех остальных частей расчета метод Стеффенсена требует только функции быть непрерывным и иметь близкое решение.[1] Несколько скромных модификаций ступени при расчете уклона существуют для размещения функций это не совсем соответствует требованию.

Достоинства и недостатки

Основное преимущество метода Стеффенсена в том, что он имеет квадратичная сходимость[1] подобно Метод Ньютона - то есть оба метода находят корни уравнения так же «быстро». В этом случае быстро означает, что для обоих методов количество правильных цифр в ответе удваивается с каждым шагом. Но формула метода Ньютона требует вычисления производной функции а также функция , а метод Стеффенсена требует только сам. Это важно, когда дериватив недоступен легко или эффективно.

Цена быстрой сходимости - двойная оценка функции: оба и должны быть рассчитаны, что может занять много времени, если это сложная функция. Для сравнения секущий метод требуется только одна оценка функции на шаг. Метод секанса увеличивает количество правильных цифр «всего» примерно в 1,6 раза за шаг, но можно сделать вдвое больше шагов метода секанса за заданное время. Поскольку метод секущей может выполнять в два раза больше шагов за то же время, что и метод Стеффенсена,[а] когда оба алгоритма успешны, метод секущей сходится быстрее, чем метод Стеффенсена на практике: метод секущей достигает коэффициента примерно (1,6)2 ≈ 2,6 раза больше цифр для каждых двух шагов (две оценки функции) по сравнению с коэффициентом Стеффенсена, равным 2 для каждого шага (две оценки функции).

Подобно большинству других итерационные алгоритмы поиска корней, решающим недостатком метода Стеффенсена является выбор начального значения . Если значение не "достаточно близко" к реальному решению , метод может потерпеть неудачу и последовательность значений может либо метаться между двумя крайностями, либо расходиться до бесконечности.

Вывод с использованием процесса дельта-квадрата Эйткена

Версия метода Стеффенсена, реализованная в MATLAB код, показанный ниже, можно найти с помощью Дельта-квадрат процесс Эйткена для ускорения сходимости последовательности. Чтобы сравнить следующие формулы с формулами в разделе выше, обратите внимание, что . Этот метод предполагает начало с линейно сходящейся последовательности и увеличивает скорость сходимости этой последовательности. Если признаки согласен и «достаточно близко» к желаемому пределу последовательности , можно предположить следующее:

тогда

так

и поэтому

 .


Решение для желаемого предела последовательности дает:



что приводит к более быстро сходящейся последовательности:

Реализация в Matlab

Вот источник реализации метода Стеффенсена в MATLAB.

функцияСтеффенсен(f, p0, tol)% Эта функция принимает в качестве входных данных: итерационную функцию с фиксированной точкой, f, % и первоначальное предположение относительно фиксированной точки p0 и допуск tol.% Предполагается, что итерационная функция с фиксированной точкой вводится как% встроенная функция. % Эта функция вычислит и вернет фиксированную точку p, %, что делает выражение f (x) = p истинным с точностью до желаемого % допуск, тол.формат compact% Укорачивает вывод.формат long% Печатает больше десятичных знаков.за i = 1: 1000% приготовьтесь к большому, но конечному количеству итераций.               % Это так, что если метод не сойдется, мы не будем               % застрял в бесконечном цикле.    p1=ж(p0);  % вычисляет следующие два предположения для фиксированной точки.    p2=ж(p1);    п=p0-(p1-p0)^2/(p2-2*p1+p0) % использовать метод дельта-квадрата Эйткена для                                % найти лучшее приближение к p0.    если abs (p-p0)         перемена %, если да, остановите итерации, мы получили ответ.    конецp0 = p;              % обновить p0 для следующей итерации.конецесли пресс(п-p0)>тол       % Если мы не соблюдаем допуск, мы выводим                       % сообщение об ошибке.    «не удалось сойтись за 1000 итераций».конец

Реализация на Python

Вот источник реализации метода Стеффенсена в Python.

def грамм(ж, Икс: плавать):    "" "Функция разделенных разностей первого порядка.    Аргументы:        f (вызываемый): ввод функции в g        x (float): точка, в которой нужно вычислить g    """    возвращаться лямбда Икс: ж(Икс + ж(Икс)) / ж(Икс) - 1def Steff(ж, Икс: плавать):    "" "Алгоритм Стеффенсона для поиска корней.    Этот рекурсивный генератор сначала возвращает значение x_n + 1, а затем, когда генератор выполняет итерацию,    он дает x_n + 2 со следующего уровня рекурсии.    Аргументы:        f (вызываемый): функция, корень которой мы ищем        x (float): начальное значение при первом вызове, каждый уровень n, который функция рекурсирует x, равен x_n    """    если грамм(ж, Икс)(Икс) != 0:        урожай Икс - ж(Икс) / грамм(ж, Икс)(Икс)  # Сначала дайте x_n + 1        уступить от Steff(ж, Икс - ж(Икс) / грамм(ж, Икс)(Икс))  # Затем даем новый итератор

Обобщение

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

Этот метод нахождения неподвижных точек действительной функции был обобщен для функций на Банахово пространство . Обобщенный метод предполагает, что семья из ограниченный линейные операторы связана с и можно найти, чтобы удовлетворить условию[2]

В простой форме, приведенной в предыдущем разделе, функция просто принимает и производит действительные числа. Там функция это разделенная разница. Здесь в обобщенном виде оператор является аналогом разделенной разности для использования в Банахово пространство. Оператор эквивалентно матрица чьи записи являются функциями вектор аргументы и .

Тогда метод Стеффенсена очень похож на метод Ньютона, за исключением того, что он использует разделенную разницу вместо производной . Таким образом, он определяется как

за , и где - тождественный оператор.

Если оператор удовлетворяет

для некоторой постоянной , то метод квадратично сходится к фиксированной точке если начальное приближение «достаточно близко» к желаемому решению , что удовлетворяет  .

Примечания

  1. ^ Потому что требует предварительного расчета , две оценки должны выполняться последовательно - алгоритм как таковой невозможно ускорить выполнение параллельных вычислений функций. Это еще один недостаток метода Стеффенсена.

Рекомендации

  1. ^ а б c Дальквист, Гермунд; Бьорк, Оке (1974). Численные методы. Перевод Андерсона, Нед. Энглвуд Клиффс, Нью-Джерси: Prentice Hall. стр.230–231.
  2. ^ Johnson, L.W .; Шольц, Д. (Июнь 1968 г.). «О методе Стеффенсена». Журнал SIAM по численному анализу. 5 (2): 296–302. Дои:10.1137/0705026. JSTOR  2949443.