• Название:

    решение СЛАУ

  • Размер: 0.24 Мб
  • Формат: PDF
  • или
  • Сообщить о нарушении/Abuse
  • Название: Microsoft Word - 1_1_a.doc

1 . Ч И СЛ Е Н Н Ы Е М Е ТОД Ы Л И Н Е Й Н О Й А Л Г Е Б Р Ы
В разделе «Численные методы линейной алгебры» рассматриваются численные
методы решения систем линейных алгебраических уравнений (СЛАУ)

и численные

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

1 . 1 . Ч и с л е н н ы е м е тод ы р е ш е н и я СЛ АУ
Из прямых методов решения СЛАУ рассмотрим методы Гаусса и прогонки.
1.1.1. Метод Гаусса
В методе Гаусса матрица СЛАУ с помощью равносильных преобразований преобразуется
в верхнюю треугольную матрицу, получающуюся в результате прямого хода. В обратном
ходе определяются неизвестные.
Пусть дана СЛАУ
a11 x1 + a12 x 2 + ... + a1n x n = b1
a x + a x + ... + a x = b
 21 1
22 2
2n n
2

................................
a n1 x1 + a n 2 x 2 + ... + a nn x n = bn

Запишем расширенную матрицу системы:

Ведущая строка → 








x1

x2

x3 L

xn

a11

a12

a13

a 21

a 22

a 23 L a 2 n

a31

a32

a33 L a3n

L

L

L

L a1n

L

L

a n1 a n 2 a n 3 L a nn
↑ Ведущий столбец

b

a
a
a
b1  (− 21 a11 ); (− 31 a11 );K; (− n1 a11 )

b2 
1

→
b3 
−й шаг

L
bn 

На первом шаге алгоритма Гаусса выберем диагональный элемент a11 ≠ 0 (если он
равен 0, то первую строку переставляем с какой-либо нижележащей строкой) и объявляем
его ведущим, а соответствующую строку и столбец, на пересечении которых он стоит ведущими. Обнулим элементы a 21 ,..., a n1 ведущего столбца. Для этого сформируем числа

(− a 21

a11 ); (− a31 a11 );...; (− a n1 a11 ) . Умножая ведущую строку на число

(− a 21

a11 ) ,

складывая со второй и ставя результат на место второй строки, получим вместо элемента
a 2 j , j = 2, n ,

нуль, а вместо элементов

a 21

b2

– соответственно элементы

j = 2, n , b21 = b2 + b1 (− a 21 a11 ) и т.д. Умножая ведущую строку

a 12 j = a 2 j + a1 j (− a 21 a11 ),

на число (− a n1 a11 ) , складывая с n-ой строкой и ставя результат на место n-ой строки,
получим вместо элемента a n1 нуль, а остальные элементы этой строки будут иметь вид:

bn1 = bn + b1 (− a n1 a11 ) . Сохраняя ведущую строку неизменной,

a 1nj = a nj + a1 j (− a n1 a11 ),

получим в результате 1-го шага алгоритма Гаусса следующую матрицу:

x1

Ведущая строка → 





a11
0
0
L
0

x2

x3 L x n b
a12 a13 L a1n b1 
1
1
a 122 a 123 L a 12 n b21  − a32 a122 ;K; − an 2 a122
1
1
L a31n b31 
a32
a33
2
→
−й шаг

L L L L L
a 1n 2 a 1n 3 L a 1nn bn1 
↑ Ведущий столбец

(

) (

)

На втором шаге алгоритма Гаусса в качестве ведущего элемента выбирается элемент
1
a22
≠ 0 (если он равен нулю, то вторую строку взаимно меняем на нижележащую строку).
1
 a32
  a 1n 2 

Формируются числа  − 1 ;...;  − 1  , которые ставятся около ведущей строки.
 a 22   a 22 

 a1 
Умножая ведущую строку на число  − 132  и складывая результат с третьей строкой,
 a 22 
1
нуль, а вместо элементов a31 j , j = 3, n , b31 , Σ13 – элементы
получим вместо элемента a32

a32 j

=

a31 j

+

1 
 a32
,
1 
a
 22 

a12 j  −

j = 3, n ,

b32

=

b31

1 
 a32
 ,. И так далее. Умножая ведущую
1 
a
 22 

+ b21  −

 a1n 2 
строку на число  − 1  , складывая результат с n-ой строкой и ставя полученную сумму
 a 22 
на место n-ой строки, получим вместо элемента a 1n 2 нуль, а вместо элементов a1nj , bn1 , Σ1n

 a1 
j = 3, n , bn2 = bn1 + b21  − n1 2  . Сохраняя 1-ую и 2-ую
 a 22 

 a1 
- элементы a nj2 = a1nj + a12 j  − n1 2 ,
 a 22 

строки матрицы неизменными, получим в результате второго шага алгоритма Гаусса
следующую матрицу:
x1
 a11
 0

 0

L
 0

Ведущая строка →

x2
a12

x3 L x n b
a13 L a n1 b1 
a 123 L a 12 n b21 
2

→
L a32n b32  3
a33
→ L (
n −1)−й шаг
− й шаг

L L L L
2
a n23 L a nn
bn2 
↑ Ведущий столбец

a 122
0
L
0

После (n-1)-го шага алгоритма Гаусса получаем следующую расширенную матрицу,
содержащую верхнюю треугольную матрицу СЛАУ:
x1

x2

a11
0

0

L
 0

a12

a13

1
22

a

0

a

1
23
2
33

L

L L

0

0

a

x3 L

xn

b

L

a1n

b1

L

a

L

a

1
2n
2
3n

1
2
2
3

L

L a

n −1
nn

b
b

L

bnn −1






L


Прямой ход алгоритма Гаусса завершен.
В обратном ходе алгоритма Гаусса из последнего уравнения сразу определяется x n ,
из предпоследнего - x n−1 и т.д. Из первого уравнения определяется x 1 .
n −1
ann
x n = bnn−1
 n −2
an −1n −1x n −1 + ann−−12n x n = bnn−−12

...................................
a x +...+a x = b
1n n
1
 11 1

⇒ xn
⇒ x n−1
⇒ x1

Замечание 1. Если элементы какой-либо строки матрицы системы в результате
преобразований стали равными нулю, а правая часть не равна нулю, то СЛАУ
несовместна, поскольку не выполняются условия теоремы Кронекера-Капелли.
Замечание 2. Если элементы какой-либо строки матрицы системы и правая часть в
результате преобразований стали равными нулю, то СЛАУ совместна, но имеет
бесконечное множество решений, получающееся с помощью метода Гаусса для СЛАУ
порядка r , где r - ранг матрицы исходной СЛАУ.

Замечание 3. В результате прямого хода метода Гаусса можно вычислить
определитель матрицы A исходной СЛАУ:

2
n −1
det A = (−1) p a11 a 122 a 33
⋅ ... ⋅ a nn

При этом с помощью множителя (−1) p , где p - число перестановок строк в

процессе прямого хода,

учитываются соответствующие перемены знаков вследствие

перестановок строк.

Замечание 4. Метод Гаусса можно применить для обращения невырожденной
( det A ≠ 0 ) матрицы.
Действительно, пусть требуется обратить невырожденную матрицу

A = [aij ] ,

i, j = 1, n . Тогда, сделав обозначение A −1 = X , X = [ xij ] , i, j = 1, n , можно выписать
1
0
матричное уравнение AX = E , где E - единичная матрица E = 
...

0

0
1
...
0

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

0
0 
, на основе
...

1

которого можно записать цепочку СЛАУ
 x11   1 
   
 x 21   0 
A⋅  =  ,
...
...
   
 x   0
 n1   

 x12   0 

  
 x 22   1 
,
=
A⋅
...   ...

  
x  0
 n2   

 x1n   0 
   
x  0
… A ⋅  2n  =   ,
...
...
   
x  1
 nn   

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

x2n

...
x12
x11

...
x 22
x 21

... x nn
... ...
... x n 2
... x n1 b1 b 2

a11
a 21
...
a n1

a12
a 22
...
an2

... a1n
... a 2 n
... ...
... a nn

1
0
...
0

0
1
...
0

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

bn
0
0
... ...
1

В результате применения (n − 1) -го шага метода Гаусса получаем:

x1n

x2n

...
x12
x11

...
x 22
x 21

... x nn
... ...
... x n 2
... x n1

a11

a12
a122
...
0

... a1n b11 b12
1
1
b22
... a12 n b21
...
...
... ...
n −1
bnn1−1 bnn2−1
... a nn

...
0

b1

b2

При этом первый столбец ( x11

L bn

... b1n
... b21n
... ...
n −1
... bnn

...

x 21 ... x n1 ) T

обратной матрицы определяется в

обратном ходе метода Гаусса с правой частью b1 , столбец ( x12
частью b 2 и так далее. Столбец ( x1n

x2n

x 22

... x n 2 ) T - с правой

... x nn ) T определяется с правой частью b n .

П
Пример 1.1. Методом Гаусса решить СЛАУ.
10 x1 + x 2 + x3 = 12

2 x1 + 10 x 2 + x3 = 13
2 x + 2 x + 10 x = 14
2
3
 1

Р е ш е н и е.
Прямой ход:
x1

x2

x3

10 1 1

 2 10 1
 2 2 10

x1

x2

b
12
13
14

x3

1
10 1

 0 9,8 0,8
 0 1,8 9,8


b
12
10,6
11,6

 (−2 / 10); (−2 / 10)

1
→

−й шаг


x1

x2

x3

1
10 1



→  0 9,8 0,8
 (−1,8 / 9,8) 2
−й шаг
 0 0 9,653




b
12
10,6
9,653







Обратный ход:
9,653x3 = 9,653,

x3 = 1

9,8 x 2 + 0,8 x3 = 10,6,

x2 = 1

x1 = 1.
10 x1 + x 2 + x3 = 12,
Ответ: x1 = x 2 = x3 = 1 .
Пример 1.2. Методом Гаусса вычислить определитель матрицы и обратить
матрицу СЛАУ из примера 1.1.
Р е ш е н и е.

 10 1 1 


A =  2 10 1  ;
 2 2 10 


Прямой ход.
x13 x 23 x33

x12

x 22

x 23

x11

x 21

x31

b1 b 2 b 3

10

 2
 2


1
10
2

1
1
10

1
0
0

x13

x 23

x33

x12

x 22

x 23

x11

x 21

x31

10

0
0


1
9,8
1,8

x13

x 23

x33

x12

x 22

x32

x11

x 21

x31

1
0,8
9,8

0 0
1 0
0 1

det A = 10 ⋅ 9.8 ⋅ 9.65 = 945.994

 (−2 / 10); (−2 / 10)

1
→

−й шаг



b1

b 2 b3

1
− 0,2
− 0,2

0 0
1 0
0 1

b1

(точное значение 946).



→
 (−1,8 / 9,8) 2
−й шаг



b2

b3

0
0
1
1
1

10


− 0,2
0
1

 0 9,8 0.8

0
0 9,653 − 0,163 − 0,184 1


Обратный ход:
9,653 x31 = −0,163
9,653 x32 = −0,184
9,653 x33 = 1



9,8 x 21 + 0,8 x31 = −0,2 9,8 x 22 + 0,8 x32 = 1
9,8 x 23 + 0,8 x33 = 0
10 x + x + x = 1
10 x + x + x = 0 10 x + x + x = 0
21
31
22
32
23
33
 11
 12
 13
− 0.0085 − 0.0095 
 x11 x12 x13   0.104




Отсюда A −1 =  x 21 x 22 x 23  =  − 0.019
− 0.0085 
0.104
 x
 
0.104 
 31 x32 x33   − 0.0169 − 0.019
− 0,0085 − 0,0095   1,004
0
0,0005 
10 1 1   0,104






