В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465)
Текст из файла
Â.Á. Àíäðååâ×ÈÑËÅÍÍÛÅ ÌÅÒÎÄÛ×àñòü I2Ãëàâà IÂû÷èñëèòåëüíûå ìåòîäû ëèíåéíîéàëãåáðû35Ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ â ëèíåéíîé àëãåáðå èìåþòñÿ, åñëè ïîíèìàòü èõäîñòàòî÷íî øèðîêî, äâå îñíîâíûå çàäà÷è:1◦ ðåøåíèå ñèñòåì ëèíåéíûõ óðàâíåíèé,2◦ âû÷èñëåíèå ñîáñòâåííûõ çíà÷åíèé è ñîáñòâåííûõ âåêòîðîâ ìàòðèöû.Îñíîâíîå âíèìàíèå â ëåêöèÿõ áóäåò óäåëåíî ðåøåíèþ ïåðâîé çàäà÷è, äà è òîïðè âåñüìà îãðàíè÷èòåëüíûõ ïðåäïîëîæåíèÿõ. Âòîðàÿ çàäà÷à áîëåå òðóäíàÿ ååìû êîñíåìñÿ ìåíåå ïîäðîáíî. ñèëó òåîðåìû Êðîíåêåðà - Êàïåëëè ñèñòåìà ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèéAx = bðàçðåøèìà òîãäà è òîëüêî òîãäà, êîãäà ðàíã ìàòðèöû A ðàâåí ðàíãó ðàñøèðåííîéìàòðèöû [Ab].
Ýòî çàâåäîìî òàê, åñëè ìàòðèöà A êâàäðàòíàÿ è íåâûðîæäåííàÿ, ò.å.det A 6= 0.  ýòîì ñëó÷àå ñèñòåìà íå òîëüêî ðàçðåøèìà ïðè ëþáûõ b, íî è èìååòåäèíñòâåííîå ðåøåíèå. (Ðàçðåøèìà îäíîçíà÷íî).Èìåííî ýòîò ñëó÷àé ìû è áóäåì èçó÷àòü.Ìåòîäû ðåøåíèÿ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé äåëÿòñÿ íà äâå ãðóïïû. Ê ïåðâîé ãðóïïå ïðèíàäëåæàò òàê íàçûâàåìûå ïðÿìûå ìåòîäû àëãîðèòìû,ïîçâîëÿþùèå ïîëó÷èòü ðåøåíèå çà êîíå÷íîå ÷èñëî àðèôìåòè÷åñêèõ äåéñòâèé. Ñþäàîòíîñÿòñÿ èçâåñòíîå ïðàâèëî Êðàìåðà íàõîæäåíèÿ ðåøåíèÿ ïðè ïîìîùè îïðåäåëèòåëåé, ìåòîä èñêëþ÷åíèÿ Ãàóññà, ìåòîä ïðîãîíêè ìåòîä ðåøåíèÿ ñèñòåì ñ òðåõäèàãîíàëüíûìè ìàòðèöàìè. Ñóùåñòâóþò è äðóãèå ìåòîäû, èç êîòîðûõ îòìåòèì ìåòîäÕîëåöêîãî (ìåòîä êâàäðàòíûõ êîðíåé), ïðèìåíÿåìûé ê ñèñòåìàì ñ ñèììåòðè÷íûìèïîëîæèòåëüíî îïðåäåëåííûìè ìàòðèöàìè, ìåòîä âðàùåíèé è ìåòîä îòðàæåíèé.Âòîðóþ ãðóïïó ñîñòàâëÿþò ïðèáëèæåííûå ìåòîäû, â ÷àñòíîñòè, èòåðàöèîííûå. èòåðàöèîííûõ ìåòîäàõ ðåøåíèå ñèñòåìû ïîëó÷àåòñÿ êàê ïðåäåë ïðè ñòðåìëåíèè÷èñëà èòåðàöèé n ê áåñêîíå÷íîñòè.
Ïðè êîíå÷íûõ n, êàê ïðàâèëî, ïîëó÷àþòñÿ ëèøüïðèáëèæåííûå ðåøåíèÿ.Ïðÿìûå è èòåðàöèîííûå ìåòîäû èìåþò ñâîþ îáëàñòü ïðèìåíåíèÿ: åñëè ðàçìåðíîñòü ñèñòåìû íå ñëèøêîì âåëèêà, òî ÷àñòî ïðåäïî÷òèòåëüíåå èñïîëüçîâàòü ïðÿìûåìåòîäû. Èòåðàöèîííûå ìåòîäû âûãîäíû äëÿ ñèñòåì áîëüøîãî ïîðÿäêà.
Îñîáåííî âñëó÷àå ìàòðèö ñïåöèàëüíîãî âèäà. íàñòîÿùåì êóðñå îñíîâíîå âíèìàíèå áóäåò óäåëåíî ïðÿìûì ìåòîäàì, à èòåðàöèîííûõ ìåòîäîâ êîñíåìñÿ ëèøü êðàòêî. Áîëåå ïîäðîáíî èòåðàöèîííûå ìåòîäû áóäóòèçëîæåíû âî âòîðîé ÷àñòè êóðñà "×èñëåííûå ìåòîäû", êîòîðàÿ ÷èòàåòñÿ íà ÷åòâåðòîìêóðñå.6 1Ìåòîä èñêëþ÷åíèÿ Ãàóññà èòðåóãîëüíîå (LU ) ðàçëîæåíèåìàòðèöû1.1 Ìåòîä èñêëþ÷åíèÿ ÃàóññàÑèñòåìà Ax = b â ðàçâåðíóòîé ôîðìå èìååò âèänXaij xj = bi ,(1.1)i = 1, . . . , n.j=1Êàê èçâåñòíî, ìåòîä Ãàóññà èëè ìåòîä ïîñëåäîâàòåëüíîãî èñêëþ÷åíèÿ íåèçâåñòíûõñîñòîèò â òîì, ÷òî íåèçâåñòíûå xj , j = 1, . .
. , n − 1 ïîñëåäîâàòåëüíî èñêëþ÷àþòñÿ èçñîîòâåòñòâóþùèõ óðàâíåíèé ñèñòåìû (1.1) , â ðåçóëüòàòå ÷åãî îíà ïðåîáðàçóåòñÿ êýêâèâàëåíòíîé ñèñòåìå ñ òðåóãîëüíîé ìàòðèöåé(0)(0)(0)+ ...+ a1n xn(1)(1)+ ...+ a2n xna11 x1 + a12 x2 + a13 x3a22 x2 + a23 x3(0)= b1 ,(0)(1)= b2 ,(1)..............................................................(i−1)aiixi + . . .(i−1)+ ainxn(i−1)= bi,(1.2)..............................................................(n−1)ann(k)(n−1)xn = b n(k),êîýôôèöèåíòû aij êîòîðîé è êîìïîíåíòû åå ïðàâîé ÷àñòè bi âû÷èñëÿþòñÿ ïî ôîðìóëàìi, j = k + 1, .
. . , n;(k)(k−1)(k−1)aij = aij− lik akj ,(1.3)k = 1, . . . , n − 1;78 1. ÌÅÒÎÄ ÃÀÓÑÑÀ È ÒÐÅÓÃÎËÜÍÎÅ ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛ(k)bi(k−1)= bi(k−1)− lik bki, j = k + 1, . . . , n;k = 1, . . . , n − 1;,à(k−1)lik = aik(0)(k−1)/akk(1.4)i = k + 1, . . . , n;k = 1, . . . , n − 1;,(1.5)(0)ïðè÷åì aij = aij , bi = bi .Âû÷èñëåíèÿ ïî ôîðìóëàì (1.3)-(1.5)íàçûâàþòñÿ ïðÿìûì õîäîì ìåòîäà Ãàóññà.Ïîñëå ýòîãî íåèçâåñòíûå xk ïîñëåäîâàòåëüíî, íà÷èíàÿ ñ xn , íàõîäÿòñÿ èç (1.2) ïîôîðìóëàìnhi.X(i−1)(i−1)(i−1)xi = b i−aij xjaii ,i = n, .
. . , 1.(1.6)j=i+1Âû÷èñëåíèÿ ïî ýòèì ôîðìóëàì íàçûâàþò îáðàòíûì õîäîì ìåòîäà Ãàóññà.Çàìå÷àíèå 1.1.  ôîðìóëàõ (1.2) ïðè ïðåáðàçîâàíèÿõ ñèñòåìû (1.1) ïåðâîå óðàâíå-íèå îñòàëîñü áåç èçìåíåíèÿ. Ñ ðàâíûì óñïåõîì ìîæåò áûòü èñïîëüçîâàí è äðóãîéâàðèàíò èñêëþ÷åíèÿ, êîãäà ïåðâîå óðàâíåíèå (1.1) äåëèòñÿ íà a11 , à âìåñòî (1.2)ïîëó÷àåòñÿ ñèñòåìà ñ åäèíè÷íûìè êîýôôèöèåíòàìè ïðè xj â j -îì óðàâíåíèè.Çàìå÷àíèå 1.2. Âû÷èñëåíèÿ ïî ôîðìóëàì (1.5), (1.6) , à, ñëåäîâàòåëüíî, è ïî ôîðìóëàì (1.3), (1.4) âîçìîæíû ëèøü òîãäà, êîãäà âñå ÷èñëà(i−1)aii6= 0,(1.7)i = 1, .
. . , n.Íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ âûïîëíåíèÿ (1.7) óñòàíàâëèâàþòñÿ â äîêàçûâàåìîé ÷óòü ïîçæå òåîðåìå 1.21.2LU ðàçëîæåíèå ìàòðèöû.Ïîêàæåì, ÷òî ìåòîä Ãàóññà ýêâèâàëåíòåí ðàçëîæåíèþ ìàòðèöû A ñèñòåìû (1.1) âïðîèçâåäåíèå íèæíåé L è âåðõíåé U òðåóãîëüíûõ ìàòðèö ñ ïîñëåäóþùèì ðåøåíèåìâñïîìîãàòåëüíûõ ñèñòåì ñ ýòèìè ìàòðèöàìè.
 ñàìîì äåëå, èç (1.4) íàõîäèì, ÷òî(k−1)bi(k−2)= bi(k−2)− li k−1 bk−1 .Ïîäñòàâëÿÿ ýòî ñîîòíîøåíèå â (1.4), ïîëó÷èì(k)bi(k−2)= bi(k−2)(k−1)− li k−1 bk−1 − lik bk(k−2).(k−3), à çàòåì äëÿ biÒî÷íî òàê æå ïîäñòàâëÿÿ ñþäà âûðàæåíèÿ äëÿ bièìåòü(0)(1)(k−1)(0)(k).bi = bi − li1 b1 − li2 b2 − · · · − lik bkè ò.ä., áóäåì1.2. LU ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛ.9(0)(j)Ïîëàãàÿ çäåñü k = i − 1 è âûðàæàÿ bibi =i−1X= bi ÷åðåç bi , ïîëó÷èì(j−1)lij bj(i−1)+ bi.(1.8)j=1Îáîçíà÷èì ñòîëáåö ïðàâîé ÷àñòè ñèñòåìû (1.2) ÷åðåç y = [y1 . . . yn ]T , ïîëàãàÿ(i−1)yi = bi(1.9). ýòèõ îáîçíà÷åíèÿõ (1.8) ïåðåïèøåòñÿ òàêbi =i−1Xlij yj + yi ,i = 1, . .
