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

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

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

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

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

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

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

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

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

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

${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 4left(1-{frac {1}{3}}+{frac {1}{5}}-{frac {1}{7}}+{frac {1}{9}}-cdots ight),}$ который имеет точную сумму ${displaystyle pi .}$

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

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

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

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

${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

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

Мотивация

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

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

с участием ${displaystyle |q|<1}$ так что последовательность сходится временно к результату серии ${displaystyle A}$ для ${displaystyle n o 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 { ext{and}}qquad A_{n+1}=A+alpha q^{n+1}.}$

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

${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 {egin{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}}{egin{vmatrix}1&cdots &1&1Delta 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}.}$

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

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

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

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

Заметки

1. Венигер (2003).
2. Бендер и Орзаг (1999), стр. 368–375.
3. Ван Дайк (1975), стр. 202–205.
4. Бендер и Орзаг (1999), стр. 389–392.

использованная литература

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