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

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

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

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

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

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

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

предстоит определить. Во-первых, частичная сумма $A_{n}$ определяется как:

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

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

$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})}}$

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

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

Пример

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

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

$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. Частичная сумма $A_{6}$ имеет только одну цифру точности, в то время как шестизначная точность требует суммирования около 400 000 членов.

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

$n$	$A_{n}$	$S(A_{n})$	$S^{2}(A_{n})$	$S^{3}(A_{n})$
0	4.00000000	—	—	—
1	2.66666667	3.16666667	—	—
2	3.46666667	3.13333333	3.14210526	—
3	2.89523810	3.14523810	3.14145022	3.14159936
4	3.33968254	3.13968254	3.14164332	3.14159086
5	2.97604618	3.14271284	3.14157129	3.14159323
6	3.28373848	3.14088134	3.14160284	3.14159244
7	3.01707182	3.14207182	3.14158732	3.14159274
8	3.25236593	3.14125482	3.14159566	3.14159261
9	3.04183962	3.14183962	3.14159086	3.14159267
10	3.23231581	3.14140672	3.14159377	3.14159264
11	3.05840277	3.14173610	3.14159192	3.14159266
12	3.21840277	3.14147969	3.14159314	3.14159265

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

Мотивация

Преобразование Шанкса мотивировано наблюдением, что — для большего $n$ — частичная сумма $A_{n}$ нередко ведет себя примерно так

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

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

$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}.$

Эти три уравнения содержат три неизвестных: $A,$ $\alpha$ и $q.$ Решение для $A$ дает

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

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

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

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

$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}}},$

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

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

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

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

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

См. также

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

Ссылки

• Шанкс, Д. (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
• Бендер, СМ ; Орзаг, С.А. (1999), Передовые математические методы для ученых и инженеров , Springer, ISBN  0-387-98931-5
• Венигер, Э.Дж. (1989). «Преобразования нелинейных последовательностей для ускорения сходимости и суммирования расходящихся рядов». Отчеты по компьютерной физике . 10 (5–6): 189–371. arXiv : math.NA/0306302 . Бибкод : 1989CoPhR..10..189W . дои : 10.1016/0167-7977(89)90011-7 .
• Брезински, К.; Редиво-Залья, М. ; Саад, Ю. (2018), «Преобразования последовательности Шэнкса и ускорение Андерсона», SIAM Review , 60 (3): 646–669, doi : 10.1137/17M1120725 , hdl : 11577/3270110
• Сенхаджи, Миннесота (2001), «О числах обусловленности преобразования Шанкса», J. Comput. Прил. Математика. , 135 (1): 41–61, Bibcode : 2001JCoAM.135...41S , doi : 10.1016/S0377-0427(00)00561-6
• Винн, П. (1956), «Об устройстве для вычисления преобразования em ₍ Sn ₎ », Mathematical Tables and Other Aids to Computing , 10 (54): 91–96, doi : 10.2307/2002183 , JSTOR   2002183
• Винн, П. (1962), «Методы ускорения для повторяющихся векторных и матричных задач», Math. Комп. , 16 (79): 301–322, doi : 10.1090/S0025-5718-1962-0145647-X