книги / Численные методы. Ч. 1

к	j< i
к '
1,	j = *
0,	j> i
	j= i
1«-	j* i
Теперь матрицу А можно представить разложением
А = NKU.		(2.5)

Благодаря симметрии матрицы А имеет место равенство Ат = А , что позволяет произвести следующие преобразования:

UTKTNT = N K U ,

UTKT = N K U (N t )''

N"'UTK T = KU(NT) '‘

IC- W K 1 = U (N t )~'

В силу того, что К '.К 1 являются диагональными матрицами, N4 , и 1 - нижние

треугольные, U,(NT)	верхние	треугольные,	в левой части	последнего равенства
находится нижняя треугольная		матрица, а в	правой части	верхняя треугольная.

Равенство возможно лишь при условии, что и в левой, и в правой частях этого тождества расположены диагональные матрицы.

Матрицы (N r) ' и U имеют единицы на главной диагонали; следовательно, их произведение также содержит единичную главную диагональ, то есть

U (N t ) '‘ = E , U = N T

Отсюда следует, что соотношение (2.5) можно переписать в виде

А = NKNT

Далее представим матрицу К в виде

где

|к Г =

	K = |K T -D -|K f >
'	о	о
О	[г«Г ^	о
О	о	и

О О О

-------------------1

	о	о	о		J x „ | .
	sign(X,„)		о	0	0
	0	sign(A.22)		0	0
D =	0		0	sign(X33)	0
	0		0	0	sign(X,

Сравнивая	теперь	соотношение	A = | N |K|1/2J*D ||K|,/2 N	с формулой (2.4),
получаем для	матрицы	S выражение	S = |K|I/2-Nt , то есть	верхнюю треугольную

матрицу с положительными элементами на главной диагонали. Таким образом, конструктивно показано разложение (2.4).

Обозначим	y = Sx,	z=D Sx, тогда алгоритм	метода	квадратного	корн*
S1 (D [Sx]) = Г можно рассматривать как последовательность трех процессов:
1) S*z = f	то есть	вычисления решения z	системы	уравнений с	нижней
треугольной матрицей:

2)Dy = z , вычисления решения системы уравнений с диагональной матрицей;

3)Sx = у определения из системы уравнений с верхней треугольной матрицей искомого решения.

Построим разложение вида (2.4) для симметричной матрицы третьего ранга:

а11	а12	ai3		SN	Sl2	SI3		dii	0	0	"
a:i	a::	2J	, S =	0	S22	S2^	. D =	0	d22	0
a3i		азз		0	0	s33		0	0	d33_

ч .	0	o ’ 4 ,		0	0 ' 4 .			S.2	* . з '
ST D S = S l 2	S22	0	0	d 22	0		0	S 22	«23
_S .3	S 23	S 33	0	0	d 33_		0	0	S33
s lld ll		0		0	4 .	S,2		» . з “
= Sn d ll	S j 2d 2 2			0	0	S22		S 23
s l J d ll	S 2 ^ d 22		S33d 33_		0	0		S33_

SUd ll S| | S| 2d l 1 s „ s , 4d M

s n s i : d M	s i l s IJd	ll
S?jd i . + S b d 2j	Sl2Sl3d ll + S !3S 2 )d 12
Si : Sl3d M + S 32S : J d 2I	S?id ll + * » < * »	+ S 5 l d »

Положим dM=sign(aM), тогда из уравнения aM=sf,du получим sM= ^|ам| .

Далее, из уравнения а,2 = S||S(2d|, следует, что

В силу условия det(A)*0 и теоремы 2.2 можно ожидать, что а,, *0 . Аналогично можно вычислить

а —с с н	с -	°13	-	°13
“ 13 “ а 1Г 1Э и И*	а 13 “	,	“	С Г *
		d , , s "		d l l ^ l a lll
a:j =sfjdn +s22d22,		sjjdjj =a,2-s,J,dn .

Полагая d,, = sign(a22 - s ’jd,,), получим

.	”	_ L	]	_	I a na n	—a i:	*0
				r	a	=i l r ^ S r

- в силу упомянутого условия det(A) * 0.

а 23 S l2Sl3d ll

^IJ S	Ski^kkSk)	__
------ и	- --------- .	i < j = 2,m

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

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

алгоритма метода квадратного корня.

1. Факторизация исходной матрицы, то есть вычисление матриц S и D:

m -(m -l)		m-(m2 -1)
2	+	6	*
2. Выполнение “обратного” хода:
m (т -1 ) .			,
------------+ т

3.Вычисление т раз значений квадратных корней.

„			-	m (m J + 9m + 2)				_	m3
Общее количество операции равно — ----------------, или приблизительно — , что
					6				6
