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

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

ПроблемаРедагувати

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

 

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

 

де  

за допомогою полінома   порядок якого  . Рунге виявив, що отримана інтерполяція коливається і має досить велику похибку поблизу кінців інтервалу, тобто поблизу точок −1 і 1. Можна довести, що верхня межа похибка інтерполяції прямує до нескінченності, коли ступінь полінома зростає:

 

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

ПричинаРедагувати

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

 

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

 

Позначимо   вузлову функцію:

 

і нехай   буде максимумом функції  

 

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

 

де   це розмір кроку.

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

 .

З цього,

 

Але для випадку функції Рунге, заданої вище:  перші дві похідні

 

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

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

Розв'язання проблемиРедагувати

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

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

ПриміткиРедагувати

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