В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 7
Текст из файла (страница 7)
. T24 T23 .Ïîñëå (n − 1) øàãîâ ïîëó÷èì ñèñòåìó(n−1)a11(n−1)x2 + a13(n−1)x2 + a23x1 + a12a22(n−1)x3 + . . . + a1n(n−1)xn = b 1(n−2)x3 + . . . + a2n(n−1),(n−2)xn = b 2(n−1),....................................................................(n−1)ann(n−1)xn = b n,(5.7)5.1. ÌÅÒÎÄ ÂÐÀÙÅÍÈÉãäå(l−1)akj(l−2)= ckl akj51(k−1)+ skl alj,(k)alj(l−2)= −skl akj(k−1)+ ckl alj,j = k, k + 1, .
. . , n,(l−1)bk(l−2)= ckl bk(k−1)+ skl bl,(k)blk = 1, . . . , n,(l−2)= −skl bk(k−1)+ ckl bl,(5.8)l = k + 1, . . . , n,à(l−2)ckl = r³(k−1)akk´2 ³´2 ,(l−2)(k−1)+ alkakkskl = r³(l−2)akkalk´2³+(k−1)alk´2 .(5.9) ìàòðè÷íîé çàïèñè ïîëó÷åííàÿ ñèñòåìà èìååò âèäA(n−1) x = b(n−1) ,ãäåA(n−1) = Tn−1 A(n−2) ,b(n−1) = Tn−1 b(n−2) ,Tn−1 = Tn−1n .Îáîçíà÷èì ÷åðåç R ïîëó÷åííóþ âåðõíþþ òðåóãîëüíóþ ìàòðèöó A(n−1) . Îíà ñâÿçàíà ñ èñõîäíîé ìàòðèöåé A ðàâåíñòâîìR = T A,(5.10)ãäå T = Tn−1 Tn−2 .
. . T1 .Çàìå÷àíèå 5.2. Äåéñòâèå ìàòðèöû Tkl íà âåêòîð x ýêâèâàëåíòíî åãî ïîâîðîòó ïðîòèâõîäà ÷àñîâîé ñòðåëêè â êîîðäèíàòíîé ïëîñêîñòè Oxk xl íà óãîë ϕkl òàêîé, ÷òîcos ϕkl = ckl ,sin ϕkl = skl .Ñóùåñòâîâàíèå òàêîãî óãëà ãàðàíòèðóåòñÿ ñîîòíîøåíèÿìè (5.9). Ýòà ãåîìåòðè÷åñêàÿèíòåðïðåòàöèÿ è äàëà íàçâàíèå ìåòîäó.Ñ ó÷åòîì (5.2), (5.6) è ò.ä. ëåãêî âèäåòü, ÷òîTkl TklT = I,ò.å. ìàòðèöû Tkl îðòîãîíàëüíûå.
Ïðîèçâåäåíèå îðòîãîíàëüíûõ ìàòðèö åñòü ìàòðèöàîðòîãîíàëüíàÿ, è ïîýòîìó T åñòü îðòîãîíàëüíàÿ ìàòðèöà, ðàâíî êàê è T T = T −1 = Q.Îòñþäà è èç (5.10) íàõîäèì, ÷òîA = QR.(5.11)Óïðàæíåíèå 5.3. Ïîêàçàòü, ÷òî äëÿ ïîñòðîåíèÿ ðàçëîæåíèÿ (5.11) ñ èñïîëüçîâàíèåì ôîðìóë (5.8), (5.9), òðåáóåòñÿ ≈ 4n3 /3 äåéñòâèé óìíîæåíèÿ.52 5. ÌÅÒÎÄÛ ÂÐÀÙÅÍÈÉ È ÎÒÐÀÆÅÍÈÉÇàìå÷àíèå 5.3.
Ïðèíèìàÿ âî âíèìàíèå ðåçóëüòàòû âû÷èñëåíèé èç óïðàæíåíèÿ 5.3,çàêëþ÷àåì, ÷òî ìåòîä âðàùåíèé ïðèìåðíî â ÷åòûðå ðàçà áîëåå òðóäîåìîê, ÷åì ìåòîäÃàóññà.Âûÿñíèì, êàêèìè æå äîñòîèíñòâàìè îáëàäàåò ýòîò ìåòîä ïî ñðàâíåíèþ ñ ìåòîäîì Ãàóññà, áëàãîäàðÿ êîòîðûì îí çàñëóæèâàåò ïðàâî íà ñóùåñòâîâàíèå íåñìîòðÿ íàáîëüøóþ òðóäîåìêîñòü.Ñ ó÷åòîì (5.2) èç (5.5) íàõîäèì, ÷òî(1)(1)[a1j ]2 + [a2j ]2 = c212 a21j + s212 a22j + 2c12 s12 a1j a2j ++ s212 a21j + c212 a22j − 2s12 c12 a1j a2j = a21j + a22j ,j = 1, 2, . . . , n,ò.å. ñóììà êâàäðàòîâ ïåðâûõ ýëåìåíòîâ j -ãî ñòîëáöà íå èçìåíèëàñü.
Åñëè ó÷åñòü,÷òî íà ïåðâîì ìàëîì øàãå êîýôôèöèåíòû îñòàëüíûõ óðàâíåíèé íå èçìåíèëèñü, òîïîëó÷åííîå ðàâåíñòâî îçíà÷àåò: äëèíà ëþáîãî ñòîëáöà ìàòðèöû íå èçìåíèëàñü. Òî÷íîòàê æå èç ôîðìóë (5.6), (5.7) âûâîäèì, ÷òî(2)(1)(1)[a1j ]2 + [a3j ]2 = [a1j ]2 + a23j ,j = 1, . . . , n,ò.å. äëèíû ñòîëáöîâ íåèçìåííû è íà 2-îì ìàëîì øàãå. Ýòî âåðíî è ïî îòíîøåíèþ êêàæäîìó èç ïîñëåäóþùèõ øàãîâ, è ïî îòíîøåíèþ ê ïðÿìîìó õîäó â öåëîì. Òàêèìîáðàçîì, â îòëè÷èå îò ìåòîäà Ãàóññà ìåòîä âðàùåíèé çàñòðàõîâàí îò ðîñòà ýëåìåíòîâïðîìåæóòî÷íûõ ìàòðèö: íà ïðîòÿæåíèè âñåãî ïðîöåññà èñêëþ÷åíèÿ àáñîëþòíàÿ âåëè(k)÷èíà êîýôôèöèåíòà aij íå ìîæåò ïðåâîñõîäèòü äëèíó j -ãî ñòîëáöà èñõîäíîé ìàòðèöûA.
Êàê ñëåäñòâèå, ìàòðèöà δA ìàòðèöà ýêâèâàëåíòíûõ âîçìóùåíèé, ó÷èòûâàþùàÿîøèáêè ïðîìåæóòî÷íûõ âîçìóùåíèé, äëÿ ìåòîäà âðàùåíèé áóäåò ìàëà, ò.å. ìåòîäâñåãäà óñòîé÷èâ.5.2 Ìåòîä îòðàæåíèéÐàññìîòðèì åùå îäèí ìåòîä, êîòîðûé äàåò ðàçëîæåíèå ìàòðèöû A â âèäå ïðîèçâåäåíèÿ îðòîãîíàëüíîé è âåðõíåé òðåóãîëüíîé ìàòðèö. Ýòî áóäåò ìåòîä îòðàæåíèé.Ïóñòü w íåêîòîðûé âåêòîð (ñòîëáåö) åäèíè÷íîé äëèíûkwk22 = (w, w) = wT w = 1.(5.12)Ââåäåì â ðàññìîòðåíèå ìàòðèöóU = I − 2wwT ,êîòîðóþ íàçîâåì ìàòðèöåé îòðàæåíèÿ è èçó÷èì åå ñâîéñòâà.(5.13)5.2. ÌÅÒÎÄ ÎÒÐÀÆÅÍÈÉ531◦ .
Ìàòðèöà U ñèììåòðè÷íà, ò.å.U = UT . ñàìîì äåëå, òàê êàê(5.14)(wwT )T = (wT )T wT = wwT ,òî wwT åñòü ñèììåòðè÷íàÿ ìàòðèöà, à â ñèëó (5.13) âìåñòå ñ íåé ñèììåòðè÷íîéÿâëÿåòñÿ è ìàòðèöà U .2◦ . Ìàòðèöà U åñòü îðòîãîíàëüíàÿ ìàòðèöà, ò.å.U −1 = U T .(5.15)Ïðèíèìàÿ âî âíèìàíèå (5.14), (5.13) è (5.12), èìååìU U T = U U = (I − 2wwT )(I − 2wwT ) =TT= I − 4wwT + 4w w| {zw} w = I,k1÷òî è îçíà÷àåò ñïðàâåäëèâîñòü (5.15).3◦ . ×èñëî λ = −1 ÿâëÿåòñÿ îäíîêðàòíûì ñîáñòâåííûì çíà÷åíèåì ìàòðèöû U , êîòîðîìó îòâå÷àåò ñîáñòâåííûé âåêòîð w èç (5.13).
×èñëî λ = 1 ÿâëÿåòñÿ (n − 1)-êðàòíûìñîáñòâåííûì çíà÷åíèåì ìàòðèöû U , êîòîðîìó îòâå÷àåò (n − 1)-ìåðíîå ñîáñòâåííîåïîäïðîñòðàíñòâî, ñîñòîÿùåå èç âñåõ âåêòîðîâ v , îðòîãîíàëüíûõ w. ñèëó (5.14), (5.15) èìååì U 2 = U U T = I . Òàê êàê âñå ñîáñòâåííûå çíà÷åíèÿìàòðèöû I ðàâíû 1, òî ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû U óäîâëåòâîðÿþò ñîîòíîøåíèþλ2U = 1, è, ñëåäîâàòåëüíî, ðàâíû ëèáî +1, ëèáî −1.Äàëåå, ïðèíèìàÿ âî âíèìàíèå (5.13), (5.12), íàõîäèì, ÷òîTU w = (I − 2wwT )w = w − 2w w| {zw} = −w.(5.16)k1Íàêîíåö, ïóñòüÒîãäà(v, w) = wT v = 0.U v = (I − 2wwT )v = v − 2wwT v = v,(5.17)÷òî è òðåáîâàëîñü äîêàçàòü.4◦ . Âåêòîð U y åñòü çåðêàëüíîå îòðàæåíèå âåêòîðà y îòíîñèòåëüíî ïëîñêîñòè, îðòîãîíàëüíîé âåêòîðó w.Ïóñòü y ïðîèçâîëüíûé âåêòîð.
Ïðåäñòàâèì åãî â âèäåy = z + v,(5.18)54 5. ÌÅÒÎÄÛ ÂÐÀÙÅÍÈÉ È ÎÒÐÀÆÅÍÈÉãäå z ïðîåêöèÿ y íà w, ò.å. z = (w, y)w, à âåêòîð v îðòîãîíàëåí w: (w, v) = 0).Ïðèíèìàÿ âî âíèìàíèå (5.16), (5.17), íàõîäèì, ÷òîU y = U (z + v) = −z + v(5.19)(ñì. ðèñ.1)w6z 67yv-−z ?wU yÐèñ. 15◦ . Âåêòîðû y − U y è y + U y îðòîãîíàëüíû äðóã äðóãó. Ïðè ýòîì, åñëè y = z + v ,êàê â (5.18), òîy − U y = 2z,zkw,(5.20)y + U y = 2v,v ⊥ w.(5.21)Óòâåðæäåíèÿ ñëåäóþò èç (5.18), (5.19).6◦ . Ïóñòü x è y ïðîèçâîëüíûå âåêòîðû åäèíè÷íîé äëèíû.
Òîãäà, åñëèw=y + sign (x, y) x,ky + sign (x, y) xk2(5.22)òî ìàòðèöà îòðàæåíèÿ U , ïîñòðîåííàÿ ïî âåêòîðó w, ïåðåâîäèò âåêòîð y â âåêòîð,êîëëèíåàðíûé âåêòîðó x. ñàìîì äåëå, ïóñòü ìàòðèöà îòðàæåíèÿ U îáëàäàåò èñêîìûì ñâîéñòâîì, ò.å. U y =−σx. Íàéäåì âåêòîð w, îáðàçóþùèé ýòó ìàòðèöó. Ñîãëàñíî ñâîéñòâó 5◦ (ñì. (5.20))èñêîìûé âåêòîð w êîëëèíåàðåí âåêòîðó y − U y , à ïîñêîëüêó kwk2 = 1, òîw=y + σx.ky + σxk2 ñèëó 2◦ ìàòðèöà U îðòîãîíàëüíà è ïîýòîìókU yk2 = kyk2 = 1 = |σ| kxk2 = |σ|,(5.23)5.2.
ÌÅÒÎÄ ÎÒÐÀÆÅÍÈÉ55ò.å. σ = ±1. Åñëè y = ±x, òî çíàìåíàòåëü (5.23) áóäåò ðàâåí íóëþ ïðè σ = −sign (x, y) =∓1. Ýòîãî íå ïðîèçîéäåò, åñëè σ = sign (x, y). Åñëè âåêòîð y áëèçîê ê x, òî ìû áóäåìèçáàâëåíû îò íåïðèÿòíîñòåé, ñâÿçàííûõ ñ äåëåíèåì íà ìàëîå ÷èñëî, âûáðàâ è çäåñüσ = sign (x, y). Èç ñêàçàííîãî ñëåäóåò, ÷òî â îáùåì ñëó÷àå öåëåñîîáðàçíî âûáèðàòü σñîãëàñíî (5.22), à åñëè (y, x) = 0, òî, íàïðèìåð, σ = 1.Âîñïîëüçóåìñÿ ìàòðèöåé îòðàæåíèÿ äëÿ ïðèâåäåíèÿ êâàäðàòíîé ìàòðèöû ê òðåóãîëüíîìó âèäó. Íà ïåðâîì øàãå ïðèâåäåíèÿ ðàññìîòðèì â êà÷åñòâå âåêòîðà y èçñâîéñòâà 6◦ íîðìèðîâàííûé ïåðâûé ñòîëáåö ìàòðèöû Avu nuXy1 = [a11 a21 . .
. an1 ]T /ta2i1 ,(5.24)i=1à â êà÷åñòâå x âåêòîð e1 = [1 0 . . . 0]T . Åñëè a21 = a31 = · · · = an1 = 0, òî ïåðåõîäèì(1)ê ñëåäóþùåìó øàãó, ïîëîæèâ A(1) = A, U1 = I è ââåäÿ îáîçíà÷åíèÿ aij = aij . Âïðîòèâíîì ñëó÷àå óìíîæèì ìàòðèöó A ñëåâà íà ìàòðèöó îòðàæåíèÿU1 = I − 2w1 w1T = In − 2w1 w1T ,(5.25)ãäå âåêòîð w1 âû÷èñëÿåòñÿ ñîãëàñíî ôîðìóëå (5.22)w1 = ðåçóëüòàòå ïîëó÷èì ìàòðèöóy1 + sign(e1 , y1 )e1.ky1 + sign(e1 , y1 )e1 k2(5.26)A(1) = U1 A,â ïåðâîì ñòîëáöå êîòîðîé ñòîÿò íóëè âî âñåõ ïîçèöèÿõ, êðîìå ïåðâîé. Ýòèì çàêàí÷èâàåòñÿ ïåðâûé ýòàï.Ïóñòü ìû óæå îñóùåñòâèëè l−1 > 0 øàãîâ è ïðèøëè ê ìàòðèöå A(l−1) ñ ýëåìåíòàìè(l−1)(l−1)aij òàêèìè, ÷òî aij = 0 ïðè i > j , j = 1, .
. . , l − 1.  ïðîñòðàíñòâå Rn−l+1 âåêòîðîâðàçìåðíîñòè n − l + 1 ðàññìîòðèì âåêòîðq(l−1) (l−1)(l−1) T(l−1)(l−1)yl = [all al+1,l . . . anl ] / (all )2 + · · · + (anl )2 .(l−1)(l−1)(l−1)Åñëè al+1,l = al+2,l = · · · = anl= 0, òî ïåðåõîäèì ê ñëåäóþùåìó øàãó, ïîëîæèâA(l) = A(l−1) ,Ul = I. ïðîòèâíîì ñëó÷àå ñòðîèì ìàòðèöó îòðàæåíèÿVl = In−l+1 − 2wl wlT(ðàçìåðû ìàòðèöû Vl è âåêòîðà wl ðàâíû (n − l + 1)), ïåðåâîäÿùóþ âåêòîð yl â âåêòîð,êîëëèíåàðíûé el = [1 0 . . . 0]T ∈ Rn−l+1 , è ïåðåõîäèì ê ìàòðèöåA(l) = Ul A(l−1) ,(5.27)56 5. ÌÅÒÎÄÛ ÂÐÀÙÅÍÈÉ È ÎÒÐÀÆÅÍÈÉãäå·¸Il−1 0Ul =0 Vl .Ïîñëå (n − 1) øàãîâ ìû ïðèõîäèì ê ìàòðèöåA(n−1) = Un−1 Un−2 . .
. U1 A,èìåþùåé ïðàâóþ òðåóãîëüíóþ ôîðìó. Îáîçíà÷èìUn−1 . . . U1 = U.ÒîãäàA(n−1) = U A,A = U T A(n−1) .Åñëè íóæíî ðåøèòü ñèñòåìó (5.1), òî ïîñëå îïèñàííûõ ïðåîáðàçîâàíèé ïðèõîäèì êýêâèâàëåíòíîé ñèñòåìåA(n−1) x = U b(5.28)ñ òðåóãîëüíîé ìàòðèöåé.Óïðàæíåíèå 5.4. Ïîñòðîèòü àëãîðèòì ìåòîäà îòðàæåíèé, ïðè êîòîðîì äëÿ ðàçëî-æåíèå ìàòðèöû â ïðîèçâåäåíèå îðòîãîíàëüíîé è âåðõíåé òðåóãîëüíîé ìàòðèö äîñòàòî÷íî ≈ 23 n3 äåéñòâèé óìíîæåíèÿ. 6Ðàçíîñòíûå óðàâíåíèÿ6.1 Ðàçíîñòíûå óðàâíåíèÿÏóñòü y(n) = yn ôóíêöèÿ öåëî÷èñëåííîãî àðãóìåíòà n ∈ Z. Áóäåì åå íàçûâàòüñåòî÷íîé ôóíêöèåé. Îáîçíà÷èì ÷åðåç ∇ (íàáëà) îïåðàòîð ëåâîé êîíå÷íîé ðàçíîñòè(ðàçíîñòè íàçàä), ò.å.∇yn = yn − yn−1 .(6.1)Ñòåïåíü îïåðàòîðà ∇ îïðåäåëèì ðåêóððåíòíûì îáðàçîì∇k = ∇(∇k−1 ).(6.2)Ïóñòü a(n), b(n), c(n), d(n) è f (n) çàäàííûå ñåòî÷íûå ôóíêöèè. Ðàññìîòðèì óðàâíåíèåa(n)∇3 yn + b(n)∇2 yn + c(n)∇yn + d(n)yn = f (n)(6.3)îòíîñèòåëüíî ñåòî÷íîé ôóíêöèè yn .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
