Введение

Форма интерполяции
В численном анализе полиномиальная интерполяция — это интерполяция заданного набора данных из двух переменных полиномом наименьшей возможной степени, проходящим через точки этого набора данных. Для заданного набора из n + 1 точек данных, где никакие две точки не совпадают, полиномиальная функция f(x) называется интерполирующей данные, если f(xi) = yi для каждого i от 0 до n. Всегда существует единственный такой полином, который обычно задается двумя явными формулами: полиномами Лагранжа и полиномами Ньютона.

Приложения

Первоначальное применение интерполяционных многочленов заключалось в аппроксимации значений важных трансцендентных функций, таких как натуральный логарифм и тригонометрические функции. Начиная с нескольких точно вычисленных точек данных, соответствующий интерполяционный многочлен аппроксимирует функцию в любой близлежащей точке. Полиномиальная интерполяция также является основой алгоритмов численного интегрирования (правило Симпсона) и численных методов решения обыкновенных дифференциальных уравнений (многосеточные методы). В компьютерной графике полиномы могут использоваться для аппроксимации сложных плоских кривых, заданных несколькими точками, например, формы букв в типографике. Обычно это делается с помощью кривых Безье, которые являются простым обобщением интерполяционных многочленов (определяющих как точки, так и касательные в этих точках). В численном анализе полиномиальная интерполяция необходима для выполнения умножения и возведения в степень со сложностью менее квадратичной, таких как умножение Карацубы и умножение Тума-Кука, где интерполяция по точкам на многочлене произведения позволяет получить требуемое конкретное произведение. Например, если a = f(x) = a0x0 + a1x1 + ··· и b = g(x) = b0x0 + b1x1 + ···, то произведение ab является конкретным значением W(x) = f(x)g(x). Можно легко найти точки на W(x) при малых значениях x, и интерполяция на основе этих точек позволит получить коэффициенты W(x) и конкретное произведение ab. Как показано в умножении Карацубы, этот метод существенно быстрее квадратичного умножения, даже для умеренно больших входных данных, особенно на параллельном оборудовании. В информатике полиномиальная интерполяция также приводит к алгоритмам для безопасных многосторонних вычислений и разделения секрета.

Следующее

Если f — многочлен степени не выше n, то интерполяционный многочлен для f в n различных точках совпадает с самим f.

Не-Вандермондские алгоритмы

Чтобы найти интерполяционный полином p(x) в векторном пространстве P(n) многочленов степени n, можно использовать обычный мономиальный базис для P(n) и обратить матрицу Вандермонда методом Гаусса, что требует O(n³) операций. Для улучшения этого алгоритма более удобный базис для P(n) может упростить вычисление коэффициентов, которые затем необходимо пересчитать в терминах мономиального базиса. Один из способов – записать интерполяционный полином в форме Ньютона (то есть, используя ньютоновский базис) и использовать метод конечных разностей для построения коэффициентов, например, алгоритм Невилла. Это требует O(n²) операций. Более того, добавление новой точки к набору данных требует лишь O(n) дополнительных вычислений, в то время как для других методов необходимо пересчитывать всё заново. Другой метод предпочтителен, когда требуется не вычислять коэффициенты p(x), а лишь одно значение p(a) в точке x = a, не входящей в исходный набор данных. Форма Лагранжа вычисляет значение p(a) со сложностью O(n²). Форма Бернштейна использовалась в конструктивном доказательстве теоремы Вейерштрасса о приближении и приобрела большое значение в компьютерной графике в виде кривых Безье.

Ошибка интерполяции: формула остатков Лагранжа

При интерполяции заданной функции f многочленом степени n в узлах x0, x1, ..., xn мы получаем ошибку

где – (n+1)-я разделенная разность данных. Кроме того, существует формула остатка Лагранжа для ошибки, для функции f, которая (n+1) раз непрерывно дифференцируема на замкнутом интервале [a, b], и многочлена степени не выше n, интерполирующего f в n+1 различных точках. Для каждого x из [a, b] существует c, такое что

Эта оценка погрешности предполагает выбор точек интерполяции xi для минимизации произведения , что достигается узлами Чебышева.

Постоянные Лебежга

Мы фиксируем узлы интерполяции x0, ..., xn и интервал [a, b], содержащий все узлы интерполяции. Процесс интерполяции отображает функцию f в полином p. Это определяет отображение X из пространства C([a, b]) всех непрерывных функций на [a, b] в само себя. Отображение X линейно и является проекцией на подпространство полиномов степени n или меньше. Постоянная Лебега L определяется как операторная норма отображения X. Имеем (частный случай леммы Лебега):

Иными словами, интерполяционный полином не более чем в (L + 1) раз хуже наилучшего возможного приближения. Это наводит на мысль о поиске набора узлов интерполяции, при котором L будет малым. В частности, для узлов Чебышева имеем:

Следовательно, мы снова приходим к выводу, что узлы Чебышева – очень хороший выбор для полиномиальной интерполяции, поскольку рост L с увеличением n является экспоненциальным для равноотстоящих узлов. Однако эти узлы не являются оптимальными.

Связанные понятия

Феномен Рунге показывает, что при больших значениях n интерполяционный полином может сильно колебаться между точками данных. Эта проблема обычно решается использованием сплайн-интерполяции. В этом случае интерполянт – не полином, а сплайн: цепочка из нескольких полиномов более низкой степени. Интерполяция периодических функций гармоническими функциями осуществляется преобразованием Фурье. Это можно рассматривать как форму полиномиальной интерполяции с гармоническими базисными функциями, см. тригонометрическую интерполяцию и тригонометрический полином. Задачи интерполяции Эрмита – это те, в которых заданы не только значения полинома p в узлах, но и все производные до заданного порядка. Это оказывается эквивалентным системе полиномиальных сравнений, и может быть решено с помощью китайской теоремы об остатках для полиномов. Интерполяция Биркгоффа – это дальнейшее обобщение, в котором предписываются только производные некоторых порядков, а не обязательно все порядки от 0 до k. Методы коллокации для решения дифференциальных и интегральных уравнений основаны на полиномиальной интерполяции. Метод рациональной аппроксимации – это обобщение, которое рассматривает отношения полиномиальных функций. И, наконец, многомерная интерполяция для пространств более высокой размерности.