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

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

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

Проблема

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

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

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

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

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

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

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

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

Причина

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

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

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

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

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

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

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

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

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

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

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

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

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

З цього,

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

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

${\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.^{[джерело?]}

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

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

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