Проверка: A ⋅ A −1 =  2 10 1  ⋅  − 0,019
− 0,0085  =  0,001 1,004
0,104
0 ,
 2 2 10   − 0,0169 − 0,019
0,104   0,001 0,001 1,004 

 
т.е. с точностью до ошибок округления получена единичная матрица.

Замечание 5. Компьютерная реализация метода Гаусса часто осуществляется с
использованием LU-разложения матриц.

LU – разложение матрицы A представляет собой разложение матрицы A в
произведение нижней и верхней треугольных матриц, т.е.
A = LU ,

где L - нижняя треугольная матрица (матрица, у которой все элементы, находящиеся
выше главной диагонали равны нулю, lij = 0 при i < j ), U - верхняя треугольная матрица
(матрица, у которой все элементы, находящиеся ниже главной диагонали равны нулю,
u ij = 0 при i > j ).
LU – разложение может быть построено с использованием описанного выше метода
Гаусса. Рассмотрим k - ый шаг метода Гаусса, на котором осуществляется обнуление
поддиагональных элементов k - го столбца матрицы A ( k −1) .

Как было описано выше, с

этой целью используется следующая операция:
a ij( k ) = a ij( k −1) − µ i( k ) a kj( k −1) ,

µ i( k ) =

aik( k −1)
, i = k + 1, n , j = k , n .
a kk( k −1)

В терминах матричных операций такая операция эквивалентна умножению
A ( k ) = M k A ( k −1) , где элементы матрицы M k определяются следующим образом
 1, i = j

m =  0, i ≠ j , j ≠ k .
− µ ( k ) , i ≠ j , j = k
 k +1
k
ij

0
1

1
0
0
0
Т.е. матрица M k имеет вид 
0
0
 ... ...

0
0


0

0

0

0

0

0

1

0

0

−µ
...

1 0
... ...

− µ n( k )

0

(k )
k +1

0

0

0
0
.
0
...
1 

При этом выражение для обратной операции запишется в виде A ( k −1) = M −k1A ( k ) , где

M k−1

0
1

1
0
0
0
=
0
0
 ... ...

0
0


0

0

0

0

0

0

1

0

0

µ k( k+1)
...

µ n( k )

1 0
... ...
0

0

0

0
0

0
...
1 

В результате прямого хода метода Гаусса получим A ( n −1) = U ,
A = A ( 0) = M 1−1 A (1) = M 1−1 M 2−1 A ( 2 ) = M 1−1 M 2−1 ...M n−−11 A ( n −1) ,

где A ( n −1) = U - верхняя треугольная матрица, а L = M 1−1 M 2−1 ...M n−−11 - нижняя треугольная
 1
 (1)
 µ2
 µ (1)
матрица, имеющая вид L =  3
 ...
 ...

 µ (1)
 n

0

0

0

0

1

0

0

0

1

0

0

... µ
...

1
...

0
...

µ

( 2)
3

...
...

µ n( 2)

(k )
k +1

µ n( k )

µ n( k +1) ... µ n( n −1)

0

0
0
.
0
...
1 

Таким образом, искомое разложение A = LU получено.
В частности, для рассмотренного выше примера 1.1. LU – разложение матрицы А
0 0  10 1
1 
10 1 1   1

 
 

имеет вид A =  2 10 1  =  0,2 1 0  ⋅ 
9,8 0,8  = LU
 2 2 10   0,2 0,18 1  
9,65 

 
 

В дальнейшем LU – разложение может быть эффективно использовано при решении
систем линейных алгебраических уравнений вида Ax = b . Действительно, подставляя LU
– разложение в СЛАУ, получим LUx = b , или Ux = L−1b . Т.е. процесс решения СЛАУ
сводится к двум простым этапам.
На первом этапе решается СЛАУ Lz = b . Поскольку матрица системы - нижняя
треугольная, решение можно записать в явном виде:
i −1

z1 = b1 , z i = bi − ∑ l ij z j , i = 2, n .
j =1

На втором этапе решается СЛАУ Ux = z с верхней треугольной матриц