Перетворення Шенкса

Перетворення Шенкса — це чисельний метод пришвидшення швидкості збіжності ряду або послідовності. Цей метод названий на честь Деніела Шенкса^[en], який перевідкрив це перетворення в 1955 році. Вперше його вивів та опублікував Р. Шмідт 1941 року^[1].

Можна обчислити лише кілька членів ряду збурень — зазвичай не більше двох чи трьох, і майже ніколи більше семи. Отриманий ряд часто збігається дуже повільно або навіть розбігається. І все ж ці кілька членів містять разючу кількість інформації, і дослідник має докласти всіх зусиль, щоб її витягти.
Цей підхід переконливо викладено у чудовій статті Шенкса (1955), де наведено низку вражаючих прикладів, зокрема кілька з гідромеханіки.

Мільтон ван Дайк^[en] (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}\,}$

Часткові суми утворюють нову послідовність ${\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}}$ — це нова послідовність, визначена як^[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}))),}$ тощо.

Зверніть увагу, що нелінійне перетворення, яке використовується в перетворенні Шенкса, по суті таке ж, як і в процесі Ейткена дельта-квадрат^[en], тому, як і в методі Айткена, крайній правий вираз у визначенні ${\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. Часткова сума ${\displaystyle A_{6}}$ має лише 1 точний знак, а для точності у 6 знаків потрібно підсумовувати близько 400000 членів.

У таблиці нижче наведено часткові суми ${\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})}$ має 6 точних знаків, — цей результат отримано шляхом 3 повторних перетворень Шенкса, застосованих до перших 7 членів ${\displaystyle A_{0},\ldots ,A_{6}.}$ Як згадувалося раніше, ${\displaystyle A_{n}}$ досягає точності до 6 знаків лише після підсумовування приблизно 400000 членів.

Мотивація

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

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

Ці три рівняння містять три невідомі: ${\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}}}.}$

Узагальнене перетворення Шенкса

Узагальнене перетворення Шенкса 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}.}$

Ця модель поведінки збіжності містить ${\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].

Обчислення визначників вимагає виконання багатьох арифметичних операцій, проте Пітер Вінн відкрив рекурсивну процедуру обчислення, яка називається епсилон-алгоритмом і дозволяє уникнути обчислення визначників^[5][6].