Дельта-квадратичный процесс Эйткена

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

Определение

Учитывая последовательность $X={(x_{n})}_{n\in \mathbb {N} }$ , с этой последовательностью сопоставляют новую последовательность $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} ^{*}},$ который можно, с улучшенной численной стабильностью , также записать как $(AX)_{n}=x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}},$ или эквивалентно как $(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})}}$ где $\Delta x_{n}={(x_{n+1}-x_{n})},\ \Delta x_{n+1}={(x_{n+2}-x_{n+1})},$ и $\Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n},\$ для $n=0,1,2,3,\dots$ .

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

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

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

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

Конвергенция $\ \{x_{n}\}_{n=1}^{\infty }\$ ограничивать $\ \ell \$ называется «линейным», если существует такое число $µ \in (0, 1),$ для которого $\lim _{n\to \infty }{\frac {|x_{n+1}-\ell |}{|x_{n}-\ell |}}=\mu \ .$ Это означает, что расстояние между последовательностью и ее пределом сокращается почти в одинаковой пропорции на каждом шаге, и эта скорость сокращения с каждым шагом становится все ближе к постоянной. (Это также называется «геометрической сходимостью»; эта форма сходимости характерна для степенных рядов .)

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

$A$ не является линейным оператором, но выпадает постоянный член, а именно: $\ A[x-\ell ]=Ax-\ell \ ,$ если $\ell$ является константой. Это ясно из выражения $\ Ax\$ в терминах конечно-разностного оператора $\ \Delta \ .$

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

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

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

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

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

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

Пример 1 : Значение ${\sqrt {2}}\approx 1.4142136$ можно аппроксимировать, приняв начальное значение для $a_{0}$ и повторяя следующее: $a_{n+1}={\frac {a_{n}+{\frac {2}{a_{n}}}}{2}}.$ Начиная с $a_{0}=1:$

$н$	$x$ = повторяющееся значение	$Топор$
0	1	1.4285714
1	1.5	1.4141414
2	1.4166667	1.4142136
3	1.4142157	--
4	1.4142136	--

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

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

${\frac {\pi }{4}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}\approx 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.

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

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

Этот псевдокод также вычисляет приближение Эйткена к $f^{\prime }(\alpha )$ . Экстраполяции Эйткена будут обозначаться aitkenX. Во время вычисления экстраполяции важно проверить, не становится ли знаменатель слишком маленьким, что может произойти, если у нас уже есть большая точность; без этой проверки разделение может внести большое количество ошибок. Это небольшое число будем обозначать epsilon. Поскольку двоичное представление фиксированной точки может быть бесконечным (или, по крайней мере, слишком большим, чтобы поместиться в доступную память), вычисление остановится, как только аппроксимация окажется в пределах tolerance истинной стоимости.

%These choices depend on the problem being solved
x0 = 1                      %The initial value
f(x) = (1/2)*(x + 2/x)      %The function that finds the next element in the sequence
tolerance = 10^-10          %10 digit accuracy is desired
epsilon = 10^-16            %Do not divide by a number smaller than this

maxIterations = 20          %Do not allow the iterations to continue indefinitely
haveWeFoundSolution = false %Were we able to find the solution to within the desired tolerance? not yet

for i = 1 : maxIterations 
    x1 = f(x0)
    x2 = f(x1)

    if (x1 ~= x0)
        lambda = absoluteValue((x2 - x1)/(x1 - x0))  %OPTIONAL: Computes an approximation of |f'(fixedPoint)|, which is denoted by lambda
    end

    denominator = (x2 - x1) - (x1 - x0);

    if (absoluteValue(denominator) < epsilon)        %To avoid greatly increasing error, do not divide by too small of a number
        print('WARNING: denominator is too small')
        break                                        %Leave the loop
    end

    aitkenX = x2 - ( (x2 - x1)^2 )/denominator
    
    if (absoluteValue(aitkenX - x2) < tolerance)     %If the value is within tolerance
        print("The fixed point is ", aitkenX))       %Display the result of the Aitken extrapolation
        haveWeFoundSolution = true
        break                                        %Done, so leave the loop
    end

    x0 = aitkenX                                     %Update x0 to start again                  
end

if (haveWeFoundSolution == false)   %If we were not able to find a solution to within the desired tolerance
    print("Warning: Not able to find solution to within the desired tolerance of ", tolerance)
    print("The last computed extrapolate was ", aitkenX)
end

См. также

Примечания

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

Ссылки

Уильям Х. Пресс и др. , Численные рецепты на языке C , (1987) Издательство Кембриджского университета, ISBN 0-521-43108-5 (см. раздел 5.1 )
Абрамовиц и Стегун, Справочник по математическим функциям , раздел 3.9.7
Кендалл Э. Аткинсон, Введение в численный анализ , (1989) John Wiley & Sons, Inc., ISBN 0-471-62489-6

[1] Эйткен, Александр (1926). «О численном решении Бернулли алгебраических уравнений». Труды Королевского общества Эдинбурга . 46 : 289–305. дои : 10.1017/S0370164600022070 .

[1]