Egyszerű iterációs módszer lineáris egyenletrendszerek megoldására (slough). Lineáris algebrai egyenletrendszerek numerikus megoldása

Az iteratív módszerek előnye, hogy alkalmazhatók rosszul kondicionált rendszerekre és magasrendű rendszerekre, önkorrekciójuk és egyszerű PC-n való implementálásuk. A számítások megkezdéséhez az iteratív módszerekhez meg kell adni a kívánt megoldás kezdeti közelítését.

Megjegyzendő, hogy az iteratív folyamat konvergenciájának feltételei és sebessége jelentősen függ a mátrix tulajdonságaitól A rendszerről és a kezdeti közelítések megválasztásáról.

Az iterációs módszer alkalmazásához az eredeti (2.1) vagy (2.2) rendszert a formára kell redukálni

amely után az ismétlődő képletek szerint hajtjuk végre az iteratív folyamatot

, k = 0, 1, 2, ... . (2.26A)

Mátrix Gés vektort a (2.1) rendszer transzformációja eredményeként kapjuk.

A konvergenciához (2.26 A) szükséges és elégséges ahhoz, hogy |l én(G)| < 1, где lén(G) – Mind sajátértékek mátrixok G. Konvergencia akkor is bekövetkezik, ha || G|| < 1, так как |lén(G)| < " ||G||, ahol a " bármely.

Szimbólum || ... || a mátrix normáját jelenti. Értékének meghatározásakor leggyakrabban két feltétel ellenőrzésénél állnak meg:

||G|| = vagy || G|| = , (2.27)

Hol . A konvergencia akkor is garantált, ha az eredeti mátrix Aátlós dominanciával rendelkezik, i.e.

. (2.28)

Ha (2.27) vagy (2.28) teljesül, az iterációs módszer minden kezdeti közelítéshez konvergál. Leggyakrabban a vektort nullának vagy egységnek veszik, vagy magát a vektort a (2.26)-ból veszik.

Számos megközelítés létezik az eredeti rendszer (2.2) mátrixszal történő átalakítására A hogy biztosítsuk a formát (2.26) vagy teljesítsük a (2.27) és (2.28) konvergenciafeltételeket.

Például a (2.26) a következőképpen érhető el.

Hadd A = IN+ VEL, det IN#0; Akkor ( B+ VEL)= Þ B= −C+ Þ Þ B –1 B= −B –1 C+ B–1, honnan= − B –1 C+ B –1 .

Elhelyezés - B –1 C = G, B–1 = , megkapjuk (2.26).

A (2.27) és (2.28) konvergenciafeltételekből jól látható, hogy a reprezentáció A = IN+ VEL nem lehet önkényes.

Ha mátrix A teljesíti a (2.28) feltételeket, akkor mátrixként IN kiválaszthatja az alsó háromszöget:

, a ii ¹ 0.

; Þ ; Þ ; Þ

Az a paraméter kiválasztásával biztosíthatjuk, hogy || G|| = ||E+a A|| < 1.

Ha a (2.28) érvényesül, akkor a (2.26)-ra való transzformáció minden egyes megoldással elvégezhető én a (2.1) rendszer egyenlete x i a következő ismétlődő képletek szerint:

(2.28A)

Ha a mátrixban A nincs átlós dominancia, ezt néhány olyan lineáris transzformációval kell elérni, amelyek nem sértik az egyenértékűségüket.

Példaként tekintsük a rendszert

(2.29)

Mint látható, az (1) és (2) egyenletben nincs átlós dominancia, a (3)-ban viszont igen, ezért változatlanul hagyjuk.

Az (1) egyenletben érjünk el diagonális dominanciát. Szorozzuk meg (1)-et a-val, (2)-t b-vel, adjuk össze mindkét egyenletet, és a kapott egyenletben válasszuk ki a-t és b-t úgy, hogy átlós dominancia legyen:

(2a + 3b) X 1 + (–1,8a + 2b) X 2 +(0,4a – 1,1b) X 3 = a.

Ha a = b = 5-öt veszünk, akkor 25-öt kapunk X 1 + X 2 – 3,5X 3 = 5.

Az (1) túlsúlyú (2) egyenlet átalakításához szorozzuk meg g-vel, a (2) szorozzuk d-vel, és vonjuk ki (2) az (1)-et. Megkapjuk

(3d – 2g) X 1 + (2d + 1,8 g) X 2 + (–1,1 nap – 0,4 g) X 3 = −g.

Ha d = 2, g = 3, akkor 0-t kapunk X 1 + 9,4 X 2 – 3,4 X 3 = −3. Ennek eredményeként megkapjuk a rendszert

(2.30)

Ezzel a technikával a mátrixok széles osztályára lehet megoldást találni.

vagy

A = (0,2; –0,32; 0) vektort véve kezdeti közelítésnek T, ezt a rendszert technológia segítségével oldjuk meg (2.26 A):

k = 0, 1, 2, ... .

A számítási folyamat leáll, ha a megoldásvektor két szomszédos közelítése pontosan egybeesik, azaz.

