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

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

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

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

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

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