УП_Вычисл_матем_Кузина-Кошев

	Решение.		1	0,99
	Матрица коэффициентов					; вектор свободных членов
		A
			0,99	0,98

1,99				1
b		, точное решение системы x			.
1,97			cond1 A	1
Используя функцию				системы Mathcad, вычислим число

обусловленности СЛАУ: cond A 39600 1.

0,000097

Внесем небольшую ошибку в правую часть системы b .

0,000106

Система примет вид

x	0,99x					1,989903;
1				2			1,970106.
0,99x1 0,98x2
Найдя ее новое решение		x				3		, можем оценить абсолютную
					1,0203
погрешность решения x		2
					.
	2,0203

Этот пример наглядно демонстрирует, как при большом значении cond A небольшие ошибки в правой части системы способны исказить

решение СЛАУ до неприемлемой степени.

Контрольные вопросы и задания

1.Что такое матрица? Приведите примеры треугольной, ленточной, диагональной, единичной матриц.

2.Какие функции MS Excel используются при решении СЛАУ прямыми методами?

3.Какая система уравнений называется однородной, неособенной, невырожденной, недоопределенной?

4.Как вычислить скалярное и векторное произведения двух векторов?

5.Как можно определить норму матрицы? Чему равна норма единичного вектора?

6.Чтотакоесобственныезначенияматрицы, сингулярныечисламатрицы?

7.Как вычисляется квадратичная форма матрицы? Какая квадратичная форма матрицы считается положительно определенной?

8.Почему один из прямых методов решения СЛАУ называется методом LU-разложения?

9.На что влияет число обусловленности СЛАУ?

10.От чего зависит точность решения СЛАУ?

51

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

3.1. Общие сведения

Идея всех итерационных методов решения СЛАУ состоит в том, чтобы,

задав некоторое начальное приближение к решению x(0) Rn , последовательно уточнять его, определяя последующие приближения

x 1 , x 2 , ..., x k , x k 1 ... При этом каждое x k 1 выражается через x k , x k 1 ,

x k 2 … с помощью формул, соответствующих методу решения.

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

приближений определяется через	предыдущий x k 1 f (x k ) ,		то метод
называется одношаговым или двухслойным.
Если x k 1 вычисляется	по	двум предыдущим	итерациям
x k 1 f (x k , x k 1 ) , то имеем двухшаговый, или трехслойный, метод.
Каноническая формула одношаговых итерационных методов записы-
вается следующим образом:
B x k 1 x k		Ax k b ,	(17)
(k 1)

гдеВ– некоторая матрица размера n n , для которой существует обратная;

А – матрица коэффициентов СЛАУ ( A An n ); k – номер итерации;

(k 1) – итерационный параметр, причем (k 1) 0 .

Если B E – единичная матрица, то метод называется явным. Явная схема имеет вид:

x k 1 x k	Ax	k	b
(k 1)
или

x k 1 x k (k 1) Ax k b .

Вобщемслучае B E , идлянахождения x k 1 используетсяследующая система уравнений:

Bx k 1 Bx k (k ) (Ax k b).

Такой метод определения x k 1 называется неявной схемой.

Естественно, решение системы уравнений для нахождения x k 1 должно быть достаточно простым.

52

Точность решения СЛАУ – это мера отклонения вектора x k от вектора x* , где x* – точное решение.

Пусть z k x k x* , тогда, подставляя выражение для z k в формулу (17), отображающую канонический вид итерационного метода, получим:

z k 1 z k

B (k ) Az k 0 .

Итерационный метод сходится, если норма вектора z k стремится к 0 при k , т.е. z k 0, k .

Обозначим m – номер итерации, для которой относительное отличие решения, полученного численным методом, от точного решения задачи не больше, чем некоторое заранее заданное малое число :

x m x* x 0 x* .

Обозначим g 0 – общее число арифметических операций для одной

итерации решения.

Тогда Q( ) mg0 определяет количество арифметических операций,

необходимых для совершения m итераций.

Задача состоит в том, чтобы выбрать итерационный метод решения, т.е.

матрицу B и последовательность (k ) таким образом, чтобы минимизировать число Q( ) .

3.2. Метод простой итерации

Рассмотрим итерационный процесс решения СЛАУ (17), когда B E ,

(k 1) .

Вразвернутой форме получим явную двухслойную (одношаговую)

схему:

k 1

k

n

k

a

x

b

.

xi

xi

ij

j

i

j 1

Существуют и другие варианты метода простой итерации. Наиболее распространенная форма записи метода выглядит следующим образом:

		1		n
	xi k 1			aij x jk bi .		(18)
		aii		j 1
				j i

Преобразуем эту форму записи к общему виду.

53

Запишем сумму в матричной форме:

n		n
aij xjk 1 aij xi k aii xi k Ax k i Dx k i ;
j 1		j 1
j i
здесь D (aij ij )	–	диагональная матрица с диагональными элемен-
		тами aii ;
ij	–	символ Кронекера,
		1	при i j,
		ij	при i j.
		0

Тогда из формулы (18) получим:

aii xi k 1 bi Ax k i Dx k i ;

Dx k 1 i bi Ax k i Dx k i .

Следовательно, общую схему можно записать в виде

D x k 1 x k	Ax k b,	1.

Метод простой итерации в такой форме записи представляет собой формально неявную схему, но поскольку D является диагональной

матрицей, то x k 1 можно явно выразить через x k .

3.3. Метод Зейделя

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

a x

a x

2

....

a

x

n

b ;

11 1

12

1n

1

a21 x1 a22 x2 ...

a2n xn b2 ;

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

a

x

a

n2

x

2

...

a

nn

x

n

b .

n1 1

n

54

Представим эту систему в следующей форме:

			1						n
x1
			a11			aij x j					b1 ;
									j 2
.......... .......... .......... .......
			1
									n
xi								aij x j		bi ;
			aii
								j 1
					i				j
.......... .......... .......... .......
				1				n 1
xn									aij x j		bn .
				ann
									j 1

Построим итерационную схему по методу Зейделя:

k 1

1

n

k

x1

( aij x j

b1 );

a11

j 2

k 1

1

k 1

n

k

x2

(a21 x1

aij x j

b2 );

a22

j 3

..........

..........

..........

..........

..........

....

1

i 1

n

xi k 1

( aij x jk 1 aij x jk bi );

aii

j 1

j i 1

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

1

n 1

xnk 1

( aij x jk

1 bn ).

a

nn

j 1

Вобщем виде i-е уравнение для схемы метода Зейделя можно записать

ввиде

i	n
aij x jk 1 aij x jk bi .		(19)
j 1	j i 1

Каноническая форма записи для метода Зейделя выражается следующим соотношением:

(A D) x k 1 x k	Ax k b,	1,
A A D A ,		(20)

где D, A , A – соответственно диагональная, поддиагональная и наддиагональная матрицы.

55

3.4. Метод релаксации (модификация метода Зейделя для ускорения сходимости)

Рассмотрим метод, представленный следующей канонической формой:

D A x k 1

x k

Ax k

b,

.

Перейдем от канонической формы к вычислительной схеме:

1

k 1

1

k

k

D A

x

D A

x

Ax

b ;

1

Dx k 1

A x k 1

1

Dx k

A x k Ax k b;

1

Dx k 1

1

Dx k

b A x k 1 A x k Dx k ;

Dx k 1

Dx k b A x k 1 A D x k .

Выпишем i-e уравнение:

k 1

k

i 1

k 1

n

k

aii xi

aii xi

bi

aij x j

aij x j

,

или

j 1

j i

k 1

k

i 1

k 1

n

k

xi

xi

bi aij xj

aij xj

, 0

2.

(21)

a

j 1

j i

ii

Если 0 1, то имеем метод нижней релаксации; если 1 2 – метод верхней релаксации.

3.4. Вопросы сходимости стационарных итерационных методов

Метод называется стационарным, когда компоненты матрицы B и итерационный параметр не зависят от номера итерации k.

Справедлива следующая теорема сходимости итерационных методов решения СЛАУ.

	Для	того чтобы				стационарный итерационный процесс
B	x k 1	x k	Ax k b	решения системы Ax b был сходящимся:
		τ
				z k		0, k , z k x k x* ,

56

необходимо, чтобы матрица А была симметрической положительной матрицей A AT , A 0 и выполнялось условие

B 2 A 0,

то есть чтобы матрица B 2 A была положительно определенной.

Рассмотрим схему решения вопросов сходимости на примере метода простой итерации, причем будем считать, что А – симметрическая положительная матрица:

x k 1 x k

k

T

E

Ax

b,

A A , A 0.

A

Можно доказать, что

A

E , т.е. матрица E

положительно опре-

A

A

делена и, следовательно,

справедливо

неравенство

E

A

A

A.

2

A

2

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

A

1

A

A 0.

A

2

A

2

Так как А – симметрическая положительная матрица, то необходимо,

чтобы коэффициент

1

был больше нуля или

2

. Это и будет

A

2

A

условием сходимости метода простой итерации.

