part2 / vm

	x(k ) , x(k 1)												2k 1						c e	1			η(k ) , c e														1	η(k 1)
				c 2														1	1														1
	2k 1										e			, e		1		c e				, η(k 1) c η(k ) , e																										1			η(k ) , η(k 1)
	1				1							1							1	1																	1
																																															2				2k 1
	2k 1			c 2							η(k ) , η(k 1)												2k 1 c 2															O																,
	1				1																									1						1											1
поскольку ||e1||=1, вектор η(k) ортогонален вектору e1																																																	при любом k=1, 2,… и
																							2						2				2k 1																				n		2k 1
							η(k ) , η(k 1)												c																		c2																	.
																						2					1																					n
																																																				1
Аналогично получаем
																																														2				2k 2
												x(k 1) , x(k 1)											2k 2 c													2		O																.
																												1							1											1
Следовательно,
												x(k ) , x(k 1)																									2			2k 1
		(k )																													O																,
																												1
	1											x(k 1) , x(k 1)																									1
																																														2				k
			x(k )						x(k ) , x(k ) 1/ 2																										k c			O															,		(2.57)
																															1					1										1
											x(k )							sign								k e1
		e(k )																																	r (k ) ,
																								1
	1										x(k )																			1
															k										-1, x 0,
где e11 signc1 e1 ,	r(k )	O										2			, signx
									1																		1, x 0.

Таким образом, при условии (2.54) итерационный процесс (2.55) позволяет найти с любой точностью максимальное по модулю собственное значение λ1

(ибо (1k ) 1 при k→∞) и соответствующий ему собственный вектор e1, так как

||r(k)|| →0 при k→∞.

Рассмотрим некоторые замечания:

1. Если |λ1|>1, то ||x(k)||→∞, а если |λ1|<1, то ||x(k)||→0 при k→∞. То и другое явление при счете на машине нежелательно (в одном случае произойдет переполнение, в другом – появляется машинный ноль). Поэтому следует итерации вести по формулам

41

e(0)

x(0)

,

1

x(0)

x(k ) Ae1(k 1) ,

(1k )

x(k ) , e1(k 1) ,

e1(k )

x(k )

,

x(k )

не имеющим указанного недостатка и дающим тот же результат (те же e1(k ) , (1k ) ),

что и формулы (2.55), (2.56).

2. Если при выборе x(0) будет выполнено c1=0, то за счет ошибок округлений через несколько итераций появится ненулевая компонента,

отвечающая e1. Тогда с некоторым запаздыванием итерационный процесс выйдет на первое собственное значение.

Рассмотрим теперь задачи, решение которых сводится к отысканию максимального по модулю собственного значения некоторой матрицы B=g(A),

такой, что это собственное значение соответствует отыскиваемому собственному значению матрицы A. В качестве такой матрицы B часто берется матрица вида

B=a0E+a1A+a2A2+…+ amAm,

(2.58)

собственные числа λi(B) которой, согласно (2.51), связаны с собственными числами λi(A) матрицы A соотношением

	B a	0	a	A a	2	A a	m A ,	i 1, 2, , n. (2.59)
i			1 i	2	i	m	i

Перейдем к решению конкретных задач.

Нахождение минимального и максимального собственного значения

Пусть найдено наибольшее по модулю собственное значение λ1 матрицы A.

Возможны два случая:

1. λ1>0, т. е. λ1= λmax(A). Для нахождения λmin(A) возьмем матрицу

B= λ1E – A,

собственными значениями которой являются числа λi(B) = λ1– λi(A)≥0 для

любого i=1, 2, …, n. Тогда λmax(B) = λ1– λmin(A). Причем max	B max		i B		в
	1 i n

силу неотрицательности спектра матрицы B. Определив максимальное по модулю значение λmax(B) итерационным методом (2.57), находим минимальное собственное значение матрицы A:

42

λmin(A) = λ1– λmax(B).

2. λ1<0, т. е. λ1= λmin(A). В этом случае, проведя аналогичные рассуждения для матрицы B=A – λ1E, максимальное собственное значение матрицы A

находим по формуле

λmax(A) = λ1+ λmax(B).

Нахождение расстояния ρ0 от заданной точки λ=λ0 до ближайшего собственного значения матрицы. Рассмотрим случай, представляющий наибольший интерес:

min i A 0	max i A .
1 i n	1 i n

Обозначим

0 min i A 0 ,

1 i n

l max max i A 0

1 i n

(2.60)

, 0 min i A .

1 i n

Докажем, что

0 l 1 B ,

где B – максимальное по модулю собственное значение матрицы

B E l12 A 0 E 2 ,

где E – единичная матрица. Поскольку матрица B – матрица вида (2.58), то,

учитывая (2.59) и (2.60), имеем для любого i=1, 2 ,…, n

			i B 1			1		i A 0 2	0.
							l 2
	Отсюда
			B 1	1		* A 0 2 1				02
											,
				l 2						l 2

где λ*(A) – ближайшее к λ0 собственное значение матрицы A. Следовательно,

расстояние ρ0 от произвольной точки λ0 спектра матрицы A до ближайшего собственного значения матрицы равно

0 l 1 B .

43

Замечание. Если λ0=0, то ρ0 – это расстояние от нуля до ближайшего собственного значения матрицы A, т.е. ρ0=| λn|, где λn - минимальное по модулю собственное значение матрицы A.

44

f (x) C a,b .

3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ ВЫСШИХ ПОРЯДКОВ И ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ.

В этом разделе мы рассмотрим некоторые методы численного решения

нелинейного скалярного уравнения вида

f(x)=0, (3.1)

где f (x) – заданная функция действительного аргумента x, в частности, f (x)

может быть многочленом степени n от x.

Будем считать f (x) непрерывной функцией на отрезке a,b D (a, b –

могут быть ±∞). Всякое число x* из D такое, что f(x*)=0,

называется корнем уравнения (3.1) или нулем функции f(x). Пусть f(x) – гладкая функция (т.е. функция, имеющая достаточное число производных). Число x*

называется корнем k–кратности, если при x=x* вместе с функцией f(x) в нуль обращаются все ее производные до (k–1) – й включительно:

f x* f x* f (k 1) (x* ) 0, f (k ) (x* ) 0.

Однократный корень называется простым.

Алгебраическим уравнением с одним неизвестным называется уравнение

вида:

xn a	n 1	xn 1 a x a	0	0,	(3.2)
		1

где n – целое неотрицательное число, называемое степенью уравнения; a0, a1, … ,an–1 – коэффициенты уравнения; x – неизвестное, которое следует определить.

Известно, что алгебраическое уравнение (3.2) степени n имеет ровно n

корней, если любой k – кратный корень считать столько раз, какова его

кратность.

Для нелинейного уравнения справедливы утверждения:

Пусть Если f(a)∙f(b)<0, то между a и b имеется нечетное число

корней. Если f(a)∙f(b)>0, то между a и b существует четное число корней или их нет вовсе.

45

f (x)

Если f (x) C1[a,b] , f(a)∙f(b)<0 и не меняет знака на [a,b], то между a и b

содержится ровно один корень уравнения.

Если уравнение f(x)=0 не является алгебраическим, то уравнение (3.1)

называется трансцендентным. Например,

f (x) tg x 1x 0.

Трансцендентное уравнение иногда можно свести к алгебраическому нелинейному уравнению.

При отыскании корня уравнения (3.1) решаем две задачи.

Задача 1. Отделение корней, т.е. отыскание достаточно малых областей, в

каждой из которых заключен один и только один корень уравнения.

Задача 2. Вычисление корней с заданной точностью.

3.1 Устойчивые решения, число обусловленности функции одной переменой.

Решение прикладных задач, как правило, начинается с создания приемлемых физических и математических моделей. Пусть есть точно поставленная задача: найти на промежутке [a,b] корень уравнения

f (x) 0, a x b. (3.3)

И пусть ищутся корни приближенного уравнения

f (x) 0, a x b, (3.4)

с указанием погрешности в исходных данных:

f (x) f (x)		,	0,	a x b. (3.5)

Рассмотрим некоторые трудности, возникающие при решении задач (3.3)–

(3.5).

1. Пусть имеется уравнение

ex=ε,

с решением x=lnε ,где ε –малое число. Ошибка в исходных данных может привести к уравнению ex=0, не имеющему конечного решения, так как не существует конечного значения x, для которого выполнено равенство ex=0.

46

2. Нетрудно убедиться, что уравнение x2–2x+1=0

имеет корни x1* 1, x2* 1, а уравнение x2–2x+1.01=0

обладает корнями x1* 1 0.1i, x2* 1 0.1i. В этом случае погрешность (ε=0.01) в

исходных данных вывела корни уравнения x2–2x+1=0 из области действительных чисел и перевела их в область комплексных чисел.

3. Уравнение

x 13 2x 16 1 0

имеет действительный корень x*=1, а уравнение

x 13 2x 16 0.99 0,

отличающееся от предыдущего лишь погрешностью в свободном члене ε=10–2

имеет действительные корни x1* 1.771561, x2* 0.531441.

Решение уравнения (3.2) называется устойчивым, если малым изменениям

в исходных данных соответствуют малые изменения в решении. Иными

словами, если f (x) f (x) при всех x [a,b], то и

x* x* ,

где x * – точное решение уравнения f x* 0 , x* – точное решение уравнения f x* 0 ; ε, δ(ε) – сколь угодно малые числа.

Рассмотрим условия, при которых за решение исходной математической модели (уравнение (3.3)) можно принять решение задачи (3.4)–(3.5). Для этого оценим разность уравнений через погрешность в исходных данных и функцию

(3.4). Справедливо равенство:

f x

f x

f

x

x

, где

[x

, x

] [a,b]

*

*

*

*

*

*

или, так как f x* 0

*

*

f x*

x

f

при f

x

0.

47

Обозначим через δf разность в точке x * функций f (x* ) f (x* ) f , т.е. δf –

вариация функций точной и приближенной в точке x * . Получим сразу, учтя то

обстоятельство, что f (x* ) 0,

x* x*

f

.

f

Тогда

x

*

x

*

f min

f x

1

.

Назовем величину

a x b

1

1

M

min

f x

(3.6)

min

f x

a x b

a x b

локальным числом обусловленности функции f(x). При этом величина, которая будет определять характер обусловленности задачи (3.4)–(3.5) есть следующая величина:

m

f

min

1

M

f

.

(3.7)

f x

a x b

Чем больше (меньше) m на отрезке [a, b], где находится корень уравнения,

тем хуже (лучше) обусловленность задачи. Так в нелинейном уравнении (п.3):

x 13 2x 16

0.99 0,

f

0.01;

1

23

x

56

x

;

f x

3

при x=1. Следовательно,

эта функция

f x x

13

2x

16

0.99 плохо

min f x 0

x x 13

2x 16

1,

а

оценка

x* x*

. Хотя эта

обусловлена для функции f

оценка носит мажорантный (оценочный) характер, она должна настораживать.

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

Займемся первой из поставленных задач при нахождении корней уравнения f(x)=0.

3.2 Отделение корней Существуют несколько различных способов отделения корней уравнения:

теорема Штурма, теорема о перемене знака функции f(x) и ее производной на

48

промежутке изменения f(x), графический способ и т.п. Часто для отыскания грубых значений корней можно построить график функции y=f(x) и найти абсциссы точек пересечения графика с осью x. Иногда удобней представить уравнение f(x)=0 в виде φ(x)=ψ(x), а затем построить графики функций y=φ(x), y=ψ(x) и найти абсциссы их точек пересечения, которые приближенно равны значениям корней. Опишем один из способов отделения корней (графический)

на примере.

Пример. Найти корни уравнения

xsin x 1

или f (x) xsin x 1 0.

Решение.

Представим функцию f(x) в виде sin x x 1 и применим графический способ нахождения корней этого уравнения (рис. 3.1).

	Корни уравнения симметричны относительно оси 0y, поэтому мы можем
рассмотреть только положительные корни. Значения						x* , x* , могут быть
						0	1
определены довольно точно, но					xn* , n , мы определить не сможем. Тем не
менее по графику ясно,				что xn*	при n>>1 близки к nπ. Все эти полученные
приближения к			корням	уравнения мы можем взять за		начальное значения
x* 0	, x* 0	, x* 0 ,	и приступить к задаче 2 уточнения корней.
0	1	2

3.3 Методы уточнения корней уравнения

49

xn* 0

После того, как корни отделены или для них получены хорошие начальные приближения xn* 0 , появляется возможность вычислить их с заданной точностью. Методы, используемые для уточнения корней уравнения f(x)=0 при

заданном на промежутке [a, b], в котором находится один единственный

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

Метод простых итераций. Для нахождения изолированного корня x*

уравнения f(x)=0, a≤x≤b заменим исходное уравнение равносильным x=φ(x) (3.8)

и организуем итерационный процесс вида

xn+1=φ(xn), n=0, 1, 2,…, (3.9)

где x0 – заданное начальное приближение.

Можно показать что, если

1)|φ΄(x)|≤α<1 при |x – x0|≤r,

2)|φ(x0) – x0|≤r(1 – α),

то начатый с x0 метод простых итераций сходится к единственному на отрезке

[x0 – r, x0+r] корню уравнения (3.8). Причем справедливы оценки погрешности

n 1, 2, , :

x* x

n

x

n

x

n 1

,

1

x* x

n

n

x

x

0

.

1

1

Выбор функции φ(x) в итерационном процессе имеет большое значение и

может быть осуществлен не единственным образом.

Предположим, что итерационным методом следует найти корни уравнения x2 – 1 =0 на отрезке [0.1; 1.1].

Если итерационную схему записать в виде xn 1 xn xn2 1, то φ(x)=x2–1 +x.

При этом φ΄(x)=2x+1. Очевидно, что φ΄(x)≥ φ΄(0.1)=1.2 на промежутке [0.1; 1.1].

50