Численные методы. Ионкин (2012) (v1.1) (косяки есть)

Îãëàâëåíèå1×èñëåííûå ìåòîäû â ëèíåéíîé àëãåáðå3Ÿ 1. Ââåäåíèå3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Ÿ 2. Ðàçëîæåíèå ìàòðèöû íà ìíîæèòåëè. Ñâÿçü ðàçëîæåíèÿ ñ ìåòîäîìÃàóññà. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Ÿ 3. Îáðàùåíèå ìàòðèö ìåòîäîì Ãàóññà-ÆîðäàíàŸ 4. Ìåòîä êâàäðàòíîãî êîðíÿ5. . . . . .

. . . . . . .8. . . . . . . . . . . . . . . . . . . . . . . .10Ÿ 5. Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ13Ÿ 6. Òåîðåìû î ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ . . . . . . . . . . . . .19Ÿ 7. Îöåíêà ñêîðîñòè ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ25. . . . . . . .

.Ÿ 8. Èññëåäîâàíèå ñõîäèìîñòè ïîïåðåìåííîãî òðåóãîëüíîãî èòåðàöèîííîãî ìåòîäà(ÏÒÈÌ). . . . . . . . . . . . . . . . . . . . . . . . . . . .Ÿ 9. Ìåòîäû ðåøåíèÿ çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ30. . . . . . . . . . .34Ÿ 10. Ñòåïåííîé ìåòîä . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .34Ÿ 11. Ïðèâåäåíèå ìàòðèöû ê âåðõíåé ïî÷òè òðåóãîëüíîé ôîðìå (ÂÏÒÔ)40Ÿ 12. Ïîíÿòèå î QR-àëãîðèòìå. Ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõ2çíà÷åíèé . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .44Ÿ 13. Ïðåäâàðèòåëüíîå ïðåîáðàçîâàíèå ìàòðèöû ê ÂÏÒÔ . . . . . . . . .46Èíòåðïîëèðîâàíèå è ïðèáëèæåíèå ôóíêöèé48Ÿ 1. Ïîñòàíîâêà çàäà÷è èíòåðïîëèðîâàíèÿ. . . . . . . . . . . . . . . . .48Ÿ 2. Èíòåðïîëÿöèîííàÿ ôîðìóëà Ëàãðàíæà . . . . . . . . . . . . .

. . . .49Ÿ 3. Ðàçäåëåííûå ðàçíîñòè50. . . . . . . . . . . . . . . . . . . . . . . . . .Ÿ 4. Èíòåðïîëÿöèîííàÿ ôîðìóëà Íüþòîíà. . . . . . . . . . . . . . . . .Ÿ 5. Èíòåðïîëÿöèðîâàíèå ñ êðàòíûìè óçëàìè. Ïîëèíîìû Ýðìèòà. . . .5253Ÿ 6. Èñïîëüçîâàíèå Ïîëèíîìà Ýðìèòà äëÿ îöåíêè ïîãðåøíîñòè êâàäðàòóðíîé ôîðìóëû Ñèìïñîíà. . . . . . . . . . . . . . . . . . . . . .

.Ÿ 7. Íàèëó÷øåå ñðåäíåêâàäðàòè÷íîå ïðèáëèæåíèå ôóíêöèé3. . . . . . .5659×èñëåííîå ðåøåíèå íåëèíåéíûõ óðàâíåíèé è ñèñòåì íåëèíåéíûõóðàâíåíèé64Ÿ 1. Ââåäåíèå. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Ÿ 2. Ìåòîä ïðîñòîé èòåðàöèè. . . . . . . . . . . . . . . . . . . . . . . . .Ÿ 3.

Ìåòîä Ýéòêåíà óñêîðåíèÿ ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ1. . . .646567Ÿ 4. Ìåòîä Íüþòîíà è ìåòîä ñåêóùèõ. . . . . . . . . . . . . . . . . . . .Ÿ 5. Ñõîäèìîñòü ìåòîäà Íüþòîíà. Îöåíêà ñêîðîñòè ñõîäèìîñòè4. . . . .6872Ðàçíîñòíûå ìåòîäû ðåøåíèÿ çàäà÷ ìàòåìàòè÷åñêîé ôèçèêè74Ÿ 1. Ââåäåíèå74. . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .Ÿ 2. Ðàçíîñòíûå ñõåìû äëÿ ïåðâîé êðàåâîé çàäà÷è óðàâíåíèÿ òåïëîïðîâîäíîñòè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74Ÿ 3. Ñèììåòðè÷íàÿ ðàçíîñòíàÿ ñõåìà (Ñõåìà Êðàíêà-Íèêîëüñîíà) . . .

