Интерполяция алгебраическими многочленами

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Интерполяция алгебраическими многочленами функции f(x) на отрезке [a, b] — построение многочлена Pn(x) степени меньшей или равной n, принимающего в узлах интерполяции x0, x1, ..., xn значения f(xi):

Система уравнений, определяющих коэффициенты такого многочлена, имеет вид

Её определителем является определитель Вандермонда.

Он отличен от нуля при всяких попарно различных значениях xi, и интерполирование функции f по её значениям в узлах xi с помощью многочлена Pn(x) всегда возможно и единственно.

Применение[править | править вики-текст]

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

Задача интерполяции[править | править вики-текст]

Пусть в пространстве заданы точек , которые в некоторой системе координат имеют радиус-векторы .

Задача интерполяции состоит в построении кривой, проходящей через указанные точки в указанном порядке.

Решение задачи[править | править вики-текст]

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

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

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

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

Многочлен имеет коэффициентов , которые можно найти из условий .

Эти условия приводят к системе линейных уравнений для коэффициентов

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

называется определителем Вандермонда. Если узлы сетки не совпадают, он отличен от нуля, так что система уравнений имеет решение.

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

Преимущества[править | править вики-текст]

  • Для заданного набора точек и сетки параметра кривая строится однозначно.
  • Кривая является интерполяционной, то есть проходит через все заданные точки.
  • Кривая имеет непрерывные производные любого порядка.

Недостатки[править | править вики-текст]

  • С ростом числа точек порядок многочлена возрастает, а вместе с ним возрастает число операций, которое нужно выполнить для вычисления точки на кривой.
  • С ростом числа точек у интерполяционной кривой могут возникнуть осцилляции (см. пример ниже).

Пример[править | править вики-текст]

Интерполяция на последовательности сеток. Пример Рунге.

Классическим примером (Рунге), показывающим возникновение осцилляций у интерполяционного многочлена, служит интерполяция на равномерной сетке значений функции

Введем на отрезке равномерную сетку , , и рассмотрим поведение многочлена

который в точках принимает значения . На рисунке представлены графики самой функции (штрих-пунктирная линия) и трех интерполяционных кривых при :

  • интерполяция на сетке — квадратичная парабола;
  • интерполяция на сетке — многочлен четвертой степени;
  • интерполяция на сетке — многочлен восьмой степени.

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

См. также[править | править вики-текст]