Если в канонической форме записи итерационного метода принять 1 и B D , то можно доказать другую теорему сходимости метода простой итерации (метода Зейделя и метода релаксации), которая не требует симметричности и положительности матрицы коэффициентов, но требует выполнения условия преобладания диагональных элементов.

Для формулировки теоремы приведем систему Ax b к виду x A x ,

где – столбец свободных членов.

Тогда итерационная схема будет выглядеть следующим образом:

x k 1 A x k .

Имеет место следующая теорема.

57

Для СЛАУ вида x A x метод простой итерации сходится к

решению со скоростью геометрической прогрессии со знаменателем g, если A g 1.

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

Пусть

*

–

точное решение,

тогда

x

*

*

,

и можно записать

x

A x

равенство

x

*

x

k 1

*

x

k

)

или z

k 1

k

. По одному из свойств

A (x

A z

нормы получаем:

z

k 1

z

k

или

z

k 1

g

z

k

. Так как g 1

и

A

каждое последующее

приближение по

норме

меньше предыдущего

в

1g раз, то теорема доказана.

Справедливо также утверждение о том, что любую систему вида

Ax f можно привести к эквивалентной системе вида x A x , для

которой выполняются условия последней теоремы сходимости.

Докажем это утверждение.

Рассмотрим систему Ax f , где А – неособенная матрица, т.е. A 0,

и существует обратная матрица А-1.

Рассмотрим матрицу A 1 , где n n ij – матрица, у которой элементы ij – малые числа. Умножим обе части исходной системы на матрицу A 1 :

A 1 Ax A 1 f ; A 1 Ax Ax A 1 f ; x Ax A 1 f.

Получим систему		где		A,	A	1	f.	Следо-
	x A x ,		A

вательно, в силу того что элементы ij – малые числа, элементы матрицыA также малые числа, и их всегда можно сделать такими, чтобы выполнялось условие сходимости A g 1.

Пример 2 2 .

Решить СЛАУ итерационным методом средствами MS Excel

31x1 10x2 5x3 31;10x1 5x2 31x3 5;5x1 31x2 10x3 26.

58

Решение.

Приведем систему к сходящемуся виду. Методы простой итерации, Зейделя и релаксации являются сходящимися, если выполняется условие

n

aii

aij

:

a11

a12

a13

,

a22

a21

a23

,

a33

a31

a32

.

i 1

Поменяв местами строки, получим матрицу с диагональным преобладанием элементов1:

31x1 10x2 5x3 31;5x1 31x2 10x3 26;10x1 5x2 31x3 5.

Полученную матрицу коэффициентов вводим в ячейки B1-D3, столбец свободных членов – в ячейки G1-G3 (рис. 9, 10).

Итерационный метод решения в MS Excel реализован в надстройке «Поиск решения»2. В этом случае каждое уравнение должно быть записано в одной из ячеек как формула для вычисления правой части (рис. 10).

Для вычисления значений правых частей используются произвольно выбранные начальные значения вектора неизвестных x.

Эти значения заданы в ячейках В7-В9 и не изменяются, а также в ячейках С7-С9, содержимое которых используется в формулах для вычисления значений правых частей и уточняются в ходе итерационной процедуры для получения их требуемых значений (рис. 9).

Вызываем процедуру «Поиск решения» и задаем параметры.

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

2Надстройку «Поиск решения» необходимо активизировать, если она еще не подключена. Для этого необходимооткрытьзакладку«Файл» и, нажавнакнопку«Параметры», выбратькатегории«Надстройки», затем перейти в «Надстройки Excel», выбрать «Поиск решения», поставить на ней флажок. После чего она переместится в список активных надстроек, и в меню «Данные» появится соответствующая кнопка.

59

Рис. 9. Подготовка к решению СЛАУ итерационным методом в MS Excel

Однаизтакихячеек(например, F7) используетсякакцелеваяячейка. На панели процедуры поиска решения требуем установить в ней истинное значение правой части (для нашего примера должно быть 31) за счет подбора значений искомого вектора. Две другие ячейки с формулами (F8 и F9) используются как ограничения (требуем установить в них истинные значения правых частей: –26 и 5 соответственно).

В результате получено следующее решение: x1 =1,34683619; x2 = –1,02093964; x3 = –0,10850531. Решение СЛАУ представлено на рис. 10.

Пример решения этой системы уравнений в среде MathCAD различными итерационными методами (простых итераций, Зейделя, верхней и нижней релаксаций) и с помощью встроенной функции приведен авторами в лабораторном практикуме (см. пример 3, [21]).

60