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

Из задач строительства, картографии и баллистики выросла аналитическая геометри
В этой науке мы сталкиваемся с матрицами и операциями над ними:
a,b ,c :
Ex.1. Объем параллелограмма, построенного на

?

?

V ? a b c ?a ?(b ?c )
ax
V ? ay
В правой декартовой прямоугольной системе координат
az

bx
by
bz

cx
cy
cz

- определитель!

Ex.2. Пересечение двух прямых на плоскости:? a11 ?x1 ? a12 ?x 2 ?b1

?
? a 21 ?x1 ? a 22 ?x 2 ?b2

Ex.3. Общее уравнение поверхности второго порядка:
a11 x 2 ? a 22 y 2 ? a33 z 2 ? 2a12 xy ? 2a13 xz ? 2a 23 yz ? 2a14 x ? 2a 24 y ? 2a34 z ? a 44 ?0

где

a11 x 2 ? a 22 y 2 ? a 33 z 2 ? 2a12 xy ? 2a13 xz ? 2a 23 yz ?F(x, y, z)

– характеристическая квадратичная форма.

Для любой поверхности второго порядка можно определить:
-диаметральная плоскость этой поверхности, сопряженная параллельным хордам –
геометрическое место середин этих хорд;
-диаметр, сопряженный семейству плоскостей, параллельных сопряженным хордам двух
различных диаметральных плоскостей – прямая, по которой пересекаются две
диаметральные плоскости;
Перенос + поворот осей координат:
? x ?t11 ( x ? x0 ) ? t 21 ( y ? y 0 ) ? t 31 ( z ? z 0 )
?
? y ?t12 ( x ? x 0 ) ? t 22 ( y ? y 0 ) ? t 32 ( z ? z 0 )
? z ?t ( x ? x ) ? t ( y ? y ) ? t ( z ? z )
13
0
23
0
33
0
?

t11 , t 21 , t 31 - направляющие cos новых осей
( x ? x0 ), ( y ? y 0 ), ( z ? z 0 )
a11
? D ? a 21
a31

a12
a 22
a32

a13
a 23
a33

- новый центр координат
- инвариант относительно переноса и поворота

aik ?a ki

- при D ?0 все диаметры пересекаются в одной точке – центре поверхности:
? a11 x0 ? a12 y0 ? a13 z0 ?? a14
?
? a21 x0 ? a22 y0 ? a23 z0 ?? a24
? a x ? a y ? a z ?? a
34
? 31 0 32 0 33 0

координаты центра

!(необходимо решить систему линейных уравнений)

Что такое “определитель”?
Перестановка (подстановка): замена каждого элемента a ? ? другим элементом ? (a) ? ?,
при этом должны получаться все элементы ? и только один раз; т.е. это взаимно
однозначное отображение множества на себя.
? - некоторое конечное множество (далее рассматриваем только такие).

Если на множестве определено старшинство элементов, то:
Существует инверсия перестановки – нарушение порядка при перестановке.
Число инверсий – количество (число) нарушений порядка при перестановке.
Четность перестановки – четность числа инверсий.
С помощью этих понятий вводится понятие “определитель”:

A
n ?n

n – порядок квадратной матрицы
n!

det A ? A ?? ?a1? a 2 ? ? a n?

- многочлен из элементов, каждое слагаемое которого является произведением n
элементов, взятых по одному из каждой строки и каждого столбца; т.е. это сумма по
всем перестановкам
?1 2? n ?
??
??
?? ? ?? ?

Знак слагаемого “+ “, если перестановка четная.

Свойства определителя:
1) A ? AT
~
2) A ?? A
3) A ?0

~
A

, если

~
4) A ?q A

получается из A переменой местами двух строк (столбцов)

?

? a1 j
?
??
?

?
?
?
?

?
?
?
?

k ? j : aij ?q ?aik (пропорциональность строк/столбцов)

q – общий множитель какой-либо строки/столбца.

a11 ? a~11 a21 ? a~21 ? an1 ? a~n1
a12
a22
?
an 2
5)
?
?
?
?

