Екстраполяція Річардсона

Приклад методу екстраполяції Річардсона у двох вимірах.

Екстраполяція Річардсона — чисельний метод пришвидшення рядів, який використовують для покращення швидкості збіжності послідовності оцінок деякого значення $A^{\ast }=\lim _{h\to 0}A(h)$. По суті, враховуючи значення $A(h)$ для кількох значень $h$, ми можемо оцінити $A^{\ast }$ шляхом екстраполяції оцінок до $h=0$. Метод названий на честь Льюїса Фрая Річардсона, який ввів цю техніку на початку XX століття, хоча ця ідея вже була відома Християну Гюйгенсу з його розрахунків $\pi$. За словами Біркгофа та Роти, «її корисність для практичних обчислень важко переоцінити».

Практичне застосування екстраполяції Річардсона включає інтегрування Ромберга, яке застосовує екстраполяцію Річардсона до методу трапецій, та алгоритм Булірша-Штера для розв'язання звичайних диференціальних рівнянь.

Загальна формула

Позначення

Нехай $A_{0}(h)$ буде наближенням до точного значення $A^{*}$, що залежить від розміру кроку h (де ${\textstyle 0<h<1}$) з формулою для похибки виду $$A^{*}=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots$$ де $a_{i}$ є невідомими константами, а $k_{i}$ відомі константи такі, що $h^{k_{i}}>h^{k_{i+1}}$. Крім того, $O(h^{k_{i}})$ представляє похибку відсікання для наближення $A_{i}(h)$, так що $A^{*}=A_{i}(h)+O(h^{k_{i}}).$ У цьому випадку кажуть, що $A_{i}(h)$ є наближенням $O(h^{k_{i}})$.

Зверніть увагу, що спрощення за допомогою нотації O-велике забезпечує еквівалентність наступних формул: $${\begin{aligned}A^{*}&=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots \\A^{*}&=A_{0}(h)+a_{0}h^{k_{0}}+O(h^{k_{1}})\\A^{*}&=A_{0}(h)+O(h^{k_{0}})\end{aligned}}$$

Мета

Екстраполяція Річардсона — це процес, який знаходить краще наближення $A^{*}$, змінивши формулу похибки з $A^{*}=A_{0}(h)+O(h^{k_{0}})$ до $A^{*}=A_{1}(h)+O(h^{k_{1}}).$ Отже, замінивши $A_{0}(h)$ з $A_{1}(h)$ похибка відсікання зменшилася з $O(h^{k_{0}})$ до $O(h^{k_{1}})$ для того ж розміру кроку $h$. Загальна закономірність, за якою $A_{i}(h)$ є точнішою оцінкою, ніж $A_{j}(h)$ коли $i>j$. Завдяки цьому процесу ми досягли кращого наближення $A^{*}$ шляхом віднімання найбільшого члена похибки, який мав порядок $O(h^{k_{0}})$. Цей процес можна повторити, щоб видалити більше членів похибки та отримати ще кращі наближення.

Процедура

Використовуючи розміри кроків $h$ і $h/t$ для деякої константи $t$, дві формули для $A^{*}$ мають вигляд:

$$A^{*}=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+O(h^{k_{3}})$$

(1)

$$A^{*}=A_{0}\!\left({\frac {h}{t}}\right)+a_{0}\left({\frac {h}{t}}\right)^{k_{0}}+a_{1}\left({\frac {h}{t}}\right)^{k_{1}}+a_{2}\left({\frac {h}{t}}\right)^{k_{2}}+O(h^{k_{3}})$$

(2)

Щоб покращити наше наближення від $O(h^{k_{0}})$ до $O(h^{k_{1}})$ видаливши перший член похибки, ми множимо рівняння 2 на $t^{k_{0}}$ і відніміть рівняння 1, отримуючи $$(t^{k_{0}}-1)A^{*}={\bigg [}t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h){\bigg ]}+{\bigg (}t^{k_{0}}a_{1}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{1}}-a_{1}h^{k_{1}}{\bigg )}+{\bigg (}t^{k_{0}}a_{2}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{2}}-a_{2}h^{k_{2}}{\bigg )}+O(h^{k_{3}}).$$Це множення та віднімання було виконано тому, що ${\textstyle {\big [}t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h){\big ]}}$ є $O(h^{k_{1}})$ наближення $(t^{k_{0}}-1)A^{*}$. Ми можемо розв'язати нашу поточну формулу для $A^{*}$, отримавши $$A^{*}={\frac {{\bigg [}t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h){\bigg ]}}{t^{k_{0}}-1}}+{\frac {{\bigg (}t^{k_{0}}a_{1}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{1}}-a_{1}h^{k_{1}}{\bigg )}}{t^{k_{0}}-1}}+{\frac {{\bigg (}t^{k_{0}}a_{2}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{2}}-a_{2}h^{k_{2}}{\bigg )}}{t^{k_{0}}-1}}+O(h^{k_{3}})$$що можна записати як $A^{*}=A_{1}(h)+O(h^{k_{1}})$, де $$A_{1}(h)={\frac {t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h)}{t^{k_{0}}-1}}.$$

