Вычислит.матем_пособие

y( 1 )	Ay( 0 ) ,
y( 2 )	А Аy( 0 )
. . . . .
y( m )	А Аm 1 y
y( m 1 )	A Am y

A2 y( 0 ) ,

. .

Am y, Am 1 y.

3) выбирают y( m )	Am y и y( m 1 )		Am 1 y , тогда
	lim	yi( m 1 )		или 1	yi( m 1 )
1		m			( m ) ,
	n
		yi			yi

где yi – соответствующие координаты векторов y(m+1) и y(m).

Возникает вопрос выбора начального вектора у(0). При неудачном выборе можем не получить значения нужного корня, или же предела может не существовать. Этот факт при вычислении можно заметить по прыгающим значениям этого отношения, следовательно, нужно изменить у(0). В качестве первого собственного вектора можно взять вектор у(n+1) и пронормировать его.

Пример. Найти наибольшее по модулю собственное значение и соответствующий ему собственный вектор матрицы А

3 1 0 A 1 2 2 0 1 1

1

1) Выбираем начальный вектор y(0) 1 .

1

2) Вычисляем последовательно векторы y(1), y(2), …, y(10). Вычисления помещаем в таблицу 2.

Таблица 2 – Вычисление векторов y(n+1)

y(0)	А*y(0)	А2*y(0)	А3*y(0)	……..	А9*y(0)	А10* y(0)
1	4	17	69		243569	941370
1	5	18	67		210663	812585
1	2	7	25		73845	284508

41

3) Вычисляем отношения координат векторов yi(10 )и yi( 9 )

(1) y1(10 )			3.865;		( 2 )	y2(10 )	3.857;		( 3 )				y3(10 )		3.853.
1	y( 9 )				1	y( 9 )			1				y( 9 )
	1					2								3
4) Вычисляем λ1		как среднее арифметическое							(1 )	,	( 2 )		,	( 3 )
									1		1			1
					(1)	(2)	(3)
					1	1	1	3,858.
		1				3

5) Определим соответствующий числу λ1 собственный вектор:

941370

y( 10 ) A( 10 ) y( 0 )

812585 .

284508

Нормируем y(10), разделив на длину вектора

y(10 )	9413702 8125852 2845082 1.28* 106
	3

0.74

получим вектор x( 1 )

0.64 .

0.22

Далее можем определить второе собственное число

	yi( n 1)	1 yi( n )
2	yi( n 1)	1 yi( n 1) ,

где i=1,2,…,n.

При вычислении собственных чисел подобным образом, будет накапливается ошибка. Данная методика позволяет приближенно оценить собственные значения матрицы.

42

5 Задача приближения функции

Постановка задачи. Пусть на отрезке [a,b] задана функция у= f(x) своими n+1 значениями y0 f (x0 ),..., yn f (xn ) , в точках x0 ,x1 ..., xn .

Допустим, что вид функции f(x) неизвестен. На практике часто встречается задача вычисления значений функции у= f(x) в точках х,

отличных от x0 ,..., xn . Кроме того, в некоторых случаях, не смотря на то,

что аналитическое выражение у=f(x) известно, оно может быть слишком громоздким и неудобным для математических преобразований (например, специальные функции). Кроме этого значения yi могут содержать ошибки эксперимента.

Определение. Точки x0 ,..., xn называются узлами интерполяции.

Требуется найти аналитическое выражение функции F(x), совпадающей в узлах интерполяции со значениями данной функции, т.е.

F( x0 ) y0 ,F( x1 ) y1 ,..., F( xn ) yn .

Определение. Процесс вычисления значений функции F(x) в точках

отличных	от узлов	интерполирования называется интерполированием
функции	f(x). Если	х х0 ,xn , то задача вычисления приближенного

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

Геометрически задача интерполирования функции одной переменной означает построение кривой, проходящей через заданные точки ( x0 , y0 ),( x1 , y1 ),..., ( xn , yn ) (рисунок 5). То есть задача в такой постановке может

иметь бесконечное число решений.

у

x 0 x 1

x 2

x 3 х

