Tästä seuraa siis α ≈ | φ ′ (ξ) | (\displaystyle \alpha \approx |\varphi "(\xi)|). Menetelmän konvergoimiseksi riittää siis se ∀ x ∈ [ a , b ] | φ ′ (x) | ≤ 1. (\displaystyle \forall x\in \quad |\varphi "(x)|\leq 1.)

Peräkkäisten approksimaatioiden yleinen algoritmi[ | ]

Operaattoriyhtälöiden yleisessä tapauksessa tätä menetelmää kutsutaan peräkkäisten approksimaatioiden menetelmä tai yksinkertainen iterointimenetelmä. Yhtälö voidaan kuitenkin muuntaa supistumismappaukseksi, jolla on sama juuri, eri tavoin. Tämä synnyttää useita erityisiä menetelmiä, joilla on sekä lineaariset että korkeammat konvergenssinopeudet.

Kuten SLAU:ssa[ | ]

Harkitse järjestelmää:

( a 11 x 1 + … + a 1 n x n = b 1 … a n 1 x 1 + … + a n n x n = b n (\displaystyle \left\((\begin(array)(ccc)a_(11)x_(1)+) \lpisteet +a_(1n)x_(n)&=&b_(1)\\\lpisteet &&\\a_(n1)x_(1)+\lpisteet +a_(nn)x_(n)&=&b_(n) \end(array))\right.)

Sitä varten iteratiivinen laskenta näyttää tältä:

(x 1 x 2 ⋮ x n) i + 1 = (a 11 + 1 a 12 … a 1 n a 21 a 22 + 1 … a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 … a n n + 1) (x 1 x 1) ) ⋮ x n) i − (b 1 b 2 ⋮ b n) (\displaystyle \left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\ end (taulukko))\oikea)^(i+1)=\left((\begin(array)(cccc)a_(11)+1&a_(12)&\ldots &a_(1n)\\a_(21)&a_ ( 22)+1&\lpisteet &a_(2n)\\\vpisteet &\vpisteet &\dpisteet &\vpisteet \\a_(n1)&a_(n2)&\lpisteet &a_(nn)+1\end(array))\ oikea )\left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end(array))\right)^(i)-\left ( (\begin(array)(c)b_(1)\\b_(2)\\\vdots \\b_(n)\end(array))\right))

Menetelmä konvergoi lineaarisella nopeudella, jos ‖ a 11 + 1 … a 1 n ⋮ ⋱ ⋮ a n 1 … a n n + 1 ‖< 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}

Kaksinkertaiset pystypalkit tarkoittavat jotakin matriisinormia.

Yhtälön f(x)=0 ratkaisu Newtonin menetelmällä, alkuperäinen approksimaatio: x 1 =a.

Newtonin menetelmä (tangenttimenetelmä)[ | ]

Yksiulotteinen kotelo[ | ]

Alkuperäisen yhtälön muunnoksen optimointi f (x) = 0 (\displaystyle f(x)=0) supistumiskartoituksiin x = φ (x) (\displaystyle x=\varphi (x)) avulla voit saada menetelmän, jolla on neliöllinen konvergenssinopeus.

Jotta kartoitus olisi tehokkain, on välttämätöntä, että seuraavan iteroinnin pisteessä x ∗ (\displaystyle x^(*)) suoritettu φ ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=0). Etsimme ratkaisua tähän yhtälöön muodossa φ (x) = x + α (x) f (x) (\displaystyle \varphi (x)=x+\alpha (x)f(x)), sitten:

Käytetään mitä f (x) = 0 (\displaystyle f(x)=0), ja saamme lopullisen kaavan α (x) (\displaystyle \alpha (x)):

Tätä silmällä pitäen supistumisfunktio on muodossa:

Sitten algoritmi numeerisen ratkaisun löytämiseksi yhtälöön f (x) = 0 (\displaystyle f(x)=0) pelkistyy iteratiiviseksi laskentamenettelyksi:

Iteratiiviset menetelmät