? aij ? q ?akj
6) A ??
?

? a1k
?
??
?

?
?

=

a11 a 21 ? a n1 a~11
a12 a 22 ? a n 2 a12
?
? ? ? ? ?

a~21 ? a~n1
a 22 ? a n 2
? ? ?

-определитель не изменится, если к одной строке/столбцу

прибавить соответствующие элементы другой строки/столбца, умноженные на
произвольный коэффициент.
n
7) Если aik ?0 k
Частный случай теоремы Лапласа о вычислении определителя:
n

A ?? a i1 Ai1

Ai1 - алгебраическое дополнение элемента ai1

i ?1

Df.
Aij

Aij ?( ? 1) i ? j M ij
- алгебраическое дополнение aij

M ij - минор (n-1)го порядка

Df. Минор k-ого порядка – определитель матрицы, образованной из элементов матрицы,
k
Существует другая задача – решение системы линейных уравнений Ax=b
x-? – эту задачу называют первой задачей линейной алгебры.
Если

A ?0 , то ?! x – решение системы:

~
Ak - замена элементов k-ого столбца на b.
n
~
/* Ak ?? bi Aik
i ?1

xk ?

~
Ak
A

k ?1? n - правило Крамера.

k ?1? n */

Aik - алгебраическое дополнение
2 4
n , n=30 ? ?5,3 ?105 )
(оптимистичная оценка числа операций
3
Еще задачи: A? 1 ? ?
Ax ??x, x ? ? ? ? ? – вторая задача линейной алгебры (поиск собственных значений и

собственных векторов)
Все задачи связаны между собой.

Рассмотрим первую задачу линейной алгебры.
Пересечение двух прямых на плоскости, возможны варианты:
A ?? ?0
A ?0 - неустойчивость к погрешности входных данных,
плохо обусловленная система.
A ?0

A ?0 - необходимый признак обусловленности, но не достаточный

(ex. A ??E

? ? 1 ? A ?? n ? 0)

Число обусловленности:
C ( A) ?

A? 1 b
x

?

A? 1 A x
x

Ax=b
A? 1 ? A

? A? 1 ? A

C ( A) ?1 - хорошая обусловленность
На практике

max
C ( A) ?
min

Погрешность: ?x ? x ? ~
x
Невязка: r ?b ? A~
x

b
x
b
x

? A? 1 ? A

- иногда это произведение называют
числом обусловленности.

Утв.

?x ?0 ? r ?0
Но они не обязательно одновременно малы.
С помощью числа обусловленности можно установить связь ?x и r :
1) A( x ? ?x) ?b ? ?b ? ?x ? A? 1?b
?x ? A? 1
b ? A x

?b ??
?1
? ? ?x ? b ? A ? A
??
?

?x
x

?C ( A)

?b ? x

?

1
x ?b

?b
b

2)( A ? ?A)( x ? ?x) ?b
( A ? ?A) ?x ?? ?A ?x

A?x ?? ?A ?x ? ?A ??x
?x ?? A ? 1 ??A ?x ? A ? 1 ?A ??x ? ?x ? A ? 1 ? ?A ? x ? A ? 1 ? ?A ? ?x

?

?x
x
???

? C ( A)

?A
A

(1 ?

?x
x

)

y

?A
A
A
y
1? y
1
?C ( A)
?
?
?
?1 ?
?
1? y
y
y
A
C ( A) ? ?A
C ( A) ? ?A
A ? C ( A) ? ?A
?x
?A
1
C ( A)
?
?
?
?
?
y
C ( A) ? ?A
x
?A
A
1 ? C ( A)
A

Ax=b
А( n ?n)
~
A ? A - треугольная матрица

Метод Гаусса

? a11
?
?
? 0
?

aii

?0 ?
?
?
ann ??