.86Ÿ 4. Çàäà÷à Øòóðìà-Ëóèâèëëÿ . . . . . . . . . . . . . . . . . . . . . . . .87Ÿ 5. Ðàçíîñòíûå ñõåìû äëÿ óðàâíåíèÿ Ïóàññîíà. (Çàäà÷à Äèðèõëå). . .93Ÿ 6. Ðàçðåøèìîñòü ðàçíîñòíîé çàäà÷è. Ñõîäèìîñòü ðàçíîñòíîé ñõåìû . .96Ÿ 7. Îñíîâíûå ïîíÿòèÿ òåîðèè ðàçíîñòíûõ ñõåì: àïïðîêñèìàöèÿ, óñòîé÷èâîñòü, ñõîäèìîñòü5.

. . . . . . . . . . . . . . . . . . . . . . . . . .103Ìåòîäû ðåøåíèÿ îáûêíîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé(ÎÄÓ) è ñèñòåì ÎÄÓ107Ÿ 1. Ïîñòàíîâêà çàäà÷è Êîøè è ïðèìåðû ÷èñëåííûõ ìåòîäîâ ðåøåíèÿçàäà÷è Êîøè. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .Ÿ 2. Îáùàÿ ñõåìà Ðóíãå-Êóòòà. . . . . . . . . . . . . . . . . . . . . . . .Ÿ 3. Ìíîãîøàãîâûå ðàçíîñòíûå ìåòîäû107112. . . . . . . . . . . . . . . . . . .117Ÿ 4. Ïîíÿòèå óñòîé÷èâîñòè ðàçíîñòíîãî ìåòîäà . . . . . . . . . . . . . . .121Ÿ 5. Ƽñòêèå ñèñòåìû ÎÄÓ . . . . . . . . . . . .

. . . . . . . . . . . . . .126Ÿ 6. Äàëüíåéøåå îïðåäåëåíèå óñòîé÷èâîñòè è ïðèìåðû ðàçíîñòíûõ ñõåìèíòåãðèðîâàíèÿ æåñòêèõ ñèñòåì ÄÓ . . . . . . . . . . . . . . . . . .2130Ãëàâà 1×èñëåííûå ìåòîäû âëèíåéíîé àëãåáðåŸ 1. ÂâåäåíèåÐàññìîòðèì ñèñòåìó ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé:Ax = f, |A| =6 0,ãäå(1.1)A(m × m), x = (x1 , ..., xm )T , f = (f1 , ..., fm )T . ýòîì êóðñå ìû áóäåì ðàññìàòðèâàòü ïðÿìûå è èòåðàöèîííûå ìåòîäû:Ïîñ÷èòàòü îïðåäåëèòåëü ïî îïðåäåëåíèþ: ñëîæíîñòüÏî Ãàóññó:m!m33n → ∞, xn → x||xn − x|| < ε n0 (ε)Èòåðàöèîííûå:Çàäà÷à íà ñîáñòâåííûå çíà÷åíèÿ: íîðìàëüíî ðåøàåòñÿ òîëüêî ÷èñëåííîAx = λx, x 6= ~0×àñòè÷íàÿ ïðîáëåìà ñîáñòâåííûõ çíà÷åíèé íàéòè õîòÿ áû îäíî çíà÷åíèå.Ïîëíàÿ âñå çíà÷åíèÿ (QR-àëãîðèòì).A−1çàm3äåéñòâèé çà ñ÷¼ò õèòðîñòè âàëãîðèòìå.Ñâÿçü ìåòîäà Ãàóññà ñ ðàçëîæåíèåì ìàòðèöû íà ìíîæèòåëè.Ìåòîä Êðàìåðà ïëîõî ñ òî÷êè çðåíèÿ îêðóãëåíèÿ è ò.ï.3Çàäà÷à ïðèâåäåíèÿ ìàòðèöûAýëåìåíòàðíûìè ïðåîáðàçîâàíèÿìèê òðåóãîëü-íîìó âèäó.Ðàññìîòðèì 1.1:AÏðÿìîé õîä: (ìàòðèöàäèàãîíàëüíàÿ,cijñâåðõó ñïðàâà, 1 ïî äèàãîíàëè, 0âíèçó)(m3 −m)äåéñòâèé íà íàõîæäåíèå êîýôôèöèåíòîâ ìàòðèöû3m(m+1)íà ïðàâûå ÷àñòè2m(m−1)îáðàòíûé õîä2Âîçìîæåí ñëó÷àé, êîãäà ìàòðèöàAïðåäñòàâèìà â âèäåA=B×C(1.2) íå êàæäóþ ìàòðèöó ìîæíî ïðåäñòàâèòü â òàêîì âèäå.aij =mXbil clj =l=1i−1Xbil clj + bii cij +l=1mXbil cljl=i+1B íèæíÿÿ äèàãîíàëüíàÿ ìàòðèöà, C âåðõíÿÿ äèàãîíàëüíàÿ ìàòðèöà ñ åäèíèöàìè íà äèàãîíàëèaij = bii cij +i−1P⇒bil cij , bii 6= 0l=1aij −cij =aij =i−1PmPbil clj + bii cij +l=1i−1Pbil cijl=1, i≤jbii(1.3)bil clj = 0 ⇒l=i+1bij = aij −j−1Xbi,l cl,j , i ≥ j(1.4)l=1Ôîðìóëû 1.3, 1.4 ðåêóððåíòíûå.

