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

Теорема (об интерполяции с производными). Пусть F – поле, x₁, …, x_n – попарно различные точки поля F, y₁, …, y_n, z₁, …, z_n Î F. Тогда существует такой однозначно определённый многочлен f(x) Î F[x] степени не выше 2× n – 1, принимающий в точках x₁, …, x_n заданные значения y₁, …, y_n, что значения его производной в этих же точках равны z₁, …, z_n соответственно: f(x_i) = y_i, f¢ (x_i) = z_i (1 £ i £ n). Таким образом, любой многочлен степени 2× n – 1 над полем полностью определяется своими значениями и значениями своей производной в n попарно различных точках.

Доказательство. Если f(x) – искомый многочлен, то предыдущая теорема позволяет искать его в виде f(x) = L(x)+(x–x₁)× …× (x–x_n)× q(x), где q(x) – некоторый многочлен степени не выше n–1 (учтено ограничение d(f) £ 2× n–1). Остаётся найти многочлен q(x). Сведём эту задачу к предыдущей, вычислив значения многочлена q(x) в точках x₁, …, x_n.

Имеем f¢ (x) = L¢ (x)+[(x–x₁)× …× (x–x_n)]¢ × q(x)+(x–x₁)× …× (x–x_n)× q¢ (x) =

= =

Поэтому z_i = f¢ (x_i) = L¢ (x_i)+q(x_i)× (a_i –x₁)× …× (x_i –x_i–1)× (x_i –x_i+1)× …× (x_i –x_n), и значения

однозначно определены. Поэтому многочлен q(x) степени не выше n–1 однозначно восстанавливается.

Теорема доказана.

Пример. Найти многочлен, принимающий в точках 0, 1, 2 значения 1, 2, 3 и имеющий в этих точках значения производной –1, 0, 1 соответственно.

Согласно теореме будем искать многочлен в виде

f(x) = L(x)+x× (x–1)× (x–2)× q(x),

где q(x) – многочлен степени не выше 2, а L(x) = x + 1. Тогда L¢ (x) = 1 и . Решаем задачу интерполяции для q(x) поформуле Лагранжа:

= – × (x² – 3× x + 2) – (x² – 2× x) = – × x ²+ × x – 1.

Итак, окончательно получаем

f(x) = x + 1 + x× (x – 1)× (x – 2)× (– × x² + × x – 1) =

= x + 1+ x× (x² – 3× x + 2)× (– × x² + × x – 1) =

= x + 1+ x× (– × x⁴ + 8× x³ – × x² + 10× x – 2) =

= – × x⁵ + 8× x⁴ – × x³ + 10× x² – x + 1.

Упражнения: 1. Существует ли многочлен с целыми коэффициентами, принимающий в точках 1, 2, 3 значения 5, 6, 7 соответственно? Найдите такой многочлен с рациональными коэффициентами.

2. Найти все многочлены над R, принимающие в точках –1, 0, 1, 2 значения –2, –1, 0, 1 соответственно.

3. Найти все многочлены над R, принимающие в точках –1, 0, 1, 2 значения –2, –1, 0, 1 соответственно и имеющие значение производной в этих точках 0, 1, 0, –1 соответственно.

Конечно, построенный многочлен может совершенно не отражать свойств исходной функции, поскольку через заданные n точек можно провести бесконечное число графиков различных функций. Поэтому для задач аппроксимации важно уметь оценивать величину |f(x) – L(x)| отклонения интерполяционного многочлена от исходной функции с точки зрения той или иной нормы на пространстве функций.

Теорема (о величине отклонения многочлена Лагранжа). Пусть функция f: [a; b] ® R является n раз непрерывно дифференцируемой на отрезке [a; b]. Если по заданным точкам x₁, …, x_n Î [a; b] и значениям функции в этих точках y₁ = f(x₁), …, y_n = f(x_n) построен многочлен Лагранжа L(x), то справедлива оценка

,

где П_n(x) = (x – x₁)× … × (x – x_n), M_n = .

Доказательство. Рассмотрим функцию u(x) = f(x) – L(x) – c× П_n(x), где c – некоторая постоянная, значение которой будет указано позднее. Поскольку П_n(x) = 0 при x = x_i, f(x_i) = L(x_i) (1 £ i £ n), то функция u(x) имеет на отрезке [a; b], как минимум, n корней x_i Î [a; b].

Выберем точку p Î [a; b], не совпадающую с x₁, …, x_n и положим . Тогда функция u(x) будет обращаться в ноль и в точке p, т.е. она будет иметь не менее n + 1 корня на отрезке [a; b]. Пусть (для определённости) p Î (x_i; x_i+1). Тогда функция u(x) на концах каждого из отрезков [x₁; x₂], …, [x_i–1; x_i], [x_i; p], [p; x_i+1], [x_i+1; x_i+2], …, [x_n–1; x_n] принимает одинаковые (нулевые) значения. По теореме Ролля на каждом из этих отрезков производная u¢ (x) обращается в ноль. Эти n нулей производной образуют систему из (n – 1)- гоотрезка, на каждом из концов которых u¢ (x) принимает одинаковые (нулевые) значения. Значит к производной снова можно применить теорему Ролля и найти n – 1 нуль второй производной u¢ ¢ (x). Продолжая этот процесс, найдём, по крайней мере, один нуль n- й производной u⁽ⁿ⁾(x) – точку x Î [a; b].

Поскольку L(x) – многочлен степени не выше n – 1, а П_n(x) – многочлен степени n, то L⁽ⁿ⁾(x) º 0, П_n⁽ⁿ⁾(x) = n! и 0 = u⁽ⁿ⁾(x) = f ⁽ⁿ⁾(x) – 0 – c× n!, т.е. . Это значение должно совпадать с выбранным ранее: , так что f(p) = L(p) + × П_n(p).

Поскольку точка p выбиралась произвольно с единственным условием p ¹ x_i (1 £ i £ n), то получена формула f(x) = L(x) + × П_n(x) (x Î [a; b]), которая верна и при x = x_i: f(x_i) = L(x_i), × П_n(x_i) = 0. Поэтому |f(x) – L(x)| = и .

Теорема доказана.

Следствие (об аппроксимации многочленами некоторых бесконечно дифференцируемых функций). Если f – бесконечно дифференцируемая на (a; b) функция, причём все её производные ограничены одной константой на [a; b], т.е. $ M Î R " x Î [a; b] |f ⁽ⁿ⁾(x)| £ M, то функция f сколь угодно близко аппроксимируется многочленом:

" e > 0 $ p(x) Î R[x] .

Доказательство. Разобьём отрезок [a; b] на n равных отрезков точками x₁ = a, x₂, …, x_n = b и построим интерполяционный многочлен Лагранжа L(x). Тогда , и последняя величина при больших n может быть сделана меньше любого e > 0, т.к. по формуле Стирлинга .

Следствие доказано.

Замечание: Условие равномерной ограниченности всех производных на отрезке [a; b] существенно: для функции на отрезке [–1; 1] интерполирование по равномерной сетке с шагом 2 / n не приводит к близкой аппроксимации, т.к. . Причина кроется в неограниченности производных этой бесконечно дифференцируемой функции при n ® ¥.

Интерполяционный многочлен Лагранжа применяется для решения задачи интерполяции функций.

Пример. Найти приближённое значение функции, заданной таблично, в точке x = 1, 0663

Воспользуемся интерполяционной формулой Лагранжа:

,

которая может быть переписана в виде , где

П_n+1(x) = (x – x₀)× (x – x₁)× … × (x – x_n),

D_i = (x_i – x₀)× … × (x_i – x_i–1)× (x – x_i) (x_i – x_i+1)× … × (x_i – x_n).

Для равноотстоящих друг от друга узлов имеем x_i+1 = x_i + h (0 £ i £ n–1), где h = . Поэтому

D_i = (x_i – x₀)× … × (x_i – x_i–1)× (x – x_i) (x_i – x_i+1)× … × (x_i – x_n) =

= i× h× (i – 1)× h× …× h× (x – x_i)× (–h)× …× (i – n)× h = (–1)^n–i× i! × (n – i)! × (x – x_i)× hⁿ =

= (–1)^n–i× i! × (n – i)! × (x – x₀ – i× h)× hⁿ = (–1)^n–i× i! × (n – i)! × (t – i)× hⁿ⁺¹

при t = . Кроме того, П_n+1(x) = (x – x₀)× (x – x₁)× … × (x – x_n) =

= t× h× (t – 1)× h× …× (t – n)× h = t× (t – 1)× …× (t – n)× hⁿ⁺¹,

так что , где

П_n+1(t) = t× (t – 1)× …× (t – n), С_i = (–1)^n–i× i! × (n – i)!.

По этой формуле и вычисляем y(x)» L_n(x). При этом, как доказано выше, в предположении о (n+1)- кратной непрерывной дифференцируемости функции y(x) выполняется оценка , где .