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

Билет №37, 3 (1) 

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

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

Интерполяцио́нный многочле́н Лагра́нжа — многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n + 1 пар чисел , где все xi различны, существует единственный многочлен L(x) степени не более n, для которого L(xi) = yi. 

В простейшем случае (n = 1) — это линейный многочлен, график которого — прямая, проходящая через две заданные точки.

Определение

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

Лагранж предложил  способ вычисления таких многочленов:

 

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

lj(x) обладают  следующими свойствами:

являются многочленами степени n

lj(xj) = 1

lj(xi) = 0 при  

Отсюда следует, что L(x), как линейная комбинация lj(x), может иметь степень не больше n, и L(xj) = yj, Q.E.D.

[править]

Применения 

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

Пусть для функции f(x) известны значения yj = f(xj) в некоторых точках. Тогда мы можем интерполировать эту функцию как

 

В частности,

 

Значения интегралов от lj не зависят от f(x), и их можно  вычислить заранее, зная последовательность xi.

[править]

Случай равномерного распределения узлов интерполяции 

В случае равномерного распределения узлов интерполяции xi выражаются через расстояние между  узлами интерполяции h и начальную  точку x0:

, 

и, следовательно,

 

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

 

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

 

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

Интерполяционные  формулы Ньютона 

Интерполяционные  формулы Ньютона — формулы вычислительной математики, применяющиеся для полиномиального интерполирования. 

Если узлы интерполяции равноотстоящие и упорядочены по величине, так что xi + 1 − xi = h = const, то есть xi = x0 + ih, то интерполяционный многочлен можно записать в форме Ньютона. 

Интерполяционные  полиномы в форме Ньютона удобно использовать, если точка интерполирования находится вблизи начала (прямая формула Ньютона) или конца таблицы (обратная формула Ньютона).  

Короткая  форма интерполяционной формулы Ньютона 

В случае равноудаленных центров интерполяции, находящихся  на единичном расстоянии друг от друга, справедлива формула:

 
 
 

где  — обобщенные на область действительных чисел биномиальные коэффициенты(В математике биномиальные коэффициенты — это коэффициенты в разложении бинома Ньютона (1 + x)n по степеням x.). 

Прямая  интерполяционная формула  Ньютона

 

 где , а выражения вида Δkyi — конечные разности.

[править]

Обратная  интерполяционная формула  Ньютона

 где 

 

Интерполяция  кубическими сплайнами 

Под сплайном (от англ. spline — планка, рейка) обычно понимают кусочно-заданную функцию, совпадающую  с функциями более простой  природы на каждом элементе разбиения  своей области определения. 

Кубический  сплайн

 Некоторая функция f(x) задана на отрезке [a,b], разбитом на части [xi − 1,xi], a = x0 < x1 < ... < xN = b. Кубическим сплайном дефекта 1 называется функция S(x), которая:

  - на каждом  отрезке [xi − 1,xi] является многочленом  степени не выше третьей;

  - имеет непрерывные  первую и вторую производные  на всём отрезке [a,b];

 -в точках xi выполняется равенство S(xi) = f(xi), т. е. сплайн S(x) интерполирует  функцию f в точках xi.

 Для однозначного задания сплайна перечисленных  условий недостаточно, для построения сплайна необходимо наложить какие-то дополнительные требования.

 Естественным  кубическим сплайном называется кубический сплайн, удовлетворяющий также граничным  условиям вида:

 S''(a) = S''(b) = 0.

 Теорема: Для любой функции f и любого разбиения отрезка [a,b] cуществует ровно один естественный сплайн S(x), удовлетворяющий перечисленным выше условиям.

 Эта теорема  является следствием более общей  теоремы Шёнберга-Уитни об условиях существования интерполяционного  сплайна. 
 
 
 
 
 

 Наиболее  успешными средствами интерполяции числовых функций являются методы, основанные на сплайн-интерполяции. Термин "сплайн" происходит от названия гибкой рейки, с помощью которой проводят гладкие кривые через заданные точки. В заданных точках сплайн закреплялся физически. В математике под сплайном понимают интерполирующую функцию, производные которой могут иметь разрывы в узловых точках. Классическим вариантом сплайна является кубические сплайны. Эти сплайны иногда называют сплайнами Шёнберга по имени математика, который ввел эти сплайны на современном уровне. Кубические сплайны представляют собой дважды непрерывно дифференцируемые функции, которые на отрезка между соседними узлами являются кубическими многочленами. 

 Пусть также  дано разбиение отрезка  , и значения функции в узлах

 

 

  Кубическим  сплайном называется такая функция  , , что для этой функции выполнены следующие условия:

  ,

  , , .

 , ,  являются  непрерывными функциями.

 На каждом отрезке  , функция   представима в виде

   

 Как мы увидим в дальнейшем - для однозначного задания сплайна нам необходимо дополнительно добавить краевые условия на искомый сплайн. Мы будем рассматривать наиболее характерные условия:

  , .

  , . 

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

 Введем обозначение

 

  Запишем  сплайн  в следующей форме

 

  где  , . 

 Условия непрерывности  второй производной сплайна определяют систему линейных уравнений  

15,1

  где

 

  К этим  условиям следует добавить краевые  условия. В итоге для мы имеем  следующую систему уравнений  (15.2)

 

 15,2

 где

 

  Для условий  первого типа  , а для условий второго типа

   
 

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