.

A forma iteratív megoldásának technológiája (2.26 A) nevű egyszerű iterációs módszer .

Fokozat abszolút hiba az egyszerű iterációs módszerhez:

hol van a szimbólum || ... || normálisat jelent.

2.1. példa. Egyszerű iterációs módszerrel, e = 0,001 pontossággal oldja meg a rendszert lineáris egyenletek:

Az összefüggésből meghatározható az e = 0,001 pontos választ adó lépések száma

0,001 GBP.

Becsüljük meg a konvergenciát a (2.27) képlet segítségével. Itt || G|| = = max(0,56; 0,61; 0,35; 0,61) = 0,61< 1; = 2,15. Значит, сходимость обеспечена.

Kezdeti közelítésként a szabad tagok vektorát vesszük, azaz = (2,15; –0,83; 1,16; 0,44) T. Helyettesítsük be a vektorértékeket (2.26 A):

Folytatva a számításokat, az eredményeket beírjuk a táblázatba:

k	X 1	X 2	X 3	X 4
	2,15	–0,83	1,16	0,44
	2,9719	–1,0775	1,5093	–0,4326
	3,3555	–1,0721	1,5075	–0,7317
	3,5017	–1,0106	1,5015	–0,8111
	3,5511	–0,9277	1,4944	–0,8321
	3,5637	–0,9563	1,4834	–0,8298
	3,5678	–0,9566	1,4890	–0,8332
	3,5760	–0,9575	1,4889	–0,8356
	3,5709	–0,9573	1,4890	–0,8362
	3,5712	–0,9571	1,4889	–0,8364
	3,5713	–0,9570	1,4890	–0,8364

Ezrelékben kifejezett konvergencia már a 10. lépésnél megtörténik.

Válasz: X 1 » 3,571; X 2"-0,957; X 3 » 1,489; X 4 "-0,836.

Ezt a megoldást a (2.28.) képletekkel is megkaphatjuk A).

2.2. példa. Az algoritmus bemutatása képletekkel (2.28 A) fontolja meg a rendszer megoldását (csak két iteráció):

; . (2.31)

Alakítsuk át a rendszert a (2.26) alakra a (2.28) szerint A):

Þ (2.32)

Vegyük a kezdeti közelítést = (0; 0; 0) T. Aztán azért k= 0 nyilvánvaló, hogy az érték = (0,5; 0,8; 1,5) T. Helyettesítsük be ezeket az értékeket (2.32-be), azaz mikor k= 1 = (1,075; 1,3; 1,175) T.

Hiba e 2 = = max(0,575; 0,5; 0,325) = 0,575.

Az SLAE-re a módszer segítségével megoldást találó algoritmus blokkvázlata egyszerű iterációk munkaképletek szerint (2.28 A) ábrán látható. 2.4.

A blokkdiagram különlegessége a következő blokkok jelenléte:

– 13. blokk – célját az alábbiakban tárgyaljuk;

– 21. blokk – eredmények megjelenítése a képernyőn;

– 22. blokk – a konvergencia ellenőrzése (mutatója).

Elemezzük a javasolt sémát a (2.31) rendszer példáján ( n= 3, w = 1, e = 0,001):

= ; .

Tömb 1. Adja meg a kezdeti adatokat A, , w, e, n: n= 3, w = 1, e = 0,001.

I. ciklus. Állítsa be a vektorok kezdeti értékeit x 0énÉs x i (én = 1, 2, 3).

Tömb 5. Állítsa vissza az iterációs számlálót.

Tömb 6. Állítsa vissza az aktuális hibaszámlálót nullára.

IN ciklusban a mátrix sorszámai megváltoznak Aés vektor.

Ciklus II:én = 1: s = b 1 = 2 (8. mező).

Lépjen a III. beágyazott ciklushoz, 9. blokk – mátrixoszlopszám-számláló A: j = 1.

Tömb 10: j = én, ezért visszatérünk a 9. blokkhoz és növeljük j egységenként: j = 2.

A 10-es blokkban j ¹ én(2 ¹ 1) – áttérünk a 11-es blokkra.

Tömb 11: s= 2 – (–1) × X 0 2 = 2 – (–1) × 0 = 2, ugorjon a 9. blokkra, amelyben j növeld eggyel: j = 3.

A 10. blokkban a feltétel j ¹ én teljesült, ezért térjünk át a 11. blokkra.

Tömb 11: s= 2 – (–1) × X 0 3 = 2 – (–1) × 0 = 2, majd továbblépünk a 9. blokkra, amelyben j növeld eggyel ( j= 4). Jelentése j több n (n= 3) – befejezzük a ciklust, és továbblépünk a 12. blokkra.

Tömb 12: s = s / a 11 = 2 / 4 = 0,5.

Tömb 13: w = 1; s = s + 0 = 0,5.

Tömb 14: d = | x i – s | = | 1 – 0,5 | = 0,5.

Tömb 15: x i = 0,5 (én = 1).

