Добавлен: 06.02.2019
Просмотров: 4124
Скачиваний: 4
11
x
...
x
...
...
...
x
...
x
x
...
x
x
...
x
x
0
0
0
0
1
0
1
.
Аналогично повторяем указанные действия для неизвестных х
3
,х
4
,...,
х
m-1
и приходим к системе с матрицей вида:
m
m
mm
m
m
m
,
m
m
m
m
m
m
y
x
c
y
x
c
x
.
.
.
.
.
.
.
y
x
c
...
x
y
x
c
...
x
c
x
1
1
1
2
2
2
1
1
2
12
1
. (1.6)
Эта матрица является верхней треугольной:
x
...
...
x
...
...
...
...
x
...
...
x
x
...
x
x
x
...
x
x
0
0
0
1
0
0
0
1
0
0
1
0
1
.
Обратный ход метода. Из последнего уравнения системы (1.6) находим
х
m
, из предпоследнего х
m-1
, ..., из первого уравнения – х
1
.
Общая формула:
x
m
=y
m
/c
mm
,
m
i
j
j
x
ij
c
i
y
i
x
1
, (i=m-1,…,1).
Для реализации метода Гаусса требуется примерно (2/3)m
3
арифметических операций, причем большинство из них приходится на
прямой ход.
Ограничение метода единственного деления заключается в том, что
угловые элементы не равны нулю, т.е.
0
1
k
kk
а
.
12
Ведущие элементы –
1
к
кк
а
– элементы на k-ом шаге исключения. Но
если ведущий элемент близок к нулю, то в процессе вычисления может
накапливаться погрешность. В этом случае на каждом шаге исключают не х
k
,
a х
j
(при j k). Такой подход называется методом выбора главного элемента.
Для этого выбирают неизвестные x
j
с наибольшим по абсолютной величине
коэффициентом либо в строке, либо в столбце, либо во всей матрице. Для его
реализации требуется
3
1
3
2
)
m
m(m
- арифметических действий.
1.1.2 Связь метода Гаусса с разложением матрицы на множители.
Теорема об LU разложении.
Пусть дана система Aх=B (1.1), которая при прямом ходе преобразуется
в эквивалентную систему (1.6) и которую запишем в виде
Cх=y,
(1.7)
где С – верхняя треугольная матрица с единицами на главной диагонали.
Как связаны в системе (1.1) элементы В и элементы y из (1.7)?
Если внимательно посмотреть на прямой ход метода Гаусса, то можно
увидеть, что
2
1
22
1
21
2
1
11
1
y
a
y
a
b
y
a
b
)
(
.
Для произвольного j имеем
i
jj
j
j
j
y
d
...
y
d
y
d
b
2
2
1
1
, (1.7)
где j=
m
,
1
, d
ji
– числовые коэффициенты:
)
j
(
jj
jj
a
d
1
. (1.8)
Это можно записать в виде:
В=Dy,
где D-нижняя треугольная матрица с элементами
)
1
( j
jj
a
на главной диагонали
(j=
m
,
1
,
11
)
0
(
11
а
а
).
13
В связи с тем, что в методе Гаусса угловые коэффициенты не равны
нулю
0
)
1
( j
jj
a
, то на главной диагонали матрицы D стоят не нулевые
элементы. Следовательно, эта матрица имеет обратную, тогда y=D
-1
В, Сx=
D
-1
В. Тогда
D Cx=B. (1.9)
В результате использования метода Гаусса, получили разложение
матрицы А на произведение двух матриц
A = D C,
где D - нижняя треугольная матрица, у которой элементы на главной
диагонали не равны нулю, а C - верхняя треугольная матрица с
единичной диагональю.
Таким образом, если задана матрица A и вектор B, то в методе Гаусса
сначала производится разложение этой матрицы А на произведение D и C, а
затем последовательно решаются две системы:
Dy=B,
Cx=y. (1.10)
Из последней системы находят искомый вектор x. При этом
разложение матрицы А на произведение СD – есть прямой ход метода Гаусса,
а решение систем (1.10) обратный ход. Обозначим нижнюю треугольную
матрицу через L, верхнюю треугольную матрицу - U.
Теорема об LU разложении
Введем обозначения:
j
- угловой минор порядка j матрицы А, т.е.
).
A
det(
m
.
.
.
.
.
.
,
a
a
a
a
det
,
a
22
21
12
11
2
11
1
Теорема. Пусть все угловые миноры матрицы А не равны нулю (Δj 0
для j=
m
,
1
). Тогда матрицу А можно представить единственным образом
в виде произведения А=L*U.
Идея доказательства. Рассмотрим матрицу А второго порядка и будем
искать разложение этой матрицы в виде L и U.
14
1
0
1
0
12
22
21
11
22
21
12
11
u
*
l
l
l
a
a
a
a
A
.
Сопоставляя эти два равенства, определяем элементы матриц L и U
(перемножим и приравняем неизвестные). Система имеет единственное
решение. Методом математической индукции сказанное можно обобщить
для матрицы размерности m m.
Следствие. Метод Гаусса (схема единственного деления) можно
применять только в том случае, когда угловые миноры матрицы А не равны
нулю.
1.1.3 Метод Гаусса с выбором главного элемента
Может оказаться так, что система (1.1) имеет единственное решение,
хотя какой либо из миноров матрицы А равен нулю. Заранее неизвестно, что
все угловые миноры матрицы А не равны нулю. Избежать этого можно с
выбором главного элемента.
1. Выбор главного элемента по строке, т.е. производится
перенумерация неизвестных системы.
ПРИМЕР. Пусть дана система второго порядка
2
2
22
1
21
1
2
12
1
11
b
x
a
x
a
b
x
a
x
a
при а
12
> а
11
, тогда на первом шаге вместо неизвестного х
1
исключают х
2
:
2
1
21
2
22
1
1
11
2
12
b
x
a
x
a
b
x
a
x
a
.
К этой системе применяем первый шаг прямого хода метода Гаусса.
2. Выбор главного элемента по столбцу.
Предположим, что а
21
> а
11
и переставим уравнения
1
2
12
1
11
2
2
22
1
21
b
x
a
x
a
b
x
a
x
a
и применяем первый шаг прямого хода метода Гаусса. Здесь имеет место
перенумерация строк.
15
3. Поиск главного элемента по всей матрице заключается в
совместном применении методов 1 и 2. Всё это приводит к уменьшению
вычислительной погрешности.
1.1.4 Метод Холецкого (метод квадратных корней)
Пусть дана система
Ах=В , (1.11)
где матрица А - симметричная матрица. Тогда решение системы (1.11)
проводится в два этапа:
1.
Симметричная матрица А представляется как произведение
двух матриц
А = L * L
Т
.
Рассмотрим метод квадратных корней на примере системы 4-го
порядка:
44
34
33
42
32
22
41
31
21
11
44
43
42
41
33
32
31
22
21
11
44
41
14
11
0
0
0
0
0
0
0
0
0
0
0
0
l
l
l
l
l
l
l
l
l
l
*
l
l
l
l
l
l
l
l
l
l
a
...
a
...
...
...
a
...
a
.
Перемножаем матрицы в левой части разложения и сравниваем с
элементами в левой части:
11
11
a
l
,
11
12
21
a
a
l
,
11
13
31
a
a
l
,
11
14
41
a
a
l
,
2
21
22
22
l
a
l
,
22
31
21
32
32
l
l
l
a
l
,
2
32
2
31
33
33
l
l
a
l
,
2
43
2
42
2
41
44
44
l
l
l
a
l
.
2. Решаем последовательно две системы
Ly=B,
L
T
x=у.