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

Рациональная интерполяция (интерполяция рациональными функциями) — представление интерполируемой функции $f(x)$ в виде отношения двух полиномов. Ряд функций, плохо интерполируемых полиномиальными методами, удаётся хорошо приблизить рациональной функцией с полиномом в числителе и знаменателе.Шаблон:-1 Особенно это касается функций с нерегулярным характером поведения (в частности, рациональная интерполяция хорошо подходит для функций с особыми точками и резкими изменениями).

По известным $n$ точкам $f(x_{1})$, … , $f(x_{n})$ приближение к $f(x)$ ищется в виде

$R(x)={\frac {a_{0}+a_{1}x+\ldots +a_{p}x^{p}}{b_{0}+b_{1}x+\ldots +b_{q}x^{q}}}$, и $p+q+1=n$.Шаблон:-1

Коэффициенты $a_{i}$ и $b_{i}$ вычисляются из набора соотношений $R(x_{j})=f(x_{j})$, где $j=1,\ldots ,n$, которые можно записать в виде

$\sum _{j=1}^{p}{a_{j}x_{i}^{j}}-f(x_{i})\sum _{j=0}^{q}{b_{j}x_{i}^{j}}=0$, где $i=1,\ldots ,n$.Шаблон:-1

Эти уравнения образуют систему линейных алгебраических уравнений из $n$ уравнений относительно $n+1$ неизвестных. Классическая задача интерполяции сводится к решению этой системы, однако качественное и численное исследование такой системы затруднительно.Шаблон:-1 К тому же при большом количестве точек вычислить коэффициенты с большой точностью сложно — небольшой погрешности достаточно для того, чтобы полученный рациональный интерполянт не проходил через заданные точки.Шаблон:-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)=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$.Шаблон:-1 Недостаток метода в том, что не для каждого набора точек возможно построить интерполянт такого вида, причём алгоритм не предусматривает обнаружение подобных ошибок. Тем не менее, долгое время этот алгоритм оставался единственным доступным способом рациональной интерполяции.Шаблон:-1

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

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

Впоследствии Беррут усовершенствовал этот алгоритм.Шаблон:-1

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

В 2005 году Флоатером и Хорманном был описан алгоритм построения рациональной интерполирующей функции, имеющий высокую скорость работы, устойчивость и надежность.Шаблон:-1 По этим параметрам Алгоритм Флоатера — Хорманна сравним с интерполяцией сплайнами. При этом получаемая функция обладает малой погрешностью аппроксимации, степенями числителя и знаменателя не более, чем $n$, а также не имеет особых точек на действительной оси.