ИНТЕРПОЛЯЦИОННЫЙ ПОЛИНОМ ЛАГРАНЖА

Если при построении интерполяционного полинома выбрать в качестве базиса одночлены, например, 1, х, х²,...,хⁿ , как это было сделано выше, то во многих случаях система линейных уравнений для нахождения коэффициентов, получается плохо обусловленной (см. главу 4). Например, в случае равномерного распределения узлов на отрезке [0, 1] последовательные степени х, х², ... почти линейно зависимы (отчасти потому, что все они положительны и графики всех идут от точки (0, 0) к точке (1, 1). Эта близость к линейной зависимости делает решение линейной системы при нормальной рабочей точности крайне трудным делом для порядка n, превышающего 10.

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

Пусть задана таблица {x_i, y_i}, i = 0, ..., n c произвольным расположением узлов x₀ < x₁ <...< x_n .

Построим вспомогательный полином n-ой степени, который равнялся бы единице в узловой точке x=x_i , а во всех других узловых точках равнялся бы нулю:

.

Если ввести обозначение , то вспомогательный (лагранжев) полином запишется в виде:

.

Тогда интерполяционный полином Лагранжа будет представлять собой линейную комбинацию этих вспомогательных полиномов:

Очевидно, что основное условие интерполяции выполняется: L_n(x_i)=y_i .

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

В любой точке, не являющейся узлом интерполяции, функция y будет отличаться от полинома L_n. Рассмотрим погрешность интерполяционной формулы Лагранжа R_n(x)=f(x) – L_n(x).

Теорема. Если f(x) – непрерывная дифференцируемая n+1 раз на отрезке [a, b] функция, содержащая узловые точки x₀, x₁,..., x_n , то для любого xÎ[a, b] найдется такая точка xÎ[a, b], что погрешность

. (2.5)

Доказательство. Введем в рассмотрение функцию

u(z) = f(z) – L_n(z) – kw(z),

где k – неизвестный пока коэффициент.

Очевидно, что при z=x₀, x₁,...,x_n функция u(z) обращается в нуль, то есть функция u(z) на интервале [a,b] имеет n+1 корень.

Выберем k таким образом, чтобы u(x)=0 в точке, не совпадающей с узлом. Для этого достаточно положить

f(x) – L_n(x) – kw(x) = 0, то есть k = R_n(x)/w(x).

Таким образом, функция u(z)=R_n(z) – R_n(x)w(z)/w(x) равна нулю в n+2 точках x₀, x₁,..., x_n, x.

Тогда по теореме Ролля[5] ее производная u¢(z) обращается в нуль по крайней мере в n+1 точке. Применяя теорему Ролля к функции u¢(z), получаем, что ее производная u¢¢(z) обращается в нуль по крайней мере в n точках. Продолжая эти рассуждения дальше, получаем, что

обращается в нуль по крайней мере в одной точке xÎ[a, b].

Так как , а , то

.

Следовательно, ,

где .

Таким образом,

. (2.6)

Пример. Построить интерполяционный полином Лагранжа для функции f(x)=x^1/2 c узлами интерполяции х₀=100; х₁=121; х₂=144. Оценить погрешность интерполяции в точке х=116.

1. Оценим погрешность.

так как на отрезке [100,144] функция f ⁽³⁾(x)убывающая. Поэтому

2. Построим полином.

Таблица имеет вид

Тогда

Примечание 1. Если относительно функции f ничего неизвестно, кроме ее значений в узлах интерполяции, то никаких полезных суждений относительно погрешности R_n(x) сделать нельзя.

Конец примечания 1.

Примечание 2.Как видно из примера, оценку погрешности можно провести до вычисления интерполяционного многочлена, то есть это априорная оценка погрешности. Ранее мы проводили оценку погрешности по первому отброшенному члену ряда после выполнения вычислений на каждом шаге. Это была апостериорная оценка.

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

Конец примечания 2.

Теперь рассмотрим следующую задачу. Пусть задана некоторая функция (то есть принадлежащая классу непрерывных и n+1 раз дифференцируемых функций). Требуется заменить эту функцию интерполяционным полиномом L_n(x), причем имеется свобода выбора узловых точек.

Возникает вопрос, как выбрать узлы, чтобы максимальная погрешность интерполяции функции f на этом отрезке была минимальной. Это довольно сложная задача, и ее удается решить лишь для некоторых частных функций. Ограничимся решением более простой задачи, а именно, нахождением такого расположения узлов, при котором минимальна величина max½w(x)½ и поэтому минимальна правая часть оценки погрешности.

Для этого полином w(х) должен быть полиномом Чебышева (именно этот полином на отрезке [–1, 1] имеет наименьшее значение максимума модуля), а в качестве узлов интерполяции необходимо взять корни полинома Чебышева T_n+1(x) (формула (2.2)), то есть точки

k=1, ..., n+1.

Тогда w(х)=2^–nT_n+1(x) и .

В силу вышеупомянутого свойства полиномов Чебышева улучшить эту оценку за счет другого выбора узлов нельзя.

Для произвольного отрезка [a, b] оптимальные узлы интерполяции в соответствии с формулой (2.3) имеют вид

.

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