Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема.

Рассмотрим систему m линейных уравнений с n неизвестными:

ìa

x

+

a

x

+

...

+

a

x

=

b

ï 11

+

+

+

1n

n

=

ïa21x1

a22 x2

...

a2n xn

b2

í......................

ï

ïa

x

+

a

m2

x

+

...

+

a

mn

x

n

=

b

î

m1 1

Ее можно записать в матричном виде A x = B, где

æ a

a

...

a

ö

æ b

ö

æ

x

ö

ç

1n ÷

ç

÷

ç

÷

ç a21

a22

...

a2n ÷

ç b2

÷

ç x2

÷

A =ç

...

÷

b =ç

...

÷

x =ç

...

÷

ç

÷

ç

÷

ç

÷

ç

am 2

÷

ç

÷

ç

÷

èam1

amn ø

èbm

ø

è xm ø

Решить СЛУ –значит найти набор таких чисел

уравнения в верные равенства.

СЛУ совместна, если она имеет хотя бы одно решение.

СЛУ несовместна (противоречива), если она не имеет решения.

Совместная СЛУ определенна, если она имеет единственное решение и неопределенна, если более одного решения.

СЛУ имеет единственное решение, если ранг матрицы A равен рангу расширенной матрицы (A|b): rang(A) = rang(A|b).

СЛУ имеет единственное решение, если rang(A) = n и бесконечно много решений, если rang(A) < n.

Если матрица A – квадратная и det(A)¹0, то она называется невырожденной.

СЛУ с n неизвестными, имеющими невырожденную матрицу A, совместна и имеет единственное решение.

«Минусы»

· Требуют приведения к определенному виду

Единичной матрицей Eназывается квадратная матрица,у которой на главнойдиагонали стоят единицы, а на остальных местах – нули.

Обратной матрицей по отношению к матрицеAназывается такая матрицаA^-1,чтоA A^-

¹=A^-1 A = E.

Матрица A^T, полученная перестановкой в матрице A строк со столбцами, называется транспонированной.

Квадратная матрица симметрична, если A=A^T.

Все численные методы решения СЛУ можно разделить на прямые, итерационные и вероятностные.

Прямые методы дают решение системы за конечное число арифметических операций.

Например, метод Крамера (метод определителей),

метод Гаусса (метод последовательного исключения неизвестных).

	«Плюсы»	«Минусы»
·	Просты	· Достаточно громоздкие вычисления
·	Универсальны
· Не требуют приведения к
определенному виду

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

Например, метод простой итерации, метод Зейделя.

«Плюсы»

· Требуют мало места в памяти · Самоисправляющиеся методы

Вероятностные методы носят общее название–методы Монте-Карло.

Пусть получено решение СЛУ:	~	. Рассматривается вектор невязки					~	. Если
				e
x	e = b - Ax

велико, то где-то допущена ошибка, если e мало, то ошибка отсутствует.

Метод Гаусса.

Метод Гаусса относится к точным методам, однако вычислительная ошибка присутствует всегда (ошибка округления и, возможно, ошибка исходных данных). Рассмотрим систему m линейных уравнений с n неизвестными:

ìa

x

+

a

x

+

...

+

a

x

=

b

ï 11

+

+

+

1n

n

=

ïa21x1

a22 x2

...

a2n xn

b2

í......................

ï

ïa

x

+

a

m2

x

+

...

+

a

mn

x

n

=

b

î

m1 1

n

Алгоритм состоит из двух этапов.

I. Прямой ход – приведение матрицы к треугольному виду (сверху вниз):

ìx

+ a¢

x

+

...

+

a¢

x

n

=

b¢

ï

1n

ï

a¢

x

+

...

+

a¢

x

n

=

b¢

2n

í......................

ï

ï

xn

=

bn¢

î

II. Обратный ход–определение неизвестных(снизу вверх).

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

· столбец контрольных сумм S,

· столбец сточных сумм S.

Контроль в прямом ходе:

· После внесения коэффициентов при неизвестных и свободных членов исходной системы находят контрольные суммы (суммы коэффициентов и свободных членов по строкам) и вносят их в столбец S.

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

· После выполнения каждого преобразования находят строчную сумму результатов и помещают ее в столбец S.

· При отсутствии вычислительных ошибок числа в столбцах S и S должны практически совпадать.

Контроль в обратном ходе:

При безошибочном выполнении вычислений в столбце S должны быть на единицу больше соответствующих значений неизвестных из столбца свободных членов Рассмотрим примеры решения СЛУ методом Гаусса

Разделы	x1		x2	x3	св чл	сумма	S
		3,25	14,52	-1,32	367,58	384,03
		32,02	-4,36	5,73	516,91	550,3
А		7,21	11,92	-41,46	-886,32	-908,65
			4,4677	-0,4062	113,1015	118,1631	118,163
			-147,4158	18,7365	-3104,6000	-3233,2825	-3233,2793
			-20,2921	-38,5313	-1701,7818	-1760,606	-1760,6052
