книги / Линейная алгебра

6.17.Оценка погрешности решения системы линейных уравнении

Для практических целей очень важно исследовать влияние малых изменений матрицы А системы АХ = Ьи столбца 6 свободных членов на ее решение X . В общем случае система считается устойчивой, если малые возмущения в АиЬ приводят к малым возмущениям в X . Сте­ пень малости участвующих величин обычно измеряется в отношении к их значениям в невозмущенном состоянии, т.е. если

	АХ = 6 -	точная система,						(6.85)
	(А + €а ) Х	= Ь+ еъ	- возмущенная система,					(6.86)
то измеряются величины относительных возмущений
6А	IM I	SA- i	_	11(А + е л )-1 - А			- 1|
	И Г	дА	"		\\а - ц\
6Ь	I N I	' У _		Ы	_	\\х- х\\		(6.87)
	И Н Г				1 1 *	1 Г	11*11

в некоторых векторных и матричных нормах.

Предполагается, что матрица А и возмущенная матрица А 4-£а — невырожденные. Оказывается, возмущенная матрица А + €а будет невырожденной при всех возмущениях £а } удовлетворяющих условию

I M I < Ц Л " 1 1 Г 1 *

(6.88)

При выполнении условия (6.88) будут верными при любых матрич­ ных нормах соотношения

	||(Л+ ел ) - 1 - Л			- 1|	<	Н	А	- Ч М		М	(6.89)
						х - р		- Ч	Н	М
											Г
			6А -1		<	Кл •&А					(6.90)
						1 -	КА -6А
	и при подчиненных матричных нормах — соотношения
	1Ы1	=	\\х - х \\^\ * к *^ а {6а + 6Ь)'								(6-91)
	6 Х	_	||Х||		------- А		— {6А		+ 6Ь ) ,		(6.92)
	6Л	~		Ъ 1 - К А			6А к

Реш ение. Составим систему {А*А + аЕ) = А*Ь. В рассматривае­ мом случае она имеет вид

	Г	(4 + a)xi + (3 + 2г>3 =				3 + 2,
	\	(3 — 2г)х\ + (4 + а)х2 =				3 — г.
Решая эту систему, получим
„ а	/ 1 + За + (1 + a)i			1 + За — t'(l + а )\ Т
	V 3 + 8а + а 2		’	3 + 8а + а 2 )
Переходя к пределу в Х а при а			к0+, найдем искомое нормальное
псевдорешение				1 — *		т
				Н Г	)
6.16.	Н орм ы век тор ов и м атриц

Пусть дано действительное или комплексное линейное простран­ ство векторов-столбцов. Каждому вектору х из X поставим в соот­ ветствие действительное число \\х\\ и назовем его норм ой вектора х, если для любых векторов х и у из X и любого действительного или комплексного числа а выполняются следующие аксиомы:

1. ||х|| > 0, если х / О и	||х||= 0, если х = О,
2. |М|=(а|.|И,
3- lk + 1/ll < 11*11+ IMI-
Линейное пространство	X при этом называется нормирован­

ным.

Наиболее употребительными являются: 1. Октаэдрическая норма вектора

N li = X > * l ‘

*=1

2. Евклидова или сферическая норма вектора

IM I> = N 1 * \=

* = 1

3.Кубическая норма вектора

Mloo = max |г<|.

1<»<П

Под норм ой матрицы А с действительными или комплексными элементами понимают действительное число ||Л||, поставленное в со­ ответствие матрице и удовлетворяющее следующим условиям:

1. ||Л|| > 0, если А ф 0 и ЦАЦ = 0 , если А = О,

2.ЦлАЦ = |а| •ЦАЦ, в частности, ||А|| = |— А||,

3.ца + в ц < цац + цвц,

4.||АВ|| < ЦАЦ •||5||

для любых матриц А и В, для которых соответствующие операции имеют смысл, и любого комплексного числа а

Иногда в определении нормы матрицы ограничиваются лишь пер­ выми тремя условиями. В таком случае норму матрицы называют обобщ енной.

Примерами матричных норм матрицы А = (а,; ) являются:

1-	1ИН = Е и М ;
2.	\\А\\! =	max, Е , |о,-,|;
3.	ЦАЦ» = max* E j
4.	ЦАЦ* =	( E £ I E ”=I М 2)	1	=	v ^ i + --- + 0'? ~ евклидова
	норма.
Для матрицы
		/	1	2	3 \
		д _	4	5	6
		\	7	8	9
			10 11		12/

все эти нормы будут иметь соответственно значения:

1-	Р|| = Е 0 |а,-,1 = 1 + 2 + ...	+ 12 = 78,
2.	||A||i = шаху Е » 1°»;1 = т а х (1 + 4 + 7 + 10, 2 + 5 + 8 +11, 3 + 6 +
	9 + 12) = (22, 26, 30) = 30,
3.	Н-АЦоо = max, E j la»il = niax(l + 2 + 3, 4 + 5 + 6, 7 + 8 + 9, 10 +
	11 + 12) = (6, 15, 24, 33) =	33,

4- ||А||* = (ЕГ=1 Е ,"=1 Ы 2) 1'2 = V I2 + 22 + ... + 12* = ^/eso.

где Ка = 1И” 1!! *Р|| — число обусловленности матрицы А.

Эти формулы дают количественные оценки возмущения обратной матрицы и решения системы линейных алгебраических уравнений с невырожденной матрицей при возмущении системы. Они показы­ вают, что обратная матрица и решение системы будут устойчивыми к возмущениям при не слишком большом числе обусловленности ма­ трицы. Из них следует также, что в окрестности любой невырожден­ ной матрицы обратная матрица и .решение системы являются непре­ рывными функциями входных данных. При этом соотношение (6.88) определяет окрестность, в которой выполняется непрерывность по матрице. Непрерывность решения по правой части системы выпол­ няется всюду, так как на столбец свободных членов не накладывается

никаких условий.
П ример 1. В системе
*1+®2	=	1)
{Xi - 12	=	3

элементы матрицы могут изменяться на е, а свободные члены - на е\. Требуется оценить возможное изменение координат вектора-решения при е = €\ = 0.1.

Реш ение. В данной системе

А=

ипо условию

Для оценки возмущения координат вектора-решения естественно использовать кубическую норму вектора, т.е. норму ||z||oo = плах,- |®*|- Подчиненной ей матричной нормой является

||Л||оо = та х ^ | а < ,| .

3

Поэтому имеем

||Л||„ = 2, ||Л_ 1 ||00 = 1, ||Ь||оо = 3 , М е е = 2 ,

1М оо = 2е<||Л -1||-| = 1| М о о = еь

Ы с	о	=	| | * - * Н		~	<	Halloo •||Х||оо		/ f , CL\ _
							]1^	° ° —	.(6А + 6Ь )-
			1- 2-2		1 -	ЦА-iileo - 1И11
				(е + ^			= Г ^ ( £ + т ) ’
		1	- 2 •2е
						3 /
6Х <	1 -	ИЛОНИН					(«Л + » ) = г ^		( £ + | )
		\\A~4\oo -W AU -6A
В частности, если е = е\ = 0.1, то
Halloo = II* " *IU < j-^ 2								(0-1+ х )	-

“S T^O I (01 + T ) = 0<3)’

т.е. при е = £i = 0.1 координаты вектора-решения данной системы могут изменяться не более, чем на 0.(6), а их относительное измене­ ние не превосходит 0.(3).

Пример 2 . В системе

(	Xi + Х 2	—	3,
\	®1 — *2	=	4

элементы главной диагонали матрицы могут изменяться на €\, а сво­ бодные члены - на 6Г2- Оценить возможное изменение вектора-реше­ ния по длине при е = £г = 0.01.

Решение. Для оценки возмущения вектора-решения по длине есте­ ственно использовать евклидову норму ЦжЦг вектора. Подчиненной ей матричной нормой является спектральная норма \\А\\2 = у/тахХа*а -

В нашем примере матрица

- С -О

- симметрическая. Поэтому ЦАЦг = тахЦАдЦ = л/2, так как харак­ теристический многочлен |А— AJS7| = А2 — 2 имеет корни Ait2 = ±\ /2.

Ввиду того, что собственные значения матриц А и А "1 взаимно обратные, получаем

,ч - 1 „	2	1	1	1
\\А		= m ax— =	. , - Т =	—7=.
		ХА	тт| А Л|	л/2

Матрица
-	симметрическая, ее характеристический многочлен \ел - А£| =
=	(ei - А)2 имеет корни A1i2 = £i. Поэтому
		||£А||2 = тах|Аел|= е1,				6А = ! M				! i	_ f i _
								U h			~ у/2'
Далее имеем
	Н»1|2 =		11(3, 4 )т ||2 =			=	5,
	Holla = 11(о ,о )Т|= V 2■ е ,.						Sb = M				i = ^ L fi,
Поэтому
	I M h	=	\\Х-Х\\2 <	1 И " Ч Ь - 1 № - №							(6А + 6Ь) =
				1-\\а - ъ			-\\а \\2 -6А
					5\/2		/б !		е2\
				“ V 5 - e i ' 2 + Ь )'
	SX	=	I M	1Иг1 •1ИНг						(6А + 6Ь) =
			||Х||2 -1 -| | А -М | 2 -|И |2-М
				=	— ! _	(	! !	+	£а)
					л /2 - е ,		' 2	^	5	/
	В частности,		при ^ = е2 =		0.01	\\ев\\2			<	0.035, 6Х < 0.01, т.е.

длина векторагрешения может измениться не более чем на 0.035, а его относительное изменение по длине не превосходит 0.01.

6.18.Отыскание устойчивого решения системы линейных уравнений

Пусть дана точная система

и ее возмущенная система
АХ = 6.	(6.94)

Точная система с производной (т х п)-матрицей ранга г может быть как совместной, в частности, с невыроженной матрицей, так и несовместной. Поэтому естественно вести речь о нормальном псев­ дорешении Х ° системы (6.93) и о его возмущении при возмущении системы. В общем случае даже при малых возмущениях системы возможны большие возмущения в нормальном псевдорешении. Воз­ никает вопрос, нельзя ли нормальное псевдорешение системы (6.93) находить приближенно устойчивым образом и давать оценку погреш­ ности такого приближения при возмущении системы. Оказывается, что эти вопросы можно решать положительно. Для этого следует в качестве приближения к нормальному псевдорешению брать опреде­ ленную проекцию Xk псевдорешения возмущенной системы на под­ пространства правых сингулярных векторов (см. п. 6.14), т.е. пола­ гать Х° ~ Xk при определенным образом выбранном номере Jfc, или в качестве приближения нормального псевдорешения Х° брать Х а, найденное методом регуляризации (см. п. 6.15) для возмущенной си­ стемы, при некотором значении параметра а, т.е. полагать Х ° ~ Х а при определенным образом выбранном параметре а. Поясним такой подход на примере.

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

2 « i —	Х2	= 1,
- ® i +	Х2	+Х3 = 0,
	Х2	+ 2 х 3 = 1
с нормальным псевдорешением	Х° = |(1,0,1)т (см. пример 1 из п.

6.15) при возмущении перешла в систему

	{	2 x i-	*2	= 1,
		—X i+	Х2	+ Х з = О,

*2 +(2 + е)х3 = 1.

Попытаемся устойчивым образом найти нормальное псевдорешение Л’0 точной системы, решая возмущенную систему. С этой целью при­ меним метод регуляризации (см. п.6.15) к возмущенной системе. Для этого составим систему {А* А + аЕ)Х = А*6, которая в нашем случае

имеет вид

{(5 + a)xi — За?2 г- хз = 2,

—3a?i + (3 + а)х 2 + (3 + е)х3 = 0,

		—х\ + (3 + s)x 2 + (5 + 4е + £2 + ас)х3 = 2 + £.
Решая эту систему,получим
			/ A i	Дг Д з\ Т
		A _	^ Д "’	Д", Д",/
где
Д	=	36а + 13а2 + а 3 + 26аг + 7ае2 + 4а2е3 + а2е3 + е2,
Ai	=	18а + 2а2 + 9а£ + 2а£2 + £2,
Д 2	=	е2 — 5ае —а£2,	А 3 = 18а + 2а 2 + 8а£ + а 2£.

При а —►0, Х а —►Х° = (1 ,1 ,0)т	Этот вектор в два раза длиннее
вектора нормального решения Х° =	|(1, 0, 1)т точной системы и

составляет с Х° угол 60°. Если же взять а = £, то Х ° уже достаточно точно совпадает с Х°.

К такому же результату придем, если найдем нормальное псевдорешение Х° = (1, 1, 0)т возмущенной системы, вычислим его проекцию Х 2 и положим Х° = Х 2.

Обоснованию данного подхода в книге [5] посвящены параграфы 16 и 17. Приведем основные результаты из них.

Обозначим через <7i, 0-2, ..., (тв сингулярные числа матрицы А ранга г и будем считать , что (Т\ > <Т2 > •••> o’a (<7,- 7^ 0 при i = TTr)- Соответствующие сингулярные числа матрицы А обозначим^через <?!, ? 2? •••, Предположим, что найдены псевдорешение X воз­ мущенной системы и его проекции Х к, к = 1 , г на пространства Lk = < , ег,..., е* > правых сингулярных векторов e i, 62, ..., е*, со­ ответствующих сингулярным числам <?i, <72, - • 2г,. Пусть известно, что точная система совместная и возмущения ее малы по сравнению с наименьшим ненулевым сингулярным числом оу матрицы А, т.е. воз­ мущение элементов матрицы А и возмущение свободных членов си­ стемы (6.93) достаточно малы по сравнению с <тг. Тогда для нормаль­ ного псевдорешения Х° точной системы имеет место приближенное равенство

причем
	6Х° < К+(6А + 56),			(6.96)
где	\\Х°-ХГ\	_ J	M	I N I
0 _
~	||*°||*	6А =	’	\\ь\\е ’
		№

Кд = ||Л+ ||в||А||в — обобщенное число обусловленности матрицы А. Формулы (6.95) и (6.96) сохраняются и для почти совместной точ­

ной системы (6.93), т.е. для такой системы, в которой вектор

ь = (ьг, 0)т+ (О, К)т

имеет достаточно малое слагаемое (О, Ь'г)т Заметим, что формула (6.96) аналогична формуле (6.92) предыду­

щего параграфа. Причем она показывает, что если точная система совместная или почти совместная и возмущение мало по сравнению с наименьшим ненулевым сингулярным числом матрицы системы, то нормальное псевдорешение можно определить по формуле (6.95) с той же точностью, что и для системы с невырожденной матрицей.

В случае несовместности точной системы (6.93) и малого ее возму­ щения по сравнению с наименьшим ненулевым сингулярным числом также имеет место соотношение (6.95) и вместо соотношения (6.96)

выполняется соотношение
6Х° < К+(6А + 56) + К\{К+ ■6А +	(6.97)

Эта формула показывает,что точность приближения Х° с помощью Хг в значительной мере зависит от отношений ||&^||я/||Ьг||я, т.е. от степени согласованности правой и левой частей исходной системы (6.93) .

Формулы (6.93)-(6.97) верны при возмущениях достаточно малых по сравнению с наименьшим ненулевым сингулярным числом оу ма­ трицы системы. В общем случае, когда входные данные системы (6.93) заданы с точностью порядка е, то одна из проекций Xk при­ ближает нормальное псевдорешение Х° с точностью порядка fпе)2^3, если точная система совместная, и с точностью порядка (пе)1' 2, если точная система несовместная.

К аналогичному результату придем, если вместо приближенного равенства (6.95) пользоваться приближенным равенством

1 6 - 1 3 0 7

при некотором значении а, т.е. если нормальное псевдорешение Х° системы (6.93) приближать с помощью векторов Х а , которые нахо­ дятся методом регуляризации для возмущенной системы (6.94), так

как при этом оказывается верным следующее утверждение:

если входные данные системы (6.98) заданы с точностью по­ рядка е, то при некотором значении а вектор Х а приближает нормальное псевдорешение Х° системы (6.98) с точностью по­ рядка £2/ 3 б случае ее совместности и с точностью е1!2 в про­ тивном случае. Причем^если а = е2^3 в первом случае и а = е1^2 во втором случае, то Х а обеспечивает почти наилучшее при­ ближение к Х °.

Пример 2. В системах

2 х \ —	X2	= 1,	(6.99)
- * i +	X2	+*з = 0,
	Х2	+2агз = 1;
2 x i —	Х2	= 2,
—* 1 +	Х2	+ х з = 3,	( 6.100)
	Х2	+ 2 х 3 = - 1

элементы матрицы и свободные члены могут изменяться на е = 0.01. Оценить возможную погрешность приближения нормального псевдо­ решения каждой из данных систем.

Реш ение. Здесь точная система (6.99) совместная, а система (6.100) несовместная и наименьшее ненулевое сингулярное число матрицы этих систем (72 = 2 (см. пример 2 из п.6.10). Оно значительно боль­ ше возмущений элементов матрицы и свободных членов. Поэтому для обеих систем применима формула (6.95) при к = 2, по ко­ торой Х ° ~ Х 2, а погрешность этого приближенного равенства для системы (6.99) оценивается по формуле (6.96), для системы (6.100) - по формуле (6.97). Чтобы применить формулы (6.96) и (6.97), вычи­ сляем для обеих систем

№ = л/Тз, ||Л+||В = ^ , |М1* = Зе,

Кроме того,вычисляем для системы (6.100)

11*11* = V14,	IM Is = еуД,	6Ь = М ё. =	£^2,
		iPlIs	V 14