part2 / vm

	E B 1				E B B2 Bn				E				B				B		2	1 2	1	.
																					1

Из этой оценки немедленно следует сходимость ряда и, следовательно,

существование обратной матрицы (E−B)−1. Для матрицы (E+B)−1 лемма также справедлива и доказывается полностью аналогично.

Оценка влияния погрешности всех начальных данных на погрешность решения также может быть сделана при помощи числа обусловленности. А

именно, пусть матрица A, также как и правая часть b, известна с некоторой погрешностью ∆A. В такой ситуации эффективная оценка погрешности решения возможна только при условии

1 A A 0, (2.13)

которое мы будем предполагать выполненным. Система уравнений, которая

реально решается вместо системы (2.10) имеет вид

A A (x x) b b. (2.14)

С учетом (2.10) она превращается в уравнение относительно ∆x:

A A x b Ax. (2.15)

Как следует из только что доказано леммы, при выполнении условия

(2.13) матрица системы (2.15) имеет обратную (E+A−1∆A)−1A−1, норма которой

допускает оценку

E A 1 A 1 A 1

A 1

A 1

.

A 1 A

1 A A

1

Тогда можно записать

x x

1

b

A

x

A 1

A

b

E A

1

A A

1

x

x

1 A A

x

A

A .

A

С учетом очевидного неравенства ||b||≤||A||∙||x|| окончательно получаем

	A
x	1 A A b A . (2.16)

Таким образом, мы получили формулу для оценивания влияния неустранимой погрешности начальных данных, в которую входят лишь число обусловленности матрицы и относительные погрешности матрицы A и правой

21

части b. Формула (2.16) является также полезной и при определении вычислительной погрешности, поскольку погрешность округлений при арифметических операциях с матричными элементами часто можно пересчитать в погрешность начальных данных.

В заключение отметим, что иногда можно найти число обусловленности

ν(A) не вычисляя обратной матрицы и ее нормы. Так для симметричных матриц число обусловленности, определенное по норме ||A||2 есть отношение максимального к минимальному по модулю собственному числу матрицы A:

A max A .

min A

Способ определения только этих двух чисел будет изложен в разделе,

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

является не строгим.

2.2 Прямые методы решения систем алгебраических уравнений

Способы решения систем линейных уравнений в основном разделяются на две группы. К первой группе относятся точные методы, представляющие собой конечные алгоритмы для вычисления корней системы (таковы, например,

правило Крамера, метод Гаусса, метод главных элементов, разложение и др.).

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

Точные (прямые) методы решения систем алгебраических уравнений используются обычно для сравнительно небольших (n<200) систем с плотно

22

заполненной матрицей и неблизким к нулю определителем. Эффективность прямого метода зависит от числа арифметических операций, необходимых для решения поставленных задач. Так в общем случае вычисление определителя порядка n (без использования специальных приемов) требует (n−1)n!

умножений и n!−1 сложений, т.е. общее число арифметических операций равно

n n! 1.

Общее число операций для вычисления обратной матрицы равно

n2 n! 1.

Рассмотрим задачу нахождения решения системы алгебраических уравнений общего вида; т.е. нахождение x1, x2,…,xn по заданным aij и bi

( i, j 1, n ):

							a11x1 a12 x2 a1n xn b1 ,
							a21x1 a22 x2 a2n xn b2
																							,
																							. (2.17)
							a	x a			n2	x	2	a		nn		x		n	b		.
								n1 1														n
Систему (2.17) запишем в матричном виде
													Ax b, (2.18)
где A a	ij				Rn n		– данная матица; x – искомый вектор (x																	, x , …, x )T; b=(b ,
		i, j 1,n																					1		2	n	1
b2, …, bn)T – вектор с компонентами bi.
Рассмотрим векторы в пространстве Rn:
						1			0								0								0
						0		1									0								0
												, ek
			e1			0	, e2		0	,					1				k				я строка, en		0	.
						0			0								0								0
						0			0								0								1

Система векторов ek Rn образуют базис в пространстве Rn, так как это ортонормированная система линейно независимых векторов. Действительно, из

n

равенства 0 i ei 1 , , n T следует тотчас γi≡0 для любого i 1, n . Любой

i 1

23

вектор x может быть представлен в виде линейной комбинации базисных векторов ek:

		x
			1
	n	x2
	x xk ek			.
	k 1
		xn

Прежде, чем применить прямые методы к матрице общего вида,

рассмотрим решение уравнения Ax=b с матрицей специального вида: с нижней и верхней треугольной матрицами.

Прямая подстановка. Рассмотрим уравнение вида (2.18) Lx=b, но матрица L={lij}; lij=0, j>i – нижняя треугольная, т.е.

l11x1

b1

l21x1

l22 x2

b2

. (2.19)

l

x

l

n2

x

2

l

nn

x

n

b

n1 1

n

Для того, чтобы решить систему Lx=b с произвольной правой частью необходимо и достаточно, чтобы определитель матрицы L, detL≠0, т. е. lii≠0,

i 1, n .

Итак, решение системы (2.19) имеет вид:

x