А1				-0,1271	21,0602	21,9331	21,9331
				-41,1104	-1274,4261	-1315,5373	-1315,5365
А2					31,0001	32,0001	32,0001
					31,0001	32,0001
В					25,0003	26,0003
					13,9999

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

Первая половина в билете №9.

Функцию r(x,y), определяющую расстояние между точками x и y множества X назовем метрикой, если

1) r(x,y)³0

2) r(x,y)=0 • x=y

3) r(x,y)= r(y,x)

4) r(x,y)£ r(x,z)+ r(z,y).

Множество X с введенной метрикой r назовем метрическим пространством. Последовательность точек метрического пространства называется фундаментальной,

если ("e > 0)($N )("m, n > N )[r(x_m , x_n ) < e].

Пространство называется полным, если в нем любая фундаментальная последовательность сходится.

Отображение F пространства E в себя называется сжимающим, если

($a, 0 < a <1)("x, y Ï E)[r(F(x), F( y)) £ a r(x, y)]

x – неподвижная точка, если F(x)=x.

Оценка расстояния между неподвижной точкой и приближением x^(k) производится следующим образом:

r(x, x(k ))£		a k	r(x(0), x(k ))или r(x, x(k ))£		a	r(x(k -1) , x(k ) ).
1 -a	1 -a

Таким образом, чтобы погрешность вычислений была меньше наперед заданного числа

ε, достаточно потребовать r(x(k -1) , x(k ) )£ e	1 -a	.
							a
Рассмотрим 3 типа метрики.
Пусть x(x1,x2,…,xn) и y(y1,y2,…,yn) – две точки n-мерного пространства.
I. r1 (x, y) = max		xi	- yi		Максимальная из сумм модулей коэффициентов при неизвестных в
	1£i£n
правой	части	системы, взятых по	строкам, должна быть меньше единицы:
	n
a1 = max1£i£n	å aij <1

j=1

n

II. r₂₁ (x, y) = å x_i - y_i Максимальная из сумм модулей коэффициентов при неизвестных

i=1

в

правой части

системы,

взятых

по столбцам, должна быть

меньше

единицы:

n

a2

= max1£j£n

å

aij

< 1

i=1

III. r3 (x, y) =

n

- yi )2Корень квадратный из суммы квадратов коэффициентов при

å(xi

i=1

неизвестных

в

правой

части

системы, должен быть

меньше

единицы:

n

n

a3=å åaij2¹1<1

i=1

j =1

СЛУ преобразуется таким образом, чтобы по одной из метрик выполнялось α < 1.

ìx

= a

x

+

a

x

+

...

+

a

x

+

b

ï 1

1n

n

ïx2

= a21x1

+

a22 x2

+

...

+

a2n xn

+

b2

í......................

ï

ïx

n

= a

x

+

a

m2

x

+

...

+

a

mn

x

n

=

b

n

î

m1 1

При этом СЛУ задает отображение, которое при α < 1 будет сжимающим. Значит, взяв любую точку в качестве начального приближения, получим последовательность точек, которая будет сходиться к неподвижной точке; это точка и будет решением системы. Чтобы привести СЛУ к итерационному виду нужно:

1) с помощью равносильных преобразований привести систему к виду с преобладающими диагональными коэффициентами (по абсолютной величине);

2) разделить все уравнения на соответствующие диагональные коэффициенты и выразить из каждого уравнения неизвестное с коэффициентом, равным единице.

Если для этой системы α < 1, то система задает сжимающее отображение.

11. Оценка погрешности метода простой итерации. x=Bx+d;

Пусть ||B||<1, имеем:

x*=Bx*+d;

_x(k)_=Bx(k-1)_+d;

x*=x^(k)+B(x*–x^(k-1));

Вычтем из каждой части x^(k-1):

_x*–x(k-1)_=x(k)_–x(k-1)_+B(x*–x(k-1)_);

||x*–x^(k-1)||≤

||x^(k)–x^(k-1)||+||B||•||x*–x^(k-1)||;

||x*–x^(k-1)||•(1–||B||)≤

||x^(k)–x^(k-1)||;

||x*–x^(k-1)||≤

||x^(k)–x^(k-1)||/(1–||B||);

Кроме того:

||x*–x^(k)||≤||B||•||x*–x^(k-1)||;

||x*–x^(k)||≤(||B||/(1–||B||))•||x^(k)–x^(k-1)||; (1)–Разность между точным решением иk-ымприближением.

Пусть требуется найти решение с точностью ε. Из (1) имеем:

(||B||/(1–||B||))•||x^(k)–x^(k-1)||<ε;

Достаточно выполнение условия:

||x^(k)–x^(k-1)||≤((1–||B||)•ε)/||B||;–критерий выхода.

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

При решении СЛУ методом простой итерации каждый шаг итерационного процесса состоит в переходе от уже имеющегося приближения значений неизвестных к новому приближению.

Основная идея метода Зейделя состоит в том, что на каждом шаге итерационного процесса при вычислении значений y_i учитываются уже полученные значения y₁, y₂,…,y_i-

