Буслов, Яковлев - Численные методы. 2. Решение уравнений (947496), страница 4
Текст из файла (страница 4)
. . , N .j>iÒàêîé èòåðàöèîííûé ïðîöåññ íàçûâàåòñÿ ìåòîäîì Çåéäåëÿ. Ïðåäñòàâèì åãî â ìàòðè÷íîé ôîðìå. Ïóñòü L íèæíåòðåóãîëüíàÿ ìàòðèöà ñ ýëåìåíòàìèL : aijlij = 0, j<ià U âåðõíåòðåóãîëüíàÿ ìàòðèöà ñ ýëåìåíòàìè aijuij = 0, j>i, j≥i, j≤i,.Êàê è ðàíüøå ââåäåì ìàòðèöó D = diag{a11 . . . aN N } , òîãäà A = D + L + U .  ìàòðè÷íîì âèäå ìåòîäÇåéäåëÿ èìååò âèä:xs+1 = D−1 b − D−1 Lxs+1 − D−1 U xs .Ñõîäèìîñòü ìåòîäà ÇåéäåëÿÈòàê, èòåðàöèè ïî ìåòîäó Çåéäåëÿ äîëæíû áûòü îðãàíèçîâàíû òàêèì îáðàçîì, ÷òîáûDxs+1 = b − Lxs+1 − U xs ,èëèxs+1 = (D + L)−1 b − (D + L)−1 U xs .Îòîáðàæåíèå x 7→ (D + L)−1 b − (D + L)−1 U x ÿâëÿåòñÿ ñæàòèåì, åñëè ||(D + L)−1 U || < 1 , òî åñòüñïðàâåäëèâàÒåîðåìà.
Ìåòîä Çåéäåëÿ ñõîäèòñÿ, åñëè ||(D + L)−1 U || < 1.Óñëîâèÿ ýòîé òåîðåìû äîâîëüíî òðóäíî ïðîâåðÿåìû, òàê êàê ìàòðèöà (D + L)−1 U äîëæíà åùå è âû÷èñëÿòüñÿ. Ñóùåñòâóåò äîñòàòî÷íî ïðîñòîé ïðèçíàê ñõîäèìîñòè ìåòîäà Çåéäåëÿ, êîòîðûé ñâÿçàí ñ ïîíÿòèåì15ïîëîæèòåëüíîé îïðåäåëåííîñòè ìàòðèöû îòíîñèòåëüíî ñêàëÿðíîãî ïðîèçâåäåíèÿ. Íàïîìíèì, ÷òî îïåðàòîðA, äåéñòâóþùèé â åâêëèäîâîì ïðîñòðàíñòâå En íàçûâàåòñÿ ïîëîæèòåëüíî îïðåäåëåííûì, åñëèhAx, xi ≥ γhx, xi , γ > 0 .Åñëè îïåðàòîð ïîëîæèòåëüíî îïðåäåëåí, òî ó íåãî ñóùåñòâóåò è îáðàòíûé è îí òàêæå ïîëîæèòåëüíî îïðåäåëåí. Òàêæå âàæíî îòìåòèòü, ÷òî åñëè îïåðàòîð A ïîëîæèòåëüíî îïðåäåëåí è ñèììåòðè÷åí â RN , òîôîðìàhx, yiA = hAx, yióäîâëåòâîðÿåò âñåì ñâîéñòâàì ñêàëÿðíîãî ïðîèçâåäåíèÿ.
 äàëüíåéøåì, ôàêò ïîëîæèòåëüíîé îïðåäåëåííîñòè îïåðàòîðà A áóäåì îáîçíà÷àòü: A > 0 . Çàìåòèì, ÷òî â êîìïëåêñíîì åâêëèäîâîì ïðîñòðàíñòâåïîëîæèòåëüíàÿ îïðåäåëåííîñòü îïåðàòîðà A àâòîìàòè÷åñêè âëå÷åò çà ñîáîé ýðìèòîâîñòü: A = A∗ .Òåîðåìà (äîñòàòî÷íûé ïðèçíàê ñõîäèìîñòè ìåòîäà Çåéäåëÿ). Ìåòîä Çåéäåëÿ ñõîäèòñÿ â âåùåñòâåííîìåâêëèäîâîì ïðîñòðàíñòâå, åñëè A ñèììåòðè÷íàÿ ïîëîæèòåëüíî îïðåäåëåííàÿ ìàòðèöà.Äëÿ äîêàçàòåëüñòâà ýòîé òåîðåìû íàì ïîòðåáóåòñÿ ñëåäóþùàÿËåììà. Ïóñòü ïîñëåäîâàòåëüíîñòü âåêòîðîâ zk â RN îïðåäåëåíà ðåêóððåíòíûì ñîîòíîøåíèåìB(zk+1 − zk ) + Azk = 0 ,(3)ãäå B − 12 A > 0 , A > 0 è ñèììåòðè÷íà, òîãäà zk → 0 .Äîêàçàòåëüñòâî. Ïðåäñòàâèì zk â âèäåzk =1 k+11(z+ zk ) − (zk+1 − zk ) ,22è ïîäñòàâèì ýòî ïðåäñòàâëåíèå â (3), òîãäà11B(zk+1 − zk ) + A(zk+1 + zk ) − A(zk+1 − zk ) = 0 ,22èëè11(B − A)(zk+1 − zk ) + A(zk+1 + zk ) = 0 .22Óìíîæèì ýòî ðàâåíñòâî ñêàëÿðíî íà zk+1 − zk , òîãäà10 = |zk+1 − zk |B−A/2 + hA(zk+1 + zk ), zk+1 − zk i =21= |zk+1 − zk |B−A/2 + {|zk+1 |A − |zk |A } = 0 ,2ãäå | · |A = hA·, ·i , | · |B−A/2 = h{B − A/2}·, ·i íîðìû, îïðåäåëÿåìûå îïåðàòîðàìè A è B − A/2, ñîîòâåòñòâåííî.
