[ Буслов, Яковлев ] Введение в численный анализ
.pdf
|
a11 |
a12 |
|
a1N |
|
x1 |
1 = 0 |
b1 |
1 |
|
0 a21 |
a22 |
|
a2N |
1 0 x2 |
b2 |
|||||
B |
|
|
|
|
C B |
|
C |
B |
|
C |
aN1 aN2 |
|
aNN |
xN |
bN |
||||||
|
|
|
|
|
|
|||||
@ |
|
|
|
|
A @ |
|
A |
@ |
|
A |
я ля тся м то Г усс . Вн ч л исхо н я сист м при о ится к рхн тр у ольному и у. то ости тся сл ующ й посл о т льностью пр о р о ний (прямой хо м то Г усс ). Бу м счит ть ля у о ст , что эл м нты aij исхо ной м трицы и компон нты ктор bi ñòü ñîîò òñò ííî ýë ì íòû a(1)ij п р о о ш пр о р о нной м трицы
A1 è ïð î ð î ííî î êòîð b1: A = A1 ; b = b1. Д л , н тором ш при им к торой строк п р ую,
|
|
a21 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
óìíî ííóþ í a11 = c21. Ан ло ично поступим со с ми ост шимися строк ми, т при им к к ой i-ой строк |
||||||||||||||||||||||||||||||||||||||||||||
i = 2; 3; : : : ; N, п р ую, умно нную н коэффици нт i1 = |
ai1 |
. При этом соот тст нно и м нится и ктор b1. Ò êèì |
||||||||||||||||||||||||||||||||||||||||||
a11 |
||||||||||||||||||||||||||||||||||||||||||||
î ð îì |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 ø ) Èì ì ñèñò ìó óð í íèé |
A2x = b2 |
|
: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
0 |
a11(1) |
|
|
|
a12(1) |
|
|
|
|
a1(1)N |
|
|
|
|
|
x1 |
|
1 |
|
|
b1(1) |
1 |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
0 |
|
|
|
|
a(2) |
|
|
|
|
a(2) |
|
10 x2 |
|
= |
0 b(2) |
; |
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
|
|
|
|
|
|
2N |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
B |
|
|
|
|
|
|
|
|
|
|
|
|
CB |
|
|
C |
|
B |
|
C |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
(1)@ |
|
|
|
|
|
|
|
|
A@ |
|
A |
|
@ |
A |
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
0 |
|
|
|
|
a(2)N2 |
|
|
|
aNN(2) |
xN |
|
bN(2) |
|
|
|
|
|||||||||||||||||||||
(2) |
(1) |
(1) |
(2) |
|
|
|
|
(1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
aij |
= aij |
+ ci1a1j |
; bi |
|
= bi |
|
+ ci1b1 |
|
; |
i |
|
2 : |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2) |
|
||
3 ш ) При им к но ой тр ть й строк но ую торую, умно нную н c32 |
= aa22(2)32 . Òî ñ ìî ñ ë ì ñ |
|||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ai(2)2 |
|
ост льными строк ми 4 ; 5 ; : : : ; N, т. . при им к к ой i-ой строк торую умно нную н ci2 = a22(2) |
; i > 2. Ïðè |
|||||||||||||||||||||||||||||||||||||||||||
этом получим сист му |
A3x = b3 |
|
: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
0 |
a11(1) |
|
a12(1) |
a13(1) |
|
|
|
|
a1(1)N |
|
|
|
x1 |
|
1 |
|
b1(1) |
1 |
|
|
||||||||||||||||||
|
|
|
|
|
|
|
0 |
|
|
a22(2) |
a23(2) |
|
|
|
a2(2)N |
1 0 x2 |
|
0 b2(2) |
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
0 |
|
|
|
|
0 |
|
|
a33(3) |
|
|
|
a3(3)N |
|
|
|
x3 |
|
|
= |
|
b3(3) |
|
|
; |
|
|||||||||||
|
|
|
|
|
|
B |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C B |
|
|
|
|
C |
B |
|
|
|
C |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
|
|
A @ |
|
A |
@ |
|
A |
|
|
||||||||||||||||||
|
|
|
|
|
|
|
0 |
|
|
|
|
0 |
|
|
aN(3)3 |
|
|
|
aNN(3) |
xN |
bN(3) |
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
(k+1) |
|
|
(k) |
|
|
|
|
|
(k) (k+1) |
|
|
|
(k) |
|
|
|
(k) |
|
|
|
|
|
|
|
a(k) |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ik |
|
|
|
(k + 1)-ûé ø ) Ç ñü |
aij |
|
= aij |
|
+ cikakj , bi |
|
|
|
= bi |
+ cik bk |
|
, cik = akk(k) |
; i; j > k. |
|
||||||||||||||||||||||||||||||
Поступ я т к и л н (N 1)-ом ш получ м рхн тр у ольную сист му: |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
0 |
a11(1) |
|
a12(1) |
|
|
|
a13(1) |
|
|
|
|
|
|
|
|
|
a1(1)N |
|
|
|
|
x1 |
1 |
|
|
b1(1) |
1 |
|
||||||||||||
|
|
|
|
0 |
|
|
a22(2) |
|
|
|
a23(2) |
|
|
|
|
|
|
|
a2(2)N |
10 x2 |
|
0 b2(2) |
|
|||||||||||||||||||||
|
|
|
|
|
|
0 |
|
|
0 |
|
|
|
|
a33(3) |
|
|
|
|
|
|
|
a3(3)N |
|
|
|
|
x3 |
|
= |
|
b3(3) |
: |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
B |
0 |
|
|
0 |
|
|
|
|
0 |
|
|
|
a44(4) |
|
|
|
a4(4)N |
CB |
|
x4 |
C |
|
B |
b4(4) |
C |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A@ |
|
|
A |
|
@ |
|
A |
|
|||||||||||||||
|
|
|
|
0 |
|
|
0 |
|
|
|
|
0 |
|
|
|
|
|
|
|
0 aNN(N) |
|
xN |
|
bN(N) |
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
При этом мы т к получили м трицу C п р о ных коэффици нто , им ющую и : |
|
|||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
0 |
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
0 c21 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c31 |
|
|
c32 |
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
: |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c41 |
|
|
c42 |
|
c43 |
|
|
0 |
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
B |
|
|
|
|
|
|
|
|
|
|
... |
|
|
|
|
C |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
|
A |
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
cN1 |
|
|
cN2 |
|
cN3 |
|
|
|
cNN 1 |
|
0 |
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
61
Р ш ни получ нной тр у ольной сист мы Ux = f (U = AN ; f = bN ), ê ê ë êî è òü, èì ò è (î ð òíûé õî ì òî Ã óññ )
|
fNN |
|
1 |
|
N |
|
|
|
|
X |
|
||||
xN = UNN |
; xk = Ukk (fk |
Ukixi) ; k = N ; N 1 ; : : : ; 1 : |
|||||
i=k+1 |
З м тим, что при прямом хо м то Г усс мо т о никнуть ситу ция, ко происхо ит л ни н нуль, иоо щ л т льно н лить н м ло число, что ы н н к пли л сь оши к . Поэтому м то Г усс о ычно про о ят с ч стичным ы ором л но о эл м нт , то сть посл к о о ш (пусть это ыл k-й ш ) п р ст ляют строки с ном р ми k ; k + 1 ; : : : ; N т ким о р ом, что ы н м ст kk ок лся эл м нт a(mkk) , н и ольший и с х k-ом стол ц при m > k (при этом, ст ст нно, п р ст ляются и компон нты ктор b).
Мо но ля м ксим льной точности п р ст лять т к и стол цы пр о р у мой м трицы, что ы н м ст kk ок лся м ксим льный эл м нт и с х с ин кс ми ольш ли о р ными k. т проц ур н ы тся м то ом Г усс с ы ором л но о эл м нт . Он н сколько по ыш т точность по ср н нию с ч стиным ы ором л но о эл м нт , но сьм н у о н , том числ и ля про р ммиро ния, поскольку при п р ст но к строк компон нты искомо о ктор x п р ст лять н н о, то к к при п р ст но к стол цо н о п р ст лять и соот тст ующи компон нты ктор x.
Опиш м о р тный хо м то Г усс н сколько иной форм (тр у ольно р ло ни ). В м м трицы Mk ïî ïð èëó
|
0 0 |
1 |
|
0 |
|
0 |
1 |
|
|
|
1 |
0 |
|
0 |
|
0 |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
.. |
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|||||
Mk = |
|
0 |
0 |
|
1 |
|
0 |
; |
|
|
|
|
|
||||
|
|
0 |
0 |
|
ck+1;k |
|
0 |
|
|
|
0 |
0 |
|
ck+2;k |
|
0 |
|
|
B |
|
|
|
|
... |
|
C |
|
|
|
|
|
|
|
||
|
@ |
0 |
0 |
|
cN;k |
|
1 |
A |
|
|
|
|
|
|
|
то н к ом ш м то Г усс получ тся н котор я пром уточн я м триц Ak+1 =MkMk 1 : : : M1A , и ктор fk+1 = MkMk 1 : : : M1b . Н тру но и ть, что
N 1 |
N 1 |
Y |
Y |
U = MiA ; f = |
Mib ; |
i=1 |
i=1 |
N
Ux = f ; det U = YUii = det A :
i=1
Вопрос. Ïî÷ ìó det U = det A?
Если прои о ить т к ы ор л ных эл м нто , то н о хо имо исполь о ть оп р тор P п р ст но ки ин ксо
l и m, м тричны эл м нты которо о р ны: pij = 0 , i; j = l; m ; |
pim = pmi = 0 , i = l ; |
pli = pil = 0 , i = m ; |
6 |
6 |
6 |
pml = plm = 1 . При прим н нии оп р тор п р ст но ки ин ксо к м триц сл , м няются м ст ми строки м трицы и компон нты с о о но о ктор (P Ax = P b) , сли о прим нить спр к м триц , то м няются м ст ми
стол цы и компон нты р ш ния (A P P x = b).
|{z}=I
5.2.3L-R ð ëî íè
Для р ш ния чи Ax = b н сколько мо ифициру м . Им нно м N (N + 1) м трицу
62
|
|
C = 0 |
|
A |
|
|
|
|
|
. |
1 |
||
|
|
|
|
|
|
|
|
|
|
|
|
b1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
b2 |
|
|
|
|
B |
|
|
|
|
|
|
|
. |
C |
|
|
|
|
|
|
|
|
|
|
|
bN |
|||
|
|
|
@ |
|
|
|
|
|
|
|
. |
A |
|
|
X = (x1; x2; : : : ; xN ; 1)T |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
||||
è êòîð |
р м рности (N + 1), то исхо н я ч эк и л нтн сл ующ й |
||||||||||||
|
|
|
|
|
|
CX = 0 : |
|
|
|
|
|||
Ïð ñò èì C è C = LR, L íè í òð ó îëüí ÿ |
N N ì òðèö |
||||||||||||
|
|
|
|
|
l11 |
0 |
|
0 |
|
|
|||
|
|
|
|
0 l21 |
|
|
|
1 |
|
||||
|
|
L = |
l22 |
|
0 |
; |
|||||||
|
|
|
. . |
. |
. |
|
. |
|
|||||
|
|
|
|
|
. . |
. |
|
|
|||||
|
|
|
|
@ |
. . |
|
|
. . |
A |
|
|||
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
BlN1 |
lN2 |
|
|
|
lNN C |
|
|||
R |
N (N + 1)-ì òðèö è |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
r12 |
r13 |
|
|
0 |
1 |
r23 |
|
||
R = |
0 |
0 |
1 |
. |
|
|
. . |
. |
|||
B |
. . . . |
. |
|||
. . . |
|
||||
0 |
0 |
0 |
|
||
@ |
|
|
|
К к н хо ить м трицы L è R?
r1N r1;N+1 r2N r2;N+1
r3N r3;N+1
... ...
1rN;N+1
1
:
C
A
1-й ш ) ) Умно им к ую строку м трицы L |
н п р ый стол ц м трицы R, отку li1 = ci1. Ò êèì î ð îì ìû |
|||||||
опр лили п р ый стол ц м трицы |
L. |
|
|
|
|
|
|
|
) Умно им п р ую строку |
L |
í ê ûé ñòîë ö R, îòêó |
r1i = c1i=l11, то сть опр л н п р я строк |
|||||
R. |
|
|
|
|
|
|
|
|
2-й ш ) a) Умно им к ую строку |
L (н чин я со торой) н к ый стол ц |
R и опр лим торой стол ц L: |
||||||
li2 = ci2 li1r12. |
|
|
|
|
|
|
|
|
) Умно я торую строку |
L |
í ê ûé ñòîë ö |
R опр ля м торую строку R: r2i = (c2i l21r1i)=l22. |
|||||
m-й ш ) Пусть и стны п р ы m 1 |
ñòîë ö |
L è m 1 |
строк |
R, òî ïðè i m |
||||
|
|
|
|
|
|
|
m 1 |
|
|
|
|
m 1 |
|
|
cmi k=1 lmkrki |
|
|
lim = cim |
k=1 |
likrkm ; rmi = |
|
lPmm |
: |
|||
|
|
|
X |
|
|
|
|
|
Т п рь м тим, что о с н т н о хо имости р ш ть чу CX = 0 , ост точно р шить сист му RX = 0. |
||||||||
Д йст ит льно, р н м трицы R р н |
N , ò êèì î ð îì èñõî í ÿ ì òðèö A è L ûðî íû èëè í ûðî íû |
|||||||
о но р м нно. Компон нты xi í õî èì ïîñë î ò ëüíî, í ÷èí ÿ ñ N-îé: |
|
N
xN = rN;N+1 ; xi 1 = ri;N+1 X rikxk : k=i+1
Вычисл ния по и ло нному м то у тр уют р м ньший о ъ м п мяти, ч м по м то у Г усс .
5.2.4Ì òî ïpî îíêè
Пусть A тр х и он льн я м триц , которую мы пр ст им и :
63
|
|
|
|
|
0 |
c1 |
b1 |
0 |
0 |
0 |
|
0 |
|
0 |
|
1 |
|
|
|
|||||
|
|
|
|
|
a2 |
c2 |
b2 |
0 |
0 |
|
0 |
|
0 |
|
|
|
|
|||||||
|
|
A = |
|
|
0 |
a3 |
c3 |
b3 |
0 |
|
0 |
|
0 |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
A |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
B 0 |
0 |
|
0 |
0 |
0 |
aN cN C |
|
|
|
||||||||||
Çí ê ï p bi ; ci ïîñò ë í ëÿ ó î ñò . Äëÿ ð ø íèÿ ÷è |
At = s |
ýòîì ñëó÷ ïðèì íÿ òñÿ ì òî |
||||||||||||||||||||||
ïðî îíêè. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ïîëî èì a1 = bN = 0 , òî òð õ è îí ëüí ÿ ñèñò ì ìî ò ûòü ïèñ í è |
|
|
|
|||||||||||||||||||||
|
|
|
tk 1ak + tkck tk+1bk = sk ; k = 1 ; 2 ; : : : ; N : |
|
|
|
||||||||||||||||||
Р ссмотpим эту сист му по pо н . Выр им и п р о о ур н ния |
t1 ÷ ð |
t2 : |
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
b1 |
|
|
s1 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
t1c1 t2b1 = s1 ) t1 = c1 t2 + c1 : |
|
|
|
|
|
|
|
||||||||||
Ò ï ðü è òîðî î óð í íèÿ ûð èì |
t2 ÷ ð t3 : t1a2 + t2c2 t3b2 = s2, èëè |
|
|
|
|
|||||||||||||||||||
|
s1 |
|
b1 |
|
|
|
|
|
|
|
|
|
|
b2t3 |
|
|
s2 + ac12 s1 |
|
|
|
||||
|
c1 |
+ |
c1 |
t2 a2 + t2c2 t3b2 = s2 ) t2 = |
c2 |
b1 |
a2 |
+ |
c2 cb11 a2 |
: |
|
|
||||||||||||
|
c1 |
|
|
|
||||||||||||||||||||
Àí ëî è÷íî |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
tk = ktk+1 + k ; |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bk |
|
|
sk + k 1ak |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
k = |
ck k 1 ak |
; k = ck |
k 1 ak |
: |
|
|
|
|
|
||||||||
У имся спр ли ости это о пр ст л ния по ин укции. Д йст ит льно 1 = b1 ; 1 |
= |
s1 |
, ò êèì î ð îì |
|||||||||||||||||||||
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c1 |
|
c1 |
|
ин укции pн . Т п pь осущ ст им со ст нно ин укционный п р хо . Пусть tk = ktk+1 + k , òî |
||||||||||||||||||||||||
|
|
|
|
|
|
|
ak+1tk + ck+1tk+1 bk+1tk+2 = sk+1 ; |
|
|
|
|
|
|
|
||||||||||
|
|
|
ak+1( ktk+1 + k) + ck+1tk+1 bk+1tk+2 = sk+1 ; |
|
|
|
||||||||||||||||||
îòêó |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
tk+1 = |
|
|
bk+1tk+2 |
+ sk+1 + kak+1 = k+1tk+2 + k+1 ; |
|
|
|
||||||||||||||||
|
|
ck+1 |
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
kak+1 |
ck+1 kak+1 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
то сть ин укционный п р хо т к им т м сто. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Р ссмотрим т п рь к ким о р ом прим ня тся м то про онки. Н п p ом эт п (пpямой хо пpо онки) мы опp -ля м коэффици нты k ; k ÷ p è ñòíû í ì ýë ì íòû ì òpèöû A (bk ; ck ; ak) , íû í ÷ íèÿ sk è ïp û óùè k 1 ; k 1:
b1 |
9 p |
|
bk |
|
1 = c1 |
k = ck k 1ak |
|||
s1 |
> |
sk+ k 1ak |
||
1 = c1 |
= |
k = ck k 1ak |
||
Посл то о к к опр л ны коэффици нты k>è k |
í ÷èí òñÿ î p òíûé õî ïpî îíêè ñî ñò ííî îïp ë íè |
|||
|
; |
|
|
|
компон нт tk . Èì ì
64
tN = N tN+1 + N ;
ïðè ýòîì N = 0 , ò.ê. bN = 0 , N = bN . Ò êèì î ð îì
cN N 1aN
tN = N ( ) ;
tk = ktk+1 + k ( ) :
Óò p íè (Дост точно усло и p p шимости пpо онки): Пусть jckj > jbkj + jakj , k = 1 ; : : : ; N , òî
det A =6 0.
Äîê ò ëüñò î. Н о хо имо у иться, что н м н т ль фоpмул х пpямо о хо н о p щ тся нуль. Для это оост точно у иться том, что j kj < 1. Â ü ñëè ýòî ò ê, òî
jck k 1akj jckj j k 1jjak j > jckj jakj > jbkj 0
и н происхо ит л ния н нуль. Им м :
b1
j 1j = jc1 j < 1 ;
Ì òî èò ð öèé ëÿ ð ø íèÿ ëèí éíûõ ñèñò ì Ñèñò ì ëèí éíûõ óð í íèé Ax = b :
j |
k |
j |
= |
jbkj |
< jbkj |
= 1 : |
|
|
jck k 1akj |
jbkj |
|
N |
|
X |
|
aijxj = bi ; i = 1; 2; : : : ; N ; |
(1) |
j=1
мо т ыть р ш н н только прямыми м то ми, но т к и ит р ционными. Р ум тся мы пр пол м, что сист м
èì ò èíñò ííî ð ø íè , ò. . ÷òî |
det A = 0. |
|
|
|
|
|
6 |
|
|
|
|
Пр ст им м трицу A и |
A = B + D , D = diag |
a11 ; : : : ; aNN |
g |
. Ïð ïîëî èì, ÷òî |
det D = 0 , ÷òî |
|
f |
|
|
6 |
р носильно тому, что aii =6 0 ; i = 1 ; : : : ; N ( сли исхо но это н т к, то п р ст но кой строк и стол цо это о с
мо но о иться при det A =6 0 ). Òî (1) ï ð ïèñû òñÿ è Dx = b Bx, èëè
x = D 1b D 1Bx :
Пр ло им сл ующую ит р ционную проц уру
|
|
xs+1 = D 1b D 1Bxs ; |
|||
x0 прои ольный н ч льный ктор. В р рнутой форм |
|
||||
|
|
|
n |
|
|
s+1 |
1 |
1 |
X |
s |
|
xi |
= aii |
bi aii |
6 |
aijxj |
; i = 1; 2; : : : N : |
|
|
|
j=1;j=i |
|
|
Î î í ÷èì D 1b = u ; D 1B = T , то ит р ционный проц сс приним т и
xs+1 = u Txs : |
(2) |
Ò îð ì 1. Ïðîö ññ (2) ñõî èòñÿ, ëÿ ëþ î î í ÷ ëüíî î êòîð , ñëè jjD 1(A D)jj = jjT jj < 1 :
Äîê ò ëüñò î. Для ок т льст ост точно м тить, что ото р ни x ! u T x ÿ ëÿ òñÿ ñ òè ì.
Т ким о р ом посл о т льность xs им т пр л. Пусть x = lim xs, òî x = u Tx , èëè î ð ù ÿñü s!1
к исхо ной формулиро к Ax = b . Ит к ля схо имости и ло нно о м то , н ы мо о м то ом простых ит р ций, н о хо имо что ы
65
jjD 1(A D)jj < 1 :
5.2.5Ì òî Ç é ëÿ
Мо ифициру м м то простых ит р ций, коор ин тную форму которо о, ч стности, мо но пис ть и
xis+1 |
= aii1bi |
X |
aijxjs |
X |
aijxjs ; i = 1; 2; : : : ; N : |
|
|
|||||
|
|
j<i |
|
|
|
|
j>i |
|
|
|
|
|
|
|
| |
|
{z |
|
} |
|
|
|
s+1 |
s+1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
З м тим, что сли посл о т льно ычислять компон нты (s + 1)- о при ли ния x |
|
í ÷èí ÿ ñ ï ð îé x1 , òî ê |
||||||||||
|
|
|
|
|
s+1 |
|
|
s+1 |
s+1 |
|
|
|
мом нту ычисл ния конкр тной i-ой компон нты xi |
, êîîp èí òû x1 |
; : : : ; xi 1 ó îïp ë íû è èõ ìî íî ûëî |
ы исполь о ть ля опp л ния ол точно о посл ующ о при ли ния xs+1 . Мо ифициру м соот тст ующим о р ом м то простых ит р ций, м ни сумм компон нты xsj í xsj+1 . Т ким о р ом мы получ м но ую ит р ционную проц уру
s+1 |
1 |
1 |
X |
s+1 |
1 |
X |
s |
|
xi |
= aii |
bi aii |
j<i |
aij xj |
aii |
j>i |
aijxj |
; i = 1; 2; : : : ; N : |
Т кой ит p ционный пpоц сс н ы тся м то ом З й ля. Пр ст им о м тpичной фоpм . Пусть L ни н тр -
ó îëüí ÿ ì òðèö ñ ýë ì íò ìè |
|
|
|
|
|
L : |
|
|
|
|
|
lij = ( |
aij |
; j < i |
; |
||
0 |
; j |
|
i |
||
U ðõí òð ó îëüí ÿ ì òðèö ñ ýë ì íò ìè |
|
|
|
|
|
|
aij |
; j > i |
|
||
uij = ( 0 |
; j |
|
i |
: |
Ê ê è p íüø ì ì òpèöó D = diagfa11 : : : aNN g , то A = D + L + U . В м тричном и м то З й ля им ти :
xs+1 = D 1b D 1Lxs+1 D 1Uxs :
5.2.6Схо имость м то З й ля
Èò ê, èò p öèè ïî ì òî ó Ç é ëÿ îë íû ûòü îp íè î íû ò êèì î p îì, ÷òî û
Dxs+1 = b Lxs+1 Uxs ;
èëè
xs+1 = (D + L) 1b (D + L) 1Uxs :
Îòî ð íè x 7!(D + L) 1b (D + L) 1Ux ÿ ëÿ òñÿ ñ òè ì, ñëè jj(D + L) 1Ujj < 1 , ò êèì î ð îì ñïð ëè Ò îp ì . Ì òî Ç é ëÿ ñõî èòñÿ, ñëè jj(D + L) 1U jj < 1.
Усло ия этой т ор мы о ольно тpу но пpо pя мы, т к к к м тpиц (D + L) 1U ол н щ и ычисляться. Сущ ст у т ост точно пpостой пpи н к схо имости м то З й ля, котоpый с я н с поняти м поло ит льной опp -л нности м тpицы относит льно ск ляpно о пpои ния. Н помним, что оп р тор A, йст ующий кли о ом простр нст En í û òñÿ ïîëî èò ëüíî îïð ë ííûì, ñëè
66
hAx; xi hx; xi ; > 0 :
Åñëè îï ð òîð ïîëî èò ëüíî îïð ë í, òî ó í î ñóù ñò ó ò è î ð òíûé è îí ò ê ïîëî èò ëüíî îïð ë í. Ò ê
íî îòì òèòü, ÷òî ñëè îï ð òîð A ïîëî èò ëüíî îïð ë í è ñèìì òðè÷ í RN , òî ôîðì
hx; yiA = hAx; yi
у о л т оря т с м с ойст м ск лярно о прои ния. В льн йш м ф кт поло ит льной опр л нности оп р - тор A у м о о н ч ть: A > 0 . З м тим, что компл ксном кли о ом простр нст ф кт поло ит льной опр л нности п р тор A том тич ски л ч т со ой эрмито ость: A = A .
Ò îð ì ( ост точный при н к схо имости м то З й ля). М то З й ля схо ится щ ст нном кли о ом простр нст сли A симм тричн я поло ит льно опр л нн я м триц .
Äëÿ îê ò ëüñò ýòîé ò îð ìû í ì ïîòð ó òñÿ ñë óþù ÿ
Л мм .Пусть посл о т льность кторо zk опр л н р кур нтным соотнош ни м
B(zk+1 zk) + Azk = 0 ; |
(3) |
B 12 A > 0 ; A > 0 ; òî zk ! 0 .
Äîê ò ëüñò î. Ïð ñò èì zk è
zk = 12 (zk+1 + zk) 12 (zk+1 zk) ;
è ïî ñò èì ýòî ïð ñò ë íè (3), òî
B(zk+1 zk) + 12 A(zk+1 + zk) 12 A(zk+1 zk) = 0 ;
èëè
|
|
|
|
1 |
|
|
|
|
k+1 |
z |
k |
|
1 |
|
|
k+1 |
|
|
|
k |
|
|
|
|
||
|
(B |
2 A)(z |
|
|
) + |
2 A(z |
|
+ z |
|
|
) = 0 : |
|
|
|||||||||||||
Умно им это р нст о ск лярно н zk+1 zk , òî |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
0 = jz |
k+1 |
z |
k |
jB A=2 + |
1 |
|
k+1 |
|
|
k |
|
|
|
k+1 |
z |
k |
i = |
||||||||
|
|
|
|
2 hA(z |
|
|
+ z |
|
); z |
|
|
|
||||||||||||||
|
= jz |
k+1 |
z |
k |
|
|
|
|
1 |
|
k+1 |
jA jz |
k |
jAg = 0 ; |
|
|||||||||||
|
|
|
|
jB A=2 + 2 fjz |
|
|
|
|||||||||||||||||||
j jA = hA ; i ; |
j jB A=2 = hfB A=2g ; i |
|
нормы, опр ля мы оп р тор ми A и B A=2 соот тст нно. И |
|||||||||||||||||||||||
посл н о р нст силу поло ит льной опр л нности оп р тор (B A=2) сл у т что jzk+1jA jzkjA 0 , ò. . |
||||||||||||||||||||||||||
посл о т льность |
jzkjA í î ð ñò þù ÿ: jzk+1jA jzkjA . При этом посл о т льность чис л jzkjA î ð íè÷ í |
сни у поскольку jzkjA 0 . Ò êèì î ð îì ñóù ñò ó ò êîí ÷íûé ïð ë lim jzkjA = a . Íî òî è òî î ð íñò k!1
ñë ó ò, ÷òî íîðì jzk+1 zkj(B 12 A) стр мится к нулю, н чит и zk+1 zk ! 0 ; k ! 1 . В рн мся т п рь к опр л нию посл о т льности zk :
Azk = B(zk+1 zk) ;
îòêó zk = A 1B(zk+1 zk) è, ñë î ò ëüíî,
jjzkjj jjA 1Bjj jjzk+1 zkjj ! 0 ;
è ò êèì î ð îì zk ! 0, ïðè k ! 1.
67
Приступим т п рь со ст нно к ок т льст у ост точно о при н к схо имости м то З й ля. К к н тру нои ть, м то З й ля (D + L)xs+1 + Uxs = b ìî ò ûòü ïð ñò ë í è
|
|
|
(D + L)(xs+1 xs) + Axs = b : |
Пусть u точно p ш ни уp н ния |
Au = b , îíî ñóù ñò ó ò, ò ê ê ê A ïîëî èò ëüíî îïð ë ííûé îï ð òîð |
||
è, ñë î ò ëüíî, î ð òèì. Ïîëî èì ò ê zs = xs u , òî |
|||
|
|
|
(D + L)(zs+1 zs) + Azs = 0 : |
Ó èìñÿ òîì, ÷òî (D + L |
1 |
A) |
поло ит льно опр л нн я м триц сли A симм тричн иполо ит льно |
2 |
|||
îïð ë í . Ä éñò èò ëüíî |
|
D + L 12 A = D + L 12 (D + L + U) = 12 (D + L U) :
Р ссмотрим соот тст ующую к р тичную форму
h(D + L U)x; xi = hDx; xi + hLx; xi hLx; xi :
З м тим, что поскольку A симм тричн я м триц , сл о т льно LT = U è
hLx; xi = hx; LT xi = hx; Uxi = hUx; xi ;
поэтому
Xaiix2i > 0 ;
i
поскольку у поло ит льно опр л нной м трицы с и он льны эл м нты ольш нуля (поч му?): aii > 0 . Т ким о р ом мы н хо имся усло иях Л ммы, и, сл о т льно, посл о т льность zs стр мится к нулю, отку сл у т, что посл о т льность xs = u + zs стр мится к истинному р ш нию u .
68
Ãë 6
Àë ð è÷ ñêè ñï êòð ëüíû ÷è
6.1Н которы с ния и м тричной т ории
Пусть A лин йный оп р тор йст ующий щ ст нном RN или компл ксном CN Е кли о ом простр нст : |
||||
A : RN (CN ) ! RN (CN ) . |
|
|||
Число |
и ктор x н ы ются соот тст нно со ст нным числом ( н ч ни м) и со ст нным ктором |
|||
îï ð òîð |
A от ч ющим со ст нному числу , сли Ax = x . |
|||
|
В ч стности, спр ли ы сл ующи т ор мы. |
|||
|
Т ор м 1.Всякий лин йный оп р тор CN èì ò ïî êð éí é ì ð î íî ñî ñò ííî í ÷ íè . |
|||
|
|
|
||
|
Т ор м 2. Со ст нны кторы, от ч ющи р личным со ст нным н ч ниям лин йно н исимы. |
|||
|
|
|
N лин йно н исимых кторо e1; e2; : : : ; eN ( èñ ) ñóù ñò ó ò èíñò- |
|
|
Ò îð ì 3. Äëÿ ëþ î î í îð è |
|||
|
|
|
|
|
нный у льный ис e~1; e~2; : : : ; e~N |
, ò êîé ÷òî hei; e~ji = Æij . |
|||
|
З м тим, что сякий ортонормиро нный ис с мо у л н. Пусть A им т N р личных со ст нных кторо |
xi , то они о р уют ис, и, сл о т льно, сущ ст у т у льный ис x~i . В этом случ , к к н тру но у иться,
сопря нный оп р тор |
A |
( случ щ ст нно о кли о простр нст просто тр нспониро нн я м триц AT ) |
|||||||||||||||||||||||||||
èì ò ê ÷ ñò ñî ñò ííûõ í ÷ íèé ÷èñë |
|
i , к ч ст со ст нных кторо кторы у льно о ис : |
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Axi = ixi ; A x~i = ix~i : |
|
|
|
|
|
|
|
|
|
|||||||||
Ä éñò èò ëüíî |
xi; ix~i |
i |
= |
h |
xi; x~i |
i |
= |
h |
Axi; x~i |
i |
= xi; A x~i |
i |
è, í ëî è÷íî |
h |
xj; A x~i |
i |
= 0 ; |
i = j , òî ñòü |
h |
xj; A x~i |
i |
= |
|||||||
|
h |
|
|
|
|
|
|
|
h |
|
|
|
|
|
|
|
6 |
|
|
||||||||||
Æij hxj; x~ji : Êðîì òî î, í òðó íî ïîê òü ñïð ëè îñòü ñë óþù î ñï êòð ëüíî î ð ëî íèÿ îï ð òîð A : |
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N |
|
|
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
= |
X |
ih ; x~iixi = |
X |
iPi ; |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i=1 |
|
|
|
|
i=1 |
|
|
|
|
|
|
|
|
|
|
îï ð òîðû |
Pi = h ; x~iixi |
суть со ст нны про кторы оп р тор |
A . В с мом л , прои ольный ктор |
|
f |
||||||||||||||||||||||||
ìî íî ð ëî èòü ïî ñî ñò ííûì êòîð ì îï ð òîð |
A : f = Phf; x~iixi |
. Òî |
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
Af = |
hf; x~iiAxi = |
|
hf; x~ii ixi = iPif : |
|
|
|
|
|
|
|
|||||||||||
Пусть A = A эpмито м тpиц (XRN |
ñèììXтричн я). В этойXñèòó öèè ñî ñò ííû í ÷ íèÿ ù ñò í- |
ны, л р ич ск я и ом трич ск я кр тности лю о о со ст нно о н ч ния со п ют, со ст нны ктоpы xi , от ч ющи р личным со ст нным числ м орто он льны, и сущ ст у т ортонормиро нный ис и со ст нныхкторо . В случ о нокр тно ыро нно о со ст нно о н ч ния от ч ющий му со ст нный про ктор P о ном р н и им т и P = h ; xix ( сю у счит м, что со ст нный ктор x нормиро н н иницу). Если по простр нст о р ш ний Ax = x ол ч м о ном рно, то н м ы ир тся прои ольный орто ис xi è ñî ñò ííûé
69
про ктор от ч ющий со ст нному числу пр ст ля т со ой сумму соот тст ующих о ном рных про кторо
P = Ph ; xiixi .
Отм тим (л ко про ря мо ) но с ойст о орто он льных про кторо :
PiPk = ÆikPi :
Ст п нь оп р тор им т сл ующую пись ч р орто он льны про кторы
Am = X mk (A)Pk :
k
Мно очл ны от оп р тор опр ляются к к сумм соот тст ующих ст п н й. Поскольку мно очл н ми мо но пpи-ли ить лю ую функцию, то функцию от оп р тор ст ст нно опр лить к к
f(A) = Xf( k)Pk :
k
Со ст нны функции у оп p тоp и у функции от оп p тоp со п ют, то к к со ст нны н ч ния функции от оп р тор сть числ f( k).
6.2Cо ст нны числ эрмито ых м триц
6.2.1Инт рполяционный м то
Поскольку со ст нны числ i м трицы A я ляются корнями х р кт ристич ско о полином FA( ) = det(A I) ; òî
мо но ычислить FA( ) (n+1)-îì í ó û ð ííîì í ÷ íèè (èõ ñò ñò ííî û èð òü ïðîì óòê ( jjAjj; jjAjj),сли р ницы сп ктр и стны; оц нить их мо но по м ксим льному по мо улю эл м нту м трицы) и построить по ним
инт рполяционный полином ст п ни n, который со п т со ст нно с х р кт ристич ским, посл ч о опр ляютсяо корни. тот м то прим ним и ля н эрмито ых м триц (при соот тст ующ м ы ор м то опр л ния корн й).
6.2.2Í õî íè ì êñèì ëüíî î ïî ìî óëþ ñî ñò ííî î í ÷ íèÿ
Для у о ст у м счит ть, что со ст нны числ пронум ро ны поря к у ы ния их мо уля.
) Ì òî èò p öèé
Пусть g = g0 прои ольный н ч льный ктор. Опр лим посл о т льность
|
|
|
|
g |
n |
= A |
|
gn 1 |
|
= |
|
|
Ang |
|
; |
||||
|
|
|
|
|
g(n 1) |
jj |
jj |
An 1g |
jj |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
òî |
|
|
|
|
|
|
|
|
jj |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
lim jjg(n)jj = j maxj : |
|
|
|
||||||||
|
|
|
|
|
|
|
n |
|
|
Ang |
|
|
|
|
|
|
|
|
|
Äîê ò ëüñò î: Ä éñò èò ëüíî g = |
P |
Pkg ; kjg |
|
jj = |
jjjjAn 1gjjjj |
, è |
X |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Ang |
= |
X |
knPkg = maxn (Pmaxg + |
f k= maxgnPkg) : |
k=16
Пусть 0 со ст нно число, сл ующ м ксим льным по мо улю. То
jjAngjj2 = hAng; Angi = 2maxn (hPmaxg; gi + O([ 0= max]2n)) ;
70