ЧМ-Лекция 02 (Лекции (презентации))

Решение систем линейных алгебраических уравнений. Метод Гаусса.
задач строительства, картографии и баллистики выросла аналитическая геометрия.
той науке мы сталкиваемся с матрицами и операциями над ними:
1. Объем параллелограмма, построенного на a , b , c :


V  a b c a (b c )
ax
правой декартовой прямоугольной системе координатV  a y
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
~
A
~
2) A  A
, если
3) A 0
~
4) A q A
a11  a~11
a12
5)


 a1 j







 a1k







k  j : aij q aik (пропорциональность строк/столбцов)
q – общий множитель какой-либо строки/столбца.
a21  a~21  an1  a~n1
a22

an 2



 aij  q akj
6) A 
получается из A переменой местами двух строк (столбцов)

=
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 ki 1

Частный случай теоремы Лапласа о вычислении определителя:
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/* Df.(можно не давать) Алгебраическое дополнение минора M в матрице A( n n) :
( 1)
st
s - номера строк из A
t - номера столбцов из A
N
N - дополнительный минор к M
Число произведений при вычислении определителя n!
 n
n! 2n  
e

n
и n умножений в каждом слагаемом!
30!2,65 10 32
одна из задач линейной алгебры – вычисление определителя.

Существует другая задача – решение системы линейных уравнений 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
a~
( 2)
ij

aij(1)
a
(1)
i1
j 1, n
~
А  А ( 2)
(1)
bj
~
b j( 2)  (1)
ai1
 a11(1)  


 1 
 1 


~ ( 2)  n (1) 
| A |  ai1 
 i 11

(  1)
| A (1) |
~
( 2) ( 2)
5. Для элементов матрицы A a ij : i > 1
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)

  a11(1)
  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) более одного элемента, в противном
| A ( 2) |
случае – к пункту 9:
( 2)
|А
(n  1) (n  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 

n


a
x

j1 1 
l j 1

a и b есть элементы итоговых матрицы 
и столбца
a11(1)


Контроль расчетов по методу Гаусса:
Заменяем (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
На примере метода исключения Гаусса хорошо видна особенность прямых методов – конечное
число операций.