Tömb 16. Állapot ellenőrzése d > de: 0,5 > 0, ezért menjünk a 17. blokkhoz, amelyben hozzárendeljük de= 0,5 és térjen vissza a következő hivatkozással A» a II. ciklus következő lépésére – a 7. blokkra, amelyben én eggyel növeljük.

Ciklus II: én = 2: s = b 2 = 4 (8. mező).

j = 1.

A 10-es blokkon keresztül j ¹ én(1 ¹ 2) – áttérünk a 11-es blokkra.

Tömb 11: s= 4 – 1 × 0 = 4, lépjen a 9. blokkra, amelyben j növeld eggyel: j = 2.

A 10. blokkban a feltétel nem teljesül, így továbblépünk a 9. blokkra, amelyben j növeld eggyel: j= 3. Hasonlatosan továbblépünk a 11. blokkra.

Tömb 11: s= 4 – (–2) × 0 = 4, ami után befejezzük a III. ciklust, és továbblépünk a 12. blokkra.

Tömb 12: s = s/ a 22 = 4 / 5 = 0,8.

Tömb 13: w = 1; s = s + 0 = 0,8.

Tömb 14: d = | 1 – 0,8 | = 0,2.

Tömb 15: x i = 0,8 (én = 2).

Tömb 16. Állapot ellenőrzése d > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «A» a II. ciklus következő lépéséhez - a 7. blokkhoz.

Ciklus II: én = 3: s = b 3 = 6 (8. mező).

Lépjen a III. beágyazott hurok 9. blokkjához: j = 1.

Tömb 11: s= 6 – 1 × 0 = 6, ugorjon a 9. blokkra: j = 2.

A 10-es blokk segítségével áttérünk a 11-es blokkra.

Tömb 11: s= 6 – 1 × 0 = 6. Befejezzük a III. ciklust és továbblépünk a 12. blokkra.

Tömb 12: s = s/ a 33 = 6 / 4 = 1,5.

Tömb 13: s = 1,5.

Tömb 14: d = | 1 – 1,5 | = 0,5.

Tömb 15: x i = 1,5 (én = 3).

A 16. blokk szerint (beleértve a hivatkozásokat " A"És" VEL") elhagyjuk a II. ciklust, és továbblépünk a 18. blokkra.

Tömb 18. Az iterációk számának növelése azt = azt + 1 = 0 + 1 = 1.

A IV. ciklus 19. és 20. blokkjában lecseréljük a kezdeti értékeket X 0én kapott értékeket x i (én = 1, 2, 3).

Tömb 21. Az aktuális iteráció köztes értékeit nyomtatjuk ki, ebben az esetben: = (0,5; 0,8; 1,5) T, azt = 1; de = 0,5.

A 7. blokkhoz megyünk a II. ciklushoz, és új kezdeti értékekkel hajtjuk végre a figyelembe vett számításokat X 0én (én = 1, 2, 3).

Ami után megkapjuk X 1 = 1,075; X 2 = 1,3; X 3 = 1,175.

Itt tehát Seidel módszere konvergál.

A (2.33) képletek szerint

k	X 1	X 2	X 3
	0,19	0,97	–0,14
	0,2207	1,0703	–0,1915
	0,2354	1,0988	–0,2118
	0,2424	1,1088	–0,2196
	0,2454	1,1124	–0,2226
	0,2467	1,1135	–0,2237
	0,2472	1,1143	–0,2241
	0,2474	1,1145	–0,2243
	0,2475	1,1145	–0,2243

Válasz: x 1 = 0,248; x 2 = 1,115; x 3 = –0,224.

Megjegyzés. Ha az egyszerű iteráció és a Seidel metódusok ugyanarra a rendszerre konvergálnak, akkor a Seidel módszert részesítjük előnyben. A gyakorlatban azonban ezeknek a módszereknek a konvergencia területei eltérőek lehetnek, azaz az egyszerű iterációs módszer konvergál, de a Seidel-módszer divergál, és fordítva. Mindkét módszer esetében, ha || G|| közel egység, a konvergencia sebessége nagyon alacsony.

A konvergencia felgyorsítására mesterséges technikát alkalmaznak - az ún relaxációs módszer . Lényege abban rejlik, hogy az iterációs módszerrel kapott következő érték x i (k) a képlet segítségével kerül újraszámításra

ahol w általában 0 és 2 között változik (0< w £ 2) с каким-либо шагом (h= 0,1 vagy 0,2). A w paramétert úgy választjuk ki, hogy a módszer konvergenciája minimális számú iterációval elérhető legyen.

Pihenés– a test bármely állapotának fokozatos gyengülése az állapotot okozó tényezők megszűnése után (fizikai tervezés).

2.4. példa. Tekintsük az ötödik iteráció eredményét a relaxációs képlet segítségével. Vegyük w = 1,5:

Amint látja, majdnem a hetedik iteráció eredménye megszületett.

Ebben a részben egy stacionárius iteratív folyamatot fogunk megvizsgálni, amikor a mátrix és az iterációs paraméter nem függ az indextől , és bizonyítsd be a következő tételt a konvergenciájának elegendő feltételeiről.

Szamarszkij tétele