Èç ïîñëåäíåãî ðàâåíñòâà â ñèëó ïîëîæèòåëüíîé îïðåäåëåííîñòè îïåðàòîðà (B − A/2) ñëåäóåò,÷òî |zk+1 |A − |zk |A ≤ 0 , ò.å. ïîñëåäîâàòåëüíîñòü |zk |A íåâîçðàñòàþùàÿ: |zk+1 |A ≤ |zk |A . Ïðè ýòîì, ïîñëåäîâàòåëüíîñòü ÷èñåë |zk |A îãðàíè÷åíà ñíèçó ïîñêîëüêó |zk |A ≥ 0 . Òàêèì îáðàçîì, ñóùåñòâóåò êîíå÷íûéïðåäåëlim |zk |A = a . Íî òîãäà èç òîãî æå ðàâåíñòâà ñëåäóåò, ÷òî íîðìà |zk+1 − zk |(B− 12 A) ñòðåìèòñÿ êk→∞íóëþ, à çíà÷èò è zk+1 − zk → 0 , k → ∞ .
Âåðíåìñÿ òåïåðü ê îïðåäåëåíèþ ïîñëåäîâàòåëüíîñòè zk :Azk = −B(zk+1 − zk ) ,îòêóäà zk = −A−1 B(zk+1 − zk ) è, ñëåäîâàòåëüíî,||zk || ≤ ||A−1 B|| × ||zk+1 − zk || → 0 ,16è, òàêèì îáðàçîì, zk → 0, ïðè k → ∞.Ïðèñòóïèì òåïåðü ñîáñòâåííî ê äîêàçàòåëüñòâó äîñòàòî÷íîãî ïðèçíàêà ñõîäèìîñòè ìåòîäà Çåéäåëÿ. Êàêíåòðóäíî âèäåòü, ìåòîä Çåéäåëÿ (D + L)xs+1 + U xs = b ìîæåò áûòü ïðåäñòàâëåí â âèäå(D + L)(xs+1 − xs ) + Axs = b .Ïóñòü u òî÷íîå ðåøåíèå óðàâíåíèÿ Au = b , îíî ñóùåñòâóåò, òàê êàê A ïîëîæèòåëüíî îïðåäåëåííûéîïåðàòîð è, ñëåäîâàòåëüíî, îáðàòèì. Ïîëîæèì òàêæå zs = xs − u , òîãäà(D + L)(zs+1 − zs ) + Azs = 0 .Óáåäèìñÿ â òîì, ÷òî (D + L − 21 A) ïîëîæèòåëüíî îïðåäåëåííàÿ ìàòðèöà, åñëè A ñèììåòðè÷íà è ïîëîæèòåëüíî îïðåäåëåíà.
Äåéñòâèòåëüíî111D + L − A = D + L − (D + L + U ) = (D + L − U ) .222Ðàññìîòðèì ñîîòâåòñòâóþùóþ êâàäðàòè÷íóþ ôîðìóh(D + L − U )x, xi = hDx, xi + hLx, xi − hU x, xi .Çàìåòèì, ÷òî ïîñêîëüêó A ñèììåòðè÷íàÿ ìàòðèöà, ñëåäîâàòåëüíî LT = U èhLx, xi = hx, LT xi = hx, U xi = hU x, xi ,ïîýòîìóh(D + L − U )x, xi = hDx, xi =Xaii x2i > 0 ,iòàê êàê ó ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöû âñå äèàãîíàëüíûå ýëåìåíòû áîëüøå íóëÿ (ïî÷åìó?): aii > 0 .Òàêèì îáðàçîì, ìû íàõîäèìñÿ â óñëîâèÿõ Ëåììû, ñëåäîâàòåëüíî, ïîñëåäîâàòåëüíîñòü zs ñòðåìèòñÿ ê íóëþ,îòêóäà ñëåäóåò, ÷òî ïîñëåäîâàòåëüíîñòü xs = u + zs ñòðåìèòñÿ ê èñòèííîìó ðåøåíèþ u .17Ãëàâà 2Àëãåáðàè÷åñêèå ñïåêòðàëüíûå çàäà÷è2.1 Íåêîòîðûå ñâåäåíèÿ èç ìàòðè÷íîé òåîðèèÏóñòü A ëèíåéíûé îïåðàòîð, äåéñòâóþùèé â âåùåñòâåííîì RN èëè â êîìïëåêñíîì CN åâêëèäîâîìïðîñòðàíñòâå: A : RN (CN ) → RN (CN ) .×èñëî λ è âåêòîð x íàçûâàþòñÿ, ñîîòâåòñòâåííî, ñîáñòâåííûì ÷èñëîì (çíà÷åíèåì) è ñîáñòâåííûìâåêòîðîì îïåðàòîðà A, îòâå÷àþùèì ñîáñòâåííîìó ÷èñëó λ , åñëè Ax = λx . ÷àñòíîñòè, ñïðàâåäëèâû ñëåäóþùèå òåîðåìû.Òåîðåìà 1.Âñÿêèé ëèíåéíûé îïåðàòîð â CN èìååò ïî êðàéíåé ìåðå îäíî ñîáñòâåííîå çíà÷åíèå.Òåîðåìà 2.
Ñîáñòâåííûå âåêòîðû, îòâå÷àþùèå ðàçëè÷íûì ñîáñòâåííûì çíà÷åíèÿì, ëèíåéíî íåçàâè-ñèìû.Òåîðåìà 3. Äëÿ ëþáîãî íàáîðà èç N ëèíåéíî íåçàâèñèìûõ âåêòîðîâ e1 , e2 , . . . , eN(áàçèñà) ñóùå-ñòâóåò åäèíñòâåííûé äóàëüíûé áàçèñ ẽ1 , ẽ2 , . . . , ẽN , òàêîé ÷òî hei , ẽj i = δij .Çàìåòèì, ÷òî âñÿêèé îðòîíîðìèðîâàííûé áàçèñ ñàìîäóàëåí. Ïóñòü A èìååò N ðàçëè÷íûõ ñîáñòâåííûõâåêòîðîâ xi , òîãäà îíè îáðàçóþò áàçèñ, è, ñëåäîâàòåëüíî, ñóùåñòâóåò äóàëüíûé áàçèñ x̃i .  ýòîì ñëó÷àå,êàê íåòðóäíî óáåäèòüñÿ, ñîïðÿæåííûé îïåðàòîð A∗(â ñëó÷àå âåùåñòâåííîãî åâêëèäîâà ïðîñòðàíñòâàïðîñòî òðàíñïîíèðîâàííàÿ ìàòðèöà AT ) èìååò â êà÷åñòâå ñîáñòâåííûõ çíà÷åíèé ÷èñëà λ̄i , à â êà÷åñòâåñîáñòâåííûõ âåêòîðîâ âåêòîðû äóàëüíîãî áàçèñà:Axi = λi xi , A∗ x̃i = λ̄i x̃i .Äåéñòâèòåëüíî: hxi , λ̄i x̃i i = hλxi , x̃i i = hAxi , x̃i i = hxi , A∗ x̃i i è, àíàëîãè÷íî, hxj , A∗ x̃i i = 0 , i 6= j , òîåñòü hxj , A∗ x̃i i = δij hxj , λ̄x̃j i .
Êðîìå òîãî, íåòðóäíî ïîêàçàòü ñïðàâåäëèâîñòü ñëåäóþùåãî ñïåêòðàëüíîãîðàçëîæåíèÿ îïåðàòîðà A :A· =NXiiλi h·, x̃ ix =i=1NXλi P i · ,i=1ãäå îïåðàòîðû Pi · = h·, x̃i ixi ñóòü ñîáñòâåííûå ïðîåêòîðû îïåðàòîðà A .  ñàìîì äåëå, ïðîèçâîëüíûéPâåêòîð f ìîæíî ðàçëîæèòü ïî ñîáñòâåííûì âåêòîðàì îïåðàòîðà A : f = hf , x̃i ixi . ÒîãäàAf =XXXhf , x̃i iAxi =hf , x̃i iλi xi =λi Pi f .18Ïóñòü A = A∗ ýðìèòîâà ìàòðèöà (â RN ñèììåòðè÷íàÿ).  ýòîé ñèòóàöèè ñîáñòâåííûå çíà÷åíèÿâåùåñòâåííû, àëãåáðàè÷åñêàÿ è ãåîìåòðè÷åñêàÿ êðàòíîñòè ëþáîãî ñîáñòâåííîãî çíà÷åíèÿ ñîâïàäàþò, ñîáñòâåííûå âåêòîðû xi , îòâå÷àþùèå ðàçëè÷íûì ñîáñòâåííûì ÷èñëàì îðòîãîíàëüíû, è ñóùåñòâóåò îðòîíîðìèðîâàííûé áàçèñ èç ñîáñòâåííûõ âåêòîðîâ.
 ñëó÷àå îäíîêðàòíî âûðîæäåííîãî ñîáñòâåííîãî çíà÷åíèÿ λ,îòâå÷àþùèé åìó ñîáñòâåííûé ïðîåêòîð P îäíîìåðåí è èìååò âèä P = h·, xix (âñþäó ñ÷èòàåì, ÷òî ñîáñòâåííûé âåêòîð x íîðìèðîâàí íà åäèíèöó). Åñëè ïîäïðîñòðàíñòâî ðåøåíèé Ax = λx áîëåå ÷åì îäíîìåðíî, òîâ íåì âûáèðàåòñÿ ïðîèçâîëüíûé îðòîáàçèñ xi è ñîáñòâåííûé ïðîåêòîð, îòâå÷àþùèé ñîáñòâåííîìó ÷èñëóPλ , ïðåäñòàâëÿåò ñîáîé ñóììó ñîîòâåòñòâóþùèõ îäíîìåðíûõ ïðîåêòîðîâ P = h·, xi ixi .Îòìåòèì (ëåãêî ïðîâåðÿåìîå) âàæíîå ñâîéñòâî îðòîãîíàëüíûõ ïðîåêòîðîâ:Pi Pk = δik Pi .Ñòåïåíü îïåðàòîðà èìååò ñëåäóþùóþ çàïèñü ÷åðåç îðòîãîíàëüíûå ïðîåêòîðûAm =Xλmk (A)Pk .kÌíîãî÷ëåíû îò îïåðàòîðà îïðåäåëÿþòñÿ êàê ñóììà ñîîòâåòñòâóþùèõ ñòåïåíåé.
Ïîñêîëüêó ìíîãî÷ëåíàìèìîæíî ïðèáëèçèòü ëþáóþ ôóíêöèþ, òî ôóíêöèþ îò îïåðàòîðà åñòåñòâåííî îïðåäåëèòü êàêf (A) =Xf (λk )Pk .kÑîáñòâåííûå ôóíêöèè ó îïåðàòîðà è ó ôóíêöèè îò îïåðàòîðà ñîâïàäàþò, òîãäà êàê ñîáñòâåííûå çíà÷åíèÿôóíêöèè îò îïåðàòîðà åñòü ÷èñëà f (λk ).2.2 Ñîáñòâåííûå ÷èñëà ýðìèòîâûõ ìàòðèö2.2.1 Èíòåðïîëÿöèîííûé ìåòîäÏîñêîëüêó ñîáñòâåííûå ÷èñëà λi ìàòðèöû A ÿâëÿþòñÿ êîðíÿìè õàðàêòåðèñòè÷åñêîãî ïîëèíîìà FA (λ) =det(A − λI) , òî ìîæíî âû÷èñëèòü FA (λ) â (n + 1)-îì íàóãàä âûáðàííîì çíà÷åíèè λ (èõ åñòåñòâåííî âûáèðàòü â ïðîìåæóòêå (−||A||, ||A||), åñëè ãðàíèöû ñïåêòðà èçâåñòíû; îöåíèòü èõ ìîæíî ïî ìàêñèìàëüíîìóïî ìîäóëþ ýëåìåíòó ìàòðèöû) è ïîñòðîèòü ïî íèì èíòåðïîëÿöèîííûé ïîëèíîì ñòåïåíè n, êîòîðûé ñîâïàäàåò ñîáñòâåííî ñ õàðàêòåðèñòè÷åñêèì, ïîñëå ÷åãî îïðåäåëÿþòñÿ åãî êîðíè. Ýòîò ìåòîä ïðèìåíèì è äëÿíåýðìèòîâûõ ìàòðèö (ïðè ñîîòâåòñòâóþùåì âûáîðå ìåòîäà îïðåäåëåíèÿ êîðíåé).2.2.2 Íàõîæäåíèå ìàêñèìàëüíîãî ïî ìîäóëþ ñîáñòâåííîãî çíà÷åíèÿÄëÿ óäîáñòâà áóäåì ñ÷èòàòü, ÷òî ñîáñòâåííûå ÷èñëà ïðîíóìåðîâàíû â ïîðÿäêå óáûâàíèÿ èõ ìîäóëÿ.à) Ìåòîä èòåðàöèéÏóñòü g = g0 ïðîèçâîëüíûé íà÷àëüíûé âåêòîð.
Îïðåäåëèì ïîñëåäîâàòåëüíîñòügn = Agn−1An g,=||An−1 g||||g(n−1) ||òîãäàlim ||g(n) || = |λmax | .19Äîêàçàòåëüñòâî: Äåéñòâèòåëüíî, g =An g =XPPk g , k|gn || =||An g||||An−1 g||λnk Pk g = λnmax (Pmax g +,èX{λk /λmax }n Pk g) .k6=1Ïóñòü λ0 ñîáñòâåííîå ÷èñëî, ñëåäóþùåå çà ìàêñèìàëüíûì ïî ìîäóëþ. Òîãäà02n||An g||2 = hAn g, An gi = λ2nmax (hPmax g, gi + O([λ /λmax ] )) ,è||An g||||g || == |λmax |||An−1 g||snhPmax g, gi + O([λ0 /λmax ]2n )=hPmax g, gi + O([λ0 /λmax ]2n−2 )= |λmax |{1 + O([λ0 /λmax ]2n−2 )} .Òàêèì îáðàçîì, åñëè ñòàðòîâûé âåêòîð g èìåë íåíóëåâóþ ïðîåêöèþ íà ñîáñòâåííîå ïîäïðîñòðàíñòâî,îòâå÷àþùåå ìàêñèìàëüíîìó ïî ìîäóëþ ñîáñòâåííîìó çíà÷åíèþ (òî åñòü Pmax g 6= 0 ), òî ïðèâåäåííàÿ èòåðàöèîííàÿ ïðîöåäóðà ïðèâîäèò ê íàõîæäåíèþ λmax .
Îäíàêî, õîòÿ ôîðìàëüíî, ïðåäûäóùåå ðàññìîòðåíèåâåðíî ëèøü â ñëó÷àå íåíóëåâîé ïðîåêöèè, â äåéñòâèòåëüíîñòè, èç-çà îøèáîê îêðóãëåíèÿ ïðè âû÷èñëåíèÿõýòà ïðîåêöèÿ íàâåðíÿêà ïîÿâèòñÿ íà íåêîòîðîì øàãå è äàëüíåéøåå ïðèìåíåíèå ìåòîäà èòåðàöèé ïðèâåäåòê æåëàåìîìó ðåçóëüòàòó. Ïîïóòíî çàìåòèì, ÷òî åñëè ïîäïðîñòðàíñòâî îòâå÷àþùåå λmax îäíîìåðíî, òîìåòîä èòåðàöèé îäíîâðåìåííî ïðèâîäèò ê íàõîæäåíèþ ñîáñòâåííîãî âåêòîðà xmax , îòâå÷àþùåãî λmax .Ýòèì âåêòîðîì ñ òî÷íîñòüþ äî íîðìèðîâêè ÿâëÿåòñÿxmax = lim gn .n→∞Çàìå÷àíèå.
Äëÿ íàõîæäåíèÿ λmax ìîæíî ïðèìåíÿòü ìåòîä èòåðàöèé è â áîëåå ïðîñòîé ïîñòàíîâêå.Ïóñòü l-àÿ êîìïîíåíòà â ìàêñèìàëüíîãî ñîáñòâåííîãî âåêòîðà â ñòàíäàðòíîì åâêëèäîâîì áàçèñå íå ðàâíàíóëþ (õîòÿ áû îäíà òàêàÿ ñóùåñòâóåò), òîãäà(An g)l.n→∞ (An−1 g)lλmax = limá) Ìåòîä ñëåäîâÈçâåñòíî, ÷òî ñëåä ìàòðèöû (ñóììà äèàãîíàëüíûõ ýëåìåíòîâ) ðàâåí ñóììå å¼ ñîáñòâåííûõ çíà÷åíèé ñPP mó÷åòîì êðàòíîñòè:λi = T rA , òàêèì îáðàçîì,λi = T rAm è, ñëåäîâàòåëüíî,0mT rAm = λmmax [1 + (λ /λmax ) + . . .] ,ãäå λ0 ñëåäóþùåå ïî ìîäóëþ çà ìàêñèìàëüíûì ñîáñòâåííîå çíà÷åíèå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