1.

I. Условие α<1 является достаточным для сходимости итерационного процесса метода Зейделя. Причем метод Зейделя обеспечивает более быструю сходимость, чем метод простой итерации.

Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв за основу метод итерации)

program slu_zejdel1;

{ *** с использованием евклидовой метрики *** } var p,b,x1,x2,x3,y1,y2,y3,a,e: real;

N: integer;

begin

write('Введите x1, x2, x3 : '); readln(x1,x2,x3);

write('Введите A, E : '); readln(a,e);

b:=e*(1-a)/a;

N:=0; {число итераций}

repeat

N:=N+1;

y1:= 0.1362*x2-0.1790*x3+16.1433;

y2:=-0.2238*y1+0.0909*x3+25.3154;

y3:= 0.1739*y1+0.2875*y2+21.3777;

p:=sqrt(sqr(x1-y1)+sqr(x2-y2)+sqr(x3-y3));

x1:=y1; x2:=y2; x3:=y3;

until p<=b;

writeln('x1 = ',x1:8:6);

writeln('x2 = ',x2:8:6);

writeln('x3 = ',x3:8:6);

writeln('Число итераций - N = ',N);

readln

end.

Введите x1, x2, x3 : 0 0 0

Введите A, E : 0.2218 0.0001

x1 = 13.999370

x2 = 25.000219

x3 = 30.999753

Число итераций - N=6

Как видно из примера, по сравнению с методом итераций решение получено за меньшее количество шагов.

II. Рассмотрим практическую схему преобразования исходной СЛУ, гарантирующую сходимость метода Зейделя.

Пусть система записана в матричной форме: Ax=b.

Умножим левую и правую части слева на матрицу A^T: A^TAx= A^T b.

Обозначим : A^TA=C, A^T b=d.

Преобразованная система станет иметь вид: Cx=d. Такую систему называют нормальной:

· матрица C является симметричной;

· все элементы главной диагонали матрицы C положительны. Нормальную систему легко привести к виду:

xi =åaij x j

+ b j ,

(i = 1,2,¼, n) , где ai = -

cij

( j ¹ i)

и bi

=

di

.

cii

j ¹i

cii

Вычислительные формулы имеют вид:

ì

n

ïy1 = åa1 j x j + b1

ï

j =1

ï

n

ïy2

= a21 y1 + åa2 j x j + b2

ï

j =1

ï

ï...

í

i-1

n

ï

=åaij y j +åaij x j + bi

ïyi

ï

j =1

j =i

ï...

ï

n-1

ïyn =åanj y j + ann xn + bn

î

ï

j =1

Рассмотрим на примере.

æ 3,25

14,52

-1,32 ö

æ

367,58

ö

æ 3,25

32,02

7,21

ö

ç

- 4,36

÷

ç

÷

ç

- 4,36

÷

A = ç

32,02

5,73

÷

b = ç

516,91

÷

AT = ç

14,52

11,92

÷

ç

7,21

11,92

- 41,46

÷

ç

- 886,32

÷

ç

-1,32

5,73

- 41,46

÷

è

ø

è

ø

è

ø

æ

1087,827

- 6,474

-119,742 ö

æ

11355,726 ö

ç

- 6,474

- 538,3524

÷

D =

ç

- 7481,4004

÷

C = AT A = ç

371,9264

÷

AT b = ç

÷

ç

-119,742

- 538,3524

1753,5069

÷

ç

39223,5159

÷

è

ø

è

ø

После деления на диагональные элементы получим:

æ		- 0,0060	- 0,1101ö	æ	10,4389 ö
ç	- 0,0174		-1,4475	÷	ç		÷
a = ç		÷	b = ç	- 20,1153÷
ç	- 0,0683	- 0,3070		÷	ç	22,3686	÷
è	ø	è	ø

Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв в качестве метрики, используемой в программе, r1 (x, y) = max xi - yi ).

1£i£n

program slu_zejdel2;

var x1,y1,x2,y2,x3,y3,e,a,b,c: real;

N: integer;

begin

write('Введите X1, X2, X3 - '); readln(x1,x2,x3); write('Введите погрешность Е - '); readln(e); N:=0; {число итераций}

repeat

N:=N+1;

y1:= 0.0060*x2+0.1101*x3+10.4389;

y2:= 0.0174*y1+1.4475*x3-20.1153;

y3:= 0.0683*y1+0.3070*y2+22.3686;

a:=abs(y1-x1); b:=abs(y2-x2); c:=abs(y3-x3);

if a<b then a:=b;

if a<c then a:=c;

x1:=y1; x2:=y2; x3:=y3;

until a<=e;

writeln('X1 = ',x1:11:8);

writeln('X2 = ',x2:11:8);

writeln('X3 = ',x3:11:8);

writeln('Число итераций - N = ',N);

readln

end.

Введите X1, X2, X3 - 0 0 0

Введите погрешность Е - .0001

X1 = 14.00204110

X2 = 25.00128107

X3 = 31.00033269

Число итераций - N = 18