Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 59
Текст из файла (страница 59)
Åñëè ïîëó÷åíîðàçëîæåíèåA = LU ,òî, ïîñêîëüêóA−1 = U −1 L−1 ,äîñòàòî÷íî íàó÷èòüñÿ âû÷èñëÿòü îáðàòíûå êâåðõíåé è íèæíåé òðåóãîëüíûì ìàòðèöàì. Îáùåå ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé áóäåòO(n3 ).Îäíàêî, â 1965 ãîäó ïîÿâèëàñü ðàáîòà Øòðàññåíà ñ çàãîëîâêîì Ìåòîä Ãàóññà íå îïòèìàëåí, âêîòîðîé âïåðâûå áûëî ïîêàçàíî, ÷òî ñóùåñòâóþò è áîëåå áûñòðûå àëãîðèòìû. Ïóñòü èìååòñÿ àëãîðèòì≤ c nγ (íàïðèìåð, â äîïîëíèòåëüíîé ÷àñòè Ëåêöèè1 îáñóæäàåòñÿ àëãîðèòì Øòðàññåíà, äëÿ êîòîðîãî γ = log2 7 < 3). Òîãäà â ñëó÷àå ñòðîãî ðåãóëÿðíîé−1γìàòðèöû A ìîæíî ïîñòðîèòü àëãîðèòì âû÷èñëåíèÿ Añ ÷èñëîì îïåðàöèé O(n ).pÄëÿ ïðîñòîòû ïðåäïîëîæèì, ÷òî n = 2 .
Ðàçîáüåì A íà áëîêè ïîðÿäêà n/2 è ðàññìîòðèì ñëåäóþùååóìíîæåíèÿ äâóõn × n-ìàòðèöc ÷èñëîì îïåðàöèéðàâåíñòâî:I−A21 A−1110IA11A21A12A22=A110A12W,W = A22 − A21 A−111 A12 .Å. Å. ÒûðòûøíèêîâÈç íåâûðîæäåííîñòèâèäíî) èWAè285A11âûòåêàåò íåâûðîæäåííîñòü áëîêàW . Áîëåå òîãî, áëîêè A11 (÷òîA. Íåòðóäíî ïðîâåðèòü, ÷òîî÷å-(äîêàæèòå!) íàñëåäóþò ñòðîãóþ ðåãóëÿðíîñòü ìàòðèöûA110Òàêèì îáðàçîì,−1AÏîëó÷åííûå èç(∗)A12WA−1110=−1=A−1110−1−A−111 A12 W−1Wâûðàæåíèÿ äëÿ áëîêîâ ìàòðèöûÄëÿ íàøåé öåëè ôîðìóëà(∗)−1−A−111 A12 W−1W0II−A21 A−111A−1.èíîãäà íàçûâàþò.(∗)ôîðìóëàìè Ôðîáåíèóñà.nn/2. Äëÿ ðåàëèçàöèè óêàçàííîéïîðÿäêà n/2.
Îáùèå çàòðàòû íà âñåõèíòåðåñíà òåì, ÷òî ïîêàçûâàåò, êàê îáðàùåíèå ìàòðèöû ïîðÿäêàñâîäèòñÿ ê äâóì àíàëîãè÷íûì çàäà÷àì äëÿ ìàòðèöA11èWïîðÿäêàðåäóêöèè òðåáóåòñÿ âûïîëíèòü íåñêîëüêî óìíîæåíèé ìàòðèöøàãàõ ðåäóêöèè ïðîïîðöèîíàëüíû n γ2+2 n γ22+ 22 n γ23+ ...≤nγ1nγ=.2γ 1 − 1/2γ2γ − 1Âñëåä çà îòêðûòèåì Øòðàññåíà ïîÿâèëàñü ðàáîòà äðóãèõ àâòîðîâ ïîä íàçâàíèåì Ìåòîä Øòðàññåíàíå îïòèìàëåí. Íî ëèäåðñòâî íîâîãî àëãîðèòìà áûëî íå î÷åíü äîëãèì.
Ñîðåâíîâàíèå ïî ïîñòðîåíèþâñå áîëåå áûñòðûõ àëãîðèòìîâ îáðàùåíèÿ ìàòðèö è ðåøåíèÿ ñèñòåì ïðîäîëæàåòñÿ äî ñèõ ïîð, à âîïðîñîá îïòèìàëüíîì àëãîðèòìå ñ òî÷êè çðåíèÿ ÷èñëà îïåðàöèé îñòàåòñÿ îòêðûòûì.Åùå ìåíåå ÿñíûì ÿâëÿåòñÿ âîïðîñ îá àëãîðèòìå ñ ìèíèìàëüíûì ÷èñëîì ïàðàëëåëüíûõ øàãîâ (õîòÿáû â ìîäåëè áåñêîíå÷íîãî ïàðàëëåëèçìà). Äîâîëüíî äàâíî áûë ïðèäóìàí àëãîðèòì, â êîòîðîì ÷èñëîïàðàëëåëüíûõ øàãîâ â ñëó÷àå ìàòðèöû îáùåãî âèäà åñòüO(log22 n).
Íèêòî íå çíàåò, ìîæíî ëè ïîñòðîèòüáîëåå áûñòðûé ïàðàëëåëüíûé àëãîðèòì. Ëþáîïûòíî, ÷òî ïðåäúÿâëåííûé àëãîðèòì íå èìååò íè÷åãîîáùåãî íè ñ ìåòîäîì Ãàóññà, íè ñ ìåòîäîì Øòðàññåíà. Êðîìå òîãî, äàæå äëÿ òðåóãîëüíîé ìàòðèöû íåèçâåñòíî àëãîðèòìà ñ ìåíüøèì ÷èñëîì ïàðàëëåëüíûõ øàãîâ (ïî ïîðÿäêó çàâèñèìîñòè îòÇàäà÷à.çàO(nlog2 7 )Äîêàæèòå, ÷òî îïðåäåëèòåëü ñòðîãî ðåãóëÿðíîé ìàòðèöû ïîðÿäêààðèôìåòè÷åñêèõ îïåðàöèé.nn).ìîæíî âû÷èñëèòü286Ëåêöèÿ 46Äîïîëíåíèå ê ëåêöèè 1347.1Àôôèííàÿ íåçàâèñèìîñòüÒî÷êè v0 , v1 , . .
. , vk â n-ìåðíîì ïðîñòðàíñòâå íàçûâàþòñÿ àôôèííî íåçàâèñèìûìè, åñëèâåêòîðû v1 − v0 , . . . , vk − v0 ëèíåéíî íåçàâèñèìû. Ðàâíîñèëüíîå ñèììåòðè÷íîå îïðåäåëåíèå: âåêòîðû v0 , . . . , vk àôôèííî íåçàâèñèìû, åñëè èç ðàâåíñòâ α0 v0 + . . . + αk vk = 0,α0 +. . .+αk = 0 âûòåêàåò, ÷òî α0 = . . . = αk = 0.  ñàìîì äåëå, èç ýòèõ ðàâåíñòâ íàõîäèìα1 (v1 − v0 ) + . . .
+ αk (vk − v0 ) = 0, ïðè ýòîì íåîáõîäèìîñòü óñëîâèé α1 = . . . = αk = 0ðàâíîñèëüíà ëèíåéíîé íåçàâèñèìîñòè âåêòîðîâ v1 − v0 , . . . , vk − v0 . Î òî÷êàõ àôôèííîíåçàâèñèìîé ñèñòåìû ÷àñòî ãîâîðÿò òàêæå, ÷òî îíè íàõîäÿòñÿ â îáùåì ïîëîæåíèè.Çàäà÷à.Äîêàæèòå, ÷òî â ëþáîé àôôèííî íåçàâèñèìîé ñèñòåìå ñ ÷èñëîì âåêòîðîââûáðàòü ëèíåéíî íåçàâèñèìóþ ïîäñèñòåìó ñ ÷èñëîì âåêòîðîâk+1ìîæíîk.Âûïóêëàÿ îáîëî÷êà àôôèííî íåçàâèñèìûõ âåêòîðîâ v0 , v1 , . . . , vk íàçûâàåòñÿ ñèìïëåêñîì ðàçìåðíîñòè k .
Òî÷êè v0 , . . . , vk íàçûâàþòñÿ âåðøèíàìè ñèìïëåêñà. Ñîãëàñíîîïðåäåëåíèþ, ðàçìåðíîñòü ñèìïëåêñà íå çàâèñèò îò ðàçìåðíîñòè ïðîñòðàíñòâà V . Ðàçìåðíîñòüþ ïðîèçâîëüíîãî âûïóêëîãî ìíîæåñòâà íàçûâàþò ìàêñèìàëüíóþ ðàçìåðíîñòüïðèíàäëåæàùèõ åìó ñèìïëåêñîâ.Ñðåäè òî÷åê â âûïóêëîì ìíîæåñòâå M îñîáûé èíòåðåñ ïðåäñòàâëÿþò åãî óãëîâûåòî÷êè òàê íàçûâàþòñÿ òî÷êè èç M , íå ÿâëÿþùèåñÿ âíóòðåííåé òî÷êîé íè äëÿ îäíîãîîòðåçêà, ëåæàùåãî â M .
Íàïðèìåð, êðóã íà ïëîñêîñòè ÿâëÿåòñÿ âûïóêëûì ìíîæåñòâîì,à åãî óãëîâûå òî÷êè ýòî òî÷êè ãðàíè÷íîé îêðóæíîñòè.Óòâåðæäåíèå. Óãëîâûìè òî÷êàìè ñèìïëåêñà ÿâëÿþòñÿ åãî âåðøèíû è òîëüêî îíè.Äîêàçàòåëüñòâî. Ïóñòü v0 , . . . , vk âåðøèíû çàäàííîãî ñèìïëåêñà M . Äîêàæåì, ÷òîvj ÿâëÿåòñÿ óãëîâîé òî÷êîé. Îò ïðîòèâíîãî: ïóñòü vj = tx + (1 − t)y ïðè 0 < t < 1 èx 6= y :kkkkXXXXx=αi vi , y =βi vi ,αi =βi = 1, αi , βi ≥ 0.i=0i=0i=0i=0ÎòñþäàX(tαi + (1 − t)βi )(vi − vj ) = 0 ⇒ tαi + (1 − t)βi = 0 ⇒ αi = βi = 0.1 ≤ i ≤ n, i 6= jÈòàê, x = y , à ìû èñõîäèëè èç òîãî, ÷òî x 6= y .Ïóñòü òåïåðü x ∈ M ïðîèçâîëüíàÿ òî÷êà ñèìïëåêñà, îòëè÷íàÿ îò åãî âåðøèí. ÝòîkPçíà÷èò, ÷òî x =ti vi è 0 < tj < 1 õîòÿ áû äëÿ îäíîãî j . Íå îãðàíè÷èâàÿ îáùíîñòè,i=0ïðåäïîëîæèì, ÷òî 0 < t0 < 1.
Òîãäà x = t0 v0 +(1−t0 )w, ãäå w =kPi=1287(ti /(1−t0 ))vi ∈ M. 2288Ëåêöèÿ 47 äåéñòâèòåëüíîñòè äëÿ øèðîêîãî êëàññà âûïóêëûõ ìíîæåñòâ èìååò ìåñòî ýëåãàíòíûé è ãëóáîêèé ôàêò, ê äîêàçàòåëüñòâó êîòîðîãî ìû ïîêà íå ãîòîâû: ëþáàÿ òî÷êà â íèõÿâëÿåòñÿ âûïóêëîé êîìáèíàöèåé êîíå÷íîãî ÷èñëà óãëîâûõ òî÷åê. 147.2Ëèíåéíûå íåðàâåíñòâà è ìèíèìèçàöèÿÁîëüøîå ÷èñëî ïðèêëàäíûõ çàäà÷ (ñîñòàâëåíèå ðàñïèñàíèé, óïðàâëåíèå ïðîèçâîäñòâîì,îïòèìèçàöèÿ äèåòû, ïîðòôåëÿ èíâåñòèöèé è ò.
ï.) ñâÿçàíî ñ ìèíèìèçàöèåé (ìàêñèìèçàöèåé) âåùåñòâåííîé ôóíêöèè f (x) îò x = [x1 , . . . , xn ]> ∈ Rn âèäàf (x) = c> x = c1 x1 + . . . + cn xn ,ci ∈ R,c = [c1 , . . . , cn ]> 6= 0,íà ìíîæåñòâå òî÷åê M , çàäàííîì ëèíåéíûìè íåðàâåíñòâàìèa11 x1 + . . . + a1n xnam1 x1 + . . . + amn xn≤ b1 ,...≤ bm .ßñíî, ÷òî M åñòü ïåðåñå÷åíèå êîíå÷íîãî ÷èñëà ïîëóïðîñòðàíñòâ. Ïðåäïîëîæèì äîïîëíèòåëüíî, ÷òî êîîðäèíàòû òî÷åê èç M îãðàíè÷åíû.  òàêèõ ñëó÷àÿõ M íàçûâàþòâûïóêëûì ìíîãîãðàííèêîì. Èíòóèòèâíî ïîíÿòíî, ÷òî ìîæíî ãîâîðèòü î ãðàíÿõ äåòàëè âàæíû, íî ýòî ïðåäìåò îòäåëüíîãî êóðñà.Óðàâíåíèå f (x) = b ïðè ëþáîì ôèêñèðîâàííîì b îïðåäåëÿåò ãèïåðïëîñêîñòü. Î÷åâèäíî, f (x + tc) > f (x) ïðè t > 0. Áîëåå òîãî, f (x + td) > f (x) ïðè t > 0, åñëè c> d > 0(äîêàæèòå!). Îòñþäà ìîæíî âûâåñòè, ÷òî ìèíèìóì f (x) äîëæåí äîñòèãàòüñÿ â óãëîâûõ òî÷êàõ ìíîæåñòâà M (âîçìîæíî, íå òîëüêî â íèõ).
Ïðîñòàÿ ãåîìåòðè÷åñêàÿ èäåÿïîèñêà ìèíèìóìà çàêëþ÷àåòñÿ â ïåðåáîðå âñåõ óãëîâûõ òî÷åê. Êîíå÷íî, åãî ìîæíî îðãàíèçîâàòü òàê, ÷òîáû ñëåäóþùàÿ óãëîâàÿ òî÷êà ëåæàëà â òîé æå ãðàíè è óìåíüøàëàçíà÷åíèå f (x). Ôîðìàëèçàöèÿ äàííîé èäåè ïðèâåëà â ñâîå âðåìÿ ê òàê íàçûâàåìîìóñèìïëåêñ-ìåòîäó. Äî ñèõ ïîð ýòî îäèí èç îñíîâíûõ ìåòîäîâ ðåøåíèÿ çàäà÷ ñ ëèíåéíûìè îãðàíè÷åíèÿìè è ëèíåéíîé öåëåâîé ôóíêöèåé f (x) òàêèå çàäà÷è îòíîñÿòñÿ êçàäà÷àì ëèíåéíîãî ïðîãðàììèðîâàíèÿ. Äðóãîé ýôôåêòèâíûé êëàññ ìåòîäîâ èñïîëüçóåò âíóòðåííèå òî÷êè ìíîæåñòâà M è ïîëó÷èë îáùåå íàçâàíèå ìåòîäîâ âíóòðåííåéòî÷êè.
Êîíå÷íî, âåñü ýòîò êðóã âîïðîñîâ ñîñòàâëÿåò îòäåëüíóþ è îáøèðíóþ îáëàñòü ñðàçâèòûì ìàòåìàòè÷åñêèì àïïàðàòîì è ìíîãî÷èñëåííûìè ïðèëîæåíèÿìè.1 Äîñòàòî÷íî ïîòðåáîâàòü, ÷òîáû âûïóêëîå ìíîæåñòâî áûëî îãðàíè÷åííûì è çàìêíóòûì ñòðîãèåîïðåäåëåíèÿ áóäóò â ëåêöèÿõ âòîðîãî ñåìåñòðà.Äîïîëíåíèå ê ëåêöèè 1448.1Êâàäðàòíûå óðàâíåíèÿÐàññìîòðèì ïðîèçâîëüíîå êâàäðàòíîå óðàâíåíèå z 2 + az + b = 0 ñ êîìïëåêñíûìè êîýôôèöèåíòàìè a, b. Ïîñëå âûïîëíåíèÿ òðàäèöèîííûõ ïðåîáðàçîâàíèé a 2 a 2 aa 2a222+ b−= z++ b−z + az + b = z + 2 z +22224ïîëó÷àåì ðàâíîñèëüíîå óðàâíåíèåz +a 2= D,2D ≡a2− b.4Åñëè D = 0, òî åäèíñòâåííîå ðåøåíèå èìååò âèä z = a/2.  ýòîì è òîëüêî â ýòîìñëó÷àå êâàäðàòíûé òðåõ÷ëåí z 2 + az + b ÿâëÿåòñÿ êâàäðàòîì ëèíåéíîãî äâó÷ëåíà:a 2.z 2 + az + b = z +2Åñëè D = |D|(cos φ+i sin φ) 6= 0, òî â îáùåì ñëó÷àå ïîëó÷àåì ïàðó êîìïëåêñíûõ ðåøåíèéφφa p.z± = − ± |D| cos + i sin22248.2Êóáè÷åñêèå óðàâíåíèÿÏðîèçâîëüíîå êóáè÷åñêîå óðàâíåíèåz 3 + a2 z 2 + a1 z + a0 = 0ñ ïîìîùüþ çàìåíû z = x − a2 /3 ïðèâîäèòñÿ ê âèäóx3 + px + q = 0.Áóäåì èñêàòü x â âèäå x = u + v .
Òîãäàu3 + 3u2 + 3uv 2 + v 3 + p(u + v) + q = (u3 + v 3 + q) + (3uv + p)(u + v) = 0.Î÷åâèäíî, x = u + v áóäåò ðåøåíèåì óðàâíåíèÿ (∗), åñëè 3 3u + v 3 = −q,u + v3 =−q,⇒uv= −p/3.u3 v 3 = −p3 /27.289(∗)290Ëåêöèÿ 48Äâà êîìïëåêñíûõ ÷èñëà u3 è v 3 ñ çàäàííîé ñóììîé è çàäàííûì ïðîèçâåäåíèåì íàõîäÿòñÿêàê êîðíè êâàäðàòíîãî óðàâíåíèÿpw1 = u3 = −q/2 + q 2 /4 + p3 /27,p32=0⇒w + qw −p27w2 = v 3 = −q/2 − q 2 /4 + p3 /27. ðåçóëüòàòå ïîëó÷àåòñÿ ñëåäóþùàÿ ôîðìóëà Êàðäàíî: 1qqpp3323x = −q/2 + q /4 + p /27 +−q/2 − q 2 /4 + p3 /27.Ïðè ïðèìåíåíèè ôîðìóëû Êàðäàíî ñëåäóåò èìåòü â âèäó, ÷òî äëÿ êàæäîãî èç êóáè÷åñêèõ êîðíåé ñóùåñòâóþò òðè êîìïëåêñíûõ çíà÷åíèÿ, êîòîðûå íåëüçÿ âûáèðàòü íåçàâèñèìî: èõ ïðîèçâåäåíèå uv äîëæíî áûòü ðàâíî −p/3.
Äàæå â ñëó÷àå âåùåñòâåííûõêîðíåé ôîðìóëà Êàðäàíî, êàê ïðàâèëî, äàåò èõ ïðåäñòàâëåíèå ñ èñïîëüçîâàíèåì êîìïëåêñíûõ çíà÷åíèé êóáè÷åñêèõ êîðíåé.48.3Óðàâíåíèÿ ÷åòâåðòîé ñòåïåíèÎáùåå óðàâíåíèå ÷åòâåðòîé ñòåïåíèz 4 + a3 z 3 + a2 z 2 + a1 z + a0 = 0ñ ïîìîùüþ çàìåíû z = x − a3 /4 ïðèâîäèòñÿ ê âèäóx4 + px2 + qx + r = 0.(∗)Äàííîå óðàâíåíèå ìîæåò áûòü ñâåäåíî ê êóáè÷åñêîìó. Íàèáîëåå ïðîñòîé ñïîñîá äëÿýòîãî áûë ïðåäëîæåí èòàëüÿíñêèì ìàòåìàòèêîì Ôåððàðè. Èäåÿ ñîñòîèò â òîì, ÷òîáûïðåäñòàâèòü ëåâóþ ÷àñòü óðàâíåíèÿ (∗) êàê ðàçíîñòü äâóõ êâàäðàòîâ:x4 + px2 + qx + r = (x2 + y/2)2 − ((y − p)x2 − qx + (y 2 /4 − r)).Êâàäðàòíûé òðåõ÷ëåí ax2 + bx + c ÿâëÿåòñÿ êâàäðàòîì äâó÷ëåíà αx + β â òîì è òîëüêîòîì ñëó÷àå, êîãäà åãî äèñêðèìèíàíò ðàâåí íóëþ. Ïîýòîìó ïîòðåáóåì, ÷òîáû y áûëðåøåíèåì êóáè÷åñêîãî óðàâíåíèÿq 2 − 4(y − p)(y 2 /4 − r) = 0.Òîãäà äëÿ íåêîòîðûõ α, βx4 + px2 + qx + r = (x2 + y/2)2 − (αx + β)2 = (x2 + y/2 + αx + β)(x2 + y/2 − αx − β).Òàêèì îáðàçîì, ïîëó÷åíèå ðåøåíèé äëÿ (∗) ñâîäèòñÿ ê ðåøåíèþ îäíîãî êóáè÷åñêîãî èíåñêîëüêèõ êâàäðàòíûõ óðàâíåíèé. íà÷àëå 19-ãî âåêà Ðóôôèíè è Àáåëü íåçàâèñèìî äðóã îò äðóãà äîêàçàëè, ÷òîäëÿ îáùåãî àëãåáðàè÷åñêîãî óðàâíåíèÿ n-é ñòåïåíè ïðè n ≥ 5 ôîðìóëû, âûðàæàþùåéêîðíè ÷åðåç ðàäèêàëû, íå ñóùåñòâóåò.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
