2.2. Алгоритм треугольного разложения положительно определенных симметричных матриц и его применение для решения слау
Алгоритм называют еще алгоритмом Холесского разложения матриц. Он применим к симметричным положительно определенным матрицам.
Напомним,
что матрица
называется симметричной, если
,
т.е.
.
Матрица
A
называется положительно
определенной,
если скалярное произведение
для всех ненулевых векторов, или, что
то же самое,
.
Такие матрицы часто встречаются в
приложениях. В типичной ситуации
произведение
представляет собой энергию некоторой
физической системы, которая положительна
для любого вектора x
состояния системы.
Приведем для справки два критерия положительной определенности матрицы.
Критерий Сильвестра. Для того чтобы симметричная матрица была положительно определенной, необходимо и достаточно, чтобы все ведущие (угловые) миноры этой матрицы были положительными:
Для
того, чтобы матрица
была положительно определенной,
достаточно, чтобы
,
;
и для всех строк матрицы A
выполнялось свойство диагонального
преобладания:
Кроме того, известно, что у положительно определенной матрицы и только у нее все собственные значения положительны.
Теорема
(о разложении Холесского).
Если
симметричная положительно определенная
матрица, то существует и единственно
ее треугольное разложение вида
,
где L
нижняя треугольная матрица вида
, 
, 
,
a
транспонированная по отношению к L
матрица вида
.
На основе этой теоремы может быть построен алгоритм вычисления разложения, который мы приводим без вывода (так называемый алгоритм в форме скалярных произведений).
,
.
Элементы
матрицы L
рассчитывают в следующем порядке:
,
,
,
,
,
,
,
,
,
и т.д., выбирая одну из формул, приведенных
выше.
2.3. Варианты заданий
№ |
LU-разложение |
Метод Холесского |
||||||||
Матрица коэффициентов “c” |
Столбец свободных членов “d” |
Матрица “ch” |
Столбец свободных членов “d” |
|||||||
1 |
4 |
16 |
24 |
36 |
360 |
2116 |
920 |
4738 |
4646 |
27462 |
1 |
5 |
9 |
17 |
141 |
920 |
409 |
2120 |
2104 |
12306 |
|
4 |
21 |
47 |
92 |
695 |
4738 |
2120 |
11018 |
10972 |
63976 |
|
2 |
15 |
92 |
95 |
642 |
4646 |
2104 |
10972 |
10995 |
63760 |
|
2 |
2 |
6 |
10 |
4 |
130 |
144 |
900 |
1020 |
1008 |
7596 |
4 |
17 |
65 |
43 |
725 |
900 |
6409 |
8055 |
7000 |
55483 |
|
1 |
9 |
68 |
80 |
740 |
1020 |
8055 |
11186 |
8773 |
72314 |
|
8 |
27 |
68 |
48 |
819 |
1008 |
7000 |
8773 |
7731 |
60821 |
|
3 |
5 |
10 |
45 |
15 |
385 |
2401 |
1862 |
4606 |
6615 |
23030 |
2 |
7 |
30 |
27 |
271 |
1862 |
1700 |
4756 |
5930 |
20036 |
|
5 |
13 |
65 |
100 |
614 |
4606 |
4756 |
14337 |
16395 |
54264 |
|
9 |
25 |
110 |
89 |
985 |
6615 |
5930 |
16395 |
20826 |
70154 |
|
4 |
7 |
56 |
42 |
35 |
679 |
6084 |
4758 |
4446 |
10530 |
126984 |
5 |
41 |
32 |
32 |
516 |
4758 |
3746 |
3662 |
8555 |
101883 |
|
3 |
25 |
24 |
58 |
414 |
4446 |
3662 |
4627 |
10075 |
111956 |
|
8 |
69 |
62 |
117 |
1035 |
10530 |
8555 |
10075 |
22338 |
252885 |
|
5 |
9 |
72 |
54 |
45 |
756 |
2304 |
1824 |
4512 |
720 |
47280 |
5 |
46 |
42 |
67 |
846 |
1824 |
1700 |
4324 |
1370 |
43670 |
|
3 |
25 |
21 |
31 |
407 |
4512 |
4324 |
11070 |
3820 |
111060 |
|
8 |
69 |
62 |
119 |
1435 |
720 |
1370 |
3820 |
3094 |
34386 |
|
6 |
6 |
48 |
36 |
30 |
564 |
2304 |
1872 |
2352 |
720 |
30144 |
5 |
43 |
36 |
46 |
542 |
1872 |
1777 |
2023 |
1401 |
25484 |
|
3 |
25 |
21 |
31 |
320 |
2352 |
2023 |
11666 |
1284 |
95526 |
|
8 |
69 |
62 |
116 |
933 |
720 |
1401 |
1284 |
3359 |
13393 |
|
7 |
8 |
64 |
48 |
40 |
600 |
2304 |
816 |
912 |
720 |
24480 |
5 |
46 |
42 |
67 |
753 |
816 |
545 |
435 |
1071 |
12190 |
|
3 |
25 |
24 |
58 |
588 |
912 |
435 |
435 |
747 |
11670 |
|
8 |
69 |
62 |
113 |
1231 |
720 |
1071 |
747 |
3367 |
21018 |
|
8 |
3 |
24 |
18 |
15 |
189 |
2304 |
816 |
912 |
720 |
24480 |
5 |
46 |
42 |
67 |
501 |
816 |
545 |
435 |
1071 |
12190 |
|
3 |
25 |
23 |
49 |
313 |
912 |
435 |
435 |
702 |
11535 |
|
8 |
69 |
62 |
120 |
810 |
720 |
1071 |
702 |
3091 |
19965 |
|
9 |
2 |
16 |
12 |
10 |
248 |
64 |
136 |
152 |
120 |
1840 |
5 |
48 |
46 |
81 |
1228 |
136 |
545 |
435 |
1071 |
7430 |
|
3 |
25 |
23 |
49 |
700 |
152 |
435 |
435 |
702 |
6215 |
|
8 |
69 |
62 |
117 |
1762 |
120 |
1071 |
702 |
3091 |
15765 |
|
10 |
1 |
8 |
6 |
5 |
66 |
64 |
136 |
152 |
120 |
1840 |
5 |
44 |
38 |
53 |
510 |
136 |
545 |
435 |
271 |
5030 |
|
3 |
25 |
22 |
40 |
375 |
152 |
435 |
435 |
352 |
5165 |
|
8 |
69 |
62 |
118 |
1073 |
120 |
271 |
352 |
491 |
4615 |
|