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

\М в = VU,	\\Ь'2\\Е = 1
и для системы (6.99)
\\b\\E = V 2 ,	|Ы|в = £ч/з,	6 Ь = ^	= -е ^ д -

Теперь по формуле (6.96) получаем оценку возможной погрешно­ сти приближенного равенства Х° ~ для системы (6.99):

6Х° < \\А+\\в ■Р | | к (^ + 6Ь) = н

В частности, при е = 0.01 6Х° < 0.02, т.е. относительное изме­ нение вектора-решения Х° системы (6.99) по длине не превосходит 0,02 (сравни с результатами примера 1).

Для системы (6.100) формула (6.97) даст следующую оценку воз­ можной погрешности приближенного равенства Х° ~ Х 2

, vo	13	/ Зе	е>Д\	, V n	( 13е	, ty/l\
~	6	l vT3	x/lij	6	U yi3	ч/Й/

В частности, при е = 0.01 6Х° < 0.042.

Если пользоваться приближенным равенством (6.98), то оно дает приближение нормального псевдорешения для системы (6.99) при

а =	е2/3	с точностью порядка е2/3 = 0.047, а для системы (6.100) при
а =	е1/ 2 -	с точностью порядка е1/2 = 0.1.

Результаты, отмеченные в этом и предыдущем параграфах, имеют исключительное значение для обоснования большинства численных методов решения систем линейных алгебраических уравнений, а так­ же при выработке общей тактики решения таких систем на ЭВМ. Об этом см. [5, гл.5].

6.19.Рекомендации к решению систем линейных уравнении на ЭВМ

Пусть дана система

16*

Существует много различных способов для отыскания решений си­ стемы (6.101) на ЭВМ. Общеизвестны, например, метод Гаусса и раз­ личные его модификации для отыскания решений совместных систем. Из других методов многие сводятся к составлению системы нормаль­ ных уравнений (см. п. 6.14)

А* АХ = А*6,

(6.102)

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

Классические вычислительные методы для совместных систем оказываются не всегда хорошими при применении их на ЭВМ. Они во многих случаях обладают способностью накапливать ошибки вычи­ слений. Для системы (6.101), у которой ранг матрицы А меньше, чем п, и для системы с большими размерами т ип матрицы А применение таких методов на ЭВМ может привести, в результате накапливания ошибок, к решениям весьма далеким от истинных.

Существует надежный способ отыскания псевдорешений по МНК совместной (несовместной) системы (6.101) на ЭВМ, основанный на представлении ее ( т х п)-матрицы А в виде сингулярного разложения

(см. п.6.10):
A = U ЕУ*,	(6.103)

где U — ортогональная (унитарная) (га х т)-матрица, V — ортого­ нальная (унитарная) (п х п)-матрица,

i <Г1	0 \
Е =	- (га х п) — матрица.
Vo	0Vi
	о /

Этот метод позволяет находить по МНК нормальное и общее псев­ дорешения совместной (несовместной) системы (6.101) без перехода к системе нормальных уравнений (6.102). В нем предусмотрена также возможность учитывать неточности входных данных и погрешности вычислений на ЭВМ.

Для получения сингулярного разложения (6.103) и отыскания нор­ мального и общего решений с помощью этого разложения на ЭВМ

имеются стандартные программы (см. [29], [33], [37]). При примене­ нии этих программ в случае, если в системе (6.101) т < п, целесо­ образно перейти к другой системе, приписав к системе (6.101) п —т

нулевых строк. Очевидно,		что это не изменит искомого решения.
Поясним кратко содержание этого метода.
Используя сингулярное разложение (6.103) матрицы А , систему
(6.101) можно представить в виде
	UZV*X = b.			(6.104)
Отсюда, полагая
Z = V*X,		d = U -1b = U 4 )
получаем систему
	EZ =		d,	(6.105)
т.е. систему
' (7i Z\	—	d\	i	<61»6)
	" • *	о

Для учета неточности входных данных и погрешности вычислений вводят границу г. Так, например, если данные вводятся с тремя вер­ ными десятичными знаками, то подходящим будет значение г = 10“ 3. Если данные введены точно, то значение для тпринимают равным по­ рядку машинного эпсилон, умноженному на п. Выбор границы опре­ деляет, какую проекцию нормального решения возмущенной системы (6.104) на подпространства правых сингулярных векторов взять за основу, чтобы, используя ее, строить общее и нормальное решения си­ стемы (6.101) (см. формулы (6.75) и (6.76) из п. 6.14 и формулу (6.97) из п. 6.18). Делают это следующим образом. Всякое aj большее, чем

считают приемлемым и из системы (6.106) находят соответствую­ щее ему Zj = d j /<Tj. Любое <т;*меньшее, чем г, считают пренебрежимо малым и соответствующему ему Zj придают произвольное значение. По найденному вектору Z = (zi, ^2, ... , zn)T легко находится общее псевдорешение X = (xi,X 2, ••->®п)т системы (6.101) по формуле

В частности, при Z = Z 0, где все произвольные постоянные взяты равными нулю, получается нормальное решение системы (6.101)

Х ° = VZ°.

(6.108)

Формула (6.108) является матричной записью формулы (6.95) из п.6.14. Если исходная система (6.101) однородная, т.е. если АХ = 0 , то системы (6.105) и (6.106) также однородные и в них все Zj, при ко­ торых стоят коэффициенты <Tj > г, будут равны нулю, а остальные Zj могут принимать произвольные значения. Число неизвестнь£х Zj) принимающих произвольные значения, очевидно, равно п —r (где г - ранг матрицы системы), т.е. числу свободных неизвестных системы. Вектор Z = (0 ,..., 0, C i,..., Сп_г)т будет общим решением системы ЕZ = 0, а вектор X = VZ - общим решением однородной системы АХ = 0. Из общего решения (6.107) легко получить ФСР, если про­ извольным постоянным Ci, С2, ..., Сп-г последовательно придавать соответствующие значения из строк (столбцов) определителя (п — г)- го порядка, отличного от нуля. Если, кроме того, этот определитель соответствует ортогональной матрице, то в силу ортогональности матрицы V построенная ФСР будет ортогональной. Такой будет, в частности, ФСР, состоящая из последних п — г столбцов-решений матрицы V

Поэтому общее решение (6.107) системы (6.101) можно предста­ вить в виде

Х = Х ° + С М +! + C2Vr+2 + ... + Cn-rV„,

