Трансформация Шэнкса

В численном анализе преобразование Шэнкса — это метод ускорения нелинейного ряда для увеличения скорости сходимости последовательности . Этот метод назван в честь Дэниела Шэнкса , который заново открыл это преобразование последовательности в 1955 году. Впервые он был выведен и опубликован Р. Шмидтом в 1941 году. ^[1]

Можно вычислить только несколько членов разложения возмущений , обычно не более двух или трех, и почти никогда не более семи. Результирующий ряд часто медленно сходится или даже расходится. Тем не менее, эти несколько членов содержат замечательное количество информации, которую исследователь должен сделать все возможное, чтобы извлечь.
Эта точка зрения была убедительно изложена в восхитительной статье Шэнкса (1955), который демонстрирует ряд удивительных примеров, включая несколько из механики жидкости .

Милтон Д. Ван Дайк (1975) Методы возмущений в механике жидкости , стр. 202.

Формулировка

Для последовательности серия ${\displaystyle \left\{a_{m}\right\}_{m\in \mathbb {N} }}$

${\displaystyle A=\sum _{m=0}^{\infty }a_{m}\,}$

должна быть определена. Сначала частичная сумма определяется как: ${\displaystyle A_{n}}$

${\displaystyle A_{n}=\sum _{m=0}^{n}a_{m}\,}$

и образует новую последовательность . При условии, что ряд сходится, также будет стремиться к пределу , поскольку Преобразование Шэнкса последовательности — это новая последовательность, определяемая ^{[2] [3]} ${\displaystyle \left\{A_{n}\right\}_{n\in \mathbb {N} }}$ ${\displaystyle A_{n}}$ ${\displaystyle A}$ ${\displaystyle n\to \infty .}$ ${\displaystyle S(A_{n})}$ ${\displaystyle A_{n}}$

${\displaystyle S(A_{n})={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}=A_{n+1}-{\frac {(A_{n+1}-A_{n})^{2}}{(A_{n+1}-A_{n})-(A_{n}-A_{n-1})}}}$

где эта последовательность часто сходится быстрее, чем последовательность Дальнейшее ускорение может быть получено путем повторного использования преобразования Шенкса, вычислений и т. д. ${\displaystyle S(A_{n})}$ ${\displaystyle A_{n}.}$ ${\displaystyle S^{2}(A_{n})=S(S(A_{n})),}$ ${\displaystyle S^{3}(A_{n})=S(S(S(A_{n}))),}$

Обратите внимание, что нелинейное преобразование, используемое в преобразовании Шенкса, по сути, то же самое, что и в дельта-квадратичном процессе Эйткена , так что, как и в методе Эйткена, самое правое выражение в определении (т. е. ) более численно устойчиво, чем выражение слева от него (т. е. ). Как метод Эйткена, так и преобразование Шенкса работают с последовательностью, но последовательность, с которой работает преобразование Шенкса, обычно рассматривается как последовательность частичных сумм, хотя любую последовательность можно рассматривать как последовательность частичных сумм. ${\displaystyle S(A_{n})}$ ${\displaystyle S(A_{n})=A_{n+1}-{\frac {(A_{n+1}-A_{n})^{2}}{(A_{n+1}-A_{n})-(A_{n}-A_{n-1})}}}$ ${\displaystyle S(A_{n})={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}}$

Пример

Абсолютная ошибка как функция в частичных суммах и после применения преобразования Шенкса один или несколько раз: и Используемый ряд имеет точную сумму ${\displaystyle n}$ ${\displaystyle A_{n}}$ ${\displaystyle S(A_{n}),}$ ${\displaystyle S^{2}(A_{n})}$ ${\displaystyle S^{3}(A_{n}).}$ ${\displaystyle \scriptstyle 4\left(1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+{\frac {1}{9}}-\cdots \right),}$ ${\displaystyle \pi .}$

В качестве примера рассмотрим медленно сходящийся ряд ^[3]

${\displaystyle 4\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{2k+1}}=4\left(1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+\cdots \right)}$

что имеет точную сумму π  ≈ 3,14159265. Частичная сумма имеет точность только в одну цифру, в то время как шестизначная точность требует суммирования около 400 000 членов. ${\displaystyle A_{6}}$

В таблице ниже приведены частичные суммы , преобразование Шенкса для них, а также повторные преобразования Шенкса и для значений до 12. На рисунке справа показана абсолютная погрешность для результатов частичных сумм и преобразования Шенкса, наглядно демонстрирующая улучшение точности и скорости сходимости. ${\displaystyle A_{n}}$ ${\displaystyle S(A_{n})}$ ${\displaystyle S^{2}(A_{n})}$ ${\displaystyle S^{3}(A_{n})}$ ${\displaystyle n}$

Преобразование Шенкса уже имеет двузначную точность, в то время как исходные частичные суммы устанавливают ту же точность только при Примечательно, что имеет шестизначную точность, полученную в результате повторных преобразований Шенкса, примененных к первым семи членам. Как упоминалось ранее, достигает шестизначной точности только после суммирования около 400 000 членов. ${\displaystyle S(A_{1})}$ ${\displaystyle A_{24}.}$ ${\displaystyle S^{3}(A_{3})}$ ${\displaystyle A_{0},\ldots ,A_{6}.}$ ${\displaystyle A_{n}}$

Мотивация

Преобразование Шэнкса мотивировано наблюдением, что — при больших значениях — частичная сумма довольно часто ведет себя приблизительно так ^[2] ${\displaystyle n}$ ${\displaystyle A_{n}}$

${\displaystyle A_{n}=A+\alpha q^{n},\,}$

