31
Очевидно, что сходимость метода Зейделя по сравнению с методом
простой итерации более быстрая.
2.5. Метод LU-разложения
Очень легко отыскать решение системы линейных алгебраических
уравнений, если представить матрицу коэффициентов
A
системы как
произведение двух матриц: верхней треугольной матрицы
L
и нижней
треугольной матрицы
U
:
LU A
.
Такое
разложение
называется
LU
-разложением.
Запишем
определение
LU
-разложения в матричном виде на примере матрицы
размера 4х4:
44
34
33
24
23
22
14
13
12
11
43
42
41
32
31
21
441
43
42
41
34
33
32
31
24
23
22
21
14
13
12
11
0 0 0
0 0
0
1
0 1
0 0 1
0 0 0 1
u
u
u
u u u
u u u
u
m m m
m m
m
a a a a
a
a a a
a a a a
a a
a a
.
Заметим, что определение применимо и к произвольной матрице
размера
N
x
N
.
Итак, пусть матрицу коэффициентов
A
линейной системы
AX
=
B
можно разложить на треугольные матрицы:
LUX
=
B
. Тогда решение
можно получить, полагая
Y
=
UX
, и затем решить две системы:
LUB
, для
Y
,
чтобы получить
UX
=
Y
для
X
.
2.6. Метод отражений
Под нормой вектора будем понимать евклидову норму, а под нормой
матрицы
спектральную норму.
Лемма 1. Спектральная норма всякой унитарной (ортогональной в
вещественном случае) матрицы равна 1.
Доказательство. Поскольку унитарные матрицы сохраняют
евклидову длину вектора, по определению спектральной нормы получаем
для всякой унитарной матрицы
U
:
. 1
0
0
=
x
x
=
x
Ux
=U
mumer
psu
x
uer
psu
x
Лемма 2. Собственные значения всякой унитарной матрицы по
модулю равны 1.
Доказательство. Пусть
произвольное собственное значение
матрицы
U
.
1
=U
по предыдущей лемме. С другой стороны,
1
