Эксперименты лаба4,5(2курс)

Подставляя (3) в (1) получаем:

a0 + a1x0 + a2x20::: + anxn0 = y0 a0 + a1x1 + a2x21::: + anxn1 = y1

a0 + a1xn + a2x2n::: + anxnn = yn

(4) – система линейных алгебраических уравнений относительно неизвестных коэффициентов ai. Определитель такой системы отличен от нуля, если среди узлов xi нет совпадающих. Следовательно, в этом случае система (4) имеет единственное решение. Решив систему (4), построим интерполяционный многочлен. Такой метод построения носит название метода неопределенных коэффициентов.

Недостатки метода:

–при большом количестве узлов получается высокая степень многочлена,

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

Другой способ – подбор наиболее простой аппроксимирующей функции, график которой проходит максимально близко от узлов.

Мера отклонения функции '(x) от заданной функции f(x):

Метод наименьших квадратов состоит в подборе аппроксимирующей функции так, чтобы S было наименьшим.

3.2.Интерполирование

Кусочно-линейная интерполяция

2

Многочлен Лагранжа

Будем строить интерполяционный многочлен, единый для всего отрезка [x0; xn], в виде линейной комбинации многочленов степени n

так, чтобы многочлены li(x) обращались в нуль во всех узлах интерполяции, кроме i -го, где он должен равняться единице. Этим условиям при i = 0 отвечает многочлен вида:

Подставляя (9),(10) в (8) получаем интерполяционный многочлен Лагран-

3

Единственность найденного решения следует из единственности решения системы (4). Если положить n = 1 в (11), то получим рассмотренный ранее случай линейной интерполяции, при n = 2 – случай квадратичной интерполяции

Многочлен Ньютона

При построении интерполяционного многочлена Лагранжа не накладывалось никакого требования на распределение узлов интерполяции. Рассмотрим случай равноотстоящих по оси x узлов интерполяции. Введем h = xi ¡ xi¡1 – шаг интерполяции, h = const.

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

Разности первого порядка (первые разности):

¢y0 = y1 ¡ y0 = f(x0 + h) ¡ f(x0);

¢y1 = y2 ¡ y1 = f(x0 + 2h) ¡ f(x0 + h);

:::

¢yn¡1 = yn ¡ yn¡1 = f(x0 + nh) ¡ f(x0 + (n ¡ 1)h):

Разности второго порядка (вторые разности):

¢2y0 = ¢y1 ¡ ¢y0; ¢2y1 = ¢y2 ¡ ¢y1;

Разности порядка k:

¢kyi = ¢k¡1yi+1 ¡ ¢k¡1yi; i = 0; 1; :::; n ¡ 1:

Конечные разности выражаются через значения функции

¢2y0 = ¢y1 ¡ ¢y0 = (y2 ¡ y1) ¡ (y1 ¡ y0) = y2 ¡ 2y1 + y0;

¢3y0 = ¢2y1 ¡ ¢2y0 = ::: = y3 ¡ 3y2 + 3y1 ¡ y0:

В общем случае

4

Интерполяционный многочлен Ньютона будем искать в следующем виде:

N(x) = a0 + a1(x ¡ x0) + a2(x ¡ x0)(x ¡ x1) + ::: +

+ an(x ¡ x0)(x ¡ x1):::(x ¡ xn¡1): (14)

График многочлена должен проходить через заданные узлы, то есть N(xi) = yi i = 0; 1; :::; n. Для нахождения коэффициентов многочлена получаем систему

N(x0) = a0 = y0;

N(x1) = a0 + a1(x1 ¡ x0) = a0 + a1h = y1;

N(x2) = a0 + a1(x2 ¡ x0) + a2(x2 ¡ x0)(x2 ¡ x1) = = a0 + 2a1h + 2a2h2 = y2;

5

Формула (19) – второй интерполяционный многочлен Ньютона для интерполирования назад.

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

3.3.Точность интерполяции

Значения интерполяционного многочлена y = '(x) и рассматриваемой функции y = f(x) в узлах x = xi, (i = 0; 1; :::; n) в точности совпадают. Если исследуемая функция многочлен степени n, то f(x) ´ '(x). В остальных случаях разность

R(x) = f(x) ¡ '(x) =6 0:

Очевидно, что R(x) есть погрешность интерполяции и называется остаточным членом интерполяционной формулы. Можно показать, что остаточный член интерполяционного многочлена Лагранжа имеет вид

В этой формуле f(n+1)(x0) – производная (n + 1)-го порядка функции

f(x) в некоторой точке x0 2 [x0; xn].

Из анализа (20) следует, что погрешность интерполяции тем выше, чем ближе точка x лежит к концам отрезка [x0; xn]. Если же использовать интерполяционный многочлен вне отрезка [x0; xn], то погрешность возрастает очень заметно.

Остаточный член интерполяцинного многочлена Ньютона для случая равноотстоящих узлов следует из (20)

7

Из вида остаточного члена следует, что повышение степени интерполяционного многочлена уменьшает погрешность, однако из-за неясного поведения f(n+1)(x) возможны проблемы. Поэтому на практике для повышения точности целесообразно уменьшать шаг и выбирать специальное расположение узлов (например, сгущая их к концам отрезка). При этом, как правило, стараются использовать многочлены малой степени.

3.4.Задания для самостоятельной работы

Построить интерполяционный многочлен по заданным таблицам а) в форме Лагранжа; б) в форме Ньютона.

8

3.5.Примеры процедур в среде Maple

3.5.1.Построение интерполяционного многочлена Лагранжа

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

>restart;

>f:=x-> ln(x)-(sin(x))ˆ 2-exp(x); # аналитический вид функции

>n:=5; # количество шагов

>x0:=1; # первый узел интерполирования

>sh:=0.2; # шаг интерполирования

# задание узлов интерполирования и значений функции в этих узлах > for i from 0 to n do

9

x[i]:=x0+sh*i; y[i]:=f(x[i]); end do;

# Процедура создания интерполяционного многочлена в форме Лагран-

жа

> lagr:=proc(n,x,y,xx)

#n количество узлов интерполяции (степень интерполяционного многочлена)

#x узлы интерполяции

#y значения функции в узлах интерполяции

#xx неизвестная переменная в интерполяционном многочлене local i,j,s,sl;

#i, j переменные циклов

#sl слагаемое в интерполяционном многочлене

#s переменная, для накопления суммы слагаемых (многочлен Лагранжа)

s:=0;

for i from 1 to n do sl:=y[i]; for j from 1 to n do

#получение слагаемых

if (i<>j) then sl:=sl*(xx-x[j])/(x[i]-x[j]); end if; end do;

# накопление всех слагаемых образование многочлена Лагранжа s:=s+sl;

end do; return s; end proc;

> poll:=z-> lagr(n,x,y,z);

# сравнение функции с построенным интерполяционным многочленом

> plot([f(x),poll(x)],x=0..2);

3.5.2.Построение интерполяционного многочлена Ньютона

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

> restart;

#представление функции в аналитическом виде > yf :=x->sin(x)*ln(x);

#количество шагов, первый узел и шаг интерполирования > N := 20: x0 := 1: h := 0.2:

10