А. А. Самарский, А. В. Гулин


м а т р и ц а с п о л о ж и т е л ь н ы м и э л е м е н т а м и н а г л а в н о й д и а г о н а л и



Download 18,25 Mb.
Pdf ko'rish
bet62/257
Sana19.04.2022
Hajmi18,25 Mb.
#562450
1   ...   58   59   60   61   62   63   64   65   ...   257
Bog'liq
А. А. Самарский, А. В. Гулин

м а т р и ц а с п о л о ж и т е л ь н ы м и э л е м е н т а м и н а г л а в н о й д и а г о н а л и .
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/;. Из условия (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
 =
й
£/, 

/•
(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), и второй: в ка­
ком смысле следует понимать непрерывную зависимость? Ответ на 
первый вопрос очевиден: входными данными являются правая 
Download 18,25 Mb.

Do'stlaringiz bilan baham:
1   ...   58   59   60   61   62   63   64   65   ...   257




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish