Дельта-квадратный процесс Айткенса - Aitkens delta-squared process

В числовой анализ, Дельта-квадрат процесс Эйткена или же Экстраполяция Эйткена это серийное ускорение метод, используемый для ускорения скорость конвергенции последовательности. Он назван в честь Александр Айткен, который ввел этот метод в 1926 г.^[1] Его ранняя форма была известна Секи Коува (конец 17 века) и был найден для выпрямления круга, то есть вычисления π. Это наиболее полезно для ускорения сходимости линейно сходящейся последовательности.

Определение

Учитывая последовательность ${ displaystyle X = {(x_ {n})} _ {n in mathbb {N}}}$ , с этой последовательностью ассоциируется новая последовательность

{ Displaystyle AX = { left ({ frac {x_ {n} , x_ {n + 2} -x_ {n + 1} ^ {2}} {x_ {n} + x_ {n + 2}) - 2 , x_ {n + 1}}} right)} _ {n in mathbb {Z} ^ {*}},}

который может, с улучшенным числовая стабильность, также можно записать как

{ displaystyle (AX) _ {n} = x_ {n} - { frac {( Delta x_ {n}) ^ {2}} { Delta ^ {2} x_ {n}}},}

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

{ displaystyle (AX) _ {n} = x_ {n + 2} - { frac {( Delta x_ {n + 1}) ^ {2}} { Delta ^ {2} x_ {n}}} = x_ {n + 2} - { frac {(x_ {n + 2} -x_ {n + 1}) ^ {2}} {(x_ {n + 2} -x_ {n + 1}) - ( x_ {n + 1} -x_ {n})}}}

куда

{ displaystyle Delta x_ {n} = {(x_ {n + 1} -x_ {n})}, Delta x_ {n + 1} = {(x_ {n + 2} -x_ {n + 1) })},}

и

{ Displaystyle Delta ^ {2} x_ {n} = x_ {n} -2x_ {n + 1} + x_ {n + 2} = Delta x_ {n + 1} - Delta x_ {n}, }

за ${ Displaystyle п = 0,1,2,3, точки ,}$

Очевидно, ${ displaystyle AX}$ некорректно определено, если ${ displaystyle Delta ^ {2} x}$ содержит нулевой элемент или, что то же самое, если последовательность первые отличия имеет повторяющийся термин.

С теоретической точки зрения, если это имеет место только для конечного числа индексов, можно легко согласиться рассмотреть последовательность ${ displaystyle AX}$ ограничено индексами ${ displaystyle n> n_ {0}}$ с достаточно большим ${ displaystyle n_ {0}}$ . С практической точки зрения, как правило, учитываются только несколько первых членов последовательности, которые обычно обеспечивают необходимую точность. Более того, при численном вычислении последовательности нужно позаботиться о том, чтобы остановить вычисление, когда ошибки округления в знаменателе становятся слишком большими, и операция Δ² может отменить слишком много значащие цифры. (Для численного расчета лучше использовать ${ displaystyle Delta x_ {n + 1} - Delta x_ {n} = (x_ {n + 2} -x_ {n + 1}) - (x_ {n + 1} -x_ {n}) }$ скорее, чем ${ displaystyle x_ {n} -2x_ {n + 1} + x_ {n + 2} }$ .)

Характеристики

Дельта-квадратный процесс Эйткена - это метод ускорение схождения, и частный случай нелинейного преобразование последовательности.

${ displaystyle x}$ буду сходятся линейно к ${ displaystyle ell}$ если существует число μ ∈ (0, 1) такое, что

{ displaystyle lim _ {n to infty} { frac {| x_ {n + 1} - ell |} {| x_ {n} - ell |}} = mu.}

Метод Эйткена ускорит последовательность ${ displaystyle x_ {n}}$ если ${ displaystyle lim _ {n to infty} { frac {(Ax) _ {n} - ell} {x_ {n} - ell}} = 0.}$

${ displaystyle A}$ не является линейным оператором, но выпадает постоянный член, а именно: ${ Displaystyle А [х- ell] = Ax- ell}$ , если ${ displaystyle ell}$ является константой. Это видно из выражения ${ displaystyle Ax}$ с точки зрения конечная разница оператор ${ displaystyle Delta}$ .

Хотя новый процесс, как правило, не сходится квадратично, можно показать, что для фиксированная точка процесс, то есть для повторяющаяся функция последовательность ${ Displaystyle х_ {п + 1} = е (х_ {п})}$ для какой-то функции ${ displaystyle f}$ , сходящаяся к неподвижной точке, сходимость квадратичная. В этом случае метод известен как Метод Стеффенсена.

Опытным путем А-операция устраняет «самую важную ошибку». В этом можно убедиться, рассмотрев последовательность вида ${ displaystyle x_ {n} = ell + a ^ {n} + b ^ {n}}$ , куда ${ Displaystyle 0 <б <а <1}$ :Последовательность ${ displaystyle Ax}$ затем дойдет до предела, например ${ displaystyle b ^ {n}}$ уходит в ноль.

Геометрически график экспоненциальной функции ${ displaystyle f (t)}$ это удовлетворяет ${ displaystyle f (n) = x_ {n}}$ , ${ Displaystyle е (п + 1) = х_ {п + 1}}$ и ${ Displaystyle е (п + 2) = х_ {п + 2}}$ имеет горизонтальную асимптоту при ${ displaystyle { frac {x_ {n} x_ {n + 2} -x_ {n + 1} ^ {2}} {x_ {n} -2x_ {n + 1} + x_ {n + 2}}} }$ (если ${ displaystyle x_ {n} -2x_ {n + 1} + x_ {n + 2} neq 0}$ ).

Можно также показать, что если ${ displaystyle x}$ идет к своему пределу ${ displaystyle ell}$ со скоростью строго больше 1, ${ displaystyle Ax}$ не имеет лучшей скорости сходимости. (На практике редко бывает, например, квадратичная сходимость, которая означала бы более 30 или 100 правильных десятичных знаков после 5 или 7 итераций (начиная с 1 правильной цифры); обычно в этом случае ускорение не требуется.)

На практике, ${ displaystyle Ax}$ сходится к пределу намного быстрее, чем ${ displaystyle x}$ делает, как показано в приведенном ниже примере расчетов. Обычно гораздо дешевле рассчитать ${ displaystyle Ax}$ (включая только вычисление разностей, одно умножение и одно деление), чем для вычисления большего количества членов последовательности ${ displaystyle x}$ . Однако необходимо соблюдать осторожность, чтобы избежать ошибок из-за недостаточной точности при вычислении различия в числителе и знаменателе выражения.

Примеры расчетов

Пример 1: Значение ${ displaystyle { sqrt {2}} приблизительно 1,4142136}$ можно аппроксимировать, приняв начальное значение для ${ displaystyle a_ {0}}$ и повторяя следующее:

{ displaystyle a_ {n + 1} = { frac {a_ {n} + { frac {2} {a_ {n}}}} {2}}.}

Начиная с ${ displaystyle a_ {0} = 1:}$

п	Икс = повторное значение	Топор
0	1	1.4285714
1	1.5	1.4141414
2	1.4166667	1.4142136
3	1.4142157	--
4	1.4142136	--

Здесь стоит отметить, что метод Эйткена не сохраняет два шага итерации; вычисление первых трех Топор значения требовали первых пяти Икс значения. Кроме того, второе значение Ax явно уступает 4-му значению x, в основном из-за того, что процесс Эйткена предполагает линейную, а не квадратичную сходимость.^{[нужна цитата ]}.

Пример 2: Значение ${ displaystyle { frac { pi} {4}}}$ можно рассчитать как бесконечную сумму:

{ displaystyle { frac { pi} {4}} = sum _ {n = 0} ^ { infty} { frac {(-1) ^ {n}} {2n + 1}} приблизительно 0,785398 }

п	срок	Икс = частичная сумма	Топор
0	1	1	0.79166667
1	−0.33333333	0.66666667	0.78333333
2	0.2	0.86666667	0.78630952
3	−0.14285714	0.72380952	0.78492063
4	0.11111111	0.83492063	0.78567821
5	−9.0909091×10⁻²	0.74401154	0.78522034
6	7.6923077×10⁻²	0.82093462	0.78551795
7	-6.6666667×10⁻²	0.75426795	--
8	5.8823529×10⁻²	0.81309148	--

В этом примере метод Эйткена применяется к сублинейно сходящемуся ряду, что значительно ускоряет сходимость. Это все еще сублинейно, но намного быстрее, чем исходная сходимость: первое значение Ax, для вычисления которого потребовались первые три значения x, ближе к пределу, чем восьмое значение x.

Пример псевдокода для экстраполяции Эйткена

Ниже приведен пример использования экстраполяции Эйткена, чтобы помочь найти предел последовательности. ${ Displaystyle х_ {п + 1} = е (х_ {п})}$ когда дано ${ displaystyle x_ {0}}$ , которую мы считаем неподвижной точкой ${ Displaystyle альфа = е ( альфа)}$ . Например, мы могли бы иметь ${ displaystyle x_ {n + 1} = { frac {1} {2}} (x_ {n} + { frac {2} {x_ {n}}})}$ с ${ displaystyle x_ {0} = 1}$ который имеет неподвижную точку ${ displaystyle { sqrt {2}}}$ так что ${ displaystyle f (x) = { frac {1} {2}} (x + { frac {2} {x}})}$ (видеть Методы вычисления квадратных корней ).

Этот псевдокод также вычисляет приближение Эйткена к ${ displaystyle f '( alpha)}$ . Экстраполяции Эйткена будут обозначены aitkenX. Мы должны проверить, не становится ли во время вычисления экстраполяции слишком маленьким знаменатель, что может произойти, если у нас уже есть большая точность, поскольку в противном случае может быть внесена большая ошибка. Обозначим это маленькое число через эпсилон.

% Эти варианты зависят от решаемой проблемыx0 = 1                      % Начальное значениеж(Икс) = (1/2)*(Икс + 2/Икс)      % Функция, которая находит следующий элемент в последовательноститолерантность = 10^-10          % 10 желательна точностьэпсилон = 10^-16            % Не хочу делить на меньшее числомаксИтерации = 20          % Не позволяйте итерациям продолжаться бесконечноhaveWeFoundSolution = ложный % Удалось ли найти решение в пределах желаемого допуска? еще нет.за я = 1 : максИтерации     x1 = ж(x0)    x2 = ж(x1)    если (x1 ~= x0)        лямбда = абсолютная величина((x2 - x1)/(x1 - x0))  % ДОПОЛНИТЕЛЬНО: вычисляет приближение | f '(fixedPoint) |, которое обозначается лямбда    конец    знаменатель = (x2 - x1) - (x1 - x0);    если (абсолютная величина(знаменатель) < эпсилон)          % Не хочу делить на слишком маленькое число        Распечатать('ВНИМАНИЕ: знаменатель слишком мал')        перемена;                                        % Выйти из цикла    конец    aitkenX = x2 - ( (x2 - x1)^2 )/знаменатель        если (абсолютная величина(aitkenX - x2) < толерантность)       % Если результат в пределах допуска        Распечатать("Фиксированная точка", aitkenX))        % Отобразить результат экстраполяции Эйткена        haveWeFoundSolution = истинный        перемена;                                        % Готово, выходите из цикла    конец    x0 = aitkenX                                      % Обновите x0, чтобы начать заново     конецесли (haveWeFoundSolution == ложный)   % Если бы мы не смогли найти решение в пределах желаемого допуска    Распечатать(«Предупреждение: невозможно найти решение в пределах желаемого допуска», толерантность)    Распечатать(«Последняя вычисленная экстраполяция была», aitkenX)конец

Смотрите также

Примечания

^ Александр Айткен, "О численном решении Бернулли алгебраических уравнений", Труды Королевского общества Эдинбурга (1926) 46 С. 289–305.