Трансформация хвостовика

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

Формулировка [ править ]

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

${\ Displaystyle А = \ сумма _ {м = 0} ^ {\ infty} а_ {м} \,}$

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

${\ Displaystyle А_ {п} = \ сумма _ {м = 0} ^ {п} а_ {м} \,}$

и образует новую последовательность . При условии, что ряд сходится, он также приблизится к пределу, поскольку преобразование Шанкса последовательности является новой последовательностью, определенной в ^{[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. На рисунке справа показывает абсолютную погрешность для частичных сумм и результатов преобразования Shanks, ясно показывая улучшенная точность и скорость сходимости.${\displaystyle A_{n}}$${\displaystyle S(A_{n})}$${\displaystyle S^{2}(A_{n})}$${\displaystyle S^{3}(A_{n})}$${\displaystyle n}$

${\displaystyle n}$	${\displaystyle A_{n}}$	${\displaystyle S(A_{n})}$	${\displaystyle S^{2}(A_{n})}$	${\displaystyle 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

Преобразование Хвостовики уже имеет точность два цифр, в то время как исходные частичные суммы только устанавливают такую же точность при Примечательно, что имеет точность шесть цифр, полученную от повторных преобразований хвостовика применяется к первым семь терминам говорят , как и раньше, только получает точность 6 цифр после о суммировании 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},\,}$

с тем, чтобы последовательность сходится транзиторно в результате серии для Таким образом , для и соответствующих частичных сумм являются:${\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]

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Хвостовики, D. (1955), "Non-линейное преобразование расходящихся и медленно сходящиеся последовательности", Журнал математики и физики , 34 : 1-42, DOI : 10.1002 / sapm19553411 CS1 maint: discouraged parameter (link)
• Шмидт Р. (1941), "О численном решении линейных одновременных уравнений итерационным методом", Philosophical Magazine , 32 : 369–383
• Ван Дайк, доктор медицины (1975), Методы возмущений в механике жидкости (аннотированная ред.), Parabolic Press, ISBN 0-915760-01-0 CS1 maint: discouraged parameter (link)
• Бендер, СМ ; Орзаг, С.А. (1999), Передовые математические методы для ученых и инженеров , Springer, ISBN 0-387-98931-5 CS1 maint: discouraged parameter (link)
• Венигер, EJ (1989). «Нелинейные преобразования последовательностей для ускорения сходимости и суммирования расходящихся рядов». Доклады по компьютерной физике . 10 (5–6): 189–371. arXiv : math.NA/0306302 . Bibcode : 1989CoPhR..10..189W . DOI : 10.1016 / 0167-7977 (89) 90011-7 .