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

Рациональная интерполяция (интерполяция рациональными функциями) — представление интерполируемой функции $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]

Запись в явном виде

В некоторых случаях $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) = f(x_1)+\frac{x-x_1}{f^-(x_1;x_2)+\frac{x-x_2}{f^-(x_1;x_2;x_3)+\cdots+\frac{x-x_{n-1}}{f^-(x_1;\ldots;x_n)}}}$.

Алгоритмы рациональной интерполяции

Алгоритм Булирша — Штера

Для решения проблем, связанных с системой уравнений, Булирш и Штер обобщили алгоритм Невилля на случай рациональной интерполяции. Алгоритм Булирша — Штера получает рациональную функцию со степенями числителя и знаменателя, равными $n/2$.^[5][2] Недостаток метода в том, что не для каждого набора точек возможно построить интерполянт такого вида, причём алгоритм не предусматривает обнаружение подобных ошибок. Тем не менее, долгое время этот алгоритм оставался единственным доступным способом рациональной интерполяции.^[5]

Алгоритм Шнайдера — Вернера

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

Впоследствии Беррут усовершенствовал этот алгоритм.^[7]

Алгоритм Флоатера — Хорманна

В 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  (англ.). Архивировано из первоисточника 30 марта 2012. Проверено 30 апреля 2009.
4. ↑ Чередниченко В. Г. Рациональная интерполяция, аналитическое решение. // Сиб. матем. журн., 43:1. — Новосибирск, 2002. — С. 188–193.
5. ↑ ^{1 2 3 4} Бочканов Сергей, Быстрицкий Владимир. «Библиотека алгоритмов» Рациональная интерполяция  (рус.). Архивировано из первоисточника 30 марта 2012. Проверено 30 апреля 2009.
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. — Basel: Birkhäuser, 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. — 2005. (англ.)

См. также

• Аппроксимация Паде