Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1113045), страница 47
Текст из файла (страница 47)
ε. . . ε(n−1)·(n−1).Óòâåðæäåíèå. Ìàòðèöà Ôóðüå îáðàòèìà è ïðè ýòîì îáðàòíàÿ ìàòðèöà èìååò âèä1 ∗F .n nFn−1 =Äîêàçàòåëüñòâî. Ýëåìåíòû ïðîèçâåäåíèÿ ìàòðèö Fn∗ Fn ëåãêî âû÷èñëÿþòñÿ êàê ñóììû ÷ëåíîâ ãåîìåòðè÷åñêîé ïðîãðåññèè:(Fn∗ Fn )ij=n−1Xki kjε̄ ε=k=0n−1Xεk(j−i)k=0Òàêèì îáðàçîì, Fn∗ Fn = n I .=n−1XÇàäà÷à.Íàéòè ìàêñèìàëüíîå çíà÷åíèå ôóíêöèèñ ýëåìåíòàìè=ε(j−i)n −1εj−i −1n,= 0, i 6= j,i = j.2Äîêàçàòü, ÷òîAk=0Çàäà÷à.ìàòðèöε(j−i) kFn4 = n2 I .f (A) = | det A|íà ìíîæåñòâå âñåõ êîìïëåêñíûõ|aij | ≤ 1.1 Ìèíóñ äàíü ñëîæèâøåéñÿ òðàäèöèè îïðåäåëåíèÿ ïðÿìîãî è îáðàòíîãî ïðåîáðàçîâàíèé Ôóðüå:ìèíóñ äëÿ ïðÿìîãî, ïëþñ äëÿ îáðàòíîãî.22322434.2Ëåêöèÿ 34Öèðêóëÿíòíûå ìàòðèöûÊðàñèâûé è ïîëåçíûé êëàññ íîðìàëüíûõ ìàòðèö ìàòðèöû âèäàA=a0a1a2...an−2an−1an−1a0a1...an−3an−2an−2an−1a0...an−4an−3..................a2a3a4...a0a1a1a2a3...an−1a0.Ìàòðèöà A íàçûâàåòñÿ öèðêóëÿíòíîé ìàòðèöåé èëè öèðêóëÿíòîì.
 ÷àñòíîñòè, ïðèn = 4 ïîëó÷àåì" a a a a #A=0321a1a2a3a0a1a2a3a0a1a2a3a0.Êàê âèäèì, öèðêóëÿíòíàÿ ìàòðèöà ïîëíîñòüþ îïðåäåëÿåòñÿ ýëåìåíòàìè ëþáîé ñâîåéñòðîêè èëè ëþáîãî ñòîëáöà. Åå ïåðâûé ñòîëáåö åñòü a = [a0 , a1 , . . . , an−1 ]> .×òîáû íàéòè ñîáñòâåííûå çíà÷åíèÿ è ñîáñòâåííûå âåêòîðû ìàòðèöû A, âîçüìåìïðîèçâîëüíûé êîðåíü ξ ñòåïåíè n èç åäèíèöû (ξ n = 1) è ðàññìîòðèì ÷èñëîλ = λ(ξ) ≡ a0 + ξa1 + . . .
+ ξ n−1 an−1 .Ïîñëåäîâàòåëüíî óìíîæàÿ îáå ÷àñòè íà 1, ξ, ξ 2 , . . . , ξ n−1 , íàõîäèìλ·1λ·ξλ · ξ2λ · ξ n−1Ñëåäîâàòåëüíî,===...=a0+ ξ a1an−1 + ξ a0an−2 + ξ an−1+ . . . + ξ n−1 an−1 ,+ . . . + ξ n−1 an−2 ,+ . . . + ξ n−1 an−3 ,a1+ . . . + ξ n−1 a0 .+ ξ a2λ(ξ) [1, ξ, . . .
, ξ n−1 ] = [1, ξ, . . . , ξ n−1 ]A.(∗)Âûáåðåì ε = cos(−2π/n) + i sin(−2π/n). Ðàâåíñòâî (∗) ñïðàâåäëèâî ïðè ξ =1, ε, ε2 , . . . , εn−1 è, ñëåäîâàòåëüíî, äàåò ñèñòåìó ðàâåíñòâ, êîòîðàÿ â ìàòðè÷íîé çàïèñèèìååò âèäΛFn = Fn A,ãäå Fn ìàòðèöà Ôóðüå ïîðÿäêà n, Λ äèàãîíàëüíàÿ ìàòðèöà âèäàλ(1)λ(ε)Λ=..,.λ(εn−1 )Èòàê, AFn∗ = Fn∗ Λ ⇒ ñòîëáöû ìàòðèöû Fn∗ ñóòü ñîáñòâåííûå âåêòîðû ìàòðèöûA, îòâå÷àþùèå ñîáñòâåííûì çíà÷åíèÿì, ðàñïîëîæåííûì íà äèàãîíàëè ìàòðèöû Λ.
Çàìåòèì, ÷òî Fn∗ ïîëó÷àåòñÿ èç Fn ïåðåñòàíîâêîé ñòîëáöîâ: ïåðâûé ñòîëáåö îñòàåòñÿ íàìåñòå, à ñòîëáöû ñî âòîðîãî ïî ïîñëåäíèé ñòàâÿòñÿ â îáðàòíîì ïîðÿäêå. Ïîýòîìó ìîæíîóòâåðæäàòü, ÷òî áàçèñîì èç ñîáñòâåííûõ âåêòîðîâ öèðêóëÿíòíîé ìàòðèöû A ÿâëÿþòñÿñòîëáöû ìàòðèöû Ôóðüå Fn . Ïîëó÷åííûå ðåçóëüòàòû ñôîðìóëèðóåì â âèäå òåîðåìû.Òåîðåìà î öèðêóëÿíòàõ. Ïóñòü A öèðêóëÿíòíàÿ ìàòðèöà ñ ïåðâûì ñòîëáöîìa = [a0 , .
. . , an−1 ]> . ÒîãäàA=1 ∗F ΛFn ,n n(#)Å. Å. Òûðòûøíèêîâ225ãäå Fn ìàòðèöà Ôóðüå ïîðÿäêà n è Λ äèàãîíàëüíàÿ ìàòðèöà ñîáñòâåííûõ çíà÷åíèé âèäà"λ# 1λ1a0..Λ=, . . . = Fn . . . ..λnλnan−1Íåñëîæíî ïðîâåðèòü, ÷òî äëÿ ëþáûõ λ1 , . . . , λn ìàòðèöà â ïðàâîé ÷àñòè (#) ÿâëÿåòñÿ öèðêóëÿíòíîé ìàòðèöåé. Îòñþäà ÿñíî, ÷òî ïðîèçâåäåíèå öèðêóëÿíòíûõ ìàòðèöîñòàåòñÿ öèðêóëÿíòíîé ìàòðèöåé.Ìàòðèöà, îáðàòíàÿ ê íåâûðîæäåííîé öèðêóëÿíòíîé ìàòðèöå, òàêæå ÿâëÿåòñÿ öèðêóëÿíòíîé.34.3Àëãåáðû ìàòðèöËþáàÿ ëèíåéíàÿ êîìáèíàöèÿ öèðêóëÿíòîâ åñòü öèðêóëÿíò. Òàêèì îáðàçîì, ìíîæåñòâî öèðêóëÿíòîâ ïîðÿäêà n ÿâëÿåòñÿ n-ìåðíûì ëèíåéíûì ïðîñòðàíñòâîì, íà êîòîðîìîïðåäåëåíà îïåðàöèÿ óìíîæåíèÿ ýëåìåíòîâ, êîòîðàÿ âìåñòå ñ îïåðàöèåé ñëîæåíèÿ ïðåâðàùàåò äàííîå ëèíåéíîå ïðîñòðàíñòâî â êîëüöî.Ïóñòü â ëèíåéíîì ïðîñòðàíñòâå V îïðåäåëåíà îïåðàöèÿ óìíîæåíèÿ ýëåìåíòîâ, êîòîðàÿ äåëàåò åãî òàêæå êîëüöîì ñ åäèíèöåé, è ïóñòü óìíîæåíèå ïðîèçâîëüíûõ ýëåìåíòîâa è b è óìíîæåíèå íà ÷èñëî α ñâÿçàíû àêñèîìîé α(ab) = (αa)b = a(αb).
 òàêèõ ñëó÷àÿõïðîñòðàíñòâî V íàçûâàåòñÿ àëãåáðîé.Çàìåòèì, ÷òî óìíîæåíèå öèðêóëÿíòîâ êîììóòàòèâíî ïîýòîìó îíè äàþò ïðèìåðêîììóòàòèâíîé àëãåáðû ìàòðèö. Âñå ìíîæåñòâî ìàòðèö ôèêñèðîâàííîãî ïîðÿäêà n ïðèìåð íåêîììóòàòèâíîé àëãåáðû.Òåîðåìà. Ïóñòü M àëãåáðà ìàòðèö è A ∈ M íåâûðîæäåííàÿ ìàòðèöà. ÒîãäàA−1 ∈ M.Äîêàçàòåëüñòâî. Ïóñòü A ∈ M. Ïî òåîðåìå ÃàìèëüòîíàÊýëè, A àííóëèðóåòñÿ ñâîèìõàðàêòåðèñòè÷åñêèì ìíîãî÷ëåíîì: a0 I + a1 A + . .
. + an−1 An−1 + An = 0. Åñëè A íåâûðîæäåííàÿ ìàòðèöà, òî, óìíîæàÿ îáå ÷àñòè íà A−1 è ó÷èòûâàÿ, ÷òî a0 = (−1)n det A 6= 0,ïîëó÷àåì1a1 I + a2 A + . . . an−1 An−2 + An−1 ∈ M.2A−1 = −a0Ïî àíàëîãèè ñ öèðêóëÿíòàìè, ìîæíî ïîñòðîèòü ìíîãî äðóãèõ êîììóòàòèâíûõ ìàòðè÷íûõ àëãåáð.Óòâåðæäåíèå. Äëÿ ëþáîé ôèêñèðîâàííîé íåâûðîæäåííîé ìàòðèöû Q ∈ Cn×n âñåìàòðèöû âèäà QΛQ−1 , ãäå Λ ïðîèçâîëüíàÿ äèàãîíàëüíàÿ ìàòðèöà ïîðÿäêà n, îáðàçóþò êîììóòàòèâíóþ àëãåáðó.Äîêàçàòåëüñòâî.
Óêàçàííîå ìíîæåñòâî ìàòðèö îáîçíà÷èì ÷åðåç M. Åñëè A1 , A2 ∈ M,òî A1 = QΛ1 Q−1 , A2 = QΛ2 Q−1 äëÿ êàêèõ-òî äèàãîíàëüíûõ ìàòðèö Λ1 è Λ2 . ÒîãäàαA1 + βA2 = Q(Λ1 + Λ2 )Q−1 ∈ M è A1 A2 = Q(Λ1 Λ2 )Q−1 ∈ M. 2Çàìå÷àíèå. Äàííîå óòâåðæäåíèå îïèñûâàåò íå âñå âîçìîæíûå êîììóòàòèâíûå àëãåá-226Ëåêöèÿ 34ðû ìàòðèö.
Íàïðèìåð, ïóñòü M ñîñòîèò èç âñåõ n × n-ìàòðèö âèäàA=a0a1a2...an−2an−1a0a1...an−3an−2a0......an−3...a1...a0a1.(∗)a0Íåñëîæíî ïðîâåðèòü, ÷òî M ÿâëÿåòñÿ êîììóòàòèâíîé àëãåáðîé, íî â M èìåþòñÿíåäèàãîíàëèçóåìûå ìàòðèöû (äîêàæèòå!). Åùå îäèí ïðèìåð êîììóòàòèâíîé àëãåáðû ìíîæåñòâî ìàòðèö A òàêèõ, ÷òî A> ∈ M.Çàäà÷à.Äàíà æîðäàíîâà êëåòêàêîììóòèðóþùèõ ñ34.4J>Jïîðÿäêàn.Äîêàæèòå, ÷òî ìíîæåñòâî âñåõ, ñîâïàäàåò ñ ìíîæåñòâîì ìàòðèö âèäàn × n-ìàòðèö,(∗).Îäíîâðåìåííîå ïðèâåäåíèå ê òðåóãîëüíîìó âèäóÒåîðåìà. Äëÿ ïðîèçâîëüíîé êîììóòàòèâíîé àëãåáðû ìàòðèö M ñóùåñòâóåò îáðàòèìàÿ ìàòðèöà Q òàêàÿ, ÷òî äëÿ ëþáîé A ∈ M ìàòðèöà Q−1 AQ ÿâëÿåòñÿ âåðõíåéòðåóãîëüíîé.Äîêàçàòåëüñòâî.
Ïóñòü ìàòðèöû A1 , . . . , Ak ∈ M ⊂ Cn×n îáðàçóþò áàçèñ â ëèíåéíîìïðîñòðàíñòâå M. Äîêàæåì, ÷òî îíè èìåþò îáùèé ñîáñòâåííûé âåêòîð.Îáîçíà÷èì ÷åðåç L ñîáñòâåííîå ïîäïðîñòðàíñòâî ìàòðèöû A1 äëÿ ñîáñòâåííîãî çíà÷åíèÿ λ1 . Ïóñòü A1 x = λ1 x, x 6= 0. ÒîãäàA1 (A2 x) = A2 (A1 x) = λ1 (A2 x).(∗)Ñëåäîâàòåëüíî, A2 x ∈ L.
Áîëåå òîãî, Al2 x ∈ L äëÿ âñåõ l = 1, 2, ... . Ïóñòü M ìèíèìàëüíîå ïîäïðîñòðàíñòâî, ñîäåðæàùåå âñå âåêòîðû âèäà Al2 x. Î÷åâèäíî, ýòî ìèíèìàëüíîå ïîäïðîñòðàíñòâî, èíâàðèàíòíîå îòíîñèòåëüíî A2 è ñîäåðæàùåå x.  ñèëó (∗)çàêëþ÷àåì, ÷òî M ⊂ L.  M îáÿçàòåëüíî èìååòcÿ ñîáñòâåííûé âåêòîð äëÿ A2 , îí æåáóäåò ñîáñòâåííûì âåêòîðîì è äëÿ A1 .Äàëåå ïî èíäóêöèè. Ïóñòü L ñîäåðæàùåå x 6= 0 ïåðåñå÷åíèå ñîáñòâåííûõ ïîäïðîñòðàíñòâ L1 , . . .
, Lk , îòâå÷àþùèõ ñîîòâåòñòâåííî ìàòðèöàì A1 , . . . , Ak−1 , à M ñîäåðæàùåå x ìèíèìàëüíîå ïîäïðîñòðàíñòâî, èíâàðèàíòíîå îòíîñèòåëüíî Ak (î÷åâèäíî, îíî ñîñòîèò èç âåêòîðîâ âèäà p(Ak )x äëÿ âñåâîçìîæíûõ ìíîãî÷ëåíîâ p). Ëåãêî ïðîâåðèòü, ÷òî M ÿâëÿåòñÿ (íåíóëåâûì!) ïîäïðîñòðàíñòâîì äëÿ êàæäîãî èç ñîáñòâåííûõïîäïðîñòðàíñòâ L1 , . . . , Lk . Ïîýòîìó M ⊂ L, à ñîäåðæàùèéñÿ â M ñîáñòâåííûé âåêòîðäëÿ Ak ÿâëÿåòñÿ ñîáñòâåííûì âåêòîðîì òàêæå äëÿ A1 , . . . , Ak−1 .Èòàê, ïóñòü x îáùèé ñîáñòâåííûé âåêòîð äëÿ A1 , . .
. , Ak . Ïóñòü P ëþáàÿîáðàòèìàÿ ìàòðèöà, ïåðâûé ñòîëáåö êîòîðîé ðàâåí x. Òîãäà êàæäàÿ èç ìàòðèöP A1 P −1 , . . . , P Ak P −1 èìååò áëî÷íûé âèäλi vi>−1P Ai P =, Bi ∈ C(n−1)×(n−1) .0 BiÍåïîñðåäñòâåííî ïðîâåðÿåòñÿ, ÷òî ìàòðèöû B1 , . . .
, Bk êîììóòèðóþò. Åñëè îíè îäíîâðåìåííî ïðèâîäÿòñÿ ê âåðõíåìó òðåóãîëüíîìó âèäó ñ ïîìîùüþ îáðàòèìîé ìàòðèöû ZÅ. Å. Òûðòûøíèêîâ227ïîðÿäêà n − 1 (êàæäàÿ èç ìàòðèö Z −1 Bi Z ÿâëÿåòñÿ âåðõíåé òðåóãîëüíîé), òî ìàòðèöà1 0Q=P0 Zîäíîâðåìåííî ïðèâîäèò ê òðåóãîëüíîìó âèäó êàæäóþ èç ìàòðèö A1 , . .
. , Ak . Òî æåâåðíî è äëÿ ïðîèçâîëüíîé ëèíåéíîé êîìáèíàöèè ìàòðèö A1 , . . . , Ak . 2Çàäà÷à.ìàòðèöûkèPn − k,èÌàòðèöûQAèòàêèå, ÷òîBIP AQ = k0ñîîòâåòñòâåííî, è, êðîìåÇàäà÷à.n êîììóòèðóþò.÷òî ñóùåñòâóþò íåâûðîæäåííûå Äîêàæèòå,0X 0è P BQ =, ãäå áëîêè Ik , X è N, Y èìåþò ïîðÿäîêN0 Yòîãî, ìàòðèöà Ik åäèíè÷íàÿ, à N íèëüïîòåíòíàÿ.ïîðÿäêàA, B ∈ Cn×n det(λA − B) 6= 0.Äîêàæèòå,Ik 0X0÷òî ñóùåñòâóþò íåâûðîæäåííûå ìàòðèöû P è Q òàêèå, ÷òî P AQ =è P BQ =,0 N0 In−kãäå áëîêè Ik , X è N, In−k èìåþò ïîðÿäîê k è n − k , ñîîòâåòñòâåííî, è, êðîìå òîãî, ìàòðèöû Ik è In−kåäèíè÷íûå, à N íèëüïîòåíòíàÿ.Äëÿ ìàòðèöñóùåñòâóåò ÷èñëîλòàêîå, ÷òîÄÎÏÎËÍÈÒÅËÜÍÀß ×ÀÑÒÜ34.5Áûñòðîå ïðåîáðàçîâàíèå ÔóðüåÓìíîæåíèå ìàòðèöû Ôóðüå Fn íà âåêòîð-ñòîëáåö x ∈ Cn íàçûâàåòñÿ ïðÿìûì ïðåîáðàçîâàíèåì Ôóðüå âåêòîðà x.Êëàññè÷åñêîå ïðàâèëî óìíîæåíèÿ ìàòðèöû íà âåêòîð äàåò àëãîðèòì ñ ÷èñëîì îïåðàöèé ïîðÿäêà n2 .
Îäíàêî, ñïåöèàëüíûé âèä ìàòðèöû Fn ïîçâîëÿåò óìíîæàòü åå íàâåêòîð ñ çàòðàòîé ëèøü O(n log2 n) àðèôìåòè÷åñêèõ îïåðàöèé!Àëãîðèòìû ñ òàêèì ñâîéñòâîì (áûñòðîå ïðåîáðàçîâàíèå Ôóðüå) íà÷àëè âíåäðÿòüñÿâ ïðàêòèêó âû÷èñëåíèé â 60-õ ãîäàõ 20-ãî âåêà è ïðîèçâåëè áóêâàëüíî ïåðåâîðîò â ðÿäåðàçäåëîâ ïðèêëàäíîé ìàòåìàòèêè. 2 Òàê èëè èíà÷å, áûñòðîå ïðåîáðàçîâàíèå Ôóðüåñòàëî îñíîâíîé êîìïîíåíòîé ìíîãèõ áûñòðûõ àëãîðèòìîâ â çàäà÷àõ ëèíåéíîé àëãåáðû.Ïðåäïîëîæèì, ÷òî n = 2L è m = n/2. Áóäåì íóìåðîâàòü ñòðîêè è ñòîëáöû ìàòðèöûFn ÷èñëàìè îò 0 äî n − 1. Îò Fn ïåðåéäåì ê ìàòðèöå Fen , â êîòîðîé ñíà÷àëà èäóò ïîäðÿäâñå ñòðîêè Fn ñ ÷åòíûìè íîìåðàìè, à çàòåì âñå ñòðîêè ñ íå÷åòíûìè íîìåðàìè (ÿñíî,÷òî Fen = Pn Fn , ãäå Pn ñîîòâåòñòâóþùàÿ ìàòðèöà ïåðåñòàíîâêè).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
