Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 69
Текст из файла (страница 69)
Íàïðèìåð, ñêàëÿðíîåïðîèçâåäåíèåZ1(f, g) =−1ïîðîæäàåòìíîãî÷ëåíû ×åáûøåâà.f (x)g(x)√dx,1 − x2f, g ∈ Pn ,328Ëåêöèÿ 57Äîïîëíåíèå ê ëåêöèè 3258.1Ìèíèìàëüíûé ìíîãî÷ëåí ìàòðèöûÏî òåîðåìå ÃàìèëüòîíàÊýëè, ìàòðèöà A ∈ Cn×n àííóëèðóåòñÿ ñâîèì õàðàêòåðèñòè÷åñêèì ìíîãî÷ëåíîì: åñëè f (λ) = det(A − λI), òî f (A) = 0. Ìíîãî÷ëåí ìèíèìàëüíîéñòåïåíè ñ òåì æå ñâîéñòâîì íàçûâàåòñÿ ìèíèìàëüíûì ìíîãî÷ëåíîì ìàòðèöû A.Ëåììà. Ìèíèìàëüíûé ìíîãî÷ëåí ÿâëÿåòñÿ äåëèòåëåì õàðàêòåðèñòè÷åñêîãî ìíîãî÷ëåíà.Äîêàçàòåëüñòâî. Ïóñòü φ(λ) è f (λ) ìèíèìàëüíûé è õàðàêòåðèñòè÷åñêèé ìíîãî÷ëåíû äëÿ A.
Âûïîëíèì äåëåíèå ñ îñòàòêîì: f (λ) = q(λ)φ(λ) + r(λ). Î÷åâèäíî, r(A) = 0.Íåðàâåíñòâî deg r(λ) < deg φ(λ) ïðîòèâîðå÷èëî áû ìèíèìàëüíîñòè ìíîãî÷ëåíà φ(λ).Ïîýòîìó r(λ) íóëåâîé ìíîãî÷ëåí. 2Òåîðåìà. Ïóñòü A èìååò ïîïàðíî ðàçëè÷íûå ñîáñòâåííûå çíà÷åíèÿ λ1 , . . . , λm . Ñòåïåíü ìèíèìàëüíîãî ìíîãî÷ëåíà ìàòðèöû A ðàâíà ñóììå n1 + . . . + nm , ãäå ni ìàêñèìàëüíûé ïîðÿäîê æîðäàíîâûõ êëåòîê äëÿ ñîáñòâåííîãî çíà÷åíèÿ λi .Äîêàçàòåëüñòâî.Äîñòàòî÷íî ðàññìîòðåòü ðàçëîæåíèå ïðîèçâîëüíîãî âåêòîðà x =Pxj ïî öèêëè÷åñêèì ïîäïðîñòðàíñòâàì Lj (ïîñëåäíèå â ïðÿìîé ñóììå äàþò Cn ).
Ïóñòüïîäïðîñòðàíñòâà Lj1 , . . . , Ljm îòâå÷àþò, ñîîòâåòñòâåííî, λ1 , . . . , λm è èìåþò ðàçìåðíîñòèn1 , . . . , nm . Òîãäà ker(A − λi I)ni = Ki ⇒(A − λ1 I)n1 . . . (A − λm I)nm x = 0.Òàêèì îáðàçîì, ñòåïåíü ìèíèìàëüíîãî ìíîãî÷ëåíà íå âûøå n1 + . . . + nm . òî æå âðåìÿ, ñòåïåíü ìèíèìàëüíîãî ìíîãî÷ëåíà íå ìîæåò áûòü ìåíüøå: æîðäàíîâà êëåòêà ïîðÿäêà ni äëÿ λi íå ìîæåò áûòü àííóëèðîâàíà ìíîãî÷ëåíîì ñòåïåíè ìåíüøåni , ïðè ýòîì åå ìèíèìàëüíûé ìíîãî÷ëåí åñòü â òî÷íîñòè (λi − λ)ni è ýòîò ìíîãî÷ëåí íåìîæåò àííóëèðîâàòü íè îäíó èç æîðäàíîâûõ êëåòîê, îòâå÷àþùèõ äðóãîìó ñîáñòâåííîìó çíà÷åíèþ. 258.2Æîðäàíîâà ôîðìà: ïðÿìîå äîêàçàòåëüñòâî ïî èíäóêöèèÏóòü ê òåîðåìå î ïðèâåäåíèè êâàäðàòíîé êîìïëåêñíîé ìàòðèöû ê æîðäàíîâîé ôîðìå, î÷åâèäíî, ïîòðåáîâàë îò íàñ èçðÿäíûõ óñèëèé.
Ïîýòîìó åñòåñòâåííî æåëàíèå êàê-òî åãî ñðåçàòü â êàêîé-òîñòåïåíè ýòî óäàåòñÿ ñ ïîìîùüþ ñëåäóþùåãî ðàññóæäåíèÿ, ïðåäëîæåííîãî À. Ô. Ôèëèïïîâûì.Òåîðåìà. Ïóñòü L èíâàðèàíòíî îòíîñèòåëüíî A ∈ Cn×n è ñóæåíèå A íà L èìååò åäèíñòâåííîåñîáñòâåííîå çíà÷åíèå λ êðàòíîñòè k . Òîãäà ñóùåñòâóåò öåïî÷êà ëèíåéíî íåçàâèñèìûõ âåêòîðîâx1 , . . . , xk ∈ L òàêàÿ, ÷òî äëÿ êàæäîãî jAxj = λxjëèáîAxj = λxj + xj−1 .329330Ëåêöèÿ 58Äîêàçàòåëüñòâî.Ïåðåéäåì ê ìàòðèöåB = A − λIè áóäåì äîêàçûâàòü ñóùåñòâîâàíèå öåïî÷êè ñîñâîéñòâàìèBxj = 0ÏðèëèáîBxj = xj−1 .k = 1 ýòî î÷åâèäíî (â äàííîì ñëó÷àå L îäíîìåðíîå èíâàðèàíòíîå ïîäïðîñòðàíñòâî).
Ðàññóæäàÿïî èíäóêöèè, ïðåäïîëîæèì, ÷òî â ñëó÷àå, êîãäà ðàçìåðíîñòü èíâàðèàíòíîãî ïîäïðîñòðàíñòâà ðàâíàimB ∩ L.ßñíî, ÷òîÈòàê, ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ, èìååòñÿ öåïî÷êà ëèíåéíî íåçàâèñèìûõ âåêòîðîây1 , . . . , y rr < k , öåïî÷êà íóæíîãîr ≡ dim(imB ∩ L) < k .âèäà ñóùåñòâóåò.  êà÷åñòâå òàêîãî ïðîñòðàíñòâà âîçüìåìòàêèõ, ÷òîByj = 0ßñíî, ÷òî ñèñòåìày1 , . . . , y këèáîByj = yj−1 .ðàçáèâàåòñÿ êà êîíå÷íîå ÷èñëî æîðäàíîâûõ öåïî÷åê:yi1 , .
. . , yj1 ; . . . ; yil , . . . , yjl .Òàêèì îáðàçîì, æîðäàíîâûõ öåïî÷åê âñåãî l , à âåêòîðûy i1 , . . . , y ilèyj1 , . . . , yil íà÷àëüíûå è êîíå÷-íûå âåêòîðû ýòèõ öåïî÷åê.Âñå âåêòîðû, è â ÷àñòíîñòè, êîíå÷íûå âåêòîðû æîðäàíîâûõ öåïî÷åê, ïðèíàäëåæàòíàéäóòñÿ âåêòîðûw1 , . .
. , wlimB .Ïîýòîìóòàêèå, ÷òîBw1 = yj1 , . . . , Bwl = yjl .Çàìåòèì, ÷òîw1 , . . . , wl ∈ kerB r+1 ∩ L.Íà÷àëüíûå âåêòîðû æîðäàíîâûõ öåïî÷åê ëèíåéíî íåçàâèñèìû (êàê ÷àñòü ëèíåéíî íåçàâèñèìîékerB ∩ L, íî, âîçìîæíî, èõ íåäîñòàòî÷íî äëÿz1 , . . . , zs äîïîëíÿþò ñèñòåìó yi1 , . . .
, yil äî áàçèñàñèñòåìû) è ïðèíàäëåæàò ïîäïðîñòðàíñòâóòîãî, ÷òîáûñîñòàâèòü åãî áàçèñ. Ïóñòü âåêòîðûâ ïîäïðîñò-ðàíñòâåkerB ∩ L.Çàìåòèì, ÷òîdim L = dim(imB ∩ L) + dim(kerB ∩ L).z1 , . . . , zs ,èìååò íóæíûé âèä, è â íåé ðîâíî(∗)yi1 , . . . , yj1 , w1 ,dim L = r + (l + s)Òàêèì îáðàçîì, öåïî÷êà âåêòîðîâ... ,yil , . .
. , yjl , wl(∗)âåêòîðîâ. Îñòàåòñÿ ëèøü äîêàçàòü, ÷òî ñèñòåìàëèíåéíî íåçàâèñèìà. ÇàïèøåìX X Xαi zi +βi yi +γi wi = 0.B , ïîëó÷àåì ðàâíóþ íóëþ ëèíåéíóþ êîìáèíàöèþ ÷àñòè âåêòîðîâ yi áåçyi1 , . . . , yil . Îòñþäà íàõîäèì, ÷òî γi = 0 äëÿ âñåõ 1 ≤ i ≤ l è1 ≤ i ≤ r, êðîìå i = i1 , . . . , il . Òàêèì îáðàçîì,!!slXXαi zi +βit yit = 0.Óìíîæèâ îáå ÷àñòè ñëåâà íàíà÷àëüíûõ âåêòîðîâ æîðäàíîâûõ öåïî÷åêβi = 0äëÿ âñåõi=1t=1Äàííàÿ ñèñòåìà ëèíåéíî íåçàâèñèìà ïî ïîñòðîåíèþ⇒âñåαièβitðàâíû íóëþ.2Äîïîëíåíèå ê ëåöèè 3459.1ÑâåðòêèÏóñòü öèðêóëÿíòíàÿ ìàòðèöà A îïðåäåëÿåòñÿ ïåðâûì ñòîëáöîì a.
Âåêòîð y = Ax íàçûâàåòñÿ ïåðèîäè÷åñêîé ñâåðòêîé âåêòîðîâ a è x. Îáîçíà÷åíèå: y = a ∗ x.Çàäà÷à.Äîêàæèòå, ÷òîa ∗ x = x ∗ a.Ñîãëàñíî òåîðåìå î öèðêóëÿíòàõ, âû÷èñëåíèå ïåðèîäè÷åñêîé ñâåðòêè âåêòîðîâ èçRn (óìíîæåíèå íà öèðêóëÿíòíóþ ìàòðèöó) ñâîäèòñÿ ê òðåì óìíîæåíèÿì íà ìàòðèöóÔóðüå. Ïîñëåäíåå ìîæíî âûïîëíèòü ñ ïîìîùüþ àëãîðèòìà áûñòðîãî ïðåîáðàçîâàíèÿÔóðüå çà O(n log n) àðèôìåòè÷åñêèõ îïåðàöèé, åñëè n = 2L .Ðåøåíèå ëèíåéíûõ ñèñòåì ñ öèðêóëÿíòíîé ìàòðèöåé îñóùåñòâëÿåòñÿ ñ òåìè æå çàòðàòàìè (äîêàæèòå!).Ïóñòü òåïåðü a = [a−n+1 , a−n+2 , .
. . , a0 , a1 , . . . , an−1 ]> ∈ C2n−1 è x ∈ Cn . Ïîä àïåðèîäè÷åñêîé ñâåðòêîé âåêòîðîâ a è x èíîãäà ïîíèìàåòñÿ âåêòîð y = Ax, ãäåa0a−1 . . . a−n+1 a1a0. . . a−n+2 .A= ......... ...an−1 an−2 . . . a0Ìàòðèöà A òàêîãî âèäà íàçûâàåòñÿ òåïëèöåâîé ìàòðèöåé.êóëÿíò ÿâëÿåòñÿ òàêæå òåïëèöåâîé ìàòðèöåé.1Çàìåòèì, ÷òî ëþáîé öèð-Óòâåðæäåíèå. Äëÿ ëþáîãî n òåïëèöåâà ìàòðèöà ïîðÿäêà n ìîæåò áûòü óìíîæåíàíà âåêòîð ñ çàòðàòîé O(n log2 n) îïåðàöèé.Äîêàçàòåëüñòâî. Äîñòàòî÷íî çàìåòèòü, ÷òî òåïëèöåâó ìàòðèöó A ïîðÿäêà n ìîæíîäîñòðîèòü äî öèðêóëÿíòàC=AC12C21 C22ïîðÿäêà N = 2L < 4n. Âîò êàê ýòî äåëàåòñÿ â ñëó÷àå n = 3:C=a0a1a2000a−2a−1a−1a0a1a2000a−2a−2a−1a0a1a20000a−2a−1a0a1a2001  ÷åñòü íåìåöêîãî ìàòåìàòèêà Îòòî Òåïëèöà.33100a−2a−1a0a1a20000a−2a−1a0a1a2a2000a−2a−1a0a1a1a2000a−2a−1a0.332Ëåêöèÿ 59Äàëåå, ïóñòü uAC12x=.vC21 C220Îòñþäà ÿñíî, ÷òî u = Ax. Òàêèì îáðàçîì, óìíîæåíèå íà òåïëèöåâó ìàòðèöó ñâîäèòñÿ ê óìíîæåíèþ íà öèðêóëÿíòíóþ ìàòðèöó ïîðÿäêà N = 2L .
Ïðèìåíåíèå áûñòðîãîïðåîáðàçîâàíèÿ Ôóðüå äàåò àëãîðèòì ñ ÷èñëîì îïåðàöèé O(N log2 N ) = O(n log2 n). 259.2Ñëîæíîñòü ïðåîáðàçîâàíèÿ Ôóðüå×òî ìîæíî ñêàçàòü î ñëîæíîñòè ïðåîáðàçîâàíèÿ Ôóðüå â ñëó÷àå n 6= 2L ?Ïóñòü ýëåìåíòû ìàòðèöû Fn íóìåðóþòñÿ èíäåêñàìè îò 0 äî n − 1.  ïîçèöèè (k, l)íàõîäèòñÿ ÷èñëî222222εkl = ε(k +l −(k−l) )/2 = εk /2 ε−(k−l) εl /2 .Ïîýòîìó ìàòðèöà Ôóðüå ðàñùåïëÿåòñÿ â ïðîèçâåäåíèå òðåõ ìàòðèö 02 /2εFn = DAD, D = ε12/2..−(k−l)2 /2], 0 ≤ k, l ≤ n − 1. , A = [ε.ε(n−1)2/2Òàêèì îáðàçîì, óìíîæåíèå íà ìàòðèöó Ôóðüå ïðîèçâîëüíîãî ïîðÿäêà n ñâîäèòñÿ ê óìíîæåíèþ íà òåïëèöåâó ìàòðèöó A òîãî æå ïîðÿäêà n.
Ïîñëåäíåå ñâîäèòñÿ ê óìíîæåíèþíà öèðêóëÿíòíóþ ìàòðèöó ïîðÿäêà n ≤ N = 2L < 4n. èòîãå âñå ñâîäèòñÿ ê òðîåêðàòíîìó ïðèìåíåíèþ àëãîðèòìà áûñòðîãî ïðåîáðàçîâàíèÿ Ôóðüå ñïåöèàëüíî âûáðàííîãî ïîðÿäêà N = 2L . Îïèñàííàÿ âîçìîæíîñòü ïîëó÷åíèÿáûñòðîãî ïðåîáðàçîâàíèÿ Ôóðüå áåç îãðàíè÷åíèé íà åãî ïîðÿäîê ÿâëÿåòñÿ, âåðîÿòíî,ñàìîé ïðîñòîé íî íå åäèíñòâåííîé è íå âñåãäà íàèëó÷øåé äëÿ ïðàêòè÷åñêèõ âû÷èñëåíèé.Ìîæíî ëè ïîëó÷èòü àëãîðèòì àñèìïòîòè÷åñêè ìåíüøåé ñëîæíîñòè? Îòâåò çàâèñèòîò îãðàíè÷åíèé íà êëàññ äîïóñòèìûõ àëãîðèòìîâ. Ïóñòü ïîä àëãîðèòìîì ïîíèìàåòñÿïîñëåäîâàòåëüíîñòü îïåðàöèé âèäà z = αi x + βi y , ãäå x, y àðãóìåíòû, z ðåçóëüòàòi-îé îïåðàöèè, à αi è βi îïðåäåëÿþùèå îïåðàöèþ êîíñòàíòû. Äîêàçàíî, ÷òî åñëèâñå êîíñòàíòû îãðàíè÷åíû ïî ìîäóëþ âåëè÷èíîé M > 0, òî ÷èñëî îïåðàöèé òàêîãîâèäà, íåîáõîäèìûõ äëÿ âû÷èñëåíèÿ ïðåîáðàçîâàíèÿ Ôóðüå, íå ìåíüøå cn log2 n, ãäå cíå çàâèñèò îò n (íî çàâèñèò îò M ).Çàäà÷à.Äîêàçàòü, ÷òî äâà ìíîãî÷ëåíà ñòåïåíènìîæíî ïåðåìíîæèòü ñ çàòðàòîéO(n log2 n)àðèôìåòè÷åñêèõ îïåðàöèé.Çàäà÷à.Äàíû ÷èñëàìîæíî íàéòè ñ çàòðàòîé59.3x1 , .
. . , xn .Äîêàçàòü, ÷òî êîýôôèöèåíòû ìíîãî÷ëåíàf (x) =nQ(x − xi )i=1O(n log22 n)àðèôìåòè÷åñêèõ îïåðàöèé.Áûñòðûå ïðèáëèæåííûå âû÷èñëåíèÿÐàññìîòðèì çàäà÷ó óìíîæåíèÿ ôèêñèðîâàííîé ìàòðèöû A ïîðÿäêà n íà ïðîèçâîëüíûéâåêòîð x. Ïðè ïîñòðîåíèè àëãîðèòìà äëÿ âû÷èñëåíèÿ âåêòîðà y = Ax âõîäíûìè äàííûìè ñ÷èòàþòñÿ êîîðäèíàòû âåêòîðà x, à ðåçóëüòàòîì êîîðäèíàòû âåêòîðà y .Åñëè A = Fn ìàòðèöà Ôóðüå ïîðÿäêà n, òî y = Ax ìîæíî íàéòè çà O(n log2 n)îïåðàöèé. Ïðè òî÷íîì âûïîëíåíèè êàæäîé îïåðàöèè áóäåò ïîëó÷åí òî÷íûé âåêòîð y .Å.
Å. Òûðòûøíèêîâ333Îäíàêî, ïðàêòè÷åñêèé èíòåðåñ ïðåäñòàâëÿåò ïîëó÷åíèå íåêîòîðîãî ïðèáëèæåíèÿ ê âåêòîðó y ñ ãàðàíòèðîâàííîé òî÷íîñòüþ ε > 0. ×èñëî îïåðàöèé äëÿ ðåøåíèÿ òàêîé çàäà÷èäîëæíî çàâèñåòü, î÷åâèäíî, íå òîëüêî îò n, íî è îò ε. ïðèëîæåíèÿõ ýëåìåíòû aij ìàòðèöû A ÷àñòî îïðåäåëÿþòñÿ êàê çíà÷åíèÿ íåêîòîðîé ôóíêöèè f (u, v) â òî÷êàõ u = ui , v = vj , ãäå u1 , . . . , un è v1 , . . . , vn íåêîòîðûåñèñòåìû òî÷åê (ñåòêè) â k -ìåðíîì ïðîñòðàíñòâå:aij = f (ui , vj ),1 ≤ i, j ≤ n.Ïóñòü âñå òî÷êè ui , vj ïðèíàäëåæàò ìíîæåñòâó D ⊂ Rk , è ïðåäïîëîæèì, ÷òî äëÿ ëþáîãîε > 0 ôóíêöèÿ f (u, v) äîïóñêàåò ïðèáëèæåíèå ñ ðàçäåëåííûìè ïåðåìåííûìèf (u, v) ≈rXφs (u)ψs (v),r = r(ε),s=1ãäå|f (u, v) −rXφs (u)ψ(s (v)| ≤ ε,u, v ∈ D.s=1Òîãäà A àïïðîêñèìèðóåòñÿ ìàòðèöåé Ar âèäàrφ(u1 ) X ...
ψ(v1 ) ... ψ(vn )Ar =s=1 φ(un )(∗)ñ ïîýëåìåíòíîé îöåíêîé ïîãðåøíîñòè|aij − (Ar )ij | ≤ ε,1 ≤ i, j ≤ n.Ïðè ýòîì, î÷åâèäíî, Ax ≈ Ar x, à óìíîæåíèå ìàòðèöû Ar íà âåêòîð x òðåáóåò, â ñèëó(∗), âñåãî ëèøü O(nr) àðèôìåòè÷åñêèõ îïåðàöèé.Êàê âèäèì, ÷èñëî îïåðàöèé çàâèñèò îò n ëèíåéíî. Íî âàæíî ïîíèìàòü òàêæå, êàêîâõàðàêòåð çàâèñèìîñòè r îò ε. Ýòî âîïðîñ, îòíîñÿùèéñÿ ê òåîðèè ïðèáëèæåíèÿ ôóíêöèé.Åãî ïîëíîå èçó÷åíèå ìîæåò ïîòðåáîâàòü âåñüìà òîíêèõ ñðåäñòâ àíàëèçà.Îäíàêî, êàêèå-ëèáî îöåíêè (âîîáùå ãîâîðÿ, çàâûøåííûå) ìîæíî ïîëó÷àòü è ñ ïîìîùüþ î÷åíüïðîñòûõ ñðåäñòâ. Íàïðèìåð, ïóñòü÷òî ôóíêöèÿf (u, v)k=1èD = [a, b] îòðåçîê âåùåñòâåííîé ïðÿìîé. Ïðåäïîëîæèì,áåñêîíå÷íî äèôôåðåíöèðóåìà êàê ôóíêöèÿ îòÒîãäà ïðè ëþáîì ôèêñèðîâàííîìuìîæíî ðàçëîæèòüf (u, v) =f (u, v)vu.v = v0 = (a + b)/2:ïðè ëþáîì ôèêñèðîâàííîìâ ðÿä Òåéëîðà â òî÷êår−1 s X∂ f (v − v0 )s+ Er (u, v),s∂v v=v0s!s=0Er (u, v) îñòàòî÷íûé ÷ëåí.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