Iteratiiviset menetelmät olettavat seuraavien kolmen vaiheen toteuttamisen: täsmälliseen ratkaisuun konvergoivan iteratiivisen prosessin rakentaminen peräkkäisten approksimaatioiden laskemiseksi (eli peräkkäisten approksimaatioiden laskemiseen (ts. täsmälliseen ratkaisuun konvergoivan vektoreiden sarjan rakentaminen) ; tämän prosessin konvergenssikriteerin määrittäminen, mikä mahdollistaa vaaditun tarkkuuden saavuttamisen hetken määrittämisen; iteratiivisen prosessin konvergenssin nopeuden ja optimoinnin tutkimus, jotta voidaan vähentää tarvittavan tarkkuuden saavuttamiseen tarvittavien operaatioiden määrää.

Iteratiiviset menetelmät mahdollistavat ratkaisun saamisen ennalta määrätyllä tarkkuudella, jos menetelmän konvergenssi on todistettu. Iteratiiviset menetelmät eivät anna ehdottoman tarkkaa ratkaisua, koska se saavutetaan vektoreiden sekvenssin rajana. Suora menetelmä antaa yleensä tarkan ratkaisun, mutta kaikilla tietokoneilla esiintyvien pyöristysvirheiden vuoksi siihen ei päästä, ja a priori on jopa vaikea arvioida, kuinka paljon tämä ratkaisu eroaa tarkasta. Edellä mainitun yhteydessä iteratiiviset menetelmät mahdollistavat toisinaan ratkaisun saamisen suoria ratkaisuja tarkemmin.

Harkitse useita iteratiivisia menetelmiä lineaaristen yhtälöiden ratkaisemiseksi.

Yksinkertainen iterointimenetelmä

Yksinkertaisessa iteraatiomenetelmässä lineaaristen algebrallisten yhtälöiden järjestelmä (2.1). kirves = b pelkistetään vastaavaksi lomakejärjestelmäksi

Systeemin (2.9) ratkaisua ja siten alkuperäisen järjestelmän (2.1) ratkaisua etsitään vektorisarjan rajana:

k = 0, 1, 2,…,(2.10)

missä on ratkaisuvektorin alkuperäinen approksimaatio.

Riittävä ehto yksinkertaisen iterointimenetelmän konvergenssille määritellään seuraavalla lauseella.

LAUSE 1. Jos mikä tahansa matriisin normi, joka on yhdenmukainen vektorin tarkasteltavan normin kanssa, on pienempi kuin yksikkö (), niin yksinkertaisen iteraatiomenetelmän sekvenssi konvergoi järjestelmän (2.9) täsmälliseen ratkaisuun nopeudella, joka ei ole pienempi kuin nopeus geometrisen progression minkä tahansa alkuperäisen approksimoinnin nimittäjällä .

TODISTE. Lauseen todistamiseksi esitämme virheen . Kun suhteesta vähennetään yhtäläisyys (2.10), saadaan . Normeihin siirtyminen, meillä on

Huomaa, että eriarvoisuus edellisestä lausekkeesta on johdonmukaisuusehto matriisin ja vektorin normille. Jos , silloin minkä tahansa alkuperäisen virhevektorin (tai muuten, minkä tahansa alkuvektorin) virhesuhteella ei ole taipumusta nollata hitaammin kuin geometrinen eteneminen nimittäjällä .

Jos valitsemme normin matriisinormiksi tai sitten yksinkertaisen iteraatiomenetelmän konvergenssikysymyksen ratkaisemiseksi voidaan käyttää lauseen 1 seurausta: yksinkertainen iterointimenetelmä konvergoi, jos jokin seuraavista ehdoista täyttyy matriisille:

, i = 1,2, …, n,

, j = 1, 2, …, n.(2.11)

Yksinkertaisin ja yleisin tapa tuoda järjestelmä Ax=b muotoon (2.9), joka on kätevä iteraatioille, on diagonaalielementtien valinta jokaisen kanssa i-th yhtälö on ratkaistu suhteessa i-th tuntematon:

, i = 1, 2, …, n, (2.12)

ja yksinkertainen iterointimenetelmä voidaan kirjoittaa muodossa

Matriisilla on sitten muoto

.

Tämän matriisin elementti voidaan kirjoittaa muodossa missä on Kronecker-symboli. Tässä tapauksessa riittävä ehto yksinkertaisen iterointimenetelmän konvergenssille voidaan muotoilla matriisin diagonaalisten elementtien dominanssin ehdoksi. MUTTA, joka seuraa lausekkeesta (2.11) ja matriisin merkinnästä, ts.

i = 1, 2, …, n.

Korostamme vielä kerran, että iterointimenetelmän konvergenssin ehdon tarkastelut muodot ovat vain riittäviä. Niiden toteutus takaa menetelmän konvergenssin, mutta niiden epäonnistuminen ei yleensä tarkoita yksinkertaisen iterointimenetelmän hajoamista. Yksinkertaisen iterointimenetelmän konvergenssin välttämätön ja riittävä ehto on ehto, että kokonaislukuosa (missä on matriisin modulo-ominaisarvo MUTTA); tätä ehtoa käytetään harvoin laskennallisessa käytännössä.

Siirrytään kysymykseen ratkaisun virheen arvioimisesta. Mielenkiintoisia ovat kaksi relaatiota ratkaisun virheen estimoimiseksi: ensimmäinen suhteuttaa virheen normin kahden peräkkäisen approksimoinnin eron normiin ja sitä voidaan käyttää virheen estimoimiseen vain laskentaprosessissa; toinen liittää virheen normin alkuperäisen approksimoinnin vektorin ja vapaan termin vektorin normeihin järjestelmässä (2.9). Tarvittavat suhteet annetaan seuraavilla kahdella lauseella.

LAUSE 2. Jos jokin matriisin normi on yhdenmukainen vektorin tarkastellun normin kanssa X

. (2.13)

TODISTE. Vähennetään tasa-arvo (2.10) tasa-arvosta:

Vähentämällä molemmista osista approksimaatioarvo , muunnetaan tämä suhde muotoon

Normeihin siirtymällä saamme

Koska lauseen hypoteesin mukaan

Käyttämällä suhdetta, josta se seuraa vihdoin saamme:

LAUSE 3. Jos mikä tahansa normi on matriisi, joka on yhdenmukainen vektorin tarkastelun normin kanssa X, vähemmän kuin yksi (), silloin tapahtuu seuraava virhearvio:

Tehdään kaksi huomautusta. Ensinnäkin relaatio (2.13) voidaan kirjoittaa muodossa

joka mahdollistaa virhearvion saamisen kahden ensimmäisen iteraation tulosten perusteella. Ensinnäkin iterointimenetelmää käytettäessä on joskus suositeltavaa käyttää kahden peräkkäisen approksimoinnin eron normia laskentavirheen estimaatina. Virheen korrelaatioista seuraa, että tämä ei yleensä pidä paikkaansa. Jos normi on lähellä yksikköä, niin kerroin at voi olla melko suuri.

Peräkkäisten iteraatioiden virheet liittyvät suhteeseen

nuo. virhe muuttuu lineaarisesti askel kerrallaan. Menetelmällä sanotaan olevan lineaarinen konvergenssi tai ensimmäisen asteen konvergenssi. Vaaditun tarkkuuden saavuttamiseksi tarvittavien iteraatioiden määrä riippuu kuitenkin arvosta ja alkuperäisestä approksimaatiosta.

Siten, käyttämällä esimerkkinä yksinkertaista iteraatiomenetelmää, esitetään iteratiivisten menetelmien kolme vaihetta: kaavan (1.10) muodostaman vektorin sekvenssin rakentaminen; konvergenssiehdon määrittäminen Lauseen 1 mukaan ja konvergenssinopeuden estimaatti lauseiden 2 ja 3 avulla.

Seidelin menetelmä

Yksinkertainen iterointimenetelmä ei käytä ilmeisen ilmeistä mahdollisuutta parantaa iteratiivisen prosessin konvergenssia - vektorin äskettäin laskettujen komponenttien välitöntä sisällyttämistä laskelmaan. Tätä mahdollisuutta käytetään iteratiivisessa Seidel-menetelmässä. Iteratiivinen prosessi järjestelmälle (2.9) suoritetaan tässä tapauksessa suhteessa

i = 1, 2, …, n (2.14)

tai järjestelmälle (1.1)

Menemättä yksityiskohtiin huomaamme, että Seidelin iteraatiomenetelmä todellakin johtaa usein nopeampaan konvergenssiin kuin yksinkertainen iterointimenetelmä. On kuitenkin tapauksia, joissa Seidelin iteraatiomenetelmä konvergoi hitaammin kuin yksinkertainen iterointimenetelmä, ja jopa tapauksia, joissa yksinkertainen iteraatiomenetelmä konvergoi, mutta Seidel-iteroitumismenetelmä eroaa.

Ota huomioon, että Seidelin menetelmä konvergoi, jos matriisi MUTTA positiivinen määrätty ja symmetrinen.

Osoitetaan, että Seidelin iteraatiomenetelmä vastaa jotakin yksinkertaista iterointimenetelmää, jossa on erityisesti muodostettu matriisi ja vektori suhteessa (2.10). Tätä varten kirjoitamme järjestelmän (2.14) muotoon Matriisi (E-H) on alempi kolmiomatriisi, jonka diagonaaliset elementit ovat yhtä suuret kuin yksi. Siksi tämän matriisin determinantti on nollasta poikkeava (yksi) ja sillä on käänteinen matriisi. Sitten

Vertaamalla tätä suhdetta ratkaisuun (2.10), voimme päätellä, että Seidelin iteraatiomenetelmä on todellakin sama kuin yksinkertainen iterointimenetelmä siinä mielessä, että Seidelin iterointimenetelmän ehdon ja konvergenssikriteerin määrittämiseen voidaan käyttää annettuja lauseita. yksinkertaiselle iteraatiomenetelmälle, jos asetamme Iteratiivinen prosessi järjestelmälle (2.12) voidaan kirjoittaa myös yleisemmässä muodossa, nimittäin

Olkoon n:n algebrallisen yhtälön järjestelmä, jossa on n tuntematonta:

Yksinkertainen iterointimenetelmän algoritmi:

Huomaa, että tässä ja jatkossa alaindeksi tarkoittaa tuntemattomien vektorin vastaavaa komponenttia ja yläindeksi iteraatio- (approksimaatio) numeroa.

Sitten muodostuu syklinen matemaattinen prosessi, jonka jokainen sykli edustaa yhtä iteraatiota. Jokaisen iteraation tuloksena saadaan uusi tuntemattomien vektorin arvo. Iteratiivisen prosessin järjestämiseksi kirjoitamme järjestelmän (1) yllä olevaan muotoon. Tässä tapauksessa päälävistäjän termit normalisoidaan ja jäävät yhtäläisyysmerkin vasemmalle puolelle, kun taas loput siirretään oikealle puolelle. Supistettu yhtälöjärjestelmä näyttää:

huomaa, että ei koskaan saavuteta, mutta jokaisella seuraavalla iteraatiolla tuntemattomien vektori tulee lähemmäs tarkkaa ratkaisua.

12. Pääasiallinen iteraatiokaava, jota käytetään yksinkertaisessa iteraatiomenetelmässä epälineaarisen yhtälön ratkaisemiseksi:

13. Kriteeri iteratiivisen prosessin pysäyttämiseksi yksinkertaisessa iteraatiomenetelmässä epälineaarisen yhtälön ratkaisemiseksi:

Iteratiivinen prosessi päättyy, jos tuntemattomien vektorin jokaiselle i:nnelle komponentille tarkkuuden saavuttamisen ehto täyttyy.
huomaa, että tarkka ratkaisu yksinkertaisella iteraatiomenetelmällä ei koskaan saavuteta, mutta jokaisen seuraavan iteroinnin myötä tuntemattomien vektori lähestyy ja lähempänä tarkkaa ratkaisua

14. Kriteerit apufunktion F(x) valinnalle intervallin iteraatiosegmentille:

Kun suoritetaan matemaattista testiä yksinkertaisen iteraatiomenetelmän ratkaisemiseksi, on ensin tarkistettava konvergenssiehto. Menetelmän lähentämiseksi on välttämätöntä ja riittävää, että matriisissa A kaikkien diagonaalisten elementtien absoluuttiset arvot ovat suuremmat kuin kaikkien muiden vastaavien rivien elementtien moduulien summa:

Iteratiivisten menetelmien haitta Tämä on melko tiukka konvergenssiehto, joka ei suinkaan täyty kaikille yhtälöjärjestelmille.

Jos konvergenssiehto täyttyy, niin seuraavassa vaiheessa on tarpeen asettaa tuntemattomien vektorin alkuperäinen approksimaatio, joka on yleensä nollavektori:

15. Lineaaristen yhtälöjärjestelmien ratkaisemiseen käytetty Gaussin menetelmä tarjoaa:

Menetelmä perustuu matriisin muuntamiseen kolmiomuotoon. Tämä saavutetaan eliminoimalla peräkkäin tuntemattomat järjestelmän yhtälöistä.

Yksinkertaisen iteroinnin menetelmä, jota kutsutaan myös peräkkäisen approksimoinnin menetelmäksi, on matemaattinen algoritmi tuntemattoman suuren arvon löytämiseksi sitä asteittain tarkentamalla. Tämän menetelmän ydin on, että nimensä mukaisesti ilmaistamalla vähitellen seuraavat alkuperäisestä approksimaatiosta ne saavat yhä tarkempia tuloksia. Tätä menetelmää käytetään muuttujan arvon löytämiseen tietyssä funktiossa sekä yhtälöjärjestelmien, sekä lineaaristen että epälineaaristen, ratkaisemiseen.

Tarkastellaanpa, kuinka tämä menetelmä toteutetaan SLAE:tä ratkaistaessa. Yksinkertaisella iteraatiomenetelmällä on seuraava algoritmi:

1. Alkuperäisen matriisin konvergenssiehdon todentaminen. Konvergenssilause: jos järjestelmän alkuperäisellä matriisilla on diagonaalidominanssi (eli jokaisella rivillä päädiagonaalin elementtien on oltava suurempia moduloiltaan kuin sivudiagonaalien elementtien summa modulossa), niin yksinkertainen menetelmä iteraatiot on konvergenttia.

2. Alkuperäisen järjestelmän matriisilla ei aina ole diagonaalista dominanssia. Tällaisissa tapauksissa järjestelmä voidaan muuntaa. Yhtälöt, jotka täyttävät konvergenssiehdon, jätetään koskemattomiksi, ja niiden kanssa, jotka eivät tyydy, ne muodostavat lineaarisia yhdistelmiä, ts. kerro, vähennä, lisää yhtälöitä toisiinsa, kunnes saadaan haluttu tulos.

Jos tuloksena olevassa järjestelmässä päälävistäjällä on epämukavia kertoimia, niin tällaisen yhtälön molempiin osiin lisätään muotoa c i *x i olevat termit, joiden etumerkkien on oltava samat diagonaalielementtien etumerkkien kanssa.

3. Tuloksena olevan järjestelmän muuntaminen normaalimuotoon:

x - =β - +α*x -

Tämä voidaan tehdä monella tavalla, esimerkiksi seuraavasti: ilmaista ensimmäisestä yhtälöstä x 1 muiden tuntemattomien suhteen, toisesta - x 2, kolmannesta - x 3 jne. Tässä käytämme kaavoja:

α ij = -(a ij / a ii)

i = b i /a ii
Sinun tulee jälleen varmistaa, että tuloksena oleva normaalimuotoinen järjestelmä täyttää konvergenssiehdon:

∑ (j=1) |α ij |≤ 1, kun taas i= 1,2,...n

4. Alamme itse asiassa soveltaa itse peräkkäisten approksimaatioiden menetelmää.

x (0) - alkuperäinen approksimaatio, ilmaisemme sen kautta x (1) , sitten x (1):n kautta x (2) . Yleinen kaava matriisimuodossa näyttää tältä:

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

Laskemme, kunnes saavutamme vaaditun tarkkuuden:

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

Katsotaanpa siis yksinkertaista iterointimenetelmää käytännössä. Esimerkki:
Ratkaise SLAE:

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

Katsotaan, hallitsevatko diagonaaliset elementit moduloa.

Näemme, että vain kolmas yhtälö täyttää konvergenssiehdon. Muunnamme ensimmäisen ja toisen yhtälön, lisäämme toisen ensimmäiseen yhtälöön:

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

Vähennä ensimmäinen kolmannesta:

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

Olemme muuntaneet alkuperäisen järjestelmän vastaavaksi:

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

Palautetaan nyt järjestelmä normaaliksi:

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

Tarkistamme iteratiivisen prosessin konvergenssin:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319 = 0,9149 ≤ 1, so. ehto täyttyy.

0,3947
Alkuarvio x(0) = 0,4762
0,8511

Korvaamalla nämä arvot normaalimuotoyhtälöön, saamme seuraavat arvot:

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

Korvaamalla uusia arvoja saamme:

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

Jatkamme laskelmia, kunnes pääsemme lähemmäksi arvoja, jotka täyttävät annetun ehdon.

x(7) = 0,441091

Tarkistamme saatujen tulosten oikeellisuuden:

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

Tulokset, jotka saatiin korvaamalla löydetyt arvot alkuperäisiin yhtälöihin, täyttävät täysin yhtälön ehdot.

Kuten näemme, yksinkertainen iterointimenetelmä antaa melko tarkat tulokset, mutta tämän yhtälön ratkaisemiseen jouduimme viettämään paljon aikaa ja tekemään hankalia laskelmia.