Hadd - önadjungált pozitív definit mátrix:

,
,

- pozitív határozott mátrix, - pozitív szám:

,
.

Ezután a nulla közelítés bármely választásához iteratív folyamat, amelyet az ismétlődő képlet határoz meg , konvergál az eredeti rendszer megoldásához.

Mielőtt rátérnénk a tétel bizonyítására, beszéljük meg részletesebben annak fő követelményét - a mátrix pozitív meghatározottságát
. Ez a követelmény a következőképpen írható át:

,
,
.

azaz különösen azt feltételezi, hogy a mátrix pozitív határozott. Ezenkívül az egyenlőtlenség meghatározza azt az intervallumot, amelyben a paraméter változhat :

.

Ezen megjegyzések után áttérünk a tétel bizonyítására. A relációból fejezzük ki keresztül :

és helyettesítse be az iterációs sorozat ismétlődő képletébe. Ennek eredményeként a következőket kapjuk:

.

A különbség az iteratív képlet és az, hogy homogén.

Mátrix - pozitív határozott. Ezért nem degenerált, és inverze van
. Az ő segítségével ismétlődő kapcsolat viszonylag megoldható
:

, Szóval
.

A bal oldali egyenlőség mindkét oldalát megszorozzuk a mátrixszal , újabb ismétlődési relációt kapunk

.

Tekintsük a pozitív függvények sorozatát:

.

Hozzunk létre egy hasonló kifejezést
és alakítsa át ismétlődő képletekkel és:

A mátrix ön-adjungáltságából és a képlet következik

Ennek eredményeként a képlet a következő alakot veszi fel:

Így a funkcionálisok sorrendje feltételekhez kötve
alatta nullával határolt monoton nem növekvő sorozatot alkot

.

,

Ahol
szigorúan pozitív állandó. Ennek eredményeként szerint és lesz

Ebből az egyenlőtlenségből és a funkcionálisok sorozatának konvergenciájából ebből következik
at
. Viszont
, Szóval

A tétel bizonyítást nyert.

1. Egyszerű iterációs módszer.

Ezt a nevet adták annak a módszernek, amelyben mátrixként az identitásmátrix van kiválasztva:
, és az iterációs paraméter függetlennek tételezzük fel az iterációs számtól . Más szóval, az egyszerű iterációs módszer egy explicit stacionárius módszer, amikor a következő iteráció
az ismétlődő képlet segítségével számítjuk ki

Feltételezzük, hogy a mátrix kielégíti Szamarszkij tételének feltételeit,
, majd a képlet, amely meghatározza a konvergencia intervallum határát az iteratív paraméterhez képest , felveszi a formát

.

Hadd
- a mátrixnak megfelelő operátor sajátvektorainak ortonormális bázisa . A pozitív meghatározottság miatt minden sajátértéke pozitív. Ezeket csökkenő sorrendben számozva tekintjük:

Bővítsük ki a vektort
sajátvektorok alapján

Ennek eredményeként a képletből az következik, hogy az egyszerű iterációs módszer bármelyikre konvergál intervallumhoz tartozó

.

Az egyszerű iterációs módszer további tanulmányozását az ismétlődő képlet konkrét elemzésére alapozzuk. Mutassuk be az átmenet operátor mátrixát

,

és írd át a képletet a formába

.

Ebben az esetben a hiba
hasonló ismétlődési relációt fog kielégíteni, csak homogén

.

Bizonyítsunk be két lemmát, amelyek lehetővé teszik az egyszerű iterációs módszer konvergenciájának alaposabb feltárását.

1. lemma

Legyen a mátrix által generált operátor , sajátvektora van sajátértékkel , majd az átmeneti operátort, amelyet a mátrix generál , sajátvektora is van , hanem sajátértékkel

.

A bizonyítás elemi. Ez közvetlen ellenőrzéssel történik

Önadjungált mátrixhoz mátrix önadjunkt is. Következésképpen normáját a legnagyobb abszolút sajátérték határozza meg
:

.

2. lemma

Annak érdekében, hogy az egyszerű iterációs módszer konvergáljon a rendszer megoldásához bármilyen kezdeti közelítési választás esetén, szükséges és elegendő, hogy az átmeneti operátor összes sajátértéke abszolút értékben egynél kisebbek voltak:

,

Megfelelőség. A feltétel azt jelenti, hogy a mátrix normája szerint egynél kevesebb lesz:
. Ennek eredményeként azt kapjuk

at
.

Szükség. Tegyük fel, hogy a sajátértékek között volt legalább egy , amely nem felel meg a lemma feltételeinek, azaz.

.

Válasszuk ki az iterációs sorozat nulla tagját az alakban
, Hol a rendszer megoldása, akkor a hibasorozat nullatagja egybeesik a sajátvektorral átmeneti operátor :
. Ennek eredményeként a hibasorozat következő feltételeinek ismétlődő képlete a következő formában jelenik meg:

,
.

azaz
. Az egyenlőtlenség kielégítésének szükségessége minden sajátértékre mert az egyszerű iterációs módszer konvergenciája bebizonyosodott.

