Раціональна інтерполяція

Раціональна інтерполяція (інтерполяція раціональними функціями) - уявлення інтерпольованої функції f (x) (Точніше кажучи, ряду табличних значень) у вигляді відношення двох поліномів. Ряд функцій, погано інтерпольованої поліноміальними методами, вдається добре наблизити раціональної функцією з поліномом в чисельнику і знаменнику. [1] Особливо це стосується функцій з нерегулярним характером поведінки [2] (зокрема, раціональна інтерполяція добре підходить для функцій з особливими точками [1] і різкими змінами [2] [3]).

За відомим n крапкам f (x_1) , ..., f (x_n) наближення до f (x) шукається у вигляді

R (x) = \ frac {a_0 + a_1x + \ ldots + a_px ^ p} {b_0 + b_1x + \ ldots + b_qx ^ q} , І p + q +1 = n . [2]

Коефіцієнти a_i і b_i обчислюються з набору співвідношень R (x_j) = f (x_j) , Де j = 1, \ ldots, n , Які можна записати у вигляді

\ Sum ^ {p} _ {j = 1} {a_jx_i ^ j} - f (x_i) \ sum ^ {q} _ {j = 0} {b_jx_i ^ j} = 0 , Де i = 1, \ ldots, n . [2]

Ці рівняння утворюють систему лінійних алгебраїчних рівнянь з n рівнянь відносно n +1 невідомих. Класична задача інтерполяції зводиться до вирішення цієї системи, однак якісне і чисельне дослідження такої системи важко. [4] До того ж при великій кількості точок обчислити коефіцієнти з великою точністю складно - невеликий похибки достатньо для того, щоб отриманий раціональний інтерполянт не проходив через задані точки. [5]


1. Запис в явному вигляді

У деяких випадках R (x) можна записати в явному вигляді ( n непарне і p = q , Або n парне і p-q = 1 ). Для цього обчислюються так звані зворотні розділені різниці, які визначаються умовами

f ^ - (x_l; x_k) = \ frac {x_l - x_k} {f (x_l) - f (x_k)}

і рекурентним співвідношенням

f ^ - (x_k; \ ldots; x_l) = \ frac {x_l - x_k} {f ^ - (x_ {k +1}; \ ldots; x_l) - f ^ - (x_k; \ ldots; x_ {l- 1})} .

У підсумку інтерполюються раціональна функція записується ланцюгової дробом

f (x) = .


2. Алгоритми раціональної інтерполяції

2.1. Алгоритм Булирша - Штера

Для вирішення проблем, пов'язаних з системою рівнянь, Булірша і Штер узагальнили алгоритм Невіла на випадок раціональної інтерполяції. Алгоритм Булирша - Штера отримує раціональну функцію зі ступенями чисельника і знаменника, рівними n / 2 . [5] [2] Недолік методу в тому, що не для кожного набору точок можливо побудувати інтерполянт такого виду, причому алгоритм не передбачає виявлення подібних помилок. Тим не менше, довгий час цей алгоритм залишався єдиним доступним способом раціональної інтерполяції. [5]


2.2. Алгоритм Шнайдера - Вернера

В 1986 Шнайдер і Вернер опублікували роботу, в якій виклали свій алгоритм раціональної інтерполяції, що використовує баріцентріческое уявлення раціонального інтерполянта. [6] Алгоритм Шнайдера - Вернера дозволяє отримати раціональну функцію з необхідної ступенем знаменника m (І ступенем чисельника n-m ). Також алгоритм дозволяє перевірити інтерполянт на наявність особливих точок. [5]

Згодом Беррут удосконалив цей алгоритм. [7]


2.3. Алгоритм Флоатера - Хорманна

В 2005 Флоатером і Хорманном був описаний алгоритм побудови раціональної інтерполюється функції, що має високу швидкість роботи, стійкість і надійність. [8] За цими параметрами алгоритм Флоатера - Хорманна порівняємо з інтерполяцією сплайнами. При цьому одержувана функція має малу похибкою апроксимації, ступенями чисельника і знаменника не більше, ніж n , А також не має особливих точок на дійсній осі.


Примітки

  1. 1 2 William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery 3.2 Rational Function Interpolation and Extrapolation / / Numerical Recipes in C. - Second Edition. - Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 (Англ.)
  2. 1 2 3 4 5 Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. 17. Раціональна інтерполяція / / Чисельні методи. - 6-те видання. - М .: Біном, 2008. - С. 85. - 636 с. - (Лабораторія знань). - 3000 екз. - ISBN 978-5-94774-815-4
  3. Efunda. Engineering Fundamentals Rational Function Interpolation - www.efunda.com / math / num_interpolation / num_interpolation.cfm # Rational (Англ.) . Читальний - www.webcitation.org/66YQviQuf з першоджерела 30 березня 2012.
  4. Чередниченко В. Г. Раціональна інтерполяція, аналітичне рішення. / / Сиб. матем. журн., 43:1 - www.mathnet.ru/php/getFT.phtml?jrnid=smj&paperid=1278&what=fullt&option_lang=rus. - Новосибірськ, 2002. - С. 188-193.
  5. 1 2 3 4 Бочканов Сергій, Бистрицький Володимир. "Бібліотека алгоритмів" Раціональна інтерполяція - alglib.sources.ru / interpolation / rational.php. Читальний - www.webcitation.org/66YQwBgau з першоджерела 30 березня 2012.
  6. C. Schneider, W. Werner Some new aspects of rational interpolation / / Mathematics of Computation, № 47 (175). - 1986. - P. 285-299. (Англ.)
  7. Jean-Paul Berrut, Richard Baltensperger, Hans D. Mittelmann Recent developments in barycentric rational interpolation / / International Series of Numerical Mathematics Vol. 151 - plato.asu.edu/ftp/papers/paper105.pdf. - Basel: Birkhuser, 2005. - P. 27-51. - ISBN 3-7643-7124-2 (Англ.)
  8. Michael S. Floater, Kai Hormann Barycentric Rational Interpolation With NO Poles AND High Rates Of Approximation - cg.in.tu-clausthal.de/papers/hormann/Floater.2007.BRI.pdf. - 2005. (Англ.)