Интерполяционный многочлен Лагранжа

Интерполяцио́нный многочле́н Лагра́нжа — многочлен минимальной степени, принимающий заданные значения в заданном наборе точек, то есть решающий задачу интерполяции.

ОпределениеПравить

 
Интерполяционный многочлен Лагранжа для четырёх точек (-9,5), (-4,2), (-1,-2) и (7,9), а также полиномы  , каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных.

Пусть задана   пара чисел   где все   различны. Требуется построить многочлен   степени не более  , для которого  .

Общий случайПравить

Ж. Л. Лагранж предложил следующий способ вычисления таких многочленов:

 

где базисные полиномы   определяются по формуле

 

Для любого   многочлен   имеет степень   и

 

Отсюда следует, что  , являющийся линейной комбинацией многочленов  , имеет степень не больше   и  .

Случай равноотстоящих узлов интерполяцииПравить

Пусть узлы интерполяции   являются равноотстоящими, то есть выражаются через начальную точку   и некоторую фиксированную положительную величину   следующим образом:

 

Отсюда следует, что

 

Подставляя эти выражения в формулу для базисного полинома и вынося   за знаки произведения в числителе и знаменателе, получим

 

Теперь можно ввести замену переменной

 

и получить выражение для базисных полиномов через  , которое строится с использованием только целочисленной арифметики:

 

Данные величины называются коэффициентами Лагранжа. Они не зависят ни от  , ни от   и потому могут быть вычислены заранее и записаны в виде таблиц. Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования длинной арифметики.

Остаточный членПравить

Если считать числа   значениями некоторой функции   в узлах  , то ошибка интерполирования функции   многочленом   равна

 

где   – некоторая средняя точка между наименьшим и наибольшим из чисел  . Полагая  , можно записать

 

ЕдинственностьПравить

Существует единственный многочлен степени не превосходящей  , принимающий заданные значения в   заданной точке.

Это утверждение является обобщением того факта, что через любые две точки проходит единственная прямая.

С точки зрения линейной алгебрыПравить

На единственность интерполяционного многочлена можно также взглянуть с точки зрения СЛАУ. Рассмотрим систему уравнений  . В явном виде она записывается как

 

Её можно переписать в виде системы уравнений   с неизвестным вектором  :

 

Матрица   в такой системе является матрицей Вандермонда и её определитель равен  . Соответственно, если все точки   различны, то матрица невырождена и система обладает единственным решением.

С точки зрения китайской теоремы об остаткахПравить

По теореме Безу остаток от деления   на   равен  . Таким образом, всю систему можно воспринимать в виде системы сравнений:

 

По китайской теореме об остатках у такой системы есть единственное решение по модулю  , то есть, заданная система однозначно определяет многочлен степени не выше  . Такое представление многочлена в виде наборов остатков по модулям мономов аналогично представлению числа в виде остатков от деления на простые модули в системе остаточных классов. При этом явная формула для многочлена Лагранжа также может быть получена в соответствии с формулами китайской теоремы:  , где   и  .

ПримерПравить

 
Приближение функции   (синяя линия) многочленом   (зелёная линия).

Найдем формулу интерполяции для   имеющей следующие значения:

 
 
 
 
 
 

Получим

 

ПримененияПравить

 
Многочлены Лагранжа степеней от нулевой до пятой для функции  

Численное интегрированиеПравить

Пусть для функции   известны значения   в некоторых точках. Тогда можно интерполировать эту функцию методом Лагранжа:

 

Полученное выражение можно использовать для приближённого вычисления определённого интеграла от функции  :

 

Значения интегралов от   не зависят от   и их можно вычислить заранее с использованием последовательности  .

ЛитератураПравить

СсылкиПравить

См. такжеПравить