ChM1

xi 1, xi 1

1. Если максимальная степень интерполяционного многочлена

m=n, то это	глобальная интерполяция, потому что один многочлен
( )	используется для интерполяции

функции f(x) на всем рассматриваемом интервале изменения аргумента x.

2. Если максимальная степень интерполяционного многочлена m<n, то это локальная или кусочная интерполяция, при этом интерполяционные многочлены могут строиться отдельно для разных частей рассматриваемого интервала изменения аргумента x.

3. Если максимальная степень интерполяционного многочлена m>n, то это экстраполяция, интерполяционный многочлен используется для аппроксимации функции вне рассматриваемого отрезка.

Самый простой и наиболее часто используемый вид локальной интерполяции – это линейная интерполяция. Суть ее в том, что заданные соседние точки (xi, yi) (i=0,1,…,n) соединяются отрезками, и

функция f(x) приближается ломаной с вершинами в данных точках.

Еще один вид наиболее простой и достаточно часто используемой интерполяции это квадратичная интерполяция. Она состоит в

следующем: в качестве интерполяционной функции на отрезке принимается квадратный трехчлен. Уравнение квадратного трехчлена:

y a x2 b x c

x

x x

. Коэффициенты

a , b , c

определяют из

i

i

i

i 1

i 1

i i i

уравнений

–

условий

прохождения параболы

через три

точки

(xi 1, yi 1 ), (xi , yi ), (xi 1, yi 1 ).

эти

условия

можно

записать

так:

a x

2

b x

c y

,

i i

1

i

i 1

i

i 1

2

bi xi

ci yi ,

ai xi

2

bi xi 1

ci

yi 1.

ai xi 1

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

51

(x) a0 a1x a2 x2 ... an xn

Вначале рассмотрим случай глобальной интерполяции, т.е.

построение интерполяционного многочлена, единого для всего отрезка

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

Можно искать искомый многочлен в следующем виде: (4.1).

Из условий равенства значений этого многочлена в узлах xi

соответствующим заданным табличным значениям yi получим систему уравнений для нахождения коэффициентов ai :

a	0		a x	0	a	x	2	... a	n	x n y				,
			1		2	0					0		0
			a x		a x		2	... a		x	n		y ,
a															(4.2).
		0	1	1	2	1			n	1			1
			............................,
a	0		a x	n	a	x	2	... a	n	x		n y		.
			1		2	n					n		n

Далее решив эту систему, найдем коэффициенты многочлена (4.1).

Но данный путь при большом числе узлов требует большого объёма вычислений.

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

Ln (x) y0l0 (x) y1l1 (x) ... ynln (x) (4.3).

При этом нужно потребовать чтобы выполнялось условие: каждый многочлен li (x) должен обращаться в нуль во всех узлах интерполяции,

за исключением i-ого, где он должен равняться единице. Этим условиям отвечает многочлен вида:

	l0 (x)	(x x1 )(x x2 )...(x xn )		(4.4),
		(x0 x1 )(x0	x2 )...(x0 xn )
	действительно, при x x0	l0(x0 ) 1	и при	x x1, x2 ,..., xn числитель

выражения (4.4) обращается в нуль. По аналогии (4.4) можно получить:

52

l1 (x)

(x x0 )(x x2 )...

(x xn )

,

(x1

x0 )(x1 x2 )

(x1 xn )

l2 (x)

(x x0 )(x x1 )(x x3 )...

(x xn )

,

(x2

x0 )(x2 x1 )(x2 x3 )

(x2 xn )

..........

..........

..........

..........

..........

..........

,

(4.5).

li (x)

(x x0 )(x x1 )...

(x xi 1 )(x xi 1 )...

(x xn )

,

(xi

x0 )(xi x1 )

(xi xi 1 )(xi xi 1 )

(xi xn )

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

Подставив в (3) выражения (4) и (5), получим

n

(x x0 )(x x1 )