Замечания:
1) Если элемент на главной диагонали 0, то перестановкой строк его заменяют на ненулевой (ненулевой элемент
всегда найдется, иначе A ?0);
2) Если элемент на главной диагонали мал, то будут велики ошибки округления, поэтому цикл прямого хода
начинают с перестановки на главную диагональ max элемента из исключаемого столбца – метод Гаусса с выбором
главного элемента.
1. Поиск максимального по модулю внедиагонального элемента из A.
2. Перестановка столбцов таким образом, чтобы этот элемент оказался в 1-ом столбце; учет числа
перестановок;
3. Перестановка строк таким образом, чтобы этот элемент оказался в 1-ой строке, на месте (1;1); учет
числа перестановок l;
(1)
(1)
k ?1

А? А
(1)

|A

|?(? 1)

| A|

(1)

4. Для элементов матрицы A aij : i > 1
(1)
a
~
ij
(
2
)
j ?1, n А ? А ( 2)
a~ij ? (1)
ai1
(1)

bj
~
b j( 2) ? (1)
ai1

? a11(1) ? ?
?
?
? 1 ??
? 1 ??
?
?

~ ( 2) ? n (1) ?
| A |??? ? ai1 ??
? i ?1?1
?

( ? 1)

| A (1) |

~ ( 2) ( 2)
A
aij : i > 1
5. Для элементов матрицы
a?

( 2)
ij

?a~

(2)
ij

?(? a~ )
(1)
11

~
b? (j 2 ) ?b j( 2 ) ?(? a~11(1) )

j ?1, n

~
А ( 2) ? А? ( 2)

? a11(1)
? (1)
? ? a11
? ? a (1)
? 11

??
?
??
? ??

? n
~
( 2)
?
| A |??? ? (? a11(1) ) | A ( 2 )
? j ?1

?
| ??
?

6. Для строк матрицы ?(2) выполняем сложение с 1-ой строкой:

aij( 2) ?a? ij( 2 ) ? a?1( 2j )

i>1

| A ( 2 ) |?| A? ( 2 ) |

bi ( 2 ) ?b?i( 2 ) ? b?1( 2)

А? ( 2 ) ? А ( 2)

? a11(1)
?
? 0
? 0
?

:

??
?
??
? ??

7. Уберем 1-ую строку и 1-ый столбец, тем самым понижаем ранг матрицы на 1: n ? n-1

А ( 2) ? А ( 2) :

? a11( 2)
? ( 2)
? a 21
??
?

a12( 2 ) ? ?
?
( 2)
a 22
??
? ? ??

8. Переходим к пункту 1 с матрицей А(2), если в матрице А(2) более одного
элемента, в противном
( 2)
|
A
|
случае – к пункту 9:
| А ( 2 ) |?

(n ? 1) ?(n ? 1)

a11(1)

9. Строим итоговую треугольную матрицу (n Х n) в виде:

? a11(1)
?
? 0
? 0
?

a12(1)
a11(1)
0

? b1(1) ?
? (2) ?
? b2 ? ? ?
???
?
?

n

a13(1) ? ?
?
a12(1) ? ? ??
a11(1) ? ??

| ? |?? aij
i ?1

Связь с определителем А выпишите сами.
10. Находим значения X :

b
Xn ? n
a nm

1
Xj ?
a jj

?
??? b j ?
?

?
?
a
x
?
j1 1 ?
l ?j ?1
?
n

a и b есть элементы итоговых матрицы ?

и столбца

?

Контроль расчетов по методу Гаусса:
Заменяем (x) на (x-1), тогда

~
А ? А ?A

~
B? B

n
~
(bi ?bi ? ? aij )

:

~
Выполняем ход метода Гаусса для В и B .

(*)

j ?1

На каждом этапе свойство (*) В сохраняется.
Гипотеза:

|| z ? z ?||
|| x ? x ? ||
?k c
|| x ? ||
|| z ?||

k – не очень большое число раз

Оценка погрешности результата:
? 1?
Аz ? A ??? ??
? 1?

- или более реальный столбец, если известен порядок и знак компонентов x

zo
На примере метода исключения Гаусса хорошо видна особенность прямых методов – конечное
число операций.






Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.