Рисунок 5 - Геометрическая иллюстрация задачи интерполирования функции

Задача становится однозначной, если в качестве F(x) выбрать многочлен степени не выше n, такой что:

43

F n (x 0 )=y 0 , F n (x 1 )=y 1 ,..., F n (x n )=y n .

Определение. Многочлен F n (x), отвечающий вышеназванным условиям, называется интерполяционным многочленом.

Определение. Когда многочлен F(x) выбирается в классе степенных функций, то интерполяция называется параболической.

Знание свойств функции f позволяет осознанно выбирать класс G аппроксимирующих функций. Широко используется класс функций вида

Фm ( x )	c0 0 ( x ) c1 1( x )	... cm m ( x ),	(5.1)
являющихся линейными	комбинациями	некоторых базисных	функций

0 (x),..., m(x). Будем искать приближающую функцию в виде многочлена степени m, с коэффициентами с 0 ,...,с m , которые находятся в зависимости от вида приближения. Функцию Фm(х) называют обобщенным многочленом по системе функций 0(х), 1(х),…, m(х), а число m – его степенью. Назовем обобщенный многочлен Фm(х) интерполяционным, если он удовлетворяет условию

Фm(хi)=yi, (i=0,1,…,n).	(5.2)
Покажем, что условие (5.2) позволяет найти	приближающую
функцию единственным образом

c0	0	( x0 )	c1	1( x0 )	... cm m ( x0 )			y0
c0	0	( x1 )	c1	1( x1 )	...	cm	m ( x1 )	y1
								(5.3)
. . . . . . . . . . .
c0	0	( xn )	c1	1( xn )	...	cm	m ( xn )	yn ,

Система (5.3) есть система линейных алгебраических уравнений относительно коэффициентов с0,с1,…,сm.

Эта система n линейных уравнений имеет единственное решение, если выполняется условие m=n и определитель квадратной матрицы Р

	0	( x0 ), 1( x0 ),...,	m ( x0 )
det P	0	( x1 ), 1( x1 ),...,	m ( x1 )	0.
	. . . . . . . .
	0	( xn ), 1( xn ),...,	m ( xn )

44

0 (x),...,

Определение. Система функций m(x), линейно независимая в точках х0,х1,…,хn, которые попарно различны и выписанный выше определитель не равен нулю, называется Чебышевской системой функций. Если мы имеем такую систему, то можно утверждать, что существует единственный для данной системы функций интерполяционный многочлен Фm(х), коэффициенты которого определяются единственным образом из системы (5.3).

Пример. При m n система функций 1,х,х2,…,хm линейно независима в точках х0,х1,…,хn, если они попарно различны.

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

Рассмотрим случай, когда узлы интерполирования не равноотстоят друг от друга на отрезке [a,b]. Тогда шаг h = xi+1- x i const. Задача имеет единственное решение, если в качестве интерполирующей функции F(x) взять алгебраический многочлен

Ln(x )=a0+a1 x+a2 x2+…+anxn,

где а i неизвестные постоянные коэффициенты.

Используя условие (5.2) можем записать

L( x0 ) y0 , L( x1 ) y1 ,..., L( xn ) yn .

(5.4)

Запишем это в виде:

a	0	a x	0	a	x2	...	a	xn	y	0
		1		12	2		1n	n
a	0	a x	0	a	x2	...	a	xn	y
		1		12	2		1n	n	1		(5.5)
. . . . . . . . . .
a	0	a x	0	a	x2	...	a	xn	y	n	.
		1		12	2		1n	n

Эта система однозначно разрешима, так как система функций 1,х,х2,…,хn линейно независима в точках х0,х1,…,хn. Однозначная разрешимость следует из того факта, что определитель этой системы (определитель Вандермонда)

45

	1	x	0	x 2	...	x n
				0		0
	1	x		x 2	...	x n
			1	1		1	(xi x j ) 0.
	... ...			...	...	...
							0 j ,i n
	1	x	n	x 2	...	x n
				n		n

Без вывода приведем одну из форм записи интерполяционного многочлена Лагранжа

Ln ( x ) y0