(x xi 1)(x xi 1 )

(x xn )

Ln (x) yi

(4.6).

(x x )(x x )

(x x

)(x x

)

(x x )

i 0

i 1

i

0

i

1

i

i

i 1

i

n

Формула (4.6) называется интерполяционным многочленом

Лагранжа.

Из формулы (4.6) можно получить выражения для линейной и

квадратичной интерполяции:

n=1:

L (x) y

x x1

y

x x0

–

уравнение прямой,

проходящей через

x

1

0

x

1

x x

0

1

1

0

две точки (x0 , y0 );(x1, y1 ) ;

L2 (x)

(x x1 )(x x2 )

y1

(x x0 )(x x2 )

y2

(x x0 )(x x1 )

n=2:

y0

–

(x

x )(x

x )

(x x )(x

x )

(x x )(x

2

x )

0

1

0

2

1

0

1

2

2

0

1

уравнение параболы, проходящей через три точки (x0 , y0 );(x1, y1 );(x2 , y2 ) .

Пример 1: для функции, заданной таблицей, построить

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

x	y
0	0
1/6	1/2
1/2	1

Решение: n=2, применяя формулу (4.6), получим:

53

				(x 1			6	)(x						1	)			1						(x 0)(x 1			2	)			(x 0)(x 1				6	)
L (x)	0													2															1									,
2				(0		1	6)(0							1			2					(	1		1		1			(	1	2 0)(	1		1		6)
														2)										6 0)(	6			2)					2
		1			x(x		1			)				x(x			1			)
L (x)								2									6					,
2	2					1									1
						18										6
L (x)		18(x2					1		2		x)			6(x2						1				x),
																						6
2				2
L (x) 9x2						9		x 6x2 x,
2						2
L (x) 3x2 7								x.
2						2

Пример 2: дана таблица значений функции y f (x)

x	y
321.0	2.50651
322.8	2.50893
324.2	2.51081
325.0	2.51188

Вычислить значение f(323.5).

Решение: положим x=323.5; n=3. тогда по формуле (4.6) будем иметь:

	f (323.5)		(323.5 322.8)(323.5 324.2)(323.5 325)					2.50621
			(321 322.8)(321 324.2)(321 325)
	(323.5	321)(323.5 324.2)(323.5 325)			2.50893
	(322.8	321)(322.8 324.2)(322.8 325)
	(323.5 321)(323.5 322.8)(323.5 325)				2.51081
	(324.2 321)(324.2 322.8)(324.2 325)
	(323.5	321)(323.5 322.8)(323.5 324.2)				2.51188
	(325 321)(325 322.8)(325 324.2)

0.07996 1.18794 1.83897 0.43708 2.50987.

4.3Интерполяционные многочлены Ньютона

Теперь рассмотрим случай равноотстоящих узлов, т.е. шаг

постоянный: xi-xi-1=h – const (i=1,2,…n).

54

Прежде введем понятия конечных разностей. Допустим, что нам известны значения функций в узлах xi: yi=f(xi). Составим следующие разности значений функции:

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).

Эти значения называются первыми конечными разностями

функции.

Можно составить конечные разности второго порядка:

2 y0 y1 y0 ( y2 y1 ) ( y1 y0 ) y2 2 y1 y0 ,2 y1 y2 y1 ( y3 y2 ) ( y2 y1) y3 2 y2 y1,....

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

3 y0 2 y1 2 y0 ( y2 y1 ) ( y1 y0 ) (( y3 y2 ) ( y2 y1 )) (( y2 y1 ) ( y1 y0 ))y3 2 y2 y1 y2 2 y1 y0 y3 3y2 3y1 y0 .

Аналогично составляются разности любого порядка k:

k y0 yk kyk 1 k(k 1) yk 2 ... ( 1)k y0 (4.7) 2!

Эту формулу можно записать и для значения разности в узле xi:

