В.Б. Андреев - Численные методы (1113834), страница 7
Текст из файла (страница 7)
. . , 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 .
Óðàâíåíèå (6.3) íàçûâàåòñÿ ðàçíîñòíûì óðàâíåíèåì. Ðàçíîñòíûå óðàâíåíèÿ ÿâëÿþòñÿ àíàëîãàìè äèôôåðåíöèàëüíûõ óðàâíåíèéè â çíà÷èòåëüíîé ñòåïåíè ïîâòîðÿþò ñâîéñòâà ïîñëåäíèõ. Êàê è â ñëó÷àå äèôôåðåíöèàëüíûõ óðàâíåíèé, âàæíûì ÿâëÿåòñÿ ïîíÿòèå ïîðÿäêà ðàçíîñòíîãî óðàâíåíèÿ.Åñëè a(n) 6= 0, òî êàçàëîñü áû åñòåñòâåííûì îáúÿâèòü ïîðÿäêîì óðàâíåíèÿ (6.3)÷èñëî òðè. Îäíàêî ïðè òàêîì îïðåäåëåíèè ïîðÿäêà ðàçíîñòíîãî óðàâíåíèÿ íàñ æäóòíåïðèÿòíîñòè. ×òîáû óáåäèòüñÿ â ýòîì, ïîëîæèì â (6.3) a(n) = 1, b(n) = 0, c(n) = −3,d(n) = 2.  ðåçóëüòàòå ïîëó÷èì óðàâíåíèå∇3 yn − 3∇yn + 2yn = f (n).Ïðèíèìàÿ âî âíèìàíèå (6.1) è (6.2), íàõîäèì, ÷òî∇yn = yn − yn−1 ,∇3 yn = yn − 3yn−1 + 3yn−2 − yn−3 ,à, ïîäñòàâëÿÿ ýòè âûðàæåíèÿ â (6.4), áóäåì èìåòüyn − 3yn−1 + 3yn−2 − yn−3 − 3yn + 3yn−1 + 2yn = f (n)57(6.4)58 6.
ÐÀÇÍÎÑÒÍÛÅ ÓÐÀÂÍÅÍÈßèëè3yn−2 − yn−3 = f (n).(6.5)Ââîäÿ íîâûé èíäåêñ m = n − 2, óðàâíåíèå (6.5) ïðåîáðàçóåì ê âèäó3ym − ym−1 = f (m + 2).(6.6)Ýòî óðàâíåíèå ýêâèâàëåíòíî óðàâíåíèþ (6.4), è íàçâàòü åãî ðàçíîñòíûì óðàâíåíèåì òðåòüåãî ïîðÿäêà ïðîñòî íå ïîâîðà÷èâàåòñÿ ÿçûê. È äåëî, êîíå÷íî, íå ïðîñòî âíàçâàíèè. Îò óäà÷íî ââåäåííîãî îïðåäåëåíèÿ çàâèñèò ïðîñòîòà ïîñëåäóþùèõ óòâåðæäåíèé, èñïîëüçóþùèõ ýòî îïðåäåëåíèå. Ïîñêîëüêó çàïèñü (6.3) íå ñîäåðæèò ÿâíûìîáðàçîì èíôîðìàöèè î ÷èñëå, êîòîðûì ñëåäîâàëî áû îïðåäåëèòü ïîðÿäîê ðàçíîñòíîãîóðàâíåíèÿ, òî áóäåì ðàçíîñòíîå óðàâíåíèå çàïèñûâàòü â âèäåΦ(n, yn , yn−1 , .
. . , yn−k ) = 0.(6.7)Îïðåäåëåíèå 6.1. Óðàâíåíèå (6.7) íàçûâàåòñÿ ðàçíîñòíûì óðàâíåíèåì.Îïðåäåëåíèå 6.2. Ðàçíîñòíîå óðàâíåíèå (6.7), åñëè îíî ÿâíî çàâèñèò îò yn è îòyn−k , íàçûâåòñÿ óðàâíåíèåì k -ãî ïîðÿäêà.Îïðåäåëåíèå 6.3. Ðàçíîñòíîå óðàâíåíèå k -ãî ïîðÿäêà íàçûâàåòñÿ ëèíåéíûì, åñëèîíî ëèíåéíî çàâèñèò îò yn , yn−1 , . . . , yn−k .Ìû áóäåì èçó÷àòü òîëüêî ëèíåéíûå ðàçíîñòíûå óðàâíåíèÿ, êîòîðûå áóäåì çàïèñûâàòü â âèäåkXαj (n)yn−j = f (n), n ∈ Z.(6.8)j=0Ïîêà ìû ïðåäïîëàãàåì, ÷òî óðàâíåíèå (6.8) çàäàíî ïðè âñåõ n ∈ Z. Óðàâíåíèå (6.8)áóäåò óðàâíåíèåì k -ãî ïîðÿäêà, åñëè êîýôôèöèåíòû α0 (n) è αk (n) íå îáðàùàþòñÿ âíóëü íè ïðè îäíîì n ∈ Z.Îïðåäåëåíèå 6.4.
Ñåòî÷íàÿ ôóíêöèÿ yn , n ∈ Z íàçûâàåòñÿ ðåøåíèåì óðàâíåíèÿ(6.8), åñëè ïðè ïîäñòàíîâêå åå â (6.8) ïîñëåäíåå ïðåâðàùàåòñÿ â òîæäåñòâî.Îïðåäåëåíèå 6.5. Ñåòî÷íàÿ ôóíêöèÿ yn , n ∈ Z íàçûâàåòñÿ îáùèì ðåøåíèåìðàçíîñòíîãî óðàâíåíèÿ (6.8), åñëè â íåé ñîäåðæèòñÿ ëþáîå ðåøåíèå (6.8).Äëÿ òîãî, ÷òîáû îïðåäåëèòü êàêîå-ëèáî ðåøåíèå óðàâíåíèÿ (6.8) (÷àñòíîå ðåøåíèå)äîñòàòî÷íî óêàçàòü åãî çíà÷åíèÿ â ëþáûõ k ïîñëåäîâàòåëüíûõ òî÷êàõ, íàïðèìåð,n0 , n0 + 1, . . . , n0 + k − 1.6.2.
ÓÐÀÂÍÅÍÈß ÏÅÐÂÎÃÎ ÏÎÐßÄÊÀ596.2 Ëèíåéíûå ðàçíîñòíûå óðàâíåíèÿ ïåðâîãî ïîðÿäêàÝòè óðàâíåíèÿ èìåþò âèäα0 (n)yn + α1 (n)yn−1 = f (n).(6.9)Ïîñêîëüêó α0 (n) 6= 0, òî íà ýòîò êîýôôèöèåíò óðàâíåíèå ìîæíî ïîäåëèòü. Ïóñòüα1 (n)/α0 (n) = −qn , à f (n)/α0 (n) ñíîâà îáîçíà÷èì ÷åðåç f (n) = fn . Òîãäà ðàçíîñòíîåóðàâíåíèå ïåðâîãî ïîðÿäêà (6.9) ìîæíî ïåðåïèñàòü òàê(6.10)yn = qn yn−1 + fn .Ðàçðåøèòü ðàçíîñòíîå óðàâíåíèå çíà÷èò âûðàçèòü yn ÷åðåç èçâåñòíûå âåëè÷èíû.×òîáû ìîæíî áûëî ðåøèòü (6.10), íóæíî çàäàòü íà÷àëüíîå óñëîâèå(6.11)y0 = a.Èñïîëüçóÿ òåïåðü ðåêóððåíòíûå ñîîòíîøåíèÿ (6.10), ìîæíî ïîñëåäîâàòåëüíî îïðåäåëèòü yn ïðè âñåõ ïîñëåäóþùèõ çíà÷åíèÿõ n:y1 = q1 y0 + f1 = q1 a + f1 ,y2 = q2 y1 + f2 = q2 (q1 a + f1 ) + f2 = q1 q2 a + q2 f1 + f2è ò.ä.×àñòî áûâàåò ïîëåçíî èìåòü íå ðåêóððåíòíîå ñîîòíîøåíèå äëÿ ïîñëåäîâàòåëüíîãî âû÷èñëåíèÿ ðåøåíèÿ, à íåêîòîðóþ ôîðìóëó, ïðåäñòàâëÿþùóþ ðåøåíèå.
Íàéäåìïðåäñòàâëåíèå ðåøåíèÿ óðàâíåíèÿ (6.10). Äëÿ ýòîãî ðàññìîòðèì ñíà÷àëà îòâå÷àþùåååìó îäíîðîäíîå óðàâíåíèåyn = qn yn−1(6.12)è íàéäåì åãî ðåøåíèå. Èìååìy1 = q1 y0 ,y2 = q2 y1 ,..............yn = qn yn−1 .Ïåðåìíîæàÿ ïîñëåäîâàòåëüíî ïîëó÷åííûå ðàâåíñòâà è ñîêðàùàÿ ëåâóþ è ïðàâóþ÷àñòè íà y1 y2 . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