A 2. lemma meghatározza az egyszerű iterációs módszer konvergenciájának további tanulmányozására szolgáló programot: be kell állítani a paraméterváltoztatási tartományt amelynek minden sajátértéke kielégíti az egyenlőtlenséget. Könnyű megtenni. ábrán. Az 1. ábra a csökkenő lineáris függvények grafikonjait mutatja
. Mind ugyanarról a pontról származnak
,
és csökken a negatív együtthatók miatt at , és a leggyorsabban csökkenő függvény az
. Mikor számít
, a feltétel már nem teljesül:

, at
.

Talált érték az egyszerű iterációs módszer konvergencia intervallumának határa

.

Ezt az egyenlőtlenséget már ismerjük. Korábban Szamarszkij tételéből kaptuk, mint a konvergencia elégséges feltételét. A 2. lemma alapján végzett további elemzés lehetővé teszi az eredmény tisztázását. Most megállapítottuk, hogy az iteratív paraméter tagsága intervallum szükséges és elégséges feltétele az egyszerű iterációs módszer konvergenciájának.

Térjünk át a módszer konvergencia rátájának tanulmányozására. A hiba becslése azt mutatja, hogy a nevezővel a geometriai progresszió törvénye szerint csökken

.

Nézzük az ábrát. 2, amely segít a képlet elemzésében. Hasonló az 1. ábrához, csak a nem függvények grafikonjait mutatja
, és azok moduljai. Kicsiben minden sajátérték
pozitívak, és a legnagyobb közülük az
, ami a növekedéssel csökken a legalacsonyabb sebességen. A ponton való áthaladás után azonban
sajátérték
, változó előjellel, negatívvá válik. Ennek eredményeként most a modul növekszik nem csökken, hanem együtt nő
megközelíti a határértéket – az egységet.

Keressük a szegmenst
pont , amelyben a csökkenő függvény
növekvő függvényhez képest
. Az egyenlet határozza meg

amely megadja

.

Ennek eredményeként a következőket kapjuk:

Ennek legkisebb értéke a mátrix normája eléri a
:

.

A képlet azt mutatja, hogy rosszul kondicionált mátrix esetén az iterációs paraméter optimális megválasztása mellett is
mátrix norma közel van az egységhez, így az egyszerű iterációs módszer konvergenciája ebben az esetben lassú.

Végezetül megjegyezzük, hogy a konvergencia intervallum határát meghatározó képlet , és az iterációs paraméter optimális értékének képlete elsősorban elméleti szempontból érdekesek. Általában az SLAE megoldása során a mátrix legnagyobb és legkisebb karakterisztikus számai ismeretlen, ezért számítsa ki az értékeket És előre lehetetlen. Ennek eredményeként az iterációs paraméter Gyakran ki kell választania közvetlenül a számítási folyamat során, próba-hibával.

2. feladat.

Tekintsünk egy két egyenletrendszert két ismeretlennel

és az egyszerű iterációs módszerrel hozzávetőleges megoldást készítsünk rá.

Azonnal írjuk le a megoldást a rendszerbe

,
,

hogy azután össze tudja hasonlítani az iterációs sorozat tagjaival.

Térjünk át a rendszer egyszerű iterációs módszerrel történő megoldására. A rendszermátrixnak van formája

.

Önálló és pozitív határozott, hiszen

Készítsünk egy karakterisztikus egyenletet a mátrixra és megtalálja a gyökereit:

,

,

Segítségükkel meghatározhatja a konvergencia intervallum határát És optimális érték iterációs paraméter :

,
.

Egy iterációs sorozat létrehozásához kiválasztjuk az iterációs paraméter valamely értékét a konvergencia intervallumon, például:
. Ebben az esetben az iterációs sorozat tagjainak ismétlődő képlete a következő alakot ölti:

, Hol

Vegyük a legegyszerűbb kezdeti közelítést
és írd le az iterációs sorozat első néhány tagját , kiszámolva mindegyikre a maradékot
. Ennek eredményeként a következőket kapjuk:

,
,
,

,
,
,

,
,
,

,
,
.

A maradékok normája, bár lassan, de csökken, ami a folyamat konvergenciáját jelzi. Ugyanez látható az iteratív sorozat tagjainak összehasonlításából is a rendszer megoldásával. A lassú konvergencia a rossz mátrix kondicionálásnak köszönhető :

.

Az egyszerű iterációs módszer az eredeti egyenlet egy ekvivalens egyenlettel való helyettesítésén alapul:

Legyen ismert a gyök kezdeti közelítése x = x 0. Behelyettesítve jobb oldalon a (2.7) egyenlet alapján új közelítést kapunk , akkor hasonló módon kapjuk stb.:

. (2.8)

Az iteratív folyamat nem minden esetben konvergál az egyenlet gyökeréhez X. Nézzük meg közelebbről ezt a folyamatot. A 2.6. ábra egy egyirányú konvergens és divergens folyamat grafikus értelmezése. A 2.7. ábra kétirányú konvergens és divergens folyamatokat mutat be. A divergens folyamatot az argumentum és a függvény értékeinek gyors növekedése és a megfelelő program rendellenes leállása jellemzi.