k yi yk i kyk i 1 k(k 1) yk i 2 ... ( 1)k yi .

2!

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

N(x) a0 a1 (x x0 ) a2 (x x0 )(x x1 ) ... an (x x0 )(x x1 )...(x xn 1 ) (4.8)

График многочлена должен проходить через заданные узлы, т.е.

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 .

Из полученных выше соотношений найдем коэффициенты a0 , a1, a3 :

55

x1 x x2

a y , a

y1 a0

y1 y0

y0 ,

0

0

1

h

h

h

a

y2 2a1h a0

y2 2y0 y0

y2 2( y1 y0 ) y0

y2 2 y1 2 y0 y0

2

2h2

2h2

2h2

2h2

y

2

2 y

y

2 y

1

0

0 .

2h2

2h2

Аналогичным образом можно найти и другие коэффициенты.

Общая формула будет иметь вид:

ak k y0 , k 0,1,..., n. (4.9) k!hk

Подставляя выражения (4.9) в формулу (4.8), получим следующий вид интерполяционного многочлена Ньютона:

N (x) y		y	(x x )	2 y	(x x )(x x ) ...		n y	(x x )(x x )...(x x			)
		0		0			0
0		h	0	2h2	0	1	n!hn	0	1	n 1

(4.10)

Формулу (4.10) чаще записывают в ином

переменная t

(x x0 )

, и тогда получаем:

h

x x th,

x x1

x x0 h

x0 th x0 h

h(t 1)

0

h

h

h

h

x x2

t 2,...,

x xn 1

t n 1.

h

h

виде. Для этого вводится

t 1,

Сучетом полученных соотношений формулу (4.10) можно записать

ввиде:

N (x	th) y	t y		t(t 1)	2 y	...	t(t 1)...(t n 1)	n y	(4.11)
0	0	0	2		0		n!	0

С точки зрения повышения точности расчетов, лучше ограничиться случаем t<1, т.е. использовать формулу (4.11) для случая x0 x x1 . Для

других значений аргумента, например для случая вместо x0

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

N (x	th) y	t y		t(t 1)	2 y	...	t(t 1)...(t n 1)	n y ,i 0,1,... (4.12)
i	i	i	2		i		n!	i

56

Данное выражение называется первым интерполяционным

многочленом Ньютона для интерполирования слева направо.
Первым	интерполяционным многочленом				Ньютона (4.12) можно
воспользоваться для		вычисления		значений	функции	в точках
только левой	половины	рассматриваемого отрезка, потому что
конечные	разности	k y	вычисляются		через	значения
		i
функции yi , yi 1,..., yi k , и поэтому			мы	не можем	вычислить	разности

высших порядков при больших значениях i (k≤n-i).

Например, при i=n-3 в (4.12) можно учесть только y, 2 y, 3 y .

Для правой половины рассматриваемого отрезка разности лучше

вычислять

справа налево. В

этом случае t

(x xn )

,

т.е. t<0, и

h

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

N (x

th) y t y

t(t 1)

2 y

...

t(t 1)...(t n 1)

n y

(4.13)

n 1

n

n

2

n 2

n!

0

Полученная выше формула называется вторым интерполяционным многочленом Ньютона для интерполирования справа налево.

Пример: приняв шаг h=0.05, построить на отрезке [3.5;3.6]

интерполяционный полином Ньютона для функции, заданной таблицей

x		3.50			3.55			3.60		3.65		3.70
y		33.115			34.813			36.598		38.475		40.447
Решение: составим таблицу разностей
x			y			y				2 y		3 y
3.50			33.115			1.698				0.087		0.005
3.55			34.813			1.785				0.092		0.003
3.60			36.598			1.877				0.095
3.65			38.475			1.972
3.70			40.447
В	формуле (4.11)				полагаем			n=3. Приняв x0 3.50; y0 33.115 ,

получим:

57

N	(x) 33.115 1.698t 0.087	t(t 1)	0.005	t(t 1)(t 2)	или
3	2		6

