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

25.10.2021


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

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

R ( x ) = a 0 + a 1 x + … + a p x p b 0 + b 1 x + … + b q x q {displaystyle 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 {displaystyle p+q+1=n} .

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

∑ j = 0 p a j x i j − f ( x i ) ∑ j = 0 q b j x i j = 0 {displaystyle sum _{j=0}^{p}{a_{j}x_{i}^{j}}-f(x_{i})sum _{j=0}^{q}{b_{j}x_{i}^{j}}=0} , где i = 1 , … , n {displaystyle i=1,ldots ,n} .

Эти уравнения образуют систему линейных алгебраических уравнений из n {displaystyle n} уравнений относительно n + 1 {displaystyle n+1} неизвестных. Классическая задача интерполяции сводится к решению этой системы, однако качественное и численное исследование такой системы затруднительно. К тому же при большом количестве точек вычислить коэффициенты с большой точностью сложно — небольшой погрешности достаточно для того, чтобы полученный рациональный интерполянт не проходил через заданные точки.

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

В некоторых случаях R ( x ) {displaystyle R(x)} можно записать в явном виде ( n {displaystyle n} нечётное и p = q {displaystyle p=q} , либо n {displaystyle n} чётное и p − q = 1 {displaystyle p-q=1} ). Для этого вычисляются так называемые обратные разделенные разности, которые определяются условиями

f − ( x l ; x k ) = x l − x k f ( x l ) − f ( x k ) {displaystyle f^{-}(x_{l};x_{k})={frac {x_{l}-x_{k}}{f(x_{l})-f(x_{k})}}}

и рекуррентным соотношением

f − ( x k ; … ; x l ) = x l − x k f − ( x k + 1 ; … ; x l ) − f − ( x k ; … ; x l − 1 ) {displaystyle 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 ) + x − x 1 f − ( x 1 ; x 2 ) + x − x 2 f − ( x 1 ; x 2 ; x 3 ) + ⋯ + x − x n − 1 f − ( x 1 ; … ; x n ) {displaystyle 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 {displaystyle n/2} . Недостаток метода в том, что не для каждого набора точек возможно построить интерполянт такого вида, причём алгоритм не предусматривает обнаружение подобных ошибок. Тем не менее, долгое время этот алгоритм оставался единственным доступным способом рациональной интерполяции.

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

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

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

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

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