Методическое пособие для практических и лабораторных работ по курсу «Численные методы»

109
отрицательного влияния погрешностей округления на точность результата.
Вычислительная погрешность может существенно нарастать.
Число действий (трудоемкость метода). Для реализации метода Гаусса
(схема единственного деления) требуется примерно
3 3
2
n арифметических операций, причем подавляющее число этих действий совершается на этапе прямого хода.
Русские математики Клюев и Коковкин-Щербак доказали, что в
общем случае система линейных алгебраических уравнений не может быть
решена точными методами с помощью меньшего числа операций, чем
требуется в Гауссовском исключении.

3.2. Метод Гаусса с выбором главного элемента по столбцу

Если в схеме единственного деления на некотором шаге ведущий элемент
)
1
(
−
k
kk
a
окажется равным нулю, то схема единственного деления не может быть реализована, несмотря на то, что система
b
x
A
r r
=
(3.1) имеет единственное решение. В этом случае может быть применен метод Гаусса с выбором главного элемента.
Главный элемент можно выбирать по строчке, по столбцу (частичный выбор) или по всей матрице A. Изложим наиболее простой и широко применяемый метод исключения Гаусса с выбором главного элемента по столбцу.
Выбираем максимальный по модулю элемент в первом столбце матрицы A . Пусть
|
|
max
|
|
1 1
1
i
n
i
m
a
a
≤
≤
=
, т.е. максимальный по модулю элемент первого столбца стоит в m -й строке. Меняем местами первое и m -е уравнения системы с соответствующей перенумерацией элементов этих уравнений. Делим новое первое уравнение на коэффициент при
1
x , имеем
,
1 1
2 12 1
y
x
c
x
c
x
n
n
=
+
+
+
11 1
1
a
a
c
j
j
=
,
n
j
,...,
3
,
2
=
,
11 1
1
a
b
y
=
,
(3.8)
и, исключив
1
x из второго, третьего,…,
n -го уравнений точно так же, как в пункте 3.1, получаем систему

110








=
+
+
+
=
+
+
+
=
+
+
+
=
+
+
+
+
...
...
...
...
...
,
,
,
)
1
(
)
1
(
3
)
1
(
3 2
)
1
(
2
)
1
(
3
)
1
(
3 3
)
1
(
33 2
)
1
(
32
)
1
(
2
)
1
(
2 3
)
1
(
23 2
)
1
(
22 1
1 3
13 2
12 1
n
n
nn
n
n
n
n
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
y
x
c
x
c
x
c
x
(3.9)

Далее первое уравнение системы (3.9) оставляем без изменения.
Выбираем максимальный по модулю элемент во втором столбце матрицы системы (3.9), начиная со второй строки. Пусть
|
|
max
|
|
)
1
(
2 2
)
1
(
2
i
n
i
l
a
a
≤
≤
=
, т.е. максимальный по модулю элемент второго укороченного столбца стоит в l
- той строке. Меняем местами второе и l
-тое уравнения системы (3.9).
Исключаем
2
x из всех уравнений, начиная с третьего, и т.д. После
n шагов получаем систему уравнений с верхней треугольной матрицей.
Обратный ход метода Гаусса (т.е. вычисление неизвестных
i
x ,
n
i
,...,
1
=
) осуществляем так же, как и в схеме единственного деления.
Заметим, что дополнительная работа по выбору главных элементов в схеме частичного выбора требует порядка
2
n действий, что практически не влияет на общую трудоемкость метода.
Известно, что для некоторых классов матриц при использовании схемы единственного деления главные элементы гарантированно располагаются на главной диагонали и поэтому применять частичный выбор нет необходимости. Именно так, например, обстоит дело с системами, имеющими положительно определенные матрицы, а так же матрицы с диагональным преобладанием.
Замечание. Метод Гаусса с частичным выбором главного элемента можно применять к любой СЛАУ с невырожденной матрицей. Однако этот метод не всегда вычислительно устойчив. Например, пусть методом Гаусса с выбором главного элемента по столбцу решается система
b
x
A
r r
=
с матрицей коэффициентов












−
−
−
−
−
−
=
1 1
1 1
1 1
1 1
1 0
1 1
1 0
0 1
A

111
Приведение такой матрицы к треугольному виду прямым ходом метода
Гаусса равносильно следующей последовательности эквивалентных преобразований матрицы A :












⇒












−
⇒












−
−
−
⇒












−
−
−
−
−
−
=
8 0
0 0
4 1
0 0
2 0
1 0
1 0
0 1
4 1
0 0
4 1
0 0
2 0
1 0
1 0
0 1
2 1
1 0
2 1
1 0
2 0
1 0
1 0
0 1
1 1
1 1
1 1
1 1
1 0
1 1
1 0
0 1
A
В случае матрицы такого типа размерности
n
n
×
прямой ход метода
Гаусса допускает рост элементов матрицы до
)
1
(
2
−
n
. При больших
n это может привести если не к переполнению разрядной сетки ЭВМ, то к сильному влиянию погрешностей округлений на конечный результат.
Этот недостаток метода исключения Гаусса побуждает к разработке других точных методов, может быть более сложных, но численно более устойчивых, таких, например, как метод вращений, который будет изложен ниже.

3.3. Компактная схема Гаусса

Как было показано в параграфе 3.1., для того, чтобы решить систему
(3.1), нам достаточно знать коэффициенты
ij
c и правые части
i
y системы
(3.5). Явно их можно вычислить следующим образом.
Пусть осуществлены первые
)
1
(
−
k
шагов, т.е. уже исключены
1 1
,...,
−
k
x
x
, следовательно, система (3.1) приведена к виду:











=
+
+
=
+
+
=
+
+
+
=
+
+
+
+
=
+
+
+
+
+
−
−
−
−
−
−
−
−
−
−
...
...
...
...
,
,
...
...
...
...
...
,
...
,
...
)
1
(
)
1
(
)
1
(
)
1
(
)
1
(
)
1
(
1
,
1
,
1 1
2 2
2 2
1 1
1 2
12 1
k
n
n
k
nn
k
k
nk
k
k
n
k
kn
k
k
kk
k
n
n
k
k
k
k
k
n
n
k
k
n
n
k
k
b
x
a
x
a
b
x
a
x
a
y
x
c
x
c
x
y
x
c
x
c
x
y
x
c
x
c
x
c
x
(3.10)
Рассмотрим k -е уравнение системы (3.10) и предположим, что
0
)
1
(
≠
−
k
kk
a
. Разделив обе части этого уравнения на
)
1
(
−
k
kk
a
, получаем
k
n
n
k
k
k
k
k
y
x
c
x
c
x
=
+
+
+
+
+
,
1 1
,
,
(3.11)

112
где
)
1
(
)
1
(
−
−
=
k
kk
k
kj
kj
a
a
c
,
n
k
j
,...,
1
+
=
,
)
1
(
)
1
(
−
−
=
k
kk
k
k
k
a
b
y

Теперь уравнение (3.11) умножаем последовательно на
)
1
(
−
k
ik
a
и вычитаем, соответственно, из (i -го) уравнения системы (3.10). В результате последняя группа уравнений системы (3.10) принимает вид







=
+
+
=
+
+
=
+
+
+
+
+
+
+
+
+
+
+
+
,
...
...
...
...
,
,
)
(
)
(
1
)
(
1
,
)
(
1
)
(
,
1 1
)
(
1
,
1
,
1 1
,
k
n
n
k
nn
k
k
k
n
k
k
n
k
n
k
k
k
k
k
k
n
n
k
k
k
k
k
b
x
a
x
a
b
x
a
x
a
y
x
c
x
c
x
(3.12) где
,
)
1
(
)
1
(
)
(
kj
k
ik
k
ij
k
ij
c
a
a
a
−
−
−
=
n
k
j
i
,...,
1
,
+
=
;
,
)
1
(
)
1
(
)
(
k
k
ik
k
i
k
i
y
a
b
b
−
−
−
=
.
,...,
1
n
k
i
+
=

Таким образом, в прямом ходе метода Гаусса коэффициенты уравнений преобразуются по формулам
,
)
0
(
kj
kj
a
a
=
n
j
k
,...,
2
,
1
,
=
;
,
)
1
(
)
1
(
−
−
=
k
kk
k
kj
kj
a
a
c
,
,...,
1
n
k
j
+
=
n
k
,...,
2
,
1
=
;
(3.13)
,
)
1
(
)
1
(
)
(
kj
k
ik
k
ij
k
ij
c
a
a
a
−
−
−
=
n
k
j
i
,...,
1
,
+
=
,
n
k
,...,
1
=
(3.14)

Вычисление правых частей системы (3.5) осуществляется по формулам
,
)
0
(
k
k
b
b
=
,
)
1
(
)
1
(
−
−
=
k
kk
k
k
k
a
b
y
n
k
,...,
1
=
;
(3.15)
,
)
1
(
)
1
(
)
(
k
k
ik
k
i
k
i
y
a
b
b
−
−
−
=
n
k
i
,...,
1
+
=
(3.16)

По формулам (3.13) – (3.16) вычисляем коэффициенты
ij
c , правые части
i
y ,
,
,...,
1
n
i
=
,
,...,
1
n
i
j
+
=
системы (3.5) и затем осуществляем обратный ход, как и в схеме единственного деления.
Реализация прямого хода метода Гаусса по формулам (3.13)-(3.16) называется компактной схемой Гаусса.

113
2.4. Метод оптимального исключения

Методом оптимального исключения называется следующий алгоритм решения СЛАУ. Дана система






=
+
+
+
=
+
+
+
=
+
+
+
...
..........
..........
,
,
2 2
1 1
2 2
2 22 1
21 1
1 2
12 1
11
n
n
nn
n
n
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
(3.17)
Делим первое уравнение на
11
a . Получаем
)
1
(
1
,
1
)
1
(
1 2
)
1
(
12 1
+
=
+
+
+
n
n
n
a
x
a
x
a
x
Умножаем данное уравнение на
21
a и вычитаем его из второго уравнения системы (3.17). Получившееся второе уравнение делим на коэффициент при
2
x и исключаем
2
x из преобразованного первого уравнения. После первого шага система принимает вид:








=
+
+
+
+
=
+
+
+
+
=
+
+
+
=
+
+
+
...
...
...
...
...
...
,
,
,
3 3
2 2
1 1
3 3
3 33 2
32 1
31
)
2
(
2
)
2
(
2 3
)
2
(
23 2
)
2
(
1
)
2
(
1 3
)
2
(
13 1
n
n
nn
n
n
n
n
n
n
n
n
n
b
x
a
x
a
x
a
x
a
b
x
a
x
a
x
a
x
a
b
x
a
x
a
x
b
x
a
x
a
x

Теперь исключаем
1
x и
2
x из третьего уравнения. Преобразованное третье уравнение делим на коэффициент при
3
x и исключаем
3
x из первых двух уравнений, и т.д. В итоге получаем
i
i
y
x
=
,
n
i
,...,
2
,
1
=
, т.е. мы вычислили решение системы (3.17).
Последовательное введение уравнений экономит память ЭВМ. Метод позволяет решать системы, порядок которых в 2 раза больше чем при решении с помощью схемы единственного деления.
3.5. LU- разложение

Доказано, что с алгебраической точки зрения метод исключения Гаусса
(схема единственного деления) эквивалентен разложению матрицы A на произведение двух треугольных матриц
LU
A
=
, где
L – нижняя треугольная матрица, а U – верхняя. Пусть имеется матрица
n
j
i
a
A
1
,
)
(
=
. Если

114
известно разложение
LU
A
=
, то решение системы
b
x
A
r r
=
сводится к решению двух систем с треугольными матрицами
b
y
L
r r
=
и
y
x
U
r r
=
Решение СЛАУ с треугольными матрицами не вызывает затруднений.
Возникает вопрос, когда такое разложение возможно. Ответ на этот вопрос дает теорема.
Теорема об LU-разложении. Пусть все главные миноры матрицы A отличны от нуля (
0
≠
∆
j
,
n
j
,...,
1
=
), тогда матрицу A можно представить единственным образом в виде произведения
LU
A
=
, где
L – нижняя треугольная матрица с ненулевыми диагональными элементами,
U
– верхняя треугольная матрица с единицами по главной диагонали.
Доказательство
Доказательство будем вести по индукции по размерности матрицы.
1
=
n
: A=
( )
11
a
→
11
a
L
=
,
)
1
(
=
U
,
0 11
≠
a
2
=
n
:






=
22 21 12 11
a
a
a
a
A

Матрицы L и U будем искать в виде






=
22 21 11 0
l
l
l
L
,




=
1 0
1 12
u
U
Так как должно выполняться равенство
LU
A
=
, то, перемножая матрицы, для определения неизвестных
ij
l и
ij
u получаем систему уравнений
11 11
a
l
=
,
12 12 11
a
u
l
=
,
21 21
a
l
=
,
22 22 12 21
a
l
u
l
=
+

Решая эту систему, находим
11 11
a
l
=
,
11 12 12
a
a
u
=
,
21 21
a
l
=
,
11 12 21 22 11 22
a
a
a
a
a
l
−
=
По условию
0 11
≠
a
,
0 12 21 22 11
≠
−
a
a
a
a
, поэтому система имеет единственное решение и
0 11
≠
l
и
0 22
≠
l
Пусть утверждение теоремы справедливо для матриц порядка
)
1
(
−
k
Докажем справедливость утверждения для матрицы порядка k . Представим матрицу A следующим образом:






=
−
−
−
kk
k
k
k
a
b
a
A
A
1 1
1
r r
, где










=
−
−
k
k
k
k
a
a
a
,
1 1
1
r
,
(
)
1
,
1 1
−
−
=
k
k
k
k
a
a
b
r

115
Матрицы
k
L и
k
U будем искать в виде






=
−
−
kk
k
k
k
l
l
L
L
1 1
0
r
,




=
−
−
1 0
1 1
k
k
k
u
U
U
r
, где
)
,...,
(
1
,
1 1
−
−
=
k
k
k
k
l
l
l
r
,
T
k
k
k
k
k
u
u
u
u
)
,...,
,
(
,
1 2
1 1
−
−
=
r
– вектор- строка и вектор-столбец. По предположению индукции
1 1
1
−
−
−
=
k
k
k
U
L
A
. Исходя из матричного равенства
=
A










=






−
−
−
−
−
−
−
1 0
0 1
1 1
1 1
1 1
k
k
kk
k
k
kk
k
k
k
u
U
l
l
L
a
b
a
A
r r
r r
,
(3.18) для определения неизвестных
1
−
k
l
r
,
kk
l и
1
−
k
ur получаем систему уравнений
1 1
1
−
−
−
=
k
k
k
a
u
L
r r
,
(3.19)
1 1
1
−
−
−
=
k
k
k
b
U
l
r r
,
(3.20)
kk
kk
k
k
a
l
u
l
=
+
−
−
1 1
r r
(3.21)

Так как из равенства
1 1
1
−
−
−
=
k
k
k
U
L
A
и условия
0 1
≠
−
k
A
следует, что
0 1
≠
−
k
L
и
0 1
≠
−
k
U
, то система уравнений (3.19)-(3.21) однозначно разрешима. Отсюда
1 1
1 1
−
−
−
−
=
k
k
k
a
L
u
r r
,
1 1
1 1
−
−
−
−
=
k
k
k
U
b
l
r r
и
1 1
−
−
−
=
k
k
kk
kk
u
l
a
l
r r
Докажем, что
0
≠
kk
l
Из разложения (3.18) следует, что
)
det(
)
det(
)
det(
1 1
−
−
=
k
kk
k
k
U
l
L
A
, отсюда, т.к.
0
)
det(
≠
k
A
,
0
)
det(
1
≠
−
k
L
,
0
)
det(
1
≠
−
k
U
, то и
0
≠
kk
l
Справедливость разложения
LU
A
=
доказана. Осталось доказать единственность разложения. Будем вести доказательство от противного.
Пусть
2 2
1 1
U
L
U
L
A
=
=
(здесь нижний индекс означает номер, а не размерность), отсюда
1 2
1 2
1 1
−
−
=
U
U
L
L
(3.22)

Получили слева нижнюю треугольную матрицу, а справа
−
верхнюю, а это возможно только в том случае, если
2 1
1
L
L
−
и
1 2
1
−
U
U
−
диагональные. Но на диагонали матрицы
1 2
1
−
U
U
стоят единицы, следовательно,
E
L
L
U
U
=
=
−
−
2 1
1 1
2 1
и
2 1
U
U
=
,
2 1
L
L
=
. Теорема доказана.
Если все главные миноры матрицы A отличны от нуля, то справедливы рекуррентные формулы, позволяющие найти элементы матриц L и U :

116 11 11
a
u
=
,
j
j
a
u
1 1
=
,
11 1
1
u
a
l
j
j
=
,
n
j
,...,
3
,
2
=
,
∑
−
=
−
=
1 1
i
p
pi
ip
ii
ii
u
l
a
u
,
n
i
,...,
3
,
2
=
,
∑
−
=
−
=
1 1
i
p
pj
ip
ij
ij
u
l
a
u
,
ii
i
p
pi
jp
ji
ji
u
u
l
a
l
∑
−
=
−
=
1 1
,
n
i
,...,
3
,
2
=
,
n
i
i
j
,...,
2
,
1
+
+
=
. Здесь
1
=
ii
l
(3.23)
Замечание. Так как схема единственного деления эквивалентна
LU
- разложению, то из доказанной теоремы следует, что если все главные миноры матрицы A отличны от нуля, то схема единственного деления работает (нет деления на нуль).

Скачать 1.29 Mb.

Поделитесь с Вашими друзьями: