Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 53
Текст из файла (страница 53)
ßñíî, ÷òî ýòî çàäà÷à î ïåðïåíäèêóëÿðå â ñëó÷àå A-îðòîãîíàëüíîñòè. Ïîýòîìó y îïðåäåëÿåòñÿ èç óðàâíåíèé((x − x0 ) − y, pi )A = 0⇔(r0 − Ay, pi ) = 0, 1 ≤ i ≤ k.Çàïèñàâ y = α1 p1 + . . . + αk pk , íàõîäèì αi = (r0 , pi )/(Api , pi ). Ñëåäîâàòåëüíî, âåêòîðûxk ìîæíî âû÷èñëÿòü ïî î÷åíü ïðîñòîé ðåêóððåíòíîé ôîðìóëåxk = xk−1 + αk pk ,αk = (r0 , pk )/(Apk , pk ).Îòñþäà âèäíî, ÷òî íåâÿçêè rk = b − Axk ñâÿçàíû ðåêóððåíòíîé ôîðìóëîérk = rk−1 − αk Apk .Óäèâèòåëüíî è ïðèÿòíî òî, ÷òî äëÿ âû÷èñëåíèÿ xk òðåáóåòñÿ ëèøü îäèí âåêòîð pkèç áàçèñà p1 , . . . , pk ! Íî åùå áîëåå óäèâèòåëüíî è ïðèÿòíî òî, ÷òî pk+1 ìîæíî íàéòè,èñïîëüçóÿ ëèøü äâà âåêòîðà: pk è rk . ñàìîì äåëå, åñëè rk = 0, òî ðåøåíèå íàéäåíî.3Åñëè æå rk 6= 0, òî íåâÿçêà rk = r0 − Ay ÿâëÿåòñÿ îðòîãîíàëüíîé ïîäïðîñòðàíñòâóLk è ïîýòîìó pk+1 ìîæíî çàïèñàòü â âèäåpk+1 = rk + β1 p1 + .
. . + βk pk .Óñëîâèå A-îðòîãîíàëüíîñòè äàåò ðàâåíñòâà(Apk+1 , pi ) = 0 ⇒ βi = (Ark , pi )/((Api , pi ), 1 ≤ i ≤ k.Ïðè ýòîì (Ark , pi ) = (rk , Api ) = 0 ïðè i ≤ k − 1, òàê êàê âåêòîð Api ∈ ALi ⊂ Li+1 . Òàêèìîáðàçîì, βi = 0 ïðè 1 ≤ i ≤ k − 1 ⇒pk+1 = rk + βk pk ,38.7βk = (rk , Apk )/(Apk , pk ).Äâó÷ëåííûå ôîðìóëûÇàìåòèì, ÷òî äëÿ âû÷èñëåíèÿ αk ñîâñåì íå îáÿçàòåëüíî èñïîëüçîâàòü ôîðìóëó αk =(r0 , pk )/(Apk , pk ). Ïîñêîëüêó rk ⊥Lk , íàõîäèì 0 = (rk , pk ) = (rk−1 − αk Apk , pk ) ⇒αk =(rk−1 , rk−1 + βk−1 pk−1 )(rk−1 , rk−1 )(rk−1 , pk )==.(Apk , pk )(Apk , pk )(Apk , pk )Äàëåå, åñëè rk−1 6= 0, òî αk 6= 0 ⇒βk =3  ýòîì ñëó÷àåLk = Lk+1Apk = (rk−1 − rk )/αk⇒(rk , rk−1 − rk )(rk , rk )= −.αk (Apk , pk )(rk−1 , rk−1 )(äîêàæèòå!).254Ëåêöèÿ 38Îêîí÷àòåëüíî, ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ ñâîäèòñÿ ê èòåðàöèÿì, âûïîëíÿåìûìïî ñëåäóþùèì äâó÷ëåííûì ôîðìóëàì:xk = xk−1 + αk pk ,αk =(rk−1 , rk−1 ),(Apk , pk )rk = rk−1 − αk Apk ,pk+1 = rk + βk pk ,βk = −(rk , rk ).(rk−1 , rk−1 )Òåîðåòè÷åñêè èòåðàöèè âûïîëíÿþòñÿ äî òåõ ïîð, ïîêà rk 6= 0.
Íà ïðàêòèêå îíè îñòàíàâëèâàþòñÿ, êîãäà ||rk ||2 ñòàíîâèòñÿ äîñòàòî÷íî ìàëîé.Íàèáîëåå ñëîæíîå äåéñòâèå íà k -ì øàãå ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ ýòî óìíîæåíèå çàäàííîé ìàòðèöû A íà âåêòîð. Ïðè ýòîì ñîâñåì íå îáÿçàòåëüíî õðàíèòü âñå n2ýëåìåíòîâ ìàòðèöû â êàêîì-òî ìàññèâå òðåáóåòñÿ ëèøü íàëè÷èå êàêîé-òî ïðîöåäóðûóìíîæåíèÿ ìàòðèöû íà âåêòîð. Èìåííî â ýòîì ïëàíå èòåðàöèîííûå ìåòîäû ñóùåñòâåííî îòëè÷àþòñÿ îò ìåòîäà Ãàóññà, ýòî æå îáñòîÿòåëüñòâî äåëàåò èõ îñîáåííî ïîëåçíûìèïðè ðåøåíèè ñèñòåì ñ î÷åíü áîëüøèì ÷èñëîì íåèçâåñòíûõ.Ëåêöèÿ 3939.1Ñïåêòðàëüíûå çàäà÷èÌíîæåñòâî ñîáñòâåííûõ çíà÷åíèé ìàòðèöû íàçûâàåòñÿ òàêæå åå ñïåêòðîì, à ëþáûåçàäà÷è è ñâîéñòâà, ñâÿçàííûå ñ ñîáñòâåííûìè çíà÷åíèÿìè è âåêòîðàìè, íàçûâàþòñÿñïåêòðàëüíûìè.
 ýòîì ïëàíå òåðìèí ñïåêòðàëüíàÿ íîðìà ìàòðèöû âïîëíå ïîíÿòåí:íîðìà ||A||2 ðàâíà ñòàðøåìó ñèíãóëÿðíîìó ÷èñëó ìàòðèöû A, êîòîðîå åñòü êîðåíü êâàäðàòíûé èç ñòàðøåãî ñîáñòâåííîãî çíà÷åíèÿ ìàòðèöû AA∗ .Ìåòîäû ðåøåíèÿ ñïåêòðàëüíûõ çàäà÷ îáû÷íî îñíîâàíû íà ðåäóêöèè çàäà÷è ê àíàëîãè÷íîé çàäà÷å äëÿ ìàòðèöû ïðîñòîãî âèäà, äëÿ êîòîðîé çàäà÷à ðåøàåòñÿ óæå î÷åâèäíûì îáðàçîì. Ñóùåñòâåííîå îòëè÷èå îò çàäà÷, ñâÿçàííûõ ñ ñèñòåìàìè ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé, çàêëþ÷àåòñÿ â òîì, ÷òî â ñïåêòðàëüíûõ çàäà÷àõ ðåäóêöèÿ ïî÷òèâñåãäà ñîäåðæèò áåñêîíå÷íîå ÷èñëî øàãîâ. Íà ïðàêòèêå ýòî îçíà÷àåò, ÷òî ñ ïîìîùüþêîíå÷íîãî ÷èñëà øàãîâ èñõîäíàÿ ìàòðèöà ïðèâîäèòñÿ ê ìàòðèöå âñå åùå äîñòàòî÷íîîáùåãî âèäà, íî òàêîé, ÷òî ïóòåì çàìåíû ìàëûõ ýëåìåíòîâ íà íóëè èç íåå ïîëó÷àåòñÿèñêîìàÿ ìàòðèöà ïðîñòîãî âèäà.Òàêèì îáðàçîì, ïðè ðåøåíèè ñïåêòðàëüíûõ çàäà÷ î÷åíü âàæíî çíàòü, êàê èçìåíÿþòñÿ ñïåêòðàëüíûå ñâîéñòâà ïðè ìàëûõ âîçìóùåíèÿõ ýëåìåíòîâ ìàòðèöû.
Ïðåæäå âñåãî,÷òî áóäåò ñ ñîáñòâåííûìè çíà÷åíèÿìè? Ýòîò âîïðîñ, î÷åâèäíî, ñâÿçàí ñ âîïðîñîì îáèçìåíåíèè êîðíåé ìíîãî÷ëåíà ïðè èçìåíåíèè êîýôôèöèåíòîâ.Ïóñòü x1 , . . . , xn è y1 , . . . , yn ïîëíûå ñèñòåìû êîðíåé (ñ ó÷åòîì êðàòíîñòåé) äâóõìíîãî÷ëåíîâ ñòåïåíè n. Áàçîé äëÿ èçó÷åíèÿ áëèçêèõ ñèñòåì êîðíåé ìîæåò ñëóæèòüðàçóìíûì îáðàçîì îïðåäåëåííîå ðàññòîÿíèå ìåæäó n-ýëåìåíòíûìè ñèñòåìàìè. Íàïðèìåð, òàêîå: x1y1...ρp ( x, y ) = min ||x − Qy||p ,λ=, µ = ... ,Qxnynìèíèìóì áåðåòñÿ ïî âñåì ìàòðèöàì ïåðåñòàíîâîê Q ïîðÿäêà n, p ≥ 1.39.2Íåïðåðûâíîñòü êîðíåé ìíîãî÷ëåíàËåììà 1.
Ëþáîé êîðåíü ζ ìíîãî÷ëåíà f (z) = a0 +a1 z+. . .+an−1 z n−1 +z n óäîâëåòâîðÿåòíåðàâåíñòâóp|ζ| ≤ max ||a||1 , n ||a||1 ,Äîêàçàòåëüñòâî. Ïóñòü f (ζ) = 0⇒||a||1 = |a0 | + |a1 | + . . . + |an−1 |.|ζ|n ≤ |a0 | + |a1 ||ζ| + . . . + |an−1 ||ζ|n−1 . Åñëè255256Ëåêöèÿ 39|ζ| ≤ 1, òî ïîëó÷àåì |ζ|n ≤ ||a||1 . Åñëè |ζ| > 1, òî |ζ|n ≤ ||a||1 |ζ|n−1Åñëè äàíû ìíîãî÷ëåíû f (z) =nPai z i , g(z) =i=0nP⇒ |ζ| ≤ ||a||1 . 2bi z i , òî ïóñòü, ïî îïðåäåëåíèþ,i=0||f − g||1 =nX|ai − bi |.i=0Ïðåäïîëîæèì äàëåå, ÷òî an = bn = 1. Êîðíè f (z) è g(z) îáîçíà÷èì ÷åðåç x1 , . .
. , xnè y1 , . . . , yn è ñîñòàâèì èç íèõ âåêòîðû-ñòîëáöû x = [x1 , . . . , xn ]> è y = [y1 , . . . , yn ]> .Ëåììà 2. Ñóùåñòâóåò ïåðåñòàíîâêà i1 , . . . , in íîìåðîâ 1, . . . , n òàêàÿ, ÷òînXnX|xk − yik | ≤k=1|gk (xk )|1/(n+1−k) ,k=1ãäå g1 (z) = g(z) è gk (z) = gk+1 (z)(z − yik ), 1 ≤ k ≤ n − 1.nQÄîêàçàòåëüñòâî.
Åñëè |x1 − yi1 | = min |x1 − yi |, òî |g(x1 )| = (x1 − yi ) ≥ |x1 − yi1 |n1≤i≤ni=1. Ïóñòü f1 (z) = f (z) è fk (z) = fk+1 (z)(z − xk ), 1 ≤ k ≤ n − 1.QÒîãäà åñëè |x2 − yi2 | = min |x2 − yi |, òî |g2 (x2 )| = (x2 − yi ) ≥ |x2 − yi2 |n−1 ⇒i6=i1i6=i1⇒1/n|x1 − yi1 | ≤ |g(x1 )||x2 − yi2 | ≤ |g2 (x2 )|1/(n−1) . È òàê äàëåå. 2Ëåììà 3. Ïóñòü ζ è η êîðíè ìíîãî÷ëåíîâ f (z) è g(z), è ïóñòü ìíîãî÷ëåíû φ(z) èψ(z) îïðåäåëåíû ðàâåíñòâàìè f (z) = φ(z) (z − ζ) è g(z) = ψ(z) (z − η). Òîãäà||φ − ψ||1 ≤ γ(α, β)(α + β),α = ||f − g||1 ,β = |ζ − η|,ãäå γ(α, β) íåïðåðûâíàÿ ôóíêöèÿ îò α è β .Äîêàçàòåëüñòâî.
Åñëè f (z) =nPai z i , φ(z) =i=0òîai = ci−1 − ci ζ,n−1Pci z i è g(z) =i=0bi = di−1 − di η,nPbi z i , ψ(z) =i=0n−1Pdi z i ,i=00 ≤ i ≤ n,åñëè óñëîâèòüñÿ, ÷òî c−1 = cn = 0 = d−1 = dn . Îòñþäà ïîëó÷àåìci−1 − di−1 = (ai − bi ) + (ci − di )ζ + di (ζ − η),Îñòàåòñÿ ó÷åñòü îöåíêó ëåììû 1 äëÿ ζ .1 ≤ i ≤ n.2Òåîðåìà. Äëÿ ëþáîãî äîñòàòî÷íî ìàëîãî ε > 0 ñóùåñòâóåò δ > 0 òàêîå, ÷òî åñëè||f − g||1 ≤ δ , òî ρ1 (x, y) ≤ ε.Äîêàçàòåëüñòâî. Ðàññìîòðèì ìíîãî÷ëåíû gk (z) è fk (z), âîçíèêøèå â ôîðìóëèðîâêåè äîêàçàòåëüñòâå ëåììû 2. Î÷åâèäíî, fk (xk ) = 0. Ïîýòîìóρ1 (x, y) ≤nXk=1|xk − yik | ≤nXk=1|fk (xk ) − gk (xk )|1/(n+1−k) .Å.
Å. Òûðòûøíèêîâ257Ôèêñèðóåì f (z) è ðàññìîòðèì ìíîãî÷ëåíû g(z) ñ äîñòàòî÷íî ìàëîé íîðìîé ||f − g||1(ñòàðøèå êîýôôèöèåíòû ìíîãî÷ëåíîâ ðàâíû 1). Ñîãëàñíî ëåììå 1, âñå êîðíè ìíîãî÷ëåíîâ g(z) îãðàíè÷åíû. ßñíî, ÷òî |fk (xk ) − gk (xk )| ≤ c||fk − gk ||1 ñ íåêîòîðîé êîíñòàíòîéc > 0. Ïðèìåíÿÿ ëåììó 3, íàõîäèì, ÷òî ||fk+1 − gk+1 ||1 ñòðåìèòñÿ ê íóëþ, åñëè ||fk − gk ||1ñòðåìèòñÿ ê íóëþ. Ïîýòîìó max ||fk − gk ||1 ñòðåìèòñÿ ê íóëþ, åñëè ||f − g||1 ñòðåìèòñÿ1≤k≤nê íóëþ.
2Çàìå÷àíèå. Áîëåå òîíêîå ðàññóæäåíèå ïîçâîëÿåò ïîëó÷èòü îöåíêó1/nρ1 (x, y) ≤ cn||f − g||1 ,â êîòîðîé ïîêàçàòåëü 1/n óëó÷øèòü íåëüçÿ. Íàïðèìåð, ïóñòü f (z) = (z − ζ)n è g(z) =(z − ζ)n − ε, ε > 0. Òîãäà åñëè η êîðåíü g(z), òî |η − ζ| = ε1/n . Äàæå ïðè ìàëîì εâåëè÷èíà ε1/n ìîæåò îêàçàòüñÿ íå òàêîé óæ ìàëîé. Íàïðèìåð, åñëè ε = 10−10 , òî ïðèn = 10 ïîëó÷àåì ε1/n = 0.1, à ïðè n = 100 è n = 1000 ýòî áóäåò ≈ 0.79 è ≈ 0.98.Ïðèìåð Äæ.
Õ. Óèëêèíñîíà.20Q(z − i) èìååò n = 20 ðàçëè÷íûõ âåùåñòâåííûõi=1êîðíåé. Íåñìîòðÿ íà äîêàçàííûé íàìè ôàêò íåïðåðûâíîé çàâèñèìîñòè êîðíåé îò êîýôôèöèåíòîâ, ïðèïðàêòè÷åñêè ìàëûõÌíîãî÷ëåíf (z) =âîçìóùåíèÿõ êîðíè ìîãóò èçìåíèòüñÿ î÷åíü ñèëüíî.  äàííîì ñëó÷àå ñèòóàöèþëåãêî ïðîàíàëèçèðîâàòü, âîñïîëüçîâàâøèñü òåîðåìîé ìàòåìàòè÷åñêîãî àíàëèçà î íåÿâíîé ôóíêöèè.Ïóñòüx = x(t) êîðåíü ìíîãî÷ëåíàgt (z) = f (z) + tz 19 ,x(0) = 20x = x(t) ÿâëÿþùèéñÿ âîçìóùåíèåì êîðíÿïðè âîçìóùåíèè ëèøü îäíîãî êîýôôèöèåíòà èñõîäíîãî ìíîãî÷ëåíà ïðèz 19 .Ôóíêöèÿòèïè÷íûé ïðèìåð íåÿâíîé ôóíêöèè, çàäàííîé óðàâíåíèåìF (x, t) = 0,Îòñþäà íàõîäèì∂F dx∂x dt+∂F∂t20X∂F=∂xj=1ßñíî òàêæå, ÷òî∂F ∂t x=20dxdt=0 ⇒YãäåF (x, t) = f (x) + tx19 .∂F= − ∂F∂t / ∂x . íàøåì ñëó÷àå(x − i) + 19 t x19∂F = 19!.∂x x=20,t=0⇒1 ≤ i ≤ 20i 6= j= 2019 .Ñëåäîâàòåëüíî, ïðè óñëîâèèx(0) = 20íàõîäèìdx 2019=−≈ −4.3 · 107 .dt t=019!39.3Âîçìóùåíèå ñïåêòðà ìàòðèöûËþáûå ïðèìåðû ÷óâñòâèòåëüíîñòè êîðíåé ìíîãî÷ëåíà ê âîçìóùåíèÿì êîýôôèöèåíòîâäàþò ïðèìåðû ÷óâñòâèòåëüíîñòè ñîáñòâåííûõ çíà÷åíèé (ñïåêòðà) ìàòðèöû ê âîçìóùåíèÿì åå ýëåìåíòîâ äîñòàòî÷íî ðàññìîòðåòü ìàòðèöó Ôðîáåíèóñà äëÿ äàííîãî ìíîãî÷ëåíà.Ïðè âû÷èñëåíèè ñîáñòâåííûõ çíà÷åíèé, ñïîñîáíûõ ñèëüíî èçìåíèòüñÿ ïðè ìàëûõâîçìóùåíèÿõ ýëåìåíòîâ ìàòðèöû, ñëåäóåò çàäóìàòüñÿ î òîì, â êàêîé ñòåïåíè ìîæíîäîâåðÿòü ïîëó÷åííîìó îòâåòó.
Ñîâðåìåííàÿ òî÷êà çðåíèÿ íà ðåøåíèå ñïåêòðàëüíûõçàäà÷ 1 ñâÿçàíà ñ èçó÷åíèåì òàê íàçûâàåìûõ ñïåêòðàëüíûõ ïîðòðåòîâ: äëÿ çàäàííîéìàòðèöû A è ïàðàìåòðà ε > 0 ýòî ìíîæåñòâà âèäàS(ε) = {z ∈ C : f (λ) ≡ σmin (A − zI) ≤ ε},1 Îïèñàíèå è ðàçâèòèå äàííîé òî÷êè çðåíèÿ ìîæíî íàéòè â êíèãå: Ñ. Ê. Ãîäóíîâ,àñïåêòû ëèíåéíîé àëãåáðû,Íàó÷íàÿ êíèãà, Íîâîñèáèðñê, 1997.Ñîâðåìåííûå258Ëåêöèÿ 39ãäå σmin (B) îáîçíà÷àåò ìèíèìàëüíîå ñèíãóëÿðíîå ÷èñëî ìàòðèöû B .Î÷åâèäíî, ñïåêòð ìàòðèöû A ñîäåðæèòñÿ â S(ε). Âî ìíîãèõ çàäà÷àõ íå ñëåäóåò îæèäàòü ñêîëü-íèáóäü òî÷íîãî âû÷èñëåíèÿ îòäåëüíûõ ñîáñòâåííûõ çíà÷åíèé. Îäíàêî, âîçìóùåíèÿ ïîðÿäêà ε ìîãóò äàòü ìàòðèöó ñ ñîáñòâåííûìè çíà÷åíèÿìè, èçìåíÿþùèìèñÿâ ïðåäåëàõ ìíîæåñòâà S(ε). Òàêèì îáðàçîì, îòâåò ê çàäà÷å î âû÷èñëåíèè ñîáñòâåííûõçíà÷åíèé ïîëåçíî äàâàòü â ãðàôè÷åñêîé ôîðìå â âèäå ñîâîêóïíîñòè êðèâûõ, îïðåäåëåííûõ óñëîâèåì f (λ) = ε ïðè ðàçëè÷íûõ ε > 0 (ýòî òàê íàçûâàåìûå ëèíèè óðîâíÿôóíêöèè f (λ)).Çàäà÷à.Ñîáñòâåííûå çíà÷åíèÿ âåùåñòâåííîé ñèììåòðè÷íîé ìàòðèöûêàæèòå, ÷òî ïðè âñåõ äîñòàòî÷íî ìàëûõ ïî íîðìå âîçìóùåíèÿõìàòðèöûA+FFAïîïàðíî ðàçëè÷íû.
Äî-ñîáñòâåííûå çíà÷åíèÿ âîçìóùåííîéáóäóò âåùåñòâåííûìè.ÄÎÏÎËÍÈÒÅËÜÍÀß ×ÀÑÒÜ39.4Ïðåîáðàçîâàíèÿ îòðàæåíèÿ è âðàùåíèÿÏðè ðåøåíèè ñïåêòðàëüíûõ çàäà÷ äëÿ óïðîùåíèÿ âèäà èñõîäíîé ìàòðèöû A îáû÷íîèñïîëüçóþò óíèòàðíîå ïîäîáèå ïîäîáèå ñîõðàíÿåò ñïåêòð, à óíèòàðíîñòü ñîõðàíÿåòñèíãóëÿðíûå ÷èñëà è, ñëåäîâàòåëüíî, íå ìåíÿåò ñïåêòðàëüíûå ïîðòðåòû.Íà ïðàêòèêå óíèòàðíîå ïîäîáèå ðåàëèçóåòñÿ ñ ïîìîùüþ ïîñëåäîâàòåëüíîñòè ìàòðèöîòðàæåíèÿ èëè (êîìïëåêñíûõ) ìàòðèö âðàùåíèÿ. Âûáîð ìàòðèö îòðàæåíèÿ èëè âðàùåíèÿ ñâÿçàí ñ æåëàíèåì èñêëþ÷èòü òå èëè èíûå ýëåìåíòû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
