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

Метод ускорения ряда численного анализа

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

Определение

При наличии последовательности с дельта-квадратным процессом Эйткена сопоставляется новая последовательность ${\displaystyle X={(x_{n})}}$ ${\displaystyle n=0,1,2,3,\ldots ,}$

$${\displaystyle A[X]=(a_{n})={\left({\frac {x_{n}\,x_{n+2}-x_{n+1}^{2}}{x_{n}+x_{n+2}-2\,x_{n+1}}}\right)},}$$

что также можно записать как

$${\displaystyle A[X]=\left(x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}}\right),}$$

с и Оба являются одной и той же последовательностью алгебраически, но последний имеет улучшенную численную устойчивость в вычислительной реализации. ${\textstyle \Delta x_{n}=x_{n+1}-x_{n}}$ ${\textstyle \Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n}.}$

${\textstyle A[X]}$плохо определено, если последовательность содержит нулевой элемент, что происходит , если последовательность прямых разностей имеет любой повторяющийся член. С теоретической точки зрения, если это происходит только для конечного числа индексов, можно применить процесс Эйткена только к части последовательности с индексами, такими что является последним индексом, для которого последовательность повторяется. На практике первые несколько членов последовательности обычно обеспечивают желаемую точность; также при численном вычислении последовательности нужно позаботиться о том, чтобы остановить вычисление до того, как ошибки округления в знаменателе станут слишком большими, так как преобразование последовательности может отменить значимые цифры . ${\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_{n})}$ ${\textstyle \Delta [X]=(\Delta x_{n}),}$ ${\displaystyle X}$ ${\displaystyle n>n_{0}}$ ${\displaystyle n_{0}}$ ${\textstyle \Delta [X]}$ ${\textstyle \Delta ^{2}}$

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

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

Последовательность , которая сходится к предельному значению, называется линейно сходящейся или, более технически, Q-линейно, если существует некоторое число, для которого ${\textstyle X=(x_{n})}$ ${\textstyle \ell }$ ${\textstyle \mu \in (0,1)}$

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

Это означает, что асимптотически расстояние между последовательностью и ее пределом сокращается почти в той же пропорции на каждом шаге, и отношение сокращения становится все ближе и ближе к этой пропорции. Это также иногда называют «геометрической сходимостью», поскольку это характерное свойство для геометрических рядов , или «экспоненциальной сходимостью», поскольку это сходимость типа ${\displaystyle \mu ,}$ ${\displaystyle \mu ^{n}=\exp(n\ln \mu ).}$

Метод Эйткена ускорит сходимость последовательности, если с условиями, определенными выше, удовлетворяет ${\displaystyle X}$ ${\displaystyle A[X]=(a_{n}),}$ ${\textstyle \lim _{n\to \infty }{\frac {a_{n}-\ell }{x_{n}-\ell }}=0.}$

${\displaystyle A}$не является линейным оператором на последовательностях, но он линеен относительно сложения константных последовательностей: если — любая константная последовательность , константа для всех Это ясно из выражения в терминах оператора конечной разности ${\textstyle A[X-C]=A[X]-C,}$ ${\displaystyle C}$ ${\displaystyle C=(c)}$ ${\displaystyle n.}$ ${\displaystyle A[X]}$ ${\displaystyle \Delta .}$

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

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

Геометрически, график показательной функции , удовлетворяющей , и имеющей горизонтальную асимптоту при (если ). ${\displaystyle f(t)}$ ${\displaystyle f(n)=x_{n}}$ ${\displaystyle f(n+1)=x_{n+1}}$ ${\displaystyle f(n+2)=x_{n+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}$

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

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

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

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

Здесь стоит отметить, что метод Эйткена не экономит стоимость вычисления двух итераций; вычисление первых трех значений требовало первых пяти значений. Кроме того, второе значение менее точно, чем четвертое , что неудивительно, поскольку процесс Эйткена лучше всего подходит для последовательностей, которые сходятся линейно, а не квадратично, а метод Герона для вычисления квадратных корней сходится квадратично. ^{[ необходима цитата ]} ${\textstyle A[X]}$ ${\textstyle X}$ ${\textstyle A[X]}$ ${\textstyle X}$

Пример 2 : Значение можно вычислить как бесконечную сумму по формуле Лейбница для π : ${\displaystyle {\frac {\pi }{4}}}$

$${\displaystyle {\frac {\pi }{4}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}\approx 0.785398}$$

В этом примере метод Эйткена применяется к сублинейно сходящемуся ряду и значительно ускоряет сходимость. Сходимость все еще сублинейна, но гораздо быстрее исходной сходимости: первое значение, для вычисления которого потребовались первые три значения, ближе к пределу, чем восьмое значение. ${\textstyle A[X]}$ ${\textstyle X}$ ${\textstyle X}$

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

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

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

%Этот выбор зависит от решаемой задачи x0 = 1 %Начальное значение f ( x ) = ( 1 / 2 ) * ( x + 2 / x ) %Функция, которая находит следующий элемент в последовательности допуск = 10 ^ - 10 %Требуется точность в 10 цифр эпсилон = 10 ^ - 16 %Не делите на число меньше этого              maxIterations = 20 %Не позволяйте итерациям продолжаться бесконечно haveWeFoundSolution = false %Удалось ли нам найти решение в пределах требуемого допуска? пока нет      для i = 1 : maxIterations x1 = f ( x0 ) x2 = f ( x1 )             если ( x1 ~= x0 ) lambda = absoluteValue (( x2 - x1 ) / ( x1 - x0 )) %OPTIONAL: вычисляет приближение |f'(fixedPoint)|, которое обозначается как lambda end             знаменатель = ( x2 - x1 ) - ( x1 - x0 );         if ( absoluteValue ( denominator ) < epsilon ) %Чтобы избежать значительного увеличения ошибки, не делите на слишком маленькое число print ( 'WARNING: denominator is too small' ) break %Выйти из цикла end         aitkenX = x2 - ( ( x2 - x1 ) ^ 2 ) / знаменатель if ( absoluteValue ( aitkenX - x2 ) < допуск ) %Если значение находится в пределах допуска print ( "Фиксированная точка равна " , aitkenX )) %Отобразить результат экстраполяции Эйткена haveWeFoundSolution = true break %Выполнено, поэтому выходим из цикла end                          x0 = aitkenX %Обновите x0, чтобы начать снова конец   if ( haveWeFoundSolution == false ) %Если мы не смогли найти решение в пределах требуемого допуска print ( "Предупреждение: Не удалось найти решение в пределах требуемого допуска " , допуск ) print ( "Последний вычисленный экстраполятор был " , aitkenX ) end        

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

• Скорость сходимости
• Предел последовательности
• Итерация с фиксированной точкой
• Экстраполяция Ричардсона
• Трансформация последовательности
• Трансформация Шэнкса
• Метод Стеффенсена

Примечания

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

Ссылки

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