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

Интерполяционный многочлен Лагранжа — это многочлен степени не выше \(n\), принимающий заданные значения в \(n+1\) фиксированной точке (узлах интерполяции). Он является одним из основных способов построения интерполяционного многочлена в форме, не требующей решения системы линейных уравнений, и широко применяется в вычислительной математике, численном анализе и обработке данных.

Определение

Пусть заданы \(n+1\) различных точек \((x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\), где \(x_i\) — узлы интерполяции, а \(y_i = f(x_i)\) — значения некоторой функции \(f\) в этих узлах. Интерполяционный многочлен Лагранжа \(L_n(x)\) определяется как:

\[ L_n(x) = \sum_{i=0}^{n} y_i \cdot l_i(x), \]

где \(l_i(x)\) — базисные многочлены Лагранжа, каждый из которых равен 1 в своём узле \(x_i\) и 0 во всех остальных узлах:

\[ l_i(x) = \prod_{\substack{j=0 \\ j \neq i}}^{n} \frac{x - x_j}{x_i - x_j}. \]

Таким образом, \(L_n(x)\) является единственным многочленом степени не выше \(n\), проходящим через все заданные точки.

Свойства

Единственность

Интерполяционный многочлен Лагранжа для заданного набора точек \((x_i, y_i)\) с различными \(x_i\) существует и единственен. Это следует из того, что система из \(n+1\) линейных уравнений для коэффициентов многочлена степени \(n\) имеет единственное решение, если узлы различны. Любая другая форма интерполяционного многочлена (например, в форме Ньютона) является лишь перестановкой того же самого многочлена.

Степень многочлена

Степень \(L_n(x)\) не превышает \(n\). Если все \(y_i\) равны между собой, многочлен вырождается в константу. Если же значения \(y_i\) соответствуют многочлену степени \(m \leq n\), то \(L_n(x)\) в точности воспроизводит этот многочлен.

Погрешность интерполяции

Если функция \(f(x)\) имеет \(n+1\) непрерывную производную на отрезке, содержащем все узлы, то погрешность интерполяции в точке \(x\) оценивается формулой:

\[ R_n(x) = f(x) - L_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \cdot \prod_{i=0}^{n} (x - x_i), \]

где \(\xi\) — некоторая точка из интервала, содержащего \(x\) и все узлы. Эта формула показывает, что погрешность зависит как от гладкости функции, так и от расположения узлов.

Построение многочлена

Алгоритм

1. Для каждого \(i\) от 0 до \(n\) вычислить базисный многочлен \(l_i(x)\) как произведение дробей для всех \(j \neq i\).
2. Умножить каждый \(l_i(x)\) на соответствующее значение \(y_i\).
3. Суммировать полученные произведения.

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

Пример

Для точек \((0, 1)\), \((1, 2)\), \((2, 3)\):

• \(l_0(x) = \frac{(x-1)(x-2)}{(0-1)(0-2)} = \frac{(x-1)(x-2)}{2}\)
• \(l_1(x) = \frac{(x-0)(x-2)}{(1-0)(1-2)} = \frac{x(x-2)}{-1} = -x(x-2)\)
• \(l_2(x) = \frac{(x-0)(x-1)}{(2-0)(2-1)} = \frac{x(x-1)}{2}\)

Тогда \(L_2(x) = 1 \cdot l_0(x) + 2 \cdot l_1(x) + 3 \cdot l_2(x) = \frac{(x-1)(x-2)}{2} - 2x(x-2) + \frac{3x(x-1)}{2}\). После упрощения получаем \(L_2(x) = x + 1\), что является прямой линией, проходящей через все три точки.

Применение

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

Формулы Ньютона — Котеса (включая метод Симпсона и метод трапеций) основаны на замене подынтегральной функции интерполяционным многочленом Лагранжа с последующим точным интегрированием. Например, для двух узлов получается формула трапеций, для трёх — формула Симпсона.

Численное дифференцирование

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

Обработка сигналов и изображений

Интерполяция Лагранжа применяется для передискретизации (изменения частоты дискретизации) сигналов, а также для масштабирования изображений. Однако из-за склонности к осцилляциям на неравномерной сетке (феномен Рунге) на практике чаще используют сплайны или интерполяцию с помощью кусочно-полиномиальных функций.

Построение таблиц функций

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

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

Многочлен Ньютона

Интерполяционный многочлен Ньютона в форме с разделёнными разностями является алгебраически эквивалентным многочлену Лагранжа, но обладает преимуществом при добавлении новых узлов: не требуется пересчёт всех базисных функций. В многочлене Лагранжа при добавлении точки приходится пересчитывать все \(l_i(x)\) заново.

Сплайны

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

Интерполяция Чебышёва

Выбор узлов интерполяции по корням многочленов Чебышёва минимизирует максимальную погрешность (принцип минимакса) и уменьшает феномен Рунге. В отличие от равномерной сетки, узлы Чебышёва сгущаются к краям отрезка, что улучшает сходимость.

Феномен Рунге

При интерполяции функций с большими градиентами (например, \(f(x) = 1/(1+25x^2)\) на отрезке \([-1, 1]\)) с равномерно расположенными узлами многочлен Лагранжа высокой степени начинает сильно осциллировать на краях отрезка. Это явление называется феноменом Рунге. Для его преодоления применяют:

• выбор узлов, сгущающихся к краям (например, узлы Чебышёва);
• кусочно-полиномиальную интерполяцию (сплайны);
• уменьшение степени многочлена (например, аппроксимация по методу наименьших квадратов).

История

Метод интерполяции с помощью многочленов, проходящих через заданные точки, был известен ещё в древности (например, в вавилонской астрономии). Однако в современной форме многочлен Лагранжа был впервые опубликован французским математиком Жозефом Луи Лагранжем в 1795 году в его работе «Лекции по элементарной математике». Лагранж систематизировал и обобщил более ранние результаты, в том числе работы Исаака Ньютона и Эдварда Уоринга. В русскоязычной литературе этот многочлен часто называют «интерполяционным многочленом Лагранжа» или просто «формулой Лагранжа».

Интересные факты

• Базисные многочлены Лагранжа \(l_i(x)\) образуют разбиение единицы: \(\sum_{i=0}^{n} l_i(x) = 1\) для любого \(x\). Это свойство следует из того, что многочлен степени \(n\), равный 1 в \(n+1\) точке, тождественно равен 1.
• Если все \(y_i\) равны 0, то \(L_n(x) \equiv 0\).
• В случае двух узлов (\(n=1\)) многочлен Лагранжа вырождается в линейную интерполяцию: \(L_1(x) = y_0 \frac{x - x_1}{x_0 - x_1} + y_1 \frac{x - x_0}{x_1 - x_0}\).
• В вычислительной практике для повышения устойчивости часто используют схему Невилла, которая позволяет вычислять значение многочлена Лагранжа в точке без явного построения его коэффициентов.

Источники

• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином. Лаборатория знаний, 2008.
• Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
• Формалев В. Ф., Ревизников Д. Л. Численные методы. — М.: Физматлит, 2004.
• Лагранж Ж. Л. Лекции по элементарной математике. — М.: Наука, 1975.