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

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

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

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

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

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

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

Хитрость в том, чтобы для каждого узла i построить «базисный» полином L_i(x), который равен 1 в своём узле и 0 во всех остальных. Тогда сумма Σ y_i·L_i(x) автоматически принимает значение y_i в каждом узле. Базисный полином собирается из множителей (x − x_j)/(x_i − x_j) по всем j ≠ 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²) на одну точку: n базисных полиномов, каждый — произведение n множителей. Существует более быстрая барицентрическая форма Лагранжа: один раз за O(n²) вычисляют веса узлов, после чего каждая новая точка считается за O(n), и формула остаётся численно устойчивой. Именно барицентрический вариант применяют на практике, а не «школьную» запись. Принципиально важно: какой бы формулой мы ни пользовались, итоговый полином через данные узлы один и тот же — Лагранж, Ньютон и барицентрический дают одну кривую.

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

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

Итоги

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