Полином Лагранжа: кривая через точки

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

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

Зачем интерполировать

Часто функция известна не формулой, а таблицей: измерения в нескольких точках, значения из эксперимента, узлы расписания. А нужно значение между узлами. Интерполяция строит гладкую кривую, которая точно проходит через все известные точки, и позволяет «дочитать» промежуточные значения. Это отличается от аппроксимации (следующий раздел), где кривая проходит рядом, сглаживая шум: интерполяция требует точного попадания в узлы.

Фундаментальный факт: через $n+1$ точку с разными абсциссами проходит ровно один полином степени не выше $n$. Через 2 точки — прямая, через 3 — парабола, и так далее. Лагранж даёт его готовой формулой.

Базисные полиномы Лагранжа

Хитрость в том, чтобы для каждого узла $i$ построить «базисный» полином $L_i(x)$, который равен 1 в своём узле и 0 во всех остальных. Тогда сумма $\sum y_i \cdot L_i(x)$ автоматически принимает значение $y_i$ в каждом узле. Базисный полином собирается из множителей $(x - x_j)/(x_i - x_j)$ по всем $j \ne i$: каждый зануляется в чужом узле $x_j$ и даёт 1 в своём $x_i$.

def лагранж(xs, ys, x):
    n = len(xs)
    результат = 0.0
    for i in range(n):
        # базисный полином L_i(x), равный 1 в узле i и 0 в прочих
        Li = ys[i]
        for j in range(n):
            if j != i:
                Li *= (x - xs[j]) / (xs[i] - xs[j])
        результат += Li
    return результат

# Три точки: (0,1), (1,3), (2,2) -> единственная парабола через них
xs = [0.0, 1.0, 2.0]
ys = [1.0, 3.0, 2.0]
print("проверка попадания в узлы:")
for k in range(len(xs)):
    print(f"  P({xs[k]}) = {лагранж(xs, ys, xs[k]):.4f}  (должно быть {ys[k]})")
print("значения между узлами:")
print(f"  P(0.5) = {лагранж(xs, ys, 0.5):.6f}")
print(f"  P(1.5) = {лагранж(xs, ys, 1.5):.6f}")

Вывод:

проверка попадания в узлы:
  P(0.0) = 1.0000  (должно быть 1.0)
  P(1.0) = 3.0000  (должно быть 3.0)
  P(2.0) = 2.0000  (должно быть 2.0)
значения между узлами:
  P(0.5) = 2.375000
  P(1.5) = 2.875000

Полином точно проходит через все три узла и аккуратно интерполирует между ними — именно то, что нужно.

Сильные и слабые стороны

Формула Лагранжа красива и наглядна, но у неё есть минус: при добавлении нового узла все базисные полиномы приходится пересчитывать заново — она «не инкрементна». Если узлы фиксированы, а вычислять полином надо во многих точках, это нормально; если узлы доливаются по одному, удобнее форма Ньютона (следующий урок), которая просто дописывает слагаемое. Ещё одна проблема — общая для всех интерполяционных полиномов высокой степени — феномен Рунге (урок дальше).

Как работает под капотом

Прямое вычисление по формуле Лагранжа стоит $O(n^2)$ на одну точку: $n$ базисных полиномов, каждый — произведение $n$ множителей. Существует более быстрая барицентрическая форма Лагранжа: один раз за $O(n^2)$ вычисляют веса узлов, после чего каждая новая точка считается за $O(n)$, и формула остаётся численно устойчивой. Именно барицентрический вариант применяют на практике, а не «школьную» запись. Принципиально важно: какой бы формулой мы ни пользовались, итоговый полином через данные узлы один и тот же — Лагранж, Ньютон и барицентрический дают одну кривую.

Частые ошибки

• Совпадающие абсциссы узлов. Если два $x_i$ равны, в знаменателе $x_i - x_j$ появляется ноль — узлы обязаны иметь разные абсциссы.
• Гнать степень вверх ради точности. Много узлов = высокая степень = риск Рунге; часто лучше сплайн.
• Экстраполировать за пределы узлов. Вне отрезка узлов полином ведёт себя дико; интерполяция надёжна только между узлами.

Итоги

• Интерполяция строит функцию, проходящую точно через узлы (в отличие от сглаживающей аппроксимации).
• Через $n+1$ узел проходит единственный полином степени $\le n$; Лагранж выписывает его явно.
• Базисный полином $L_i$ равен 1 в своём узле и 0 в прочих; ответ — $\sum y_i \cdot L_i(x)$.
• Форма Лагранжа наглядна, но не инкрементна; на практике берут барицентрический вариант.