( x

x1 )...( x

xn )

y1

( x

x0 )( x

x2 )...( x

xn )

...

( x

0

x )...( x

0

x

n

)

( x

x

0

)( x

x

2

)...( x

x

n

)

1

1

1

1

(5.6)

( x

x0

)...( x

xn 1

)

... yn

.

( xn

x0

)...( xn

xn 1 )

Определение. Этот многочлен называется интерполяционным многочленом Лагранжа и сокращенно записывается в виде

n

( x

x0 )( x

x1 )...( x

xi

1 )( x

xi 1 )...( x

xn )

L n (x) =

yi

.

(5.7)

( xi

x0 )( xi

x1 )...( xi

xi

1 )( xi

xi 1 )...( xi

xn )

i o

5.1.1 Оценка погрешности интерполяционного многочлена

Оценить погрешность интерполяционной формулы Лагранжа можно только тогда, когда известно аналитическое выражение интерполируемой функции, а точнее, если известно максимальное значение (n+1)-ой производной функции f(x) на отрезке [a,b]. Пусть

|R n (x)| =| f(x) - L n (x)|,

где R n (x) –погрешность;

f(x)- точное значение функции в точке х;

L n (x)- приближенное значение, полученное по полиному Лагранжа.

Если обозначить через M n 1	= max	f (n 1) (x)	, где x [a,b], причем х0=а,
	[ a,b ]

х n = b, то

	Rn	(x)			Mn	1			(x x0 )(x x1)....(x xn )		.
max					(n	1)!
[ a,b ]

46

Рассмотрим теперь случай с равноотстоящими узлами. Тогда интерполяционная формула Лагранжа заметно упрощается. В этом случае шаг h=xi+1-xi=const. Введем в рассмотрение многочлен вида

Qi(x)=

( x x0 )( x

x1 )...( x

xi 1 )...( x

xn

)

.

( x

i

x

0

)( x

i

x )...( x

i

x

i 1

)...( x

i

x

n

)

1

Введем обозначение q=

x

x0

, отсюда следует, что

h

x x0 = q h ,

x x1 = q h h h (q 1) ,

. . . . . . . . . . .

x xi = q h i h h ( q i ),

x xn = q h n h h ( q n ).

Тогда многочлен Qi примет вид

q( q

1)

[ q

( i

1)]

[ q

( i

1)]...( q

n ) hn

Qi(x)= yi

.

i

h( i

1)

h...h(

h )...[

( n i )

h ]

Произведя простейшие преобразования, получим выражение вида:

Q		(q)=	q ( q 1)...( q n ) ( 1)n i		= ( 1)	n i Cni			q( q 1)...( q n )		,
	i			( q i ) i! ( n i )!			q i		n!
где Cni		n!		.
	i! ( n i )!

Тогда интерполяционный многочлен Лагранжа для равноотстоящих узлов имеет вид:

		q( q 1)...( q n )		n			i
L n	(x)=				( 1)	n i	Cn	yi .
		n!		i 0			q i

На практике часто пользуются линейной и квадратичной интерполяцией. В этом случае формула Лагранжа имеет вид

L1(x)= y0	( x x0 )				y1	( x	x0 )
	( x		x )			( x	x		)	- при линейной интерполяции;
		0	1		1			0

47

L2(x)= y0	( x x1 )( x				x2 )				y1	( x	x0 )( x			x2 )				y2	( x x0 )( x x1 )
	( x	0	x	)( x	0	x	2	)		( x	x	0	)( x	x	2	)			( x	2	x	0	)( x	2	x )	-
			1						1				1												1

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

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

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

узлов

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

Определение. Конечной разностью перового порядка называется разность между значениями функции в соседних узлах интерполяции. Тогда конечные разности в точках х0,х1,…,хn-1

	y0	y1 y0	f ( x1 ) f ( x0 )	f ( x0 ),
y1	y2	y1	f ( x2 ) f ( x1 )	f ( x1 ),
		. . . . . . .
yn 1	yn	yn 1	f ( xn ) f ( xn 1 )	f ( xn 1 ).
Конечная разность второго			порядка имеет вид:

