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

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

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

Проблема[ред.ред. код]

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

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

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

x_i = -1 + (i-1)\frac{2}{n},\qquad

де i \in \left\{ 1, 2, \dots, n+1 \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.

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

Причина[ред.ред. код]

Помилка між заданою функцією та інтерполюючими поліномами порядку N визначається через N-ту похідну заданої функції.

Для випадку функції Рунге, заданої вище, :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}

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

Вирішення проблеми феномена Рунге[ред.ред. код]

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