N3 (x) 33.115 1.698t 0.0435t(t 1) 0.00083t(t 1)(t 2) ,

где t x 3.50 . 0.05

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

Согласно условию интерполяции график интерполяционного многочлена y=φ(x) проходит через заданные точки, т.е. значения многочлена и данной функции y=f(x) совпадают в узлах. В общем случае в точках, отличных от узлов интерполяции точная функция и интерполирующая не совпадают, т.е. R(x) f (x) (x) 0 . Эта разность является погрешностью интерполяции и называется остаточным членом интерполяционной формулы.

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

вид:

RL (x) (x x0 )(x x1 )...(x xn ) f (n 1) (x* ) (4.14), (n 1)!

где f (n 1) (x* ) – производная n+1-го порядка функции f(x) в некоторой

точке x x*, x* [x0 , xn ].

Остаточный член интерполяционного многочлена Ньютона можно записать в виде:

R (x)	t(t 1)...(t n)		f (n 1) (x )hn 1	, t	x x0	(4.15)
N	(n	1)!	*		h

4.5Метод наименьших квадратов

Пусть заданы точки xi , yi . Задача состоит в том, чтобы найти

приближенную	зависимость	y (x) ,	значения		которой
при x xi (i 0,1,..., n)	мало отличаются от данных yi .
Приближенная	зависимость,	полученная		на	основании

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

58

						(x, a0 ,a1,..., am ) – приближенная зависимость, ai				– неизвестные
постоянные параметры.
i f (xi ) (xi ) – отклонения.
					n
Q i2 – сумма квадратов отклонений.
		i 0
Q – должна быть минимальной, из этого условия находим a0 ,...,ai ,... .
						Для этого продифференцируем каждую их переменных:
Q						0,
	a
		0
	Q				0,
	a1
............,
	Q
						0.
	am
						Решая эту систему, находим коэффициенты ai			. Затем подставляем
их в (x) и строим приближенную зависимость.
						Запишем (x)	в следующем виде: (x) a	a x a x2		... a xm .
							0	1	2	m
						n
Q ((a0 a1xi a2 xi							2 ... am xi m ) yi )2
			i 0
							(xi )
	Q					n
						2 ((a0 a1xi a2 xi2 ... am xim ) yi ) *1,
	a
		0				i 0
Q						n
	a1					2 ((a0 a1xi a2 xi2 ... am xim ) yi ) * xi ,
						i 0
............,
Q						n
						2 ((a0 a1xi a2 xi2 ... am xim ) yi ) * xim .
	am
						i 0

Приравнивая к нулю, раскрываем скобки:

59

n

n

n

n

a0 (n 1) a1 xi a2 xi2 ...

am xim yi ,

i 0

i 0

i 0

i 0

n

n

n

n

n

a0 xi a1 xi

2

a2 xi3

...

am xim 1 yi xi ,

i 0

i 0

i 0

i 0

i 0

..........

..........

..........

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

..........

..........

..,

n

n

n

n

n

0

i

1

xi m 1

a

2

i

a

m i

i i

a

xm a

xm 2

x2m

y xm ,

i 0

i 0

i 0

i 0

i 0

Решая данную систему, получим коэффициенты a0 , a1,..., am .

Пример:

x	0	2	3	4
y	3	5	2	1

По данным точкам строим приближенную зависимость

Рис 4.2 Приближенная зависимость

n=3 – количество точек, m=2 – степень приближенной зависимости.

a0 a1x a2 x2

4a0 9a1 29a2 11,9a0 29a1 99a2 20,29a0 99a1 353a2 54.

xi 2 3 4 9

xi2 4 9 16 29

xi3 8 27 64 99

xi4 16 81 256 353

a0

Решаем и получаем: a1

a2 y 3.127 1.736x 0.59x2

yi 11

yi xi 20

yi xi2 54

3.127

1.736

0.59

60