Рекурентне співвідношення

Для таких наближень можна визначити загальне рекурентне співвідношення $$A_{i+1}(h)={\frac {t^{k_{i}}A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{i}}-1}}$$ де $k_{i+1}$ задовольняє умові$$A^{*}=A_{i+1}(h)+O(h^{k_{i+1}}).$$

Властивості

Екстраполяцію Річардсона можна розглядати як лінійне перетворення послідовності.

Крім того, для оцінки можна використовувати загальну формулу $k_{0}$ (поведінка розміру кроку провідного порядку похибки відсікання), коли ні його значення, ні $A^{*}$ не відімо апріорі. Такий метод може бути корисним для кількісної оцінки невідомої швидкості збіжності. Враховуючи наближення $A^{*}$ з трьох різних розмірів кроку $h$, $h/t$, та $h/s$, точне співвідношення $$A^{*}={\frac {t^{k_{0}}A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{0}}-1}}+O(h^{k_{1}})={\frac {s^{k_{0}}A_{i}\left({\frac {h}{s}}\right)-A_{i}(h)}{s^{k_{0}}-1}}+O(h^{k_{1}})$$дає приблизне співвідношення (зверніть увагу, що позначення тут можуть викликати певну плутанину, два O, що з'являються у наведеному вище рівнянні, вказують лише на поведінку розміру кроку провідного порядку, але їхні явні форми різні, тому скорочення двох членів O є лише приблизно дійсним) $$A_{i}\left({\frac {h}{t}}\right)+{\frac {A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{0}}-1}}\approx A_{i}\left({\frac {h}{s}}\right)+{\frac {A_{i}\left({\frac {h}{s}}\right)-A_{i}(h)}{s^{k_{0}}-1}}$$яку можна розв'язати чисельно для оцінки $k_{0}$ для деяких довільних допустимих варіантів $h$, $s$, та $t$.

Оскільки $t\neq 1$, якщо $t>0$ і $s$ вибрано так, щоб $s=t^{2}$, це наближене співвідношення зводиться до квадратного рівняння для $t^{k_{0}}$, яке легко розв'язати для $k_{0}$ в термінах $h$ і $t$.

Приклад екстраполяції Річардсона

Припустимо, що ми хочемо наближено визначити $A^{*}$, і в нас є метод $A(h)$, який залежить від невеликого параметра $h$ таким чином, що $$A(h)=A^{\ast }+Ch^{n}+O(h^{n+1}).$$

Визначаємо нову функцію $$R(h,t):={\frac {t^{n}A(h/t)-A(h)}{t^{n}-1}}$$ де $h$ і ${\frac {h}{t}}$ — два різних розміри кроку.

Тоді $$R(h,t)={\frac {t^{n}(A^{*}+C\left({\frac {h}{t}}\right)^{n}+O(h^{n+1}))-(A^{*}+Ch^{n}+O(h^{n+1}))}{t^{n}-1}}=A^{*}+O(h^{n+1}).$$$R(h,t)$ називається екстраполяцією Річардсона A(h) і має оцінку похибки вищого порядку $O(h^{n+1})$ порівняно з $A(h)$.

Часто набагато легше отримати задану точність, використовуючи R(h), а не A(h′) зі значно меншим h′. У такому разі A(h′) може спричинити проблеми через обмежену точність (похибки округлення) або через збільшення кількості необхідних обчислень.

Посилання

• Feldman, Joel (2000). Richardson-Extrapolation (PDF).
• Israel, Robert. Richardson extrapolation.
• Matlab code for generic Richardson extrapolation.
• Julia code for generic Richardson extrapolation.