(6.108')

где Vr+u Vr+2i . • Vn - последние (n — г) столбцов матрицы V . Для практических целей обычно находят нормальное решение Х°

или какое-либо близкое к нему частное решение, получаемое из (6.108') при достаточно малых значениях постоянных Ci, С2, Сп- г • Но иногда приходится находить (см. формулы (6.75) и (6.76) из п.6.14) решения систем

» ( Ео"

где Efcjb - матрица, построенная на к первых строках и к первых столбцах матрицы Е, и из них выбирать наиболее подходящее реше­ ние. В этом состоит содержание сингулярного анализа (см. п. 6.18 и [5]). Подробные разъяснения по сингулярному анализу можно найти в книге [18]. Там же даны рекомендации по практическому анализу задач МНК.

На практике приведенный метод оказывается не намного более трудоемким, чем другие. Однако его применение не требует перехода к системе нормальных уравнений (6.102) и гарантирует, что следует из результатов п. 6.18, высокую надежность и точность получаемых решений. Кроме того, применение сингулярного разложения (6.103) позволяет от системы (6.101) перейти к системам (6.104)—(6.106). В этих системах легко представить себе структуру данных, уяснить смысл некорректности системы и увидеть пути ее реализации. Дру­ гими словами, применение сингулярного разложения (6.103) позво­ ляет наглядно проводить анализ данных и целенаправленно планиро­ вать эксперимент, приводящий к системе (6.101). Действительно, по виду системы (6.106) сразу замечаем, что для ее совместности необ­ ходимо и достаточно равенство нулю всех d,- при г = г + 1 ,т . Чем больше эти числа отличаются от нуля, тем будет большей некоррект­ ность системы (6.106), а следовательно, и системы (6.101). Для ис­ правления положения, очевидно, нужно попытаться так организовать эксперимент или так построить его математическую модель, приво­ дящую к системе (6.101), чтобы указанная некорректность систем (6.101) и (6.105) по крайней мере уменьшилась.

По виду системы (6.104) легко также сделать заключение о числе обусловленности Ка матрицы этой системы, полагая это число рав­ ным сг\/а8^где ст\ и а8 — соответственно наибольшее и наименьшее сингулярные числа матрицы А (при <т8 = 0 число обусловленности ма­ трицы А считают равным бесконечности). Большая величина числа обусловленности матрицы А указывает на то, что математическая модель, приводящая к системе (6.101) , не является удачной. Если рассматриваемую модель сохраним без изменений, то при решении системы (6.101) указанным способом придется более тщательно вы­ бирать границу г, которая отражает точность данных и точность машинной арифметики или использовать проекции псевдорешений на подпространства правых сингулярных векторов, т.е. проводить сингулярный анализ. Однако надежнее изменить математическую модель, приводящую к системе (6.101). Поясним это на примере (см. [33]) выбора функции, выравнивающей следующие результаты наблю­ дений:

t	1900 1910 . . .	1970
y(t)	bi	bs

Если эти данные выравнивать функцией

y{t) = C1 1 + C2t + C3t2,

(6.109)

то матрицей системы для определения неизвестных С\, С2, С3 будет (8 х 3)-матрица

1	1900	19002
1	1910	19102
1	1970	19702

Ее сингулярными числами являются

<71 = 0.106 •108, <72 = 0.648 •102, <73 = 0,346 •1(Г3.

Число обусловленности этой матрицы <т\/сгз = 0.306 •1011 весьма ве­ лико. Следовательно, вид выравнивающей функции (6.109) выбран не совсем удачно. В ней базисные функции l , t , t 2 для значений, на­ ходящихся между 1900 и 1970, близки к линейной зависимости, так как <73 близко к нулю. Для исправления положения естественно изме­ нить базисные функции и тем самым изменить вид выравнивающей функции. Вместо функции (6.109) можно взять, например, функцию

	y(t) =		Cl	1 + C2(t - 1900) + c 3{t -						1900)2				(6.110)
или функцию
	/ ,Ч	^ , , „ < - 1 9 3 5						„ Л ~ 1 9 3 5 \ 2						(е л и )
	y(t) =	Cis-1		+ с 2—		jg—	н ? з		^—	— j
соответственно с матрицами наблюдений
		1	0	0	\				1	-3 .5		3.52	\
		1	10	102					1	-2 .5		2.52
		1	20	202					1	-1 .5		1.52
		1	30	302		,	А-2 =		1	-0 .5		0.52
		1	40	402					1	0.5		0.52
		1	50	502					1	1.5		1.52
		1	60	602					1	2.5		2.52
		1	70	702	J				1	3.5		3.52	J
Сингулярными		числами			матрицы			А\	для модели			(6.110)		будут
числа	<71 = 0,684 •			104,	<т2 =		0,293		102,	<73	=	0,199 •		10, а
для	матрицы		А2	модели		(6.111)		-	числа		<7i =		0,198 •102,
<т2 =	0.648 •10,		о*з =	0,185 •10. Числа обусловленности o*i/o*3 этих
матриц соответственно равны 0.575 •104 и										10,7.	Последнее число
обусловленности совсем невелико.							Поэтому выравнивающая модель

(6.111) более надежна и приемлема по сравнению с моделью (6.110) и особенно по сравнению с моделью (6.109).

При конструировании выравнивающей функции можно также уве­ личить степень многочлена, представляющего эту функцию, или вы­ разить ее через какие-либо другие базисные функции, например, че­ рез sintf, sin 21, ..., sin п/, и с помощью сингулярного анализа выбирать наиболее приемлемую модель. Более подробное обсуждение сингуляр­ ного анализа содержится в [18].

Другим надежным методом вычисления на ЭВМ нормального ре­ шения системы , как следует из результатов п. 6.18, является метод регуляризации (см. п. 6.15).

Для решения систем линейных уравнений эффективными могут оказаться также итерационные методы. Они особенно удобны при больших размерах матрицы системы. Об итерационных методах см. гл. 8.

Таким образом, систему (6.101) следует решать на ЭВМ либо ука­ занным выше приемом, основанным на применении сингулярного раз­ ложения (6.103), либо придерживаться следующей тактики.

Если известно, что исходная система устойчива к возмущениям (хорошо обусловлена), то ее можно решать любым обычным алго­ ритмом, например, методом Гаусса или какой-либо его модифика­ цией. Если известно, что исходная система неустойчива к возмуще­ ниям (плохо обусловлена), то для отыскания ее нормального решения следует применять метод регуляризации, причем следует сразу пола­ гать а = £2/3 в случае совместности системы и а = е1/ 2 — в случае ее несовместности ( € — граница точности входных данных).

Если об устойчивости системы ничего неизвестно, то систему упрощают и попутно выясняют вопрос об ее устойчивости к возму­ щениям. Если система окажется устойчивой к возмущениям, то про­ должают ее решение обычными методами. Если же система окажется неустойчивой к возмущениям, то далее ищут ее нормальное решение методом регуляризации и в нем сразу полагают а = е2^3 в случае совместности системы и а = е1/ 2 — в случае ее несовместности. При таких значениях параметра а обеспечивается наилучшее приближе­ ние к искомому нормальному решению.

Об	оценках погрешности на каждом этапе рассматриваемой схемы
см. [5].	При больших размерах матрицы системы могут возникнуть

трудности в возможностях памяти машины и тогда более эффектив­ ными могут оказаться итерационные методы (см. гл. 8).

6.20.Упражнения

1. Пусть х = (х1,хг)т , у = (j/i, 3/2)Т — произвольные векторы линейного пространства Х2, заданные координатами в фиксированном базисе t \ , ег. Убедиться, что скалярное произведение векторов в Х 2 можно задать сле­ дующими способами:

1)	(х,у)	=	хгу!+Х2У2;
2)	(х,у)	=	2xiyi	+ 3х20г;
3)	( х , у )	=	Z iy i	+Х102 + Х 2 У 1 + 2 х 2х 2;
4)	(ж, у)	=	2X101 - Х102 -		Х201 + Ж202;
5)	(а?,0)	=	2X101	+2X102 +	2X201 +3X202;
6)	(х, 0)	=	3X101	- 2X102 -	2X201 + 5X202.