Îíè ñâÿçûâàþòBèC.Ñîîòíîøåíèå íåëèíåéíîå, íî ïðè ðàçóìíîé îðãàíèçàöèè àëãîðèòìà íà ýòî ìîæíî çàêðûòü ãëàçà.b11 = a11a1jäàëåå ïî ôîðìóëå 1.3 ⇒ c1j =b11 , j = 2...mïî ôîðìóëå 1.4 ⇒ bi1 = ai1 , i = 2...mÐàçóìíàÿ îðãàíèçàöèÿ:4Ÿ 2. Ðàçëîæåíèå ìàòðèöû íà ìíîæèòåëè. Ñâÿçü ðàçëîæåíèÿ ñ ìåòîäîì ÃàóññàÂî ââåäåíèè ìû ïîëó÷èëè ôîðìóëó ïðèci,j =bi,i 6= 0j−1Pbi,l cl,j , i ≥ ja−i,jl=1i−1Pai,j − bi,l cl,jl=1bi,i, i≤jÐàçëîæåíèå âîçìîæíî ïðè îïðåäåëåííûõ óñëîâèÿõ. Ñôîðìóëèðóåì äîñòàòî÷íûå óñëîâèÿ ðàçëîæåíèÿ ìàòðèöû A:A = BC .Óòâåðæäåíèå:Ïóñòü âñå ãëàâíûå óãëîâûå ìèíîðû ìàòðèöû A îòëè÷íû îò íóëÿ:41 = a11 6= 0a1,1 a1,242 =6= 0a2,1 a2,2a1,1 a1,2 .

. . a1,n a2,1 a2,2 . . . a2,n 4n =  . . . . . . . . . . . .  6= 0 , i = 1, 2, . . . , nan,1 an,2 . . . an,nÒîãäà ôàêòîðèçàöèÿ ìàòðèöû A âîçìîæíà è íàõîäèòñÿ åäèíñòâåííûì îáðàçîì.Äîêàçàòåëüñòâî:Äëÿ óäîáñòâà ââåäåì40 = 1Ðàñïèøåì ìàòðèöóAiêàê ïðîèçâåäåíèå ìàòðèöBièCi : Ai = Bi Ci .Îïðåäå-ëèòåëü ïðîèçâåäåíèÿ ìàòðèö åñòü ïðîèçâåäåíèå îïðåäåëèòåëåé ìàòðèö. Òîãäà4i =| Ai |=| Bi || Ci |,ãäå| Ci |= 1.Òîãäà4i = b11 b22 · · · bi−1,i−1 bi,i ⇒ bi,i =÷òä.Âñå ýëåìåíòûbi,iîòëè÷íû îò íóëÿ.Çàìå÷àíèå:54i, i = 1, 2, .

