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

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

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

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

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

Позначення

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

Зверніть увагу, що спрощення за допомогою нотації O-велике забезпечує еквівалентність наступних формул: $${\displaystyle {\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}}}$$

Мета

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

Процедура

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

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

(1)

$${\displaystyle 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)

Щоб покращити наше наближення від ${\displaystyle O(h^{k_{0}})}$ до ${\displaystyle O(h^{k_{1}})}$ видаливши перший член похибки, ми множимо рівняння 2 на ${\displaystyle t^{k_{0}}}$ і відніміть рівняння 1, отримуючи $${\displaystyle (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 ]}}$ є ${\displaystyle O(h^{k_{1}})}$ наближення ${\displaystyle (t^{k_{0}}-1)A^{*}}$. Ми можемо розв'язати нашу поточну формулу для ${\displaystyle A^{*}}$, отримавши $${\displaystyle 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}})}$$що можна записати як ${\displaystyle A^{*}=A_{1}(h)+O(h^{k_{1}})}$, де $${\displaystyle A_{1}(h)={\frac {t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h)}{t^{k_{0}}-1}}.}$$

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

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

Властивості

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

Крім того, для оцінки можна використовувати загальну формулу ${\displaystyle k_{0}}$ (поведінка розміру кроку провідного порядку похибки відсікання), коли ні його значення, ні ${\displaystyle A^{*}}$ не відімо апріорі. Такий метод може бути корисним для кількісної оцінки невідомої швидкості збіжності. Враховуючи наближення ${\displaystyle A^{*}}$ з трьох різних розмірів кроку ${\displaystyle h}$, ${\displaystyle h/t}$, та ${\displaystyle h/s}$, точне співвідношення $${\displaystyle 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 є лише приблизно дійсним) $${\displaystyle 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}}}$$яку можна розв'язати чисельно для оцінки ${\displaystyle k_{0}}$ для деяких довільних допустимих варіантів ${\displaystyle h}$, ${\displaystyle s}$, та ${\displaystyle t}$.

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

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

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

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

Тоді $${\displaystyle 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}).}$$${\displaystyle R(h,t)}$ називається екстраполяцією Річардсона A(h) і має оцінку похибки вищого порядку ${\displaystyle O(h^{n+1})}$ порівняно з ${\displaystyle A(h)}$.

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