Вычислить скалярное произведение векторов х = (1, 1)т и у = (2, —1)т при каждом из указанных способов его задания в Хг.

2.	Пусть в линейном пространстве Х 2 с базисом ei, ег скалярное произве­
дение задано формулой
		(х, 0 ) = ОГ11Х101 + « 12^202 +ОГ21Х201 + <*22^20 2 .
	Убедиться в том, что a%j				= (ei, е; ), i , j = 1,2 и выписать матрицу Гр&на
базиса ei, ег.
3 .	Дано линейное пространство Х з с базисом ei, ег, ез и
	/	54б	2	- 4 \
	Г = I	2	1	—2	1 — матрица Грама базиса ei,	ег, ез.
	V	-4	-2	5	/
	Выписать формулу скалярного умножения векторов в Х з					и, пользуясь

им, вычислить скалярное произведение (е»,е;), t,jf = 1,2 ,3 и (х,у), если
1)	X =	(1,	2,	3 ) т ,	у =	(0, 1,	2 ) т ;
2)	х =	(1,	1,	2)т ,	у =	(1, 0,	1)т ;
3 )	х =	(2,	0,	1)т ,	у =	(1, 3 ,	1)т

4 .

Применяя процесс ортогонализации, ортогонализировать следующие

системы векторов:

1) О! = (1 , -

2 , 2 )т ,

в! = (1 ,

1 , 1 ,

1)т ,

ai =

(1 ,

1 , 1 , 1)т ,

2)

а2

= ( -1 ,

О, - 1 ) т ,

а2 = (3 ,

3 , -

1

,

- 1 ) т ,

о2 =

(0,

1,

1, 1)т ,

3 )

а3

= (5 , -

3 , - 7 )т ,

а3 = ( - 2 , 0 ,

6,

8)т ,

а3 = (0 , 0 ,

1 , 1)т ,

считая, что векторы заданы координатами в ортонормированном базисе.

б.Ортонормировать системы векторов предыдущего упражнения.

6.Применяя процесс ортогонализации, ортогонализировать систему век­ торов

01 = (1, О, 1)т , а2 = (0, 1, 1)т , 03 = (О, О, 1)т ,

заданных координатами в базисе ei, ег, ез с матрицей Грама

(	2	- 2
	-2	5

7. Считал векторы заданными-1координатами2 в ортонормированном баг зисе, проверить, что следующие системы векторов ортогональны и допол­ нить их до ортогональных базисов пространства:

1) в!	= (1,	-2 ,	1, 3 )т ,	2) «1 = (1,	- 1 ,	1, - 3 )т ,	3 ) «1 = (1,	1, 1, 2)т ,
а2 =	(2, 1,	-3 ,	1)т ,	а2 = (-4,	1, 5,	0)т ,	в2 = (1, 2,	3, - 3 )т

8 . Дополнить следующие ортонормированные системы векторов, задан­ ных координатами в ортонормированном базисе, до ортонормированных базисов пространства:

	_1 I	т
1) «г		_ЗЛ	2) аг
	2’ 2’	2)
«2	1 1 1	1\ т	т
	2’ 2’ 2’	2)	а2

9. Применял процесс ортогоналиэации, построить ортогональный базис пространства, натянутого на следующие системы векторов, заданных ко­ ординатами в ортонормированном базисе:

1)	ai	=	(2,	3, - 4 ,	- 6 ) \ 2)		в! =	(1, 1,	- 1 , —2)т ,
	a2	=	(1,	8,	- 2 ,	- 1 6 )т ,а2 =		( - 2 , 1, 5, 11)т ,
	а3	= (12, 5,		-1 4 , 5)т ,			а3 =	(0, 3,	3, 7)т ,
	а4	=	(3,	11,	4,	7)т ,	а4 =	(3, - 3 , - 3 , - 9 ) т
10.	Найти базис ортогонального дополнения L L подпространства L , на-

тянутого на векторы ai, а2, аз, заданные координатами в ортонормиро­

ванном базисе:

2) О! = (1, 2, 2,

- 1)т, 3)

О! = (1, 1, -1,

- 2)т,

1) в! = (1,

3,0, 2)т,

а2

=

(3,

7, -1 , 2)т ,

а2

=

(1, 1, -5 , 3)т ,

а2

=

(5,

8 , -2 ,

- 3 )т ,

а3

=

(2,

4, -1 , 0)т ,

а3

=

(3, 2, 8 ,

- 7 )т ,

а3

=

(3,

9, 3, 8)т

11. Найти системы линейных уравнений, задающих подпространства L и L L предыдущего упражнения.

1 2 . Подпространство L задано системой уравнений

Г х\ -f х2 + яз —	=	О,
1 I l - l 2 - ® 3 + ® 4	=	0.

Найти систему уравнений, задающую ортогональное дополнение L *L.

13.Найти ортогональную проекцию х и ортогональную составляющую z

вектора у		на линейное пространство L			=< ai, a2i аз >, если
1) у = (14, -3			, - 6 , - 7 )т ,	2) у =	(2, —5, 3, 4)т ,
ai	=	(-3 , 0, 7, 6)т ,		в1 =		(1, 3,	3, 5)т ,
a2	?=	(1, 4, 3, 2)т ,		а2	=	(1, 3,	-5 ,	- 3 )т ,
а3	=	(2, 2,	-2 , —2)т ,	а3	=	(1, -5 , 3,		- 3 )т

14. Найти ортогональную проекцию х и ортогональную составляющую z вектора у = (—3, 0, —5, 9)т на подпространство L , заданное системой уравнений

{ 3xi Н" 2x2 + хз —2x4	=	О»
5xi + 4 x2 + Зхз + 2 x4	=	О,
Xi — 2X2 Зхз + 10x 4	=	0.

15. Считая, что векторы заданы в ортонормированном базисе, ортонормировать систему векторов.

1)

О!

=

(1,

1,

0 Т,

«2 =

(«, 1,

1)Т,

аз

=

(1,

*,

1)т :

2)

аз = (1, i,

»)Т.

*2 = (1, »,

1)т ,

о3 =

(*,

»,

i)T;

3)

oi

=

(1,

1,

i ) T ,

02 =

(*,

1)т ,

оз

=

(*,

1,

i ) T

16.Считая, что векторы заданы в ортонормированном базисе, убедиться

вортогональности системы векторов сц, аг и дополнить эту систему век­ торов до ортогонального базиса пространства.

1)	ai =	(i. *.	i. о т .	a2	=	(1,	i, -
2)	ai =	(1> !»	». »)Т>	Л2	=	(1,	- 1
з)	ai =	(!+.•;	1 + .': 1 , 1)т ,	a2	=	(1 -

17.Найти матрицу перехода от базиса ei, ег, ез к базису

e'i =|(4 + 3i;-4.;6 + 20J, е'2 =|(4.; 4 — 3»; —2 — 6i)7,

ез = §■(—6 —2*; —2 — 6»; 1)т и убедиться в том, что полученная матрица является унитарной.

18. Пусть ei, &2 - ортонормированный базис в Х 2 и линейный оператор <р в базисе е[ = ei,ei = ei + ег имеет матрицу

Найти матрицу сопряженного оператора <р* в базисе ej, е^.

19.Линейный оператор <р в базисе

ei = (1 , 2 , 1)т , е'2 = (1, 1 , 2)т , е'3 = (1, 1, 0 )т имеет матрицу

-ЦП)

Найти матрицу сопряженного оператора (р* в том же базисе, считая, что векторы базиса е; даны координатами в ортонормированном базисе е.

2 0 . Пусть в базисе е скалярное произведение задано формулой

(х, у) = 2xiyi + Зх2У2 + хзуг 4* 2XI02 + 2X20I + xij/з + хзуг -f х2уг + ®з02, а линейный оператор р - матрицей