с таким образом, что последовательность сходится временно к результату ряда для So для и соответствующие частичные суммы равны: ${\displaystyle |q|<1}$ ${\displaystyle A}$ ${\displaystyle n\to \infty .}$ ${\displaystyle n-1,}$ ${\displaystyle n}$ ${\displaystyle n+1}$

${\displaystyle A_{n-1}=A+\alpha q^{n-1}\quad ,\qquad A_{n}=A+\alpha q^{n}\qquad {\text{and}}\qquad A_{n+1}=A+\alpha q^{n+1}.}$

Эти три уравнения содержат три неизвестных: и Решение дает ^[2] ${\displaystyle A,}$ ${\displaystyle \alpha }$ ${\displaystyle q.}$ ${\displaystyle A}$

${\displaystyle A={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}.}$

В (исключительном) случае, когда знаменатель равен нулю: тогда для всех ${\displaystyle A_{n}=A}$ ${\displaystyle n.}$

Обобщенное преобразование Шэнкса

Обобщенное преобразование Шэнкса k -го порядка задается как отношение определителей : [ ^4]

${\displaystyle S_{k}(A_{n})={\frac {\begin{vmatrix}A_{n-k}&\cdots &A_{n-1}&A_{n}\\\Delta A_{n-k}&\cdots &\Delta A_{n-1}&\Delta A_{n}\\\Delta A_{n-k+1}&\cdots &\Delta A_{n}&\Delta A_{n+1}\\\vdots &&\vdots &\vdots \\\Delta A_{n-1}&\cdots &\Delta A_{n+k-2}&\Delta A_{n+k-1}\\\end{vmatrix}}{\begin{vmatrix}1&\cdots &1&1\\\Delta A_{n-k}&\cdots &\Delta A_{n-1}&\Delta A_{n}\\\Delta A_{n-k+1}&\cdots &\Delta A_{n}&\Delta A_{n+1}\\\vdots &&\vdots &\vdots \\\Delta A_{n-1}&\cdots &\Delta A_{n+k-2}&\Delta A_{n+k-1}\\\end{vmatrix}}},}$

с Это решение модели для поведения сходимости частичных сумм с различными переходными процессами: ${\displaystyle \Delta A_{p}=A_{p+1}-A_{p}.}$ ${\displaystyle A_{n}}$ ${\displaystyle k}$

${\displaystyle A_{n}=A+\sum _{p=1}^{k}\alpha _{p}q_{p}^{n}.}$

Эта модель поведения сходимости содержит неизвестные. Оценивая приведенное выше уравнение в элементах и ​​решая для приведенного выше выражения для преобразования Шенкса k -го порядка, получаем. Обобщенное преобразование Шенкса первого порядка равно обычному преобразованию Шенкса: ${\displaystyle 2k+1}$ ${\displaystyle A_{n-k},A_{n-k+1},\ldots ,A_{n+k}}$ ${\displaystyle A,}$ ${\displaystyle S_{1}(A_{n})=S(A_{n}).}$

Обобщенное преобразование Шенкса тесно связано с аппроксимациями Паде и таблицами Паде . ^[4]

Примечание: для вычисления определителей требуется выполнить множество арифметических операций, однако Питер Уинн открыл рекурсивную процедуру оценки, называемую эпсилон-алгоритмом, которая позволяет избежать вычисления определителей. ^{[5] [6]}

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

• Дельта-квадратный процесс Эйткена
• ускорение Андерсона
• Скорость сходимости
• Экстраполяция Ричардсона
• Трансформация последовательности

Примечания

1. Венигер (2003).
2. Bender & Orszag (1999), стр. 368–375.
3. Van Dyke (1975), стр. 202–205.
4. Bender & Orszag (1999), стр. 389–392.
5. Уинн (1956)
6. Уинн (1962)

Ссылки

• Шэнкс, Д. (1955), «Нелинейное преобразование расходящихся и медленно сходящихся последовательностей», Журнал математики и физики , 34 (1–4): 1–42, doi :10.1002/sapm19553411
• Шмидт, Р. Дж. (1941), «О численном решении линейных одновременных уравнений итерационным методом», Philosophical Magazine , 32 (214): 369–383, doi :10.1080/14786444108520797
• Ван Дайк, доктор медицины (1975), Методы возмущений в механике жидкости (аннотированное издание), Parabolic Press, ISBN 0-915760-01-0
• Бендер, CM ; Орсзаг, SA (1999), Передовые математические методы для ученых и инженеров , Springer, ISBN 0-387-98931-5
• Weniger, EJ (1989). "Нелинейные преобразования последовательностей для ускорения сходимости и суммирования расходящихся рядов". Computer Physics Reports . 10 (5–6): 189–371. arXiv : math.NA/0306302 . Bibcode : 1989CoPhR..10..189W. doi : 10.1016/0167-7977(89)90011-7.
• Брезинский, К.; Редиво-Залья, М .; Саад, Й. (2018), «Преобразования последовательностей Шэнкса и ускорение Андерсона», SIAM Review , 60 (3): 646–669, doi : 10.1137/17M1120725, hdl : 11577/3270110
• Сенхаджи, МН (2001), «О числах условий преобразования Шенкса», J. Comput. Appl. Math. , 135 (1): 41–61, Bibcode : 2001JCoAM.135...41S, doi : 10.1016/S0377-0427(00)00561-6
• Уайнн, П. (1956), «Об устройстве для вычисления преобразования e _m (S _n )», Математические таблицы и другие вспомогательные средства для вычислений , 10 (54): 91–96, doi :10.2307/2002183, JSTOR  2002183
• Уайнн, П. (1962), «Методы ускорения для итерационных векторных и матричных задач», Math. Comp. , 16 (79): 301–322, doi : 10.1090/S0025-5718-1962-0145647-X