Интерполирование функций

Основные вопросы, рассматриваемые на лекции:

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

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

3. Схема Эйткена

4. Оценка погрешности интерполяционной формулы Лагранжа

5. Конечные разности

6. Интерполяционные формулы Ньютона

§ Первая интерполяционная формула Ньютона

§ Вторая интерполяционная формула Ньютона

7. Оценка погрешностей первой и второй интерполяционных формул Ньютона

8. Обратное интерполирование

9. Интерполяция сплайнами

1. Основные понятия интерполяции, задача, приводящая к приближению функции

Интерполяция (от лат. interpolation - изменение, переделка) - в математике и статистике, отыскание промежуточных значений величины по некоторым известным её значениям [Сов. энциклопедический словарь].
Задача, приводящая к приближению функции, заключается в следующем. Известны значения функции f (x) в точках x₁, x₂, :, x_n; требуется восстановить её значения при других х.
Интерполяционный полином, передающий свойства функции f (x) будем строить в виде:
P_n(x) = c₁φ₁(x) + c₂φ₂(x) + : + c_nφ_n(x), где φ₁(x), φ₂(x), :, φ_n(x) - класс линейно-независимых функций, при этом P_n(x_i) = f (x_i), i = 1, 2, :, n.
Таким образом, P_n(x) f(x).
Точки x₁, x₂, :, x_n называются узлами интерполяции.

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

Пусть известны значения функции f (x) в (n+1) точке x₀, x₁, :, x_n. Тогда многочлен Лагранжа, передающий свойства функции f (x), можно записать так:

· Схема Эйткена

Схема Эйткена предлагает более удобную форму нахождения полинома Лагранжа.
Основная идея данного метода заключается в следующем.
На первом этапе вычисляются многочлены L_0,1(x), L_1,2(x), :, L_n-1,n(x), построенные на каждой паре соседних узлов 0,1; 1,2; :; n-1,n соответственно.
При этом , , :, .
Таким образом, многочлены, построенные на паре соседних узлов, вычисляются по формулам: .
Затем на основе этих многочленов вычисляются многочлены, построенные на тройках соседних узлов: .
И т.д. пока не получится один многочлен, построенный на всех узлах интерполяции: .
Полученный многочлен L_{0, 1, ..., n}(x) L_n(x).

· Оценка погрешности интерполяционной формулы Лагранжа

Имеем y_j = f ( x_j ), L_n(x). Многочлен L_n(x) построен так, что L_n( x_j ) = f ( x_j ).
Вычисляя погрешность R_n(x) таким образом: R_n(x) = f (x) - L_n(x), можно получить следующую формулу для оценки погрешности интерполяционной формулы Лагранжа: .
Такая оценка возможна только в том случае, когда известно аналитическое выражение для f. Если же f задана таблично, то производные заменяются конечными разностями.

· Интерполяционные формулы Ньютона

• Первая интерполяционная формула Ньютона
  Пусть y_i = f ( x_i ), x_i = x₀ + ih, i = 1, 2, :, n.
  Нужно построить P_n(x), удовлетворяющий двум условиям:

1. Степень полинома не должна превышать n.

2. P_n( x_i ) = y_i.

Формула P_n(x) для первой интерполяционной формулы Ньютона имеет вид: ,
где q = ( x - x₀ ) / h.
Первая интерполяционная формула Ньютона применяется тогда, когда x находится вначале таблицы. Тогда в качестве x₀ следует брать ближайшее слева к заданному x табличное значение.

• Вторая интерполяционная формула Ньютона
  Когда значение аргумента находится ближе к концу отрезка интерполяции, применять первую интерполяционную формулу становится невыгодно.
  Для этого применяется вторая интерполяционная формула Ньютона: ,
  где q = ( x - x_n ) / h.
  Здесь в качестве x_n следует брать ближайшее справа к заданному x табличное значение.

· Оценка погрешностей первой и второй интерполяционных формул Ньютона

Используя подстановки q = ( x - x₀ ) / h и q = ( x - x_n ) / h и заменяя соответствующим образом выражение для П_n+1(x) в формуле оценки погрешности интерполяционной формулы Лагранжа, получим формулы для оценки погрешности интерполирования по первой и второй интерполяционной формуле Ньютона соответственно:
,
.

· Обратное интерполирование

Задача обратного интерполирования заключается в следующем. Если значения {y_i} в таблице упорядочены по возрастанию или убыванию, то функция y = f (x) монотонна на [ x₀ , x_n ], и эту же таблицу можно интерпретировать как задание дискретного образа функции x = φ(y), обратной по отношению к функции y = f(x). Для этой обратной функции также может быть поставлена задача интерполирования: найти значение x* по заданному значению y*.

Пусть {x_i} равноотстоящие узлы, расположенные на расстоянии h друг от друга и построен один из полиномов Ньютона (для определённости - первый): .
При решении задачи обратного интерполирования с помощью этого полинома в его левой части возникает известное значение y*, а сама формула становится алгебраическим уравнением относительно х. Если числа {y_i} упорядочены по возрастанию или убыванию, то это уравнение имеет единственное решение на [ x₀ , x_n ].
Его решение следует искать любым из изученных ранее методов для решения нелинейных уравнений.
В рассматриваемом нами случае наиболее естественным способом для решения уравнения является метод простой итерации.
Подставим y = y* в вышепредставленную формулу и преобразуем получившееся равенство к виду: .
Это уравнение имеет структуру x = φ(x), т.е. по виду пригодно для применения метода простой итерации.
В качестве начального приближения можно взять значение x⁽⁰⁾ = x_i, ближайшее к искомому х*. Имея начальное приближение x⁽⁰⁾, строим итерационный процесс для решения полученного уравнения пока не будет достигнута заданная точность:

· Интерполяция сплайнами

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

Определение. Пусть отрезок [a, b] разбит точками на n частичных отрезков [x_i , x_i+1],i = 0, 1, :, n-1. Сплайном порядка m называется функция S_m (x), обладающая следующими свойствами:
1) Функция S_m (x) непрерывна на отрезке [a, b] вместе со своими производными до некоторого порядка р.
2) На каждом отрезке [x_i , x_i+1] функция совпадает с некоторым алгебраическим многочленомP_m,i (x) степени m.

Разность m - p между степенью сплайна и наивысшим порядком непрерывной на отрезке [a, b] производной называют дефектом сплайна.
Будем рассматривать сплайны, дефект которых равен 1.

Наиболее широкое распространение получили кубические сплайны S₃ (x).

Итак, для осуществления интерполяции необходимо построить такой сплайн, что S(x_i ) = y_i, i = 0, 1, :, n.
Согласно определению кубический сплайн можно представить в виде: ,
где каждый из P3, i (x) - многочлен третьей степени: .
При этом коэффициенты a_i = y_i.
Можно показать, что коэффициенты с_i вычисляются по формулам: .
Для вычисления коэффициентов d_i используются формулы: .
Для вычисления коэффициентов b_i - формулы: .