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

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

ì a

x

+

a

x

+

...

+

a

x

=

b

ï 11

+

+

+

1 n

n

=

ï a 21 x 1

a 22 x 2

...

a 2 n xn

b 2

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

ï

ï a

x

+

a

m 2

x

+

...

+

a

mn

x

n

=

b

î

m 1 1

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

æ a

a

...

a

ö

æ b

ö

æ

x

ö

ç

1 n ÷

ç

÷

ç

÷

ç a 21

a 22

...

a 2 n ÷

ç b 2

÷

ç x 2

÷

A =ç

...

÷

b =ç

...

÷

x =ç

...

÷

ç

÷

ç

÷

ç

÷

ç

am 2

÷

ç

÷

ç

÷

è am 1

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

+

+

+

1 n

n

=

ï a 21 x 1

a 22 x 2

...

a 2 n xn

b 2

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

ï

ï a

x

+

a

m 2

x

+

...

+

a

mn

x

n

=

b

î

m 1 1

n

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

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

ì x

+ a ¢

x

+

...

+

a ¢

x

n

=

b ¢

ï

1 n

ï

a ¢

x

+

...

+

a ¢

x

n

=

b ¢

2 n

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

ï

ï

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. r 1 (x, y) = max		xi	- yi		Максимальная из сумм модулей коэффициентов при неизвестных в
	1£ i £ n
правой	части	системы, взятых по	строкам, должна быть меньше единицы:
	n
a 1 = max1£ i £ n	å aij <1

j =1

 

n

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

i =1

 

в

правой части

системы,

взятых

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

меньше

единицы:

n

a 2

= max1£ j £ n

å

aij

< 1

i =1

III. r 3 (x, y) =

n

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

å(xi

i =1

неизвестных

в

правой

части

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

меньше

единицы:

n

n

a 3=å å aij 2¹1<1

i =1

j =1

 

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

ì x

= a

x

+

a

x

+

...

+

a

x

+

b

ï 1

1 n

n

ï x 2

= a 21 x 1

+

a 22 x 2

+

...

+

a 2 n xn

+

b 2

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

ï

ï x

n

= a

x

+

a

m 2

x

+

...

+

a

mn

x

n

=

b

n

î

m 1 1

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

 

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

 

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

 

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

 

10БИЛЕТ.Оценка погрешности метода простой итерации. 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

ï y 1 = å a 1 j x j + b 1

ï

j =1

ï

n

ï y 2

= a 21 y 1 + å a 2 j x j + b 2

ï

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	÷
è	ø	è	ø

Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв в качестве метрики, используемой в программе, r 1 (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