. . , n4i−1Óñëîâèå îòëè÷èÿ îò íóëÿ âñåõ óãëîâûõ ìèíîðîâ ÿâëÿåòñÿ äîñòàòî÷íûì. Íàïðàêòèêå ýòî íå ÿâëÿåòñÿ æåñòêèì òðåáîâàíèåì. Íàïðèìåð â ôèçèêå è õèìèèïðèñóòñòâóþò ñàìîñîïðÿæåííûå îïåðàòîðû. Ìû íå ñòàâèëè ïåðåä ñîáîé çàäà÷óäîêàçûâàòü óòâåðæäåíèå ñ ìèíèìàëüíûìè òðåáîâàíèÿìè.Äëÿ ÷åãî íóæíà ôàêòîðèçàöèÿ? Îòâåò: äëÿ óäîáñòâà ðåøåíèÿ àëãåáðàè÷åñêèõóðàâíåíèé.Ax = f, | A |6= 0, A = (m, m)(1.5)Ðàññìîòðèì ñâÿçü Ìåòîäà Ãàóññà ñ ðàçëîæåíèåì ìàòðèöûA = BC , çàòåìBCx = f ⇒íà ìíîæèòåëèïîêàæåì ýôôåêòèâíîñòü ìåòîäà.BY = f(1.6)CX = Y(1.7)Ðåøåíèå ñèñòåìû 1.5 ðàñïàëîñü íà äâà.

Èç 1.6 íàõîäèìîòêóäà íàõîäèìAYè ïîäñòàâëÿåì â 1.7,XÇàäà÷à 1:Äîêàçàòü, ÷òî íàõîæäåíèå ìàòðèöBèCòðåáóåòÐåøåíèå:m3 −móìíîæåíèé è äåëåíèé.3Ïî ôîðìóëàì ôàêòîðèçàöèèbij = aij −j−1Xbil clj , i ≥ jl=1Äëÿ âû÷èñëåíèÿ êàæäîãîbijïîòðåáóåòñÿj−1îïåðàöèÿ óìíîæåíèÿ. Îòïóñòèìèíäåêñ j:iX(j − 1) =j=1i(i − 1)2.Îòïóñòèì èíäåêñ i:mXi(i − 1)i=1=2mm1X 2 1X=i −i=2 i=12 i=1m(m + 1)(2m + 1) m(m + 1) (m − 1)m(m + 1)−=1246Èìååìaij −cij =i−1Pl=1bii6bil clj, i < j.cijÄëÿ âû÷èñëåíèÿ êàæäîãîïîòðåáóåòñÿj − 1 îïåðàöèÿ óìíîæåíèÿ è 1 îïåðàöèÿäåëåíèÿ.Îòïóñòèì èíäåêñ i:j−1X(j − 1)j2j=i=1Îòïóñòèì èíäåêñ j:mmm1X1X 2 1X(j − 1)j =j −j=2 j=12 j=12 j=1=m(m + 1)(2m + 1) m(m + 1) (m − 1)m(m + 1)−=1246Ñóììèðóåì ñ ïðåäûäóùèì ðåçóëüòàòîì:2 (m−1)(m+1)m=6m3 −m3 .ßñíî, ÷òî îñíîâíàÿ ðàáîòà èäåò íà ôàêòîðèçàöèþ.

Ñîïîñòàâèì ýòî ñ ìåòîäîìÃàóññà.ÑèñòåìóAñâîäèì ê âåðõíåé òðåóãîëüíîé ìàòðèöå (ïðÿìîé õîä):1 c1,2 c1,3 0 1 c2,2A=. . . . . . . . .0 00. . . ci,j. . . c2,j . . . . . .... 11-ÿ ñâÿçü: ðàñïèøåì ñèñòåìû 1.6 è 1.7 ïî êîîðäèíàòàì1.6 : bi,1 y1 + bi,2 y2 + · · · + bi,i yi = fi , i = 1, 2, . . . , n1.7 : xi + ci,i+1 xi+1 + · · · + ci,m xm = yi , i = 1, 2, . . . , mÂûðàçèì èç 1.6 âåêòîðy:fi −yi =Èç 1.7 âûðàçèì âåêòîðbi,i 6= 0c÷èòàÿ, ÷òîi−1Pabi,l yll=1, i = 1, 2, · · · , mbi,ix:mXxi = yi −ci,l xll=i+1Ïîñ÷èòàåì êîëè÷åñòâî äåéñòâèé. ÂyiíàõîäèòñÿÈòîãî i äåéñòâèé.7i−1óìíîæåíèé è 1 äåëåíèå.Ò.ê.i = 1, 2, .