2 y	i	y	i 1	y	i	,

. . . . . .

n y	i	(	n 1 y	i	).

Рассмотрим некоторые свойства конечных разностей. Вторая конечная разность в точке хi

	2 y	i	f ( x	x ) f ( x	x )	f ( x	) f ( x )
			i 1	i		i 1		i	.
	f ( xi 2 ) 2 f ( xi 1 ) f ( xi ) yi 2					2 yi 1		yi

Аналогично третья конечная разность

48

3 yi	yi 3	3 yi 2	3 yi 1 yi .
Общее выражение для конечной разности n-го порядка имеет вид
n yi yn i C1n yn i 1	Cn2 yn	i 2	... ( 1)m Cnm yn i m ...( 1)n yi ,

а вообще, конечная разность порядка m от конечной разности порядка n

m ( n y)

m n y .

Конечные разности n-го порядка от многочлена степени n - есть величина постоянная, а конечные разности n+1-го порядка равны нулю.

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

Pn ( x0 ) y0 ,..., Pn ( xn ) yn .

В силу единственности многочлена степени n, построенного по n+1 значениям функции f(x) многочлен Pn (x) , в конечном счете, совпадает с многочленом Лагранжа. Найдем этот многочлен в виде:

Pn ( x ) a0

a1

( x x0 )

a2 ( x x0 )( x

x1 ) ...

an ( x x0 )...( x

xn 1 ),

где аi(i=0,1,…, n) – неизвестные коэффициенты. Для нахождения а0

положим

x x0 . Тогда P(x0 )

a0 , отсюда а0=у0.

Для

вычисления a1

рассмотрим

первую

конечную

разность для

многочлена Pn(x) в точке х.

Pn ( x )

Pn ( x

h )

Pn ( x )

a0

a1( x

x0

h )

... an ( x

x0 h ) ...( x xn 1 h )

a0 a1( x

x0 )

... an ( x

x0 )...( x

xn 1 ) .

В результате преобразований получим

Pn ( x ) h

a1

2ha2 ( x

x0 ) ...

n han ( x

x0 )...( x

xn 1 ).

Вычислим первую конечную разность многочлена Pn(x) в точке х0

Pn ( x0 )

a1

h , но

Pn ( x0 )

f ( x1 )

f ( x0 )

y1

y0

y0 , откуда a1

y0

.

h

49

Чтобы определить коэффициент а2, составим конечную разность

	второго	порядка	2 P ( x )	P ( x h )			P ( x ).	Отсюда	после
			n		n		n
	преобразования получим		a2	2 y0		. Вычисляя конечные разности более
				2! h	2

высоких порядков и полагая х=х0, придем к общей формуле для определения

коэффициентов: a			i y	0		(i=0,1,2,…,n).
	i
		i! hi
Подставим значения							ai	в многочлен, в результате получим первую
интерполяционную формулу Ньютона:
pn ( x ) y0			y0				( x	x0 ) ...	n y0	( x x0 )...( x xn 1 ).
			1! h						n! hn

Первую интерполяционную формулу можно записать в том виде, в котором ее удобнее использовать для интерполирования в начале таблицы. Для этого введем переменную q=(x-x0)/h, где h-шаг интерполирования, а q- число шагов. Тогда первая формула примет вид

P ( x )	y		q y		q( q	1)		2 y		...	q( q 1)...( q n 1)		n y		.
		0		0					0					0
n					2!						n!

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

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

Pn ( x ) a0 a1( x	xn ) a2 ( x	xn )( x	xn 1 ) ...		an ( x	xn )...( x x1 ).
Неизвестные коэффициенты а0,а1,…,аn				подберем		так,	чтобы были
выполнены равенства	Pn ( x0 )	y0 , Pn ( x1 )		y1 ,..., Pn ( xn )			yn . Для этого
необходимо и достаточно, чтобы		i Pn (xn	i )	i yn i (i=0,1,…,n).
В случае, если положить			x	xn ,	то сразу		определяется
коэффициент а0

Pn (x) yn a0 .

Из выражения для первой конечной разности найдем a1 :

50