. , n.(1.10)j=1Îáîçíà÷èì ÷åðåç L íèæíþþ òðåóãîëüíóþ ìàòðèöó ñ êîýôôèöèåíòàìè lij , âû÷èñëÿåìûì ïî ôîðìóëàì (1.5), è åäèíè÷íîé ãëàâíîé äèàãîíàëüþ1 0 0 ... 0 l21 1 0 . . . 0L=(1.11) l31 l32 1 . . . 0 .. . . . . . . . . . . . . . . . . . .ln1 ln2 ln3 .
. . 1Òîãäà (1.10) ìîæíî çàïèñàòü â ìàòðè÷íîì âèäå(1.12)b = Ly.Åñëè âåðõíþþ òðåóãîëüíóþ ìàòðèöó ñèñòåìû (1.2) îáîçíà÷èòü ÷åðåç U è ïåðåïèñàòü(1.2) â ìàòðè÷íîì âèäå, òî áóäåì èìåòü(1.13)U x = y.Äåéñòâóÿ òåïåðü íà ëåâóþ è ïðàâóþ ÷àñòü (1.13) íåâûðîæäåííîé ìàòðèöåé L è ïðèíèìàÿ âî âíèìàíèå (1.12), ïîëó÷èìLU x = Ly = b⇒A = LU.(1.14)Èòàê, ìû ïîêàçàëè, ÷òî ðåàëèçàöèÿ âû÷èñëåíèé ïî ôîðìóëàì (1.3) è (1.5) ïðÿìîãîõîäà ìåòîäà Ãàóññà ýêâèâàëåíòíà ðàçëîæåíèþ ìàòðèöû A ñèñòåìû (1.1) â ïðîèçâåäåíèå íèæíåé òðåóãîëüíîé ìàòðèöû ñ åäèíè÷íîé ãëàâíîé äèàãîíàëüþ L è âåðõíåéòðåóãîëüíîé ìàòðèöû U . Ïðè ýòîì ýëåìåíòû ìàòðèöû L âû÷èñëÿþòñÿ ïî ôîðìóëàì(1.5), à ýëåìåíòû ìàòðèöû U ñóòü(k−1)ukj = akj(1.15)10 1.
ÌÅÒÎÄ ÃÀÓÑÑÀ È ÒÐÅÓÃÎËÜÍÎÅ ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛè âû÷èñëÿþòñÿ ïî ôîðìóëàì (1.3).Ïîñëå ðàçëîæåíèÿ ìàòðèöû A â ïðîèçâåäåíèå äâóõ òðåóãîëüíûõ äëÿ îòûñêàíèÿðåøåíèÿ ñèñòåìû (1.1) íóæíî ðåøèòü äâå ñèñòåìû ñ òðåóãîëüíûìè ìàòðèöàìè ñèñòåìû (1.12) è (1.13). Ðåøåíèå ñèñòåìû (1.12) çàìåíÿåò ïðåîáðàçîâàíèå âåêòîðàïðàâîé ÷àñòè ñèñòåìû (1.1) ïî ôîðìóëàì (1.4) ïðÿìîãî õîäà ìåòîäà Ãàóññà.
Ðåøåíèåæå x ñèñòåìû (1.13) ñ ó÷åòîì îáîçíà÷åíèé (1.9) è (1.15) îïðåäåëÿåòñÿ ôîðìóëàìè (1.6)îáðàòíîãî õîäà ìåòîäà Ãàóññà.Çàìå÷àíèå 1.3. Ñîîòíîøåíèÿ (1.3) ñîäåðæàò ôîðìóëû äëÿ ukj (1.15) è ïðîìåæóòî÷íûå çíà÷åíèÿ, êîòîðûå òîæå íóæíî çàïîìèíàòü è õðàíèòü. Ìû ñåé÷àñ ïðåîáðàçóåìýòè ôîðìóëû ê òàêîìó âèäó, ïðè êîòîðîì õðàíåíèå ïðîìåæóòî÷íûõ çíà÷åíèé íåòðåáóåòñÿ.Ïóñòü ìàòðèöà L èìååò âèä (1.11), ò.å. åå ýëåìåíòûlik = 0 ïðè k > i,à(1.16)u11 u12 u13 .
. . u1nu22 u23 . . . u2n u33 . . . u3n U =,. . . . . . . . . . . . . . . . . . . . . . . unnò.å.ukj = 0 ïðè k > j.(1.17)Ïîñêîëüêó LU = A, òî ïî ïðàâèëó óìíîæåíèÿ ìàòðèö íàõîäèì, ÷òîaij =nX(1.18)lik ukj .k=1Ïðåîáðàçóåì ýòó ôîðìóëó äâóìÿ ñïîñîáàìè. Â ñèëó (1.11), (1.16)nXlik ukj =k=1i−1Xlik ukj +lii=1 uij+k=1=i−1XnX0kl ik ukj =k=i+1lik ukj + uij ,k=1à â ñèëó (1.17)nXlik ukj =k=1j−1Xlik ukj + lij ujj +k=1k=j+1j−1=Xk=1nXlik ukj + lij ujj .0klik ukj =1.2.
LU ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛ.11Îòñþäà è èç (1.18) èìååìi−1hiXuij = aij −lik ukji = 1, . . . , n;j = i, . . . , n;k=1j−1iX1 hlij =aij −lik ukjj = 1, . . . , n;ujjk=1(1.19)i = j + 1, . . . , n.(j−1)Î÷åâèäíî, ÷òî ðåàëèçàöèÿ ôîðìóë (1.19) âîçìîæíà òîëüêî òîãäà, êîãäà âñå ujj = ajjâ ñèëó (1.15) îòëè÷íû îò íóëÿ (ñð. ñ (1.7)).Çàìå÷àíèå 1.4. Ôîðìóëû (1.19) óñòðîåíû òàê, ÷òî íåëüçÿ ñíà÷àëà âû÷èñëèòü âñåuij , à çàòåì âñå lij èëè íàîáîðîò. Ìîæíî ïðåäëîæèòü ñëåäóþùèé ïîðÿäîê âû÷èñëåíèéïî ôîðìóëàì (1.19):u1j = a1j ,j = 1, 2, .
. . , n;li1 = ai1 /u11 ,i = 2, 3, . . . , n;u2j = a2j − l21 u1j ,j = 2, 3, . . . , n;li2 = (ai2 − li1 u12 )/u22 ,i = 3, 4, . . . , n;è ò.ä., ò.å. ÷åðåäîâàòü âû÷èñëåíèå ñòðîê ìàòðèöû U è ñòîëáöîâ ìàòðèöû L.Ïîñëå ïîñòðîåíèÿ ìàòðèö L è U ðåøåíèå ñèñòåì (1.12) è (1.13) ñ òðåóãîëüíûìèìàòðèöàìè íàõîäÿòñÿ ïî ôîðìóëàìyi = bi −i−1Xlik yk ,i = 1, 2, . . . , n,(1.20)k=1(âû÷èñëåíèÿ âåäóòñÿ ñâåðõó âíèç).xk =niX1 hyk −ukj xj ,ukkj=k+1k = n, n − 1, . .
. , 1(1.21)(âû÷èñëåíèÿ âåäóòñÿ ñíèçó ââåðõ).Îäíîé èç âàæíåéøèõ õàðàêòåðèñòèê ëþáîãî ÷èñëåííîãî ìåòîäà ÿâëÿåòñÿ åãî òðóäîåìêîñòü. Ïîä òðóäîåìêîñòüþ ìåòîäà, ïðåäíàçíà÷åííîãî äëÿ ðåøåíèÿ ñèñòåìû (1.1),îáû÷íî ïîíèìàþò ÷èñëî àðèôìåòè÷åñêèõ äåéñòâèé, íåîáõîäèìûõ äëÿ íàõîæäåíèÿèñêîìîãî ðåøåíèÿ. ×àñòî â òðóäîåìêîñòü ìåòîäà âêëþ÷àþò ëèøü äåéñòâèÿ óìíîæåíèÿè äåëåíèÿ, êàê íàèáîëåå òðóäîåìêèå îïåðàöèè ñ òî÷êè çðåíèÿ ðàáîòû êîìïüþòåðà.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