практически в два раза меньше, чем число операций в алгоритме метода Гаусса.
Пример 2.1. Рассмотрим решение системы двух линейных алгебраических
уравнений методом квадратного корня:
[0.780х + 0,717у = 0.063;
<
10.717х + 0.659у = 0,058:
s „ = J i[ 7 = 0.883176087;			dn = l;	s, 2	= 0.811842633;
				«.А .
,, = ^|а,, -s ;,d n| = 0.00940537;				d ,,= - l:
0.883176087			0			0,063)	fz,|	[0,071333453)
1. STz = f,						0.058)	{z,[	{o,009405444|
0.811842633			0.00940537		z,
1	0	y' U 4		yiU	z ,	|0.071333453|
2. Dy = z.	-1					,
0		у, J	[z,j	[y,j	[-z .j	[-0,00940958)

либо определение [9]:

Пусть f -	“возмущенная” правая часть системы уравнений. Оценим изменение
решения бх = х - х как следствие изменения правой части		5f = 7 -	f .
Система	уравнений Ax=f называется устойчивой по		правой	части, если
V f,f ||бх|| < ||6f|| М, М > 0 - положительная константа.
Это, в частности, означает, что ||бх||->0 при		J6f|| —> 0, то		есть имеется
непрерывная зависимость решения от правой части.

Пусть определитель матрицы А отличен от нуля. В этом случае существует обратная матрица А-1. В силу линейности системы алгебраических уравнений имеем:

Абх = А(х - х) = Ах - Ах = f - f = 6f, 5х = A~‘6f,

И = | А - Ч Ф 1 « .

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

(2.7)

и роль константы М может выполнять ||а -,||. Чем ближе значение det(A) к нулю, тем больше величина ||а _||, тем значительнее отклонение бх при возмущении 6 f.

Из уравнения Ах = f следует оценка

И = м * М - Н -

Перемножая два последних неравенства, получаем

М М ^ Ц а - Ц М И Н .

и	Ф 1 | - М ^ = Мл	и
н		И ’

где Мд = ||А"‘|| |(а || - число обусловленности матрицы А, характеризующее зависимость относительной погрешности решения системы уравнений от относительного “возмущения” правой части. Очевидно, что

1= INI= ||а •А '11 <;||а Ц■||а _‘1 = м * •

Пример 2.2. Рассмотрим систему уравнений Г0,780х + 0.563у = 0,217, [о,913х + 0,659у = 0,254.

Определитель этой системы уравнений Л = 0,780 - 0,659 - 0,563 • 0,913 = 0,000001 = 10 отличен от 0, хотя и мал. Матрица коэффициентов представляется в виде

0,780 0,563

А =

0,913 0,659 Вычисление обратной матрицы приводит к значению

659000 -563000

А"1

-913000 780000

Нетрудно убедиться, что определитель обратной матрицы принимает значение А = 659000-780000-563000-913000= 1000000= 106.

При использовании для вычисления нормы матрицы выражения

I m -1

M = J z 2 X

V•=* и

получаем для рассматриваемого случая:

||А|| = 1,480952059, |а.-' || = 1480952,059.

Теперь можно оценить число обусловленности матрицы А, то есть показатель устойчивости решения при возмущении правой части системы уравнений:

МА=2193219.

Рассмотрим случай одновременного возмущения и правой части 6f, и матрицы коэффициентов 5А:

Ах = 7, А = А +5А .

Для получения полной оценки погрешности решения системы алгебраических уравнений необходимо рассмотреть вспомогательное утверждение:

Лемма 2.1. Пусть С - квадратная матрица, ||С||<1; Е - единичная матрица. Тогда существует (Е + С) ', причем

Доказательство

Для любого х имеет место неравенство

||(Е+ С)х|| =IIх+CxflS||х|| - ||Сх|| 5 ||х||- ||С||■||х|| =(l - SC|j)(|xJ =б|х| •

(2.8)

где 6 = 1- ||С|| > 0 - по условию леммы.

Рассмотрим однородное уравнение (Е + С)х = 0. Из неравенства (2.8) следует

КЕ + с)4 = | о И Н -

что возможно лишь при ||х|| = 0, откуда следует, что х = 0 . Иными словами, однородное уравнение (Е + С)х = 0 имеет только тривиальное решение. Но это означает, что определитель det(E + С) не равен нулю, то есть существует обратная матрица (Е + С) 1

Теперь рассмотрим уравнение

(Е + С)х = у,

имеющее решением х = (Е + С) ' у • С помощью выражения (2.8) получаем

||(Е+С)х| йб||х|| =5|(Е+С)*'у| -

Е + С) = sup	^ SUpу IM
	Е + С)-
И |у|,0	№»(1- № Г " и О - М ) " > - М

что и требовалось доказать.

Теорема 2.3. Пусть матрица А имеет обратную и выполнено условие

Тогда матрица А = А + 5А имеет обратную и справедлива оценка погрешности

н	<	М А	( М	, МП
н		M	L I H	+ iiriiJ-
		АМ
Доказательство
А = А +5А = а (е + А ''6а ) = А(Е + С),					С = Д 'бА .
Оценим норму матрицы С с использованием условия теоремы
||С|| = ||А-,бА)|.||А-,||.|И < |1 А- ' | | р					|	= 1.
В силу того, что матрица С удовлетворяет условию леммы 2.1, существуй
матрица (Е + С) 1 Поскольку
	A-' =(A (E + C ) ) ' = (E + C )‘V					'

то А ' существует в силу существования матриц А"1 и (Е + С )'1

Теперь определим отклонение возмущенного решения от исходНОГо:

бх = х - х = А '1? - A"'f = А -1? - A 'f + A*‘f - A " ‘f = А"'(? ^ f) + (A"‘ -A ~')f

Учитывая, что 7 - f = 6f,	f = А х, получаем
6x = A '5f + (А-' -A	l)Ax = A l6f + (A lA - A - |A)x = A '^ f + (A-1A -E )x .