|
м а т р и ц а с п о л о ж и т е л ь н ы м и э л е м е н т а м и н а г л а в н о й д и а г о н а л и .
2. Пример. Если разложение (2) получено, то решение системы
(
1
) сводится к последовательному решению двух систем уравнений
с треугольными матрицами
S'Dy=r.f,
(7)
Sx
=
у.
(
8
)
Покажем на примере матриц второго порядка как можно полу
чить разложение (
2
). Пусть
А
— действительная симметричная
матрица
А =
ди
-
д12
д 12
д
22
.
70
Будем искать S и
D
в виде
s==
S11
s
12
”l
D =
dn
0
0
S
22
J
0
^
22
.
где каждое из чисел
dn, йгг
может быть либо 4-1, либо
5*
-1. Т о гд а
VDS
^
slls
12
^U
S]
1
S
12^11
S
w
^H +
S2
и из условия (
2
) получаем три уравнения:
2
,
_
Sll“ll -- ^
11
)
Из первого уравнения
если
а ц ф
0
, то
S 11S 12^11 ---- ^ 1 2i
^12d l l
” Ь $22^22 ---- ^22-
находим dn = sig n a u, sll = 'j/|a11|.
s
12
= di
2
/ (
Sudn)
,
и, наконец,
s
: о.пп
s,
2
d,
Далее,
т. е.
d22 =
sign
(а22
—
s[2dn ), s22
=
Y \ a 22 —
s
2
12du \ .
3.
Общие расчетные формулы. Получим разложение (2) в слу
чае эрмитовой матрицы
А
произвольного порядка
т.
Если S = [ s i3]
и D = diag[du,
dmm],
то элемент матрицы
DS,
имеющий индек
сы (
i
, /), равен
т
(DS),y =
2
di‘s‘i = d “s‘i-
1=1
Кроме того, S*=[sj>], поэтому
(S 'D S );/ = ^
suditsij,
i=i
где
sи
— число, комплексно сопряженное s/;. Из условия (2) полу
чаем уравнения
т
2
sndusij = aih
i, j =
1,2, . . .,
m.
[(9)
i=i
Так как матрица
А
эрмитова, можно, не ограничивая общности,
считать, что в системе (9) выполняется неравенство
Перепи
шем (9) в виде
1-1
т
2
suSiidit
+
SuSi/dii
+ ^
stistidu
=
ац
i= i
/=1+1
и заметим, что
Su— Q
для
l>i.
Таким образом, получим систему
уравнений
i-г _
S a S ijd u
^
SuSijdti
=
й
£/,
i
/•
(10)
В частности, при
i = j
получаем
т. е.
| s
и
|Чц = аи
—
2
l s« l2d“*
1=1
(
‘- 1
\
du
= sign I
аи
—
2
1
sic \%i j ,
S( l
=
Далее, при
i< j
из (10) получим
l-l
an —
2
I s" N »
/=i
au -
2
S i i
—
/=1
Sudii
(
12
)
0 1 )
(13)
По формулам (11) — (13) находятся рекуррентно все ненулевые
элементы матриц
D
и S.
4.
Подсчет числа действий. Метод квадратного корня применя
ется обычно к системам с положительно определенной эрмитовой
матрицей
А.
В этом случае из (
6
) следует положительность диаго
нальных элементов матрицы
К,
и тем самым
D = E
в разложении
(2). Если предположить дополнительно, что
А
— действительная
матрица, то из (11) — (13) получим следующие расчетные формулы:
S n —
У
Оц,
Su
—
аи
—
2
s« •
1=1
su
—
(hilhu
i
— 2, 3, ..
aH ~
2
S‘‘SH
su
= ------ —------- , / = 2, 3, . . .,
m,
su
i =
2, 3,
. m.
i
= 2, 3,
.,m,
(14)
(15)
- . , / -
1
.
Об)
Подсчитаем сначала число умножений. Вычисления по формуле
(14) требуют
3 0 - 1 ) = = ^
умножений. Вычисления по формуле (16) при каждом фиксирован
ном / требуют
2
( » -
1
) = - (/^ и /-
72
умножений, а всего здесь требуется
2
1 = 2
( / -
2
)
0
-
1
)
■ 2
H k - \ )
т(т—
1
)
(т —
2
)
4=1
умножений. Следовательно, общее число умножений
m(m —
1
) |
т (т
—
1
)
(т —
2
)
т
(
т2
—
1
)
Число делений, необходимых для вычислений по формулам
(14) — (16), совпадает с числом наддиагональных элементов матри
цы 5 и равно
т (т
— 1)/2.
Таким образом, общее число действий умножения и деления, не
обходимое для факторизации yi = S*S,
т ( т г
—
1)
.
т ( т
— 1) __
т ( т
—
1) ( т
+
4 )
__
т а
6
2
~
6
"б"'
При больших
т
это число примерно в два раза меньше числа
умножений и делений в прямом ходе метода Гаусса. Такое сокра
щение числа действий объясняется тем, что
А
— симметричная
матрица. Заметим, что данный метод требует
т
операций извлече
ния корня.
Если матрица
А
факторизована в виде ^ = S*S, то обратный
ход метода квадратного корня состоит в последовательном реше
нии двух систем уравнений
S ' y = f , S x = y .
Решения этих систем находятся по рекуррентным формулам
/i
~ 2
W l
yt
= ---— ---,
1 = 2,3
......
т,
sii
(17)
Ui = f
i/sn>
m
9 t ~ s SH*I
' l l
Xm
—
Ут/S
m m
■
(18)
Вычисления по каждой из формул (17), (18) требуют
т
деле
ний и 0,5
т (т
—1) умножений. Следовательно, всего для обратного
хода требуется
т (т +
1) операций умножения и деления. Всего ме
тод квадратного корня при факторизации ,4 = S*S требует
.
, 1Ч ,
т(т—
l)(m + 4)
т
(т* 4- 9т + 2)
т ( т +
1
Н ---- *-------
'
-----------------
о
ь
операций умножения и деления и
т
операций извлечения квадрат
ного корня.
73
§ 6. Обусловленность систем линейных алгебраических уравнений
1. Устойчивость системы линейных алгебраических уравнений.
При использовании численных методов для решения тех или иных
математических задач необходимо различать свойства самой зада
чи и свойства вычислительного алгоритма, предназначенного для
ее решения. Для каждой математической задачи принято рассмат
ривать вопрос о ее корректности. Говорят, что задача поставлена
корректно,
если ее решение существует и единственно и если оно
непрерывно зависит от входных данных. Последнее свойство назы
вается также
устойчивостью
относительно входных данных. Сфор
мулированное здесь общее и не очень четкое определение коррект
ности должно уточняться при переходе к изучению конкретных
классов математических задач. Так, хорошо известны определения
и методы исследования корректности задачи Коши для систем
обыкновенных дифференциальных уравнений, корректная поста
новка типичных задач математической физики.
Корректность исходной математической задачи еще не гаранти
рует хороших свойств численного метода ее решения. Поэтому для
корректно поставленных задач свойства численных методов долж
ны изучаться особо.
Отметим, что часто возникает необходимость численного реше
ния некорректно поставленных задач. Этот круг вопросов подроб
но освещен в книге [38].
В настоящем параграфе вопросы корректности исходной задачи
и численных алгоритмов ее решения рассматриваются на примере
системы линейных алгебраических уравнений
A x = f
(1)
с квадратной матрицей
А
порядка
пг.
Хорошо известно, что для
каждого m-мерного вектора
f
решение
х
задачи (
1
) существует
тогда и только тогда, когда йе{Л=т^0. В этом случае можно опре
делить матрицу Л-1, обратную матрице Л, и записать решение в
виде
х= А ~ %
(
2
)
Для того чтобы убедиться в корректности задачи (1), необходи
мо еще установить непрерывную зависимость решения от входных
данных. В связи с этим возникает по крайней мере два вопроса.
Первый: что считать входными данными задачи (1), и второй: в ка
ком смысле следует понимать непрерывную зависимость? Ответ на
первый вопрос очевиден: входными данными являются правая
Do'stlaringiz bilan baham: |