b1

, x

b2 l21x1

2

1

l11

l22

................................

i 1

bi

lij x j

xi

j 1

. (2.20)

lii

.................................

n 1

bn

lnj x j

j 1

x

n

l

nn

Обратная подстановка. Аналогично решается система с верхней диагональной матрицей U={uij}; uij=0, j>i

Ux=b.

Решение может быть записано в виде x=U−1b или

24

n

bn

bn 1 un 1,1 xn

b1 u1 j

x j

x

, x

,.............,

x

j 2

. (2.21)

n

n 1

unn

un 1,n 1

1

u11

Перейдем непосредственно к методу LU – разложений матрицы A.

LU – разложение матрицы. Рассмотрим матрицу

	1		0		0			1
		0	1		0
E α eT										0,	0, ,
k
		0	0	1					n

Если вместо α выбрать вектор α(k):

	1		0		1	0
		0	1		2	0
1, ,	0						.
	0		0	1 k		0
		0	0		n	1

k й столбец

	0
	0
α (k )		,
lk 1,k
	ln,k

то матрица E α(k ) eTk станет единичной нижней треугольной матрицей вида:

		1			0		0
			0		1		0
M	k				lk 1,k			.
		0					0		(2.22)
			0		lnk		1

k й столбец

Матрица Mk называется матрицей Гаусса; вектор α(k) – вектором Гаусса;

коэффициенты lk+1,k, …, lnk – множителями Гаусса. Отметим, что определитель detMk=1 и

Mk1 E α(k )eTk .

Теорема. Пусть M1, M2, …, Mk – матрицы Гаусса (2.22), k≤n, тогда

25

x Rn , тогда если

1

0

0

0

l21

1

0

0

k

k

Mi 1 M1 1

M 21

M k1

E α(i) eTi

.

i 1

i 1

lk1

lk 2

1

0

ln2 lnk

1

ln1

Доказательство теоремы проверяется непосредственным перемножением

M 1

, i 1, 2, , k.

i

Рассмотрим далее вектор

		x
			1
M k x E α(k ) eTk	x x α(k ) eTk x x xk
		α(k ) xk
		xk 1 xk lk 1,k
				xk lnk
		xn

.

Нетрудно увидеть, что если xk≠0, то можно подобрать lij (j>i, j≠k) так,

чтобы,

		x
			1
		x
M	k	x		k , l		ik
		0
			0

	xi	,	i k 1, , n. (2.23)
	xk

Итак, мы доказали следующее утверждение.

Пусть

1.xk 0 , то Mk x x ,

2.xk 0 , то существует матрица M k (т.е. коэффициенты lik ) такая, что

справедливо (2.23).
Пусть теперь матрица	A a	ij	a	,a	2	, ,a	q	Rn q ,	M – матрица Гаусса.
			1						k

Тогда произведение матриц

26

a

a

11

1q

A M

akq

M

k

k

a

, M

k

a

2

, , M

k

a

q

ak1

.

1

ak 1,1 ak1 lk 1,1

ak 1,q akq lk 1,k

a

n,1

a

k1

l

nk

a

nq

a

kq

l

nk

Перейдем непосредственно к самому LU – разложению. Пусть матрица

A A(0)

a(0) , ,a(0) . Если a

(0)

0 , то выберем матрицу M так, чтобы

1

n

11

1

a(0)
	11
	0
M1a1(0)
	0

			a(0)
		li1			i 1. (2.24)1
	,		i1	,
			a(0)
			11

Умножая матрицу M1 на матрицу A(0), получим матрицу A(1)=M1A(0)=M1A

вида

	a(0)		a(0)	a	(0)
		11	12	1n
A(1) a1(1)		0	a(1)	a	(1)
	, , a(n1) M1A		11		2n	.
		0	(1)		(1)
			an2	ann

Коэффициенты матрицы A(1) вычисляются по формулам:

			aij(1)	aij(0)			li1aij(0) ,			j 1. (2.25)1
Далее, если a(1)	0		, то M выбираем так, чтобы
22			1
				a (0)
					12
				a(1)						(1)
		M 2a2			22		,	li 2				(2.24)2
					0					(1) , i 2.
			(1)						ai 2
									a22
					0
Поскольку a(1)	0	, то a(2)		M		2	a(1)	a(1)		. Следовательно,
12			1				1	1

						a(0)		a(0)	a(0)
							11	12	13
A(2) a(2)		M					0	a22(1)	a23(1)
	, , a(2)		2	M	1	A	0	0	a (2)
1	n								33
							0	0	an(23)

a(0)

1n

a(1)

2n

a(2)

3n

a(2)

nn

.

Элементы матрицы A(2) вычисляются аналогично коэффициентам матрицы A(1)

27

aij(2) aij(1) li 2 a2(1j) , j 2. (2.25)2

Последний шаг в этой схеме: матрица A(n−1)=Mn−1Mn…M1A – это верхняя треугольная матрица, коэффициенты которой вычисляются так:

aij(n 1)

aij(n 1) li,n 1an(n1,2j) ,

j n 1, (2.25)n–1

a(n 2)

li,n 1

i,n 1

, i n 1. (2.24)n–1

a(n 2)

n 1,n 1

Обозначим матрицу A(n−1)

через

U=Mn−1Mn…M1A

с

коэффициентами

u

ij

a(i 1)

,i 1, , n 1; j i.

Умножая

слева

U на матрицу

L M 1

M 1

M 1

ij

1

2

n 1

получим

L U M1 1 M21 Mn11 Mn 1 Mn M1 A A.

Окончательно мы имеем: M 1	M 1	M 1	U L M	n 1	M	M	A A . Таким
1	2	n 1			n	1

образом

A LU,

где матрицы L={lij} и U={uij} имеют, соответственно, вид нижней и верхней треугольной матриц:

1

L l21

ln1

0		0
1		0
			;
ln2		1

	u		u	u
		11	12		1n
U	0		u11	u2n .
		0	0
				unn

Коэффициенты матрицы L lij ,

lij

0,

j i

вычисляются по формулам (2.24),

lii 1, а

uij 0,

j i определяются

по

формулам

(2.25), если uij aij(i 1) ,

i 1, , n 1;

j i .

akk(k 1)

Итак, если на каждом шаге

0, k 1, n, то можно получить такие

верхнюю U и нижнюю L треугольные матрицы, что A=LU, причем

det(A) u

u

22

u

nn

a(0) a(1)

a(n 1) .

(2.26)

11

11

22

nn

Решение системы линейных алгебраических уравнений методом

LU – разложений.

Рассмотрим решение уравнения (2.18) методом LU – разложений.

28

Первый этап: находим LU – разложение матрицы A по схеме (2.24), (2.25).

Второй этап: запишем уравнение (2.18) в виде Ax=LUx=b; обозначим

Ux=y, тогда решение (2.18) эквивалентно решению системы

Ly b	, (2.27)
Ux y

с треугольными матрицами L и U. По формулам (2.21) мы найдем вектор y, а

затем вектор x по формулам (2.20).

Итак, методом LU – разложений получено решение линейной системы уравнений Ax=b за число арифметических операций порядка O(n3).

Одновременно вычислен определитель det матрицы A (см. формулу (2.26)).

Метод Гаусса с выбором главного (ведущего) элемента.

Пусть дана система линейных уравнений Ax=b, причем у матрицы A

некоторые диагональные элементы либо малы, либо равны нулю. Тогда метод

LU–разложений неприменим в том виде, который изложен выше, и следует подправить схему вычислений так, чтобы все оставалось законным.

Рассмотрим расширенную прямоугольную матрицу (A,b). Выберем ненулевой,

как правило, наибольший по модулю, не принадлежащий столбцу свободных членов элемент apq. Выбор максимального по модулю элемента можно проводить несколькими способами: построчным, постолбцовым выбором, либо поэлементно. Такой элемент apq матрицы A=(A,b)=(aij,ai,n+1), 1≤i, j≤n называется главным элементом.

Вычислим множители Гаусса

lip aiq , i p. (2.28)

a pq

Строка с номером p называется главной. Далее произведем операцию: от каждой неглавной строки вычтем главную, умноженную на соответствующий множитель lip для этой строки. В результате мы получим новую матрицу, у

которой q – столбец состоит из нулей. Отбрасывая этот столбец и главную p –

строку, мы получим матрицу с меньшим числом строк и столбцов на единицу.

29

Над матрицей производим те же операции с выбором главного элемента и строим матрицу A(2) и т.д.

A, A(1),…, A(n–1).

Последняя из этой последовательности матриц представляет собой двучленную матрицу–строку; ее также считаем главной строкой. Для определения неизвестного xi объединяем в систему все главные строки, начиная с последней, входящей в матрицу A(n–1). После надлежащего изменения нумерации неизвестных, получается система с треугольной матрицей, из которой легко шаг за шагом найти неизвестные данной системы Ax=b. Метод главных элементов всегда применим, если det(A)≠0. Сам метод Гаусса является частным случаем метода главных элементов, а схема метода Гаусса получается,

если за главный элемент всегда выбирать левый верхний элемент соответствующей матрицы. Решение уравнения Ax=b сводится к решению уравнения Ux=U1b, где U– верхняя треугольная матрица

u

u

u

11

12

1n

0

u

u

U

11

2n ,

0

0

unn

U b b( 0 ) ,b( 1 ) , ,b(n 1 ) T , где b(i 1)

а

b(i 2)

l

i,i

b(i 2) , i 1, n.

1

1

2

n

i

i

1 i 1

Метод Гаусса вычисления обратной матрицы. Пусть дана неособая

матрица

A a ij ; i, j

.

Для

нахождения

ее

обратной матрицы A−1={xij}

1, n

используем основное соотношение

A A 1 A xij E. (2.29)

Перемножая матрицы A∙A−1 будем иметь n систем уравнений относительно

n2

неизвестных xij

n

aik xkj

ij ,

(i, j 1, 2, , n) , (2.30)

k 1

где

ij

1

, ког да

i j,

i j.

0

, ког да

30