Феномен Рунге

Феномен Рунге — проблема, що виникає в обчислювальній математиці при використанні поліноміальної інтерполяції на рівновіддалених вузлах за допомогою поліномів високих порядків (степенів). Була описана Карлом Рунге при вивченні поводження похибок при використанні поліноміальної інтерполяції для апроксимації функцій.

Інтерполяція функції Рунге поліномамиЧервона крива — функція Рунге.
Синя крива — інтерполяція поліномом 5-го порядку (використовуючи п'ять рівновіддалених вузлів інтерполяції).
Зелена крива — інтерполяція поліномом 9-го порядку (використовуючи дев'ять рівновіддалених вузлів інтерполяції).
У точках інтерполяції, розбіжність між функцією та інтерполяційним поліномом нульова (за побудовою полінома). Проте між точками інтерполяції (особливо поблизу крайніх точок: 1 і -1) розбіжність між функцією і інтерполяційним поліномом зростає для поліномів вищого порядку.

Проблема

Розглянемо функцію:

${\displaystyle f(x)={\frac {1}{1+25x^{2}}}.\,}$

Спробуємо інтерполювати цю функцію в рівновіддалених точках x_i між −1 і 1 таких що:

${\displaystyle x_{i}={\frac {2i}{n}}-1,\qquad }$

де ${\displaystyle i\in \left\{0,2,\dots ,n\right\}}$

за допомогою полінома ${\displaystyle P_{n}(x)}$ порядок якого ${\displaystyle \leq n}$. Рунге виявив, що отримана інтерполяція коливається і має досить велику похибку поблизу кінців інтервалу, тобто поблизу точок −1 і 1. Можна довести, що верхня межа похибка інтерполяції прямує до нескінченності, коли ступінь полінома зростає:

${\displaystyle \lim _{n\rightarrow \infty }\left(\max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\right)=\infty .}$

Цей приклад показує, що поліноміальна інтерполяція високого порядку на рівновіддалених вузлах може бути небезпечною.

Причина

Похибка наближення заданої функції f(x) інтерполяційним поліномом порядку ${\displaystyle n}$ визначається так:

${\displaystyle f(x)-P_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=1}^{n+1}(x-x_{i})}$

для деякого ${\displaystyle \xi }$ у (−1, 1). Таким чином,

${\displaystyle \max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\leq \max _{-1\leq x\leq 1}{\frac {\left|f^{(n+1)}(x)\right|}{(n+1)!}}\max _{-1\leq x\leq 1}\prod _{i=0}^{n}|x-x_{i}|.}$

Позначимо ${\displaystyle w_{n}(x)}$ вузлову функцію:

${\displaystyle w_{n}(x)=(x-x_{0})(x-x_{1})\cdots (x-x_{n}).}$

і нехай ${\displaystyle W_{n}}$ буде максимумом функції ${\displaystyle w_{n}:}$

${\displaystyle W_{n}=\max _{-1\leq x\leq 1}w_{n}(x).}$

Тоді, можна довести, що коли використовувати рівновіддалені вузли, тоді:

${\displaystyle W_{n}\leq h^{n}{\frac {(n-1)!}{4}}}$

де ${\displaystyle h=2/(n-1)}$ це розмір кроку.

Більше того, припустімо, що n-та похідна ${\displaystyle f}$ обмежена, тобто

${\displaystyle \max _{-1\leq x\leq 1}f^{(n)}(x)\leq M_{n}}$.

З цього,

${\displaystyle \max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\leq M_{n}{\frac {h^{n}}{4n}}}$

Але для випадку функції Рунге, заданої вище:${\displaystyle f(x)={\frac {1}{1+25x^{2}}}}$ перші дві похідні

${\displaystyle {\begin{array}{lcl}\displaystyle f'(x)=-{\frac {50x}{\left(1+25x^{2}\right)^{2}}}&\rightarrow &\displaystyle \left|f'(1)\right|={\frac {50}{26^{2}}}=0.0740\\[1.5em]\displaystyle f''(x)={\frac {5000(1+25x^{2})-50(1+25x^{2})^{2}}{\left(1+25x^{2}\right)^{4}}}&\rightarrow &\displaystyle \left|f''(1)\right|={\frac {96200}{26^{4}}}=0.2105\end{array}}}$

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

Проте факт збільшення верхньої межі похибки до нескінченності не обов'язково означає, що сама похибка також зростає з n.^[]

Розв'язання проблеми

Порівняння похибки зі зростанням кількості вузлів інтерполяції функції Рунге використовуючи рівновіддалені вузли і вузли Чебишова

Феномен Рунге демонструє, що коли обирати рівновіддалені вузли інтерполяції, то високий порядок апроксимуючого полінома не завжди підходить.
Однак, (апроксимаційна теорема Вейєрштраса) стверджує, що для неперервної на відрізку функції існує послідовність поліноміальних апроксимацій, для яких похибка прямує до нуля. Розбіжність можна мінімізувати, якщо замість рівновіддалених вузлів обирати вузли інтерполяції в коренях поліномів Чебишова першого роду. Такий підхід гарантує, що максимальна похибка зменшуватиметься з підвищенням порядку полінома.
Проблему також можна вирішити шляхом застосуванням сплайнів, зокрема, поліноміальних, тобто, замість підвищення степеня поліномів збільшити кількість поліноміальних частин.

Примітки

1. Heath, Michael (2000). Scientific Computing. McGraw-Hill. с. 324. ISBN .
2. Lloyd N. Trefethen. Approximation Theory and Approximation Practice : With 163 figures and 210 exercises : ( )[англ.]. — 2013.