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

Лабораторная работа №4

по дисциплине «Вычислительные методы линейной алгебры».

Интерполяция функций.

Вариант 4

Выполнил: ст. гр. ПМ 11 Крамарев Д. В.

Проверил: д.ф.-м.н., проф. Чехонин К.А.

Хабаровск 2004

Задание.

1) Построить интерполяционный многочлен Ньютона. Начертить график и отметить на нем узлы интерполяции. Вычислить значения в точке х=1.25.

2) Построить интерполяционный многочлен Лагранжа. Начертить график и отметить на нем узлы интерполяции. Вычислить значение в точке х=1.2.

3) Выполнить интерполяцию сплайнами третьей степени. Построить график и отметить на нем узлы интерполяции.

Постановка задачи интерполяция.

Пусть известные значения функции образуют следующую таблицу:

При этом требуется получить значение функции f в точке x, принадлежащей
 отрезку [x₀..x_n] но не совпадающей ни с одним значением x_i.Часто при этом не известно аналитическое выражение функции f(x), или оно не пригодно для вычислений.

В этих случаях используется прием построения приближающей функции F(x), которая очень близка к f(x) и совпадает с ней в точках x₀, x₁, x₂,... x_n. При этом нахождение приближенной функции называется интерполяцией, а точки x₀,x₁,x₂,...x_n - узлами интерполяции. Обычно интерполирующую ищут в виде полинома n степени:

P_n(x)=a₀xⁿ+a₁x^n-1+a₂x^n-2+...+a_n-1x+a_n

Для каждого набора точек имеется только один интерполяционный многочлен, степени не больше n. Однозначно определенный многочлен может быть представлен в различных видах. Рассмотрим интерполяционный многочлен Ньютона и Лагранжа.

Интерполяционная формула Лагранжа.

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

Построим интерполяционный полином L_n(x) степени не больше n, и для которого выполняются условия L_n(x_i)=y_i . Запишем его в виде суммы:

L_n(x)=l₀(x)+ l₁(x)+ l₂(x)+...+ l_n(x),                                    (1)

где l_k( x_i)= y_i, если i=k, и l_k( x_i)= 0, если i≠k;

Тогда многочлен l_k( x) имеет следующий вид:

l_k(x)=                                                                                                (2)

Подставим (2) в (1) и перепишем L_n( x) в виде:

Если функция f(x), подлежащая интерполяции, дифференцируема больше чем n+1 раз, то погрешность интерполяции оценивается следующим образом:

 где0<θ<1                  (3)

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

Построение интерполяционного многочлена в форме Ньютона применяется главным образом когда разность x_i+1-x_i=h постоянна для всех значений x=0..n-1.

Конечная разность k-го порядка:

Δy_i=y_i+1-y_i

Δ²y_i= Δy_i+1- Δy_i=y_i+2-2y_i+1+y_i

………………………………

Δ^ky_i=y_i+k-ky_i+1-k+k(k-1)/2!*y_i+k-2+...+(-1)^ky_i

Будем искать интерполяционный многочлен в виде:

Pn(x)=a₀+a₁(x-x₀)+a₂(x-x₀)(x-x₁)+...+a_n(x-x₀)(x-x₁)...(x-x_n-1)

Найдем значения коэффициентов a₀, a₁, a₂, ...,a_n:

Полагая x=x₀, находим a₀=P(x₀)=y₀;

Далее подставляя значения x₁, x₂, ...,x_n получаем:

a₁=Δy₀/h

a₂=Δ²y₀/2!h²

a₃=Δ³y₀/3!h³

....................

a_n=Δⁿy₀/n!hⁿ

Таким образом:
Pn(x)=y₀+ Δy₀/h*(x-x₀)+ Δ²y₀/2!h²*(x-x₀)(x-x₁)+...+ Δⁿy₀/n!hⁿ*(x-x₀)(x-x₁)...(x-x_n-1)          (1)

Практически формула (1) применяется в несколько ином виде:

Возьмем: t=(x-x₀)/h, тогда x=x₀+th и формула (1) переписывается как:

P_n(x)=y₀+t Δ y₀+ t(t-1) / 2! Δ ² y₀+...+ t(t-1)...(t-n+1) / n! Δ ⁿ y₀                             (2)

Формула (2) называется интерполяционнойформулой Ньютона.

Погрешность метода Ньютона оценивается следующим образом:

                                                   (3)