Egy kétirányú folyamattal lehetséges a ciklus, vagyis ugyanazon függvény és argumentumértékek végtelen ismétlése. A hurkok elválasztják a divergens folyamatot a konvergenstől.

A grafikonokon jól látható, hogy mind az egy-, mind a kétoldali folyamatok esetében a gyökérhez való konvergenciát a görbe gyökérközeli meredeksége határozza meg. Minél kisebb a lejtő, annál jobb a konvergencia. Mint ismeretes, egy görbe meredekségének érintője megegyezik a görbe adott pontbeli deriváltjával.

Ezért minél kisebb a szám a gyökér közelében, annál gyorsabban konvergál a folyamat.

Ahhoz, hogy az iterációs folyamat konvergens legyen, a következő egyenlőtlenségnek kell teljesülnie a gyökér szomszédságában:

A (2.1) egyenletből a (2.7) egyenletbe való átmenet végrehajtható különféle módokon a funkció típusától függően f(x). Egy ilyen átmenetben úgy kell megszerkeszteni a függvényt, hogy a (2.9) konvergencia feltétel teljesüljön.

Tekintsük a (2.1) egyenletből a (2.7) egyenletbe való átmenet egyik általános algoritmusát.

Szorozzuk meg a (2.1) egyenlet bal és jobb oldalát egy tetszőleges állandóval bés mindkét részhez hozzáadjuk az ismeretlent X. Ebben az esetben az eredeti egyenlet gyökerei nem változnak:

Bemutatjuk a jelölést és térjünk át a (2.10) összefüggésről a (2.8) egyenletre.

A konstans önkényes megválasztása b biztosítja a (2.9) konvergencia feltétel teljesülését. Az iteratív folyamat befejezésének kritériuma a (2.2) feltétel lesz. A 2.8. ábra az egyszerű iterációk módszerének grafikus értelmezését mutatja a leírt ábrázolási módszerrel (az X és Y tengely mentén eltérő léptékek).

Ha egy függvényt a formában választunk, akkor ennek a függvénynek a deriváltja lesz. A konvergencia legnagyobb sebessége ekkor lesz és az iterációs képlet (2.11) bekerül a Newton-formulába. Így a Newton-módszer rendelkezik a legmagasabb fokú konvergenciával az összes iteratív folyamat közül.

Az egyszerű iterációs módszer szoftveres megvalósítása szubrutin eljárás formájában történik Iteras(2.1. PROGRAM).

A teljes eljárás gyakorlatilag egy Ismétlés ... ciklusból áll, a (2.11) képlet megvalósításával, figyelembe véve az iteratív folyamat leállításának feltételét (2.2 képlet).

Az eljárás beépített hurokvédelemmel rendelkezik, amely a Niter változó segítségével számolja a hurkok számát. A gyakorlati órákon a program futtatásával meg kell győződni arról, hogy az együttható megválasztása hogyan befolyásolja bés kezdeti közelítés a gyökérkeresés folyamatában. Az együttható megváltoztatásakor b a vizsgált függvény iterációs folyamatának jellege megváltozik. Először kétoldalas lesz, majd hurkok (2.9. ábra). Tengelymérleg XÉs Y különböznek. A b modulus még nagyobb értéke divergens folyamathoz vezet.

Az egyenletek közelítő megoldásának módszereinek összehasonlítása

Az egyenletek numerikus megoldására fent leírt módszerek összehasonlítását egy olyan programmal végeztük, amely lehetővé teszi a gyökér megtalálásának folyamatát grafikus formában a PC képernyőjén. A programban szereplő eljárások és az összehasonlított módszerek megvalósítása az alábbiakban találhatók (2.1. PROGRAM).

Rizs. A 2.3-2.5, 2.8, 2.9 a számítógép képernyőjének másolatai az iterációs folyamat végén.

Minden esetben a vizsgált függvényt vettük másodfokú egyenlet x 2 -x-6 = 0, amelynek analitikus megoldás x 1 = -2 és x 2 = 3. A hibát és a kezdeti közelítéseket minden módszernél egyenlőnek feltételeztük. Root keresési eredmények x= Az ábrákon bemutatott 3. ábrák a következők. A dichotómia módszer konvergál a leglassabban - 22 iterációból, a leggyorsabb az egyszerű iterációs módszer b = -0,2 - 5 iterációval. Itt nincs ellentmondás azzal az állítással, hogy Newton módszere a leggyorsabb.

A pontban vizsgált függvény származéka X= 3 egyenlő -0,2-vel, vagyis a számítás ebben az esetben gyakorlatilag Newton-módszerrel történt, a derivált értékével az egyenlet gyökénél. Az együttható megváltoztatásakor b a konvergencia üteme csökken, és a fokozatosan konvergens folyamat először ciklusokban megy végbe, majd válik divergenssé.

Az egyszerű iterációs módszer, amelyet szukcesszív közelítési módszernek is neveznek, egy matematikai algoritmus egy ismeretlen mennyiség értékének meghatározására annak fokozatos finomításával. Ennek a módszernek az a lényege, hogy ahogy a neve is sugallja, a kezdeti közelítésből fokozatosan kifejezve a későbbieket, egyre finomabb eredmények születnek. Ezt a módszert egy változó értékének meghatározására használják adott funkciót, valamint lineáris és nemlineáris egyenletrendszerek megoldásánál is.

Nézzük meg, hogyan valósul meg ez a módszer az SLAE megoldása során. Az egyszerű iterációs módszer a következő algoritmussal rendelkezik:

1. A konvergencia feltétel teljesülésének ellenőrzése az eredeti mátrixban. Konvergenciatétel: ha a rendszer eredeti mátrixa diagonális dominanciával rendelkezik (azaz minden sorban a főátló elemeinek abszolút értékben nagyobbaknak kell lenniük, mint a másodlagos átlók elemeinek abszolút értékben kifejezett összege), akkor az egyszerű iterációs módszer konvergens.

2. Az eredeti rendszer mátrixának nem mindig van diagonális túlsúlya. Ilyen esetekben a rendszer átalakítható. A konvergenciafeltételt kielégítő egyenleteket érintetlenül hagyjuk, azokkal pedig lineáris kombinációkat készítünk, amelyek nem, azaz. szorozni, kivonni, összeadni az egyenleteket, amíg a kívánt eredményt el nem kapjuk.

Ha a kapott rendszerben kényelmetlen együtthatók vannak a főátlón, akkor az i * x i alakú tagokat hozzáadjuk egy ilyen egyenlet mindkét oldalához, amelyek előjeleinek egybe kell esnie az átlós elemek előjeleivel.

3. Az eredményül kapott rendszer átalakítása normál formára:

x - =β - +α*x -

Ezt sokféleképpen megtehetjük, például így: az első egyenletből fejezzük ki az x 1-et más ismeretlenekkel, a másodikból - x 2, a harmadikból - x 3 stb. Ebben az esetben a képleteket használjuk:

α ij = -(a ij / a ii)

i = b i /a ii
Ismét meg kell győződnie arról, hogy a kapott rendszer normális kinézetű megfelel a konvergencia feltételnek:

∑ (j=1) |α ij |≤ 1, míg i= 1,2,...n

4. Valójában magát az egymást követő közelítések módszerét kezdjük alkalmazni.

x (0) a kezdeti közelítés, ezen keresztül fejezzük ki x (1)-et, majd x (2)-t x (1)-ig. Általános képlet mátrix formában pedig így néz ki:

x (n) = β - + α*x (n-1)

Addig számolunk, amíg el nem érjük a kívánt pontosságot:

max |x i (k)-x i (k+1) ≤ ε

Tehát alkalmazzuk az egyszerű iterációs módszert a gyakorlatban. Példa:
SLAE megoldása:

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 ε=10 -3 pontossággal

Nézzük meg, hogy a diagonális elemek túlsúlyban vannak-e a modulusban.

Látjuk, hogy csak a harmadik egyenlet teljesíti a konvergencia feltételt. Alakítsuk át az elsőt és a másodikat, és adjuk hozzá a másodikat az első egyenlethez:

7,6x1+0,6x2+2,4x3=3

A harmadikból kivonjuk az elsőt:

2,7x1+4,2x2+1,2x3=2

Az eredeti rendszert átalakítottuk egy egyenértékűvé:

7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1,8x1+2,5x2+4,7x3=4

Most állítsuk a rendszert normál formájába:

x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3 = 0,8511-0,383x1-0,5319x2

Ellenőrizzük az iteratív folyamat konvergenciáját:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, azaz a feltétel teljesül.

0,3947
Kezdeti tipp x(0) = 0,4762
0,8511

Ezeket az értékeket a normál alakú egyenletbe behelyettesítve a következő értékeket kapjuk:

0,08835
x(1) = 0,486793
0,446639

Új értékeket behelyettesítve a következőket kapjuk:

0,215243
x(2) = 0,405396
0,558336

Addig folytatjuk a számításokat, amíg el nem érjük az adott feltételt kielégítő értékeket.

x (7) = 0,441091

Ellenőrizzük a kapott eredmények helyességét:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

A talált értékek eredeti egyenletekbe való behelyettesítésével kapott eredmények teljes mértékben kielégítik az egyenlet feltételeit.

Amint látjuk, az egyszerű iterációs módszer meglehetősen pontos eredményeket ad, de ennek az egyenletnek a megoldásához sok időt kellett töltenünk és nehézkes számításokat kellett végeznünk.

Előadás Iteratív módszerek algebrai lineáris egyenletrendszer megoldására.

Az iteratív folyamat konvergenciájának feltétele

Egyszerű iterációs módszer

Lineáris rendszert tekintünk algebrai egyenletek

Az iteratív módszerek alkalmazásához a rendszert egyenértékű formára kell redukálni

Ezután kiválasztunk egy kezdeti közelítést az egyenletrendszer megoldásához, és megtaláljuk a gyökér közelítéseinek sorozatát.

Az iteratív folyamat konvergálásához elegendő, ha a feltétel teljesül
(mátrix norma). Az iterációk befejezésének kritériuma az alkalmazott iteratív módszertől függ.

Jacobi módszer .

A legegyszerűbb módja annak, hogy a rendszert az iterációhoz kényelmes formába hozza, a következő:

A rendszer első egyenletéből fejezzük ki az ismeretlent x 1, az általunk kifejezett rendszer második egyenletéből x 2 stb.

Ennek eredményeként egy B mátrixú egyenletrendszert kapunk, amelyben nulla elemek vannak a főátlón, a fennmaradó elemeket pedig a képletekkel számítjuk ki:

A d vektor összetevőit a következő képletekkel számítjuk ki:

Az egyszerű iterációs módszer számítási képlete:

vagy koordináta jelöléssel így néz ki:

A Jacobi-módszerben az iterációk befejezésének kritériuma a következő:

Ha
, akkor egy egyszerűbb kritériumot is alkalmazhatunk az iterációk befejezésére

1. példa Lineáris egyenletrendszer megoldása Jacobi módszerrel.

Legyen adott az egyenletrendszer:

Pontos megoldást kell találni a rendszerre

Csökkentsük le a rendszert olyan formára, amely alkalmas az iterációra:

Válasszunk egy kezdeti közelítést, pl.

- a jobb oldali vektor.

Akkor az első iteráció így néz ki:

A megoldás következő közelítéseit hasonló módon kapjuk.

Keressük meg a B mátrix normáját.

A normát fogjuk használni

Mivel az egyes sorok elemeinek moduljainak összege 0,2, akkor
, tehát az iterációk befejezésének kritériuma ebben a problémában az

Számítsuk ki a vektorkülönbségek normáit:

Mert
a megadott pontosságot a negyedik iterációnál érte el.

Válasz: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1

Seidel módszer .

A módszer a Jacobi-módszer módosításának tekinthető. A fő gondolat az, hogy a következő kiszámításakor (n+1)- az ismeretlen megközelítése x én at i >1 használat már megtalálható (n+1)- e közeledik az ismeretlenhez x 1 ,x 2 , ...,x i - 1 és nem n közelítés, mint a Jacobi módszernél.

A módszer számítási képlete koordinátajelölésben így néz ki:

A konvergenciafeltételek és az iterációk befejezésének kritériuma megegyezik a Jacobi módszerrel.

2. példa Lineáris egyenletrendszerek megoldása Seidel módszerrel.

Tekintsük párhuzamosan 3 egyenletrendszer megoldását:

Csökkentsük le a rendszereket az iterációk számára kényelmes formára:

Vegye figyelembe, hogy a konvergencia feltétele
csak az első rendszerhez készült. Számítsunk ki minden esetben 3 első közelítést a megoldásra.

1. rendszer:

A pontos megoldás a következő értékek lesznek: x 1 = 1.4, x 2 = 0.2 . Az iteratív folyamat konvergál.

2. rendszer:

Látható, hogy az iterációs folyamat eltér egymástól.

Pontos megoldás x 1 = 1, x 2 = 0.2 .

3. rendszer:

Látható, hogy az iteratív folyamat ciklusokban ment.

Pontos megoldás x 1 = 1, x 2 = 2 .

Legyen az A egyenletrendszer mátrixa szimmetrikus és pozitív határozott. Ezután a kezdeti közelítés bármely választása esetén a Seidel-módszer konvergál. Egy bizonyos mátrix normájának kicsinysége nem támaszt további feltételeket.

Egyszerű iterációs módszer.

Ha A szimmetrikus és pozitív definit mátrix, akkor az egyenletrendszer gyakran ekvivalens formára redukálódik:

x=x-τ (A x- b), τ – iterációs paraméter.

Az egyszerű iterációs módszer számítási képlete ebben az esetben a következő:

x (n+1) =x n- τ (A x (n) - b).

és a τ > 0 paramétert úgy választjuk meg, hogy lehetőség szerint minimalizáljuk az értéket

Legyen λ min és λ max az A mátrix minimális és maximális sajátértéke. A paraméter optimális megválasztása

Ebben az esetben
minimális értéket vesz fel:

3. példa Lineáris egyenletrendszerek megoldása egyszerű iterációs módszerrel. (MathCAD-ben)

Legyen adott az Ax = b egyenletrendszer

Az iteratív folyamat felépítéséhez azt találjuk sajátértékek A mátrixok:

- beépített függvényt használ a sajátértékek keresésére.

Számítsuk ki az iterációs paramétert és ellenőrizzük a konvergencia feltételt

A konvergencia feltétele teljesül.

Vegyük a kezdeti közelítést - az x0 vektort, állítsuk a pontosságot 0,001-re, és keressük meg a kezdeti közelítéseket az alábbi programmal:

Pontos megoldás

Megjegyzés. Ha a program visszaadja a rez mátrixot, akkor megtekintheti az összes talált iterációt.