Eenvoudige iteratiemethode met optimale parameter. Iteratieve methoden voor het oplossen van het slough

De eenvoudige iteratiemethode, ook wel de methode genoemd opeenvolgende benadering, - Deze wiskundig algoritme de waarde van een onbekende hoeveelheid vinden door deze geleidelijk te verfijnen. De essentie van deze methode is dat, zoals de naam al aangeeft, door de volgende geleidelijk uit te drukken vanaf de initiële benadering, ze steeds meer verfijnde resultaten krijgen. Deze methode wordt gebruikt om de waarde van een variabele in . te vinden gegeven functie, evenals bij het oplossen van stelsels van vergelijkingen, zowel lineair als niet-lineair.

Overweeg hoe: deze methode wordt gerealiseerd bij het oplossen van de SLAE. De eenvoudige iteratiemethode heeft het volgende algoritme:

1. Verificatie van de convergentievoorwaarde in de oorspronkelijke matrix. Convergentiestelling: als de oorspronkelijke matrix van het systeem diagonale dominantie heeft (d.w.z. in elke rij moeten de elementen van de hoofddiagonaal groter zijn in modulus dan de som van de elementen van de secundaire diagonalen in modulo), dan is de methode eenvoudige iteraties- convergeren.

2. De matrix van het oorspronkelijke systeem heeft niet altijd diagonale dominantie. In dergelijke gevallen kan het systeem worden omgebouwd. Vergelijkingen die voldoen aan de convergentievoorwaarde blijven onaangeroerd, en met vergelijkingen die dat niet doen, vormen ze lineaire combinaties, d.w.z. vermenigvuldigen, aftrekken, vergelijkingen bij elkaar optellen totdat het gewenste resultaat is verkregen.

Als er in het resulterende systeem onhandige coëfficiënten zijn op de hoofddiagonaal, dan worden termen van de vorm c i * x i toegevoegd aan beide delen van een dergelijke vergelijking, waarvan de tekens moeten samenvallen met de tekens van de diagonale elementen.

3. Transformatie van het resulterende systeem naar de normaalvorm:

x - =β - +α*x -

Dit kan op veel manieren, bijvoorbeeld als volgt: uit de eerste vergelijking x 1 in termen van andere onbekenden, uit de tweede - x 2, uit de derde - x 3, enz. Hier gebruiken we de formules:

α ij = -(a ij / een ii)

ik = b ik / een ii
Je moet er opnieuw voor zorgen dat het resulterende systeem van normaalvorm voldoet aan de convergentievoorwaarde:

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

4. We beginnen in feite de methode van opeenvolgende benaderingen zelf toe te passen.

x (0) - initiële benadering, we drukken er doorheen x (1) , dan drukken we door x (1) uit x (2) . Algemene formule a matrixvorm ziet eruit als:

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

We rekenen tot we de vereiste nauwkeurigheid hebben bereikt:

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

Laten we dus eens kijken naar de eenvoudige iteratiemethode in de praktijk. Voorbeeld:
SLAE oplossen:

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1.8x1+2.5x2+4.7x3=4 met nauwkeurigheid ε=10 -3

Laten we eens kijken of de diagonale elementen modulo overheersen.

We zien dat alleen de derde vergelijking voldoet aan de convergentievoorwaarde. We transformeren de eerste en tweede vergelijking, voegen de tweede toe aan de eerste vergelijking:

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

Trek de eerste van de derde af:

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

We hebben het oorspronkelijke systeem omgezet in een gelijkwaardig systeem:

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

Laten we het systeem nu weer normaal maken:

x1=0.3947-0.0789x2-0.3158x3
x2=0,4762+0,6429x1-0,2857x3
x3= 0,8511-0,383x1-0,5319x2

We controleren de convergentie van het iteratieve proces:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1 , d.w.z. de voorwaarde is voldaan.

0,3947
Initiële gok x(0) = 0,4762
0,8511

Als we deze waarden in de vergelijking van de normaalvorm vervangen, krijgen we de volgende waarden:

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

Als we nieuwe waarden substitueren, krijgen we:

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

We gaan door met de berekeningen totdat we dichter bij de waarden komen die aan de gegeven voorwaarde voldoen.

x(7) = 0,441091

Laten we de juistheid van de verkregen resultaten controleren:

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

De resultaten die worden verkregen door de gevonden waarden in de oorspronkelijke vergelijkingen te vervangen, voldoen volledig aan de voorwaarden van de vergelijking.

Zoals we kunnen zien, geeft de eenvoudige iteratiemethode behoorlijk nauwkeurige resultaten Om deze vergelijking op te lossen, moesten we echter veel tijd besteden en omslachtige berekeningen uitvoeren.

Overwegen lineair algebraïsche vergelijkingen

Laten we er een paar uitgeven equivalente transformaties. We vermenigvuldigen beide delen van het systeem met dezelfde scalaire factor en voegen een vector toe aan de rechter en linker delen van het systeem. Het systeem van vergelijkingen kan nu worden geschreven in een vorm die handig is voor iteraties:

(2.15)

Laten we nu een reeks benaderingen construeren voor de oplossing van het systeem. We kiezen een willekeurige vector - de initiële benadering van de oplossing. Meestal wordt eenvoudigweg aangenomen dat het een nulvector is. Hoogstwaarschijnlijk voldoet de initiële benadering niet aan (2.15) en dus niet aan het oorspronkelijke systeem. Wanneer het wordt gesubstitueerd in de oorspronkelijke vergelijking, ontstaat er een discrepantie. Door de discrepantie te berekenen, met behulp van (2.15), kunnen we de benadering van de oplossing verfijnen, ervan uitgaande dat

Volgens de eerste benadering wordt de discrepantie opnieuw berekend, het proces gaat verder. In de loop van de iteratie verkrijgen we een equivalente formulering van de methode genaamd eenvoudige iteratiemethode, is als volgt. Oplossing (2.15) wordt gevonden als de limiet van de reeks benaderingen, waarvan de termen zijn verbonden door een recursieve relatie (deze is gelijk aan die hierboven, de residuele vector is uitgesloten van de notatie):

(2.16)

(of wat dan ook) willekeurige vector). Als de limiet van zo'n rij bestaat, dan spreekt men van convergentie iteratief proces naar de oplossing van SLAE.

Er zijn andere vormen van het schrijven van de iteratiemethode, zoals:

Voor , de laatste formule komt overeen met het iteratieve proces met één parameter dat hierboven is besproken eenvoudige iteratiemethode. Voor , - n -stap expliciet iteratief proces, voor , - eenvoudige iteratiemethode zonder iteratieparameter. In het geval wanneer, iteratieve methode genaamd impliciet- voor berekening volgende benadering Om het op te lossen, moet je een (meestal eenvoudiger dan het originele) stelsel lineaire vergelijkingen oplossen.

Stelling ( voldoende voorwaarde convergentie eenvoudige iteratiemethode). Het iteratieve proces (2.16) convergeert naar de oplossing van de SLAE met de snelheid geometrische voortgang wanneer aan de voorwaarde is voldaan:

Bewijs.

Laat de exacte oplossing van systeem (2) zijn. Door af te trekken van (2.16)-(2.15) krijgen we , of, waarmee de fout wordt aangeduid , verkrijgen we de vergelijking voor de evolutie van de fout De keten van ongelijkheden is geldig: , waar

Hieruit volgt dat wanneer

van ongelijkheid men kan een schatting krijgen van het aantal iteraties dat nodig is om nauwkeurigheid te bereiken, d.w.z. om aan de voorwaarde te voldoen Deze schatting heeft de vorm

Stelling (convergentiecriterium) eenvoudige iteratiemethode (geen bewijs)). Laat SLAE (2.15) een unieke oplossing hebben. Dan is het voor de convergentie van het iteratieve proces (2.16) noodzakelijk en voldoende dat alle eigenwaarden matrices door absolute waarde waren minder dan één.

Vergelijk in hoeveelheid rekenkundige bewerkingen direct en iteratieve methoden. De Gauss-methode zonder het hoofdelement te kiezen vereist:

rekenkundige bewerkingen; eenvoudige iteratiemethode (2.16) , waarbij i het aantal benaderingen is dat nodig is om de gegeven nauwkeurigheid te bereiken. Dus, voor I< n/3 метод итераций становится предпочтительнее. В echte taken, in principe, bovendien iteratieve methoden kan efficiënter worden gemaakt door de iteratieparameters te wijzigen. In sommige gevallen iteratieve methoden blijken stabieler te zijn met betrekking tot de accumulatie van afrondingsfouten dan rechte lijnen.

Hoorcollege Iteratieve methoden voor het oplossen van een stelsel algebraïsche lineaire vergelijkingen.

Convergentievoorwaarde van het iteratieve proces Jacobi-methode Seidel-methode

Eenvoudige iteratiemethode

Het systeem van lineaire algebraïsche vergelijkingen wordt beschouwd

Om iteratieve methoden toe te passen, moet het systeem worden teruggebracht tot een equivalente vorm

Vervolgens wordt de initiële benadering van de oplossing van het stelsel vergelijkingen gekozen en wordt een reeks benaderingen van de wortel gevonden.

Om het iteratieve proces te laten convergeren, is het voldoende dat de voorwaarde
(matrixnorm). Het beëindigingscriterium voor iteraties is afhankelijk van de toegepaste iteratieve methode.

Jacobi-methode .

De eenvoudigste manier om het systeem in een vorm te brengen die geschikt is voor iteratie is als volgt:

Uit de eerste vergelijking van het systeem drukken we het onbekende uit x 1, uit de tweede vergelijking van het systeem dat we uitdrukken x 2, enz.

Als resultaat krijgen we een stelsel vergelijkingen met matrix B, waarin nul elementen op de hoofddiagonaal staan, en de overige elementen worden berekend met de formules:

De componenten van de vector d worden berekend met de formules:

De berekeningsformule van de eenvoudige iteratiemethode is:

of in coördinatennotatie ziet er als volgt uit:

Het criterium voor het beëindigen van iteraties in de Jacobi-methode heeft de vorm:

Als een
, dan kan een eenvoudiger criterium voor het beëindigen van iteraties worden toegepast

voorbeeld 1 Oplossing van een stelsel lineaire vergelijkingen volgens de Jacobi-methode.

Laat het stelsel vergelijkingen worden gegeven:

Het is vereist om met nauwkeurigheid een oplossing voor het systeem te vinden

We brengen het systeem in een vorm die handig is voor iteratie:

We kiezen voor een initiële benadering, bijvoorbeeld

is de vector van de rechterkant.

Dan ziet de eerste iteratie er als volgt uit:

De volgende benaderingen van de oplossing worden op soortgelijke wijze verkregen.

Vind de norm van de matrix B.

We zullen de norm gebruiken

Aangezien de som van de modules van de elementen in elke rij 0,2 is, dan is
, dus het criterium voor het beëindigen van iteraties in dit probleem is

Laten we de normen van de verschillen van vectoren berekenen:

Als
de gespecificeerde nauwkeurigheid wordt bereikt bij de vierde iteratie.

Antwoord: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1

Seidel-methode: .

De methode kan worden beschouwd als een wijziging van de Jacobi-methode. Het belangrijkste idee is dat bij het berekenen van de volgende (n+1)-de benadering van het onbekende x i Bij ik>1 gebruik al gevonden (n+1)- naderen van het onbekende x 1 ,x 2 , ...,x ik - 1, niet n de benadering, zoals in de Jacobi-methode.

De berekeningsformule van de methode in de coördinatengewijze notatie ziet er als volgt uit:

De convergentievoorwaarden en het terminatiecriterium voor iteraties kunnen op dezelfde manier worden genomen als bij de Jacobi-methode.

Voorbeeld 2 Systemen van lineaire vergelijkingen oplossen met de Seidel-methode.

Beschouw parallel de oplossing van 3 stelsels vergelijkingen:

We brengen de systemen in een vorm die geschikt is voor iteraties:

Merk op dat de convergentievoorwaarde
alleen uitgevoerd voor het eerste systeem. We berekenen in elk geval 3 eerste benaderingen van de oplossing.

1e systeem:

De exacte oplossing zijn de waarden: x 1 = 1.4, x 2 = 0.2 . Het iteratieve proces convergeert.

2e systeem:

Het is te zien dat het iteratieve proces divergeert.

Exacte oplossing x 1 = 1, x 2 = 0.2 .

3e systeem:

Het is te zien dat het iteratieve proces een lus vormt.

Exacte oplossing x 1 = 1, x 2 = 2 .

Laat de matrix van het stelsel vergelijkingen A symmetrisch en positief bepaald zijn. Dan, voor elke keuze van de initiële benadering, convergeert de Seidel-methode. Aanvullende voorwaarden aan de kleinheid van de norm van een bepaalde matrix worden hier niet gesteld.

Eenvoudige iteratiemethode.

Als A een symmetrische en positief bepaalde matrix is, wordt het stelsel vergelijkingen vaak teruggebracht tot een equivalente vorm:

x=x-τ(A x- b), τ is een iteratieve parameter.

De berekeningsformule van de eenvoudige iteratiemethode is in dit geval:

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

en de parameter τ > 0 is zo gekozen dat, indien mogelijk, de minimumwaarde

Laat λ min en λ max de minimale en maximale eigenwaarden zijn van de matrix A. De optimale keuze is de parameter

In dit geval
accepteert minimale waarde gelijk aan:

Voorbeeld 3 Systemen van lineaire vergelijkingen oplossen door eenvoudige iteratie. (in MathCAD)

Laat het stelsel vergelijkingen Ax = b

Een iteratief proces bouwen vind onze eigen aantallen matrix A:

- gebruikt een ingebouwde functie om eigenwaarden te vinden.

Bereken de iteratieve parameter en controleer de convergentievoorwaarde

Aan de convergentievoorwaarde is voldaan.

Laten we de initiële benadering nemen - de vector x0, de nauwkeurigheid instellen op 0,001 en de initiële benaderingen vinden met behulp van het onderstaande programma:

Exacte oplossing

Commentaar. Als het programma de matrix rez retourneert, kunt u alle gevonden iteraties bekijken.

1. Laat een segment weten dat één wortel van de vergelijking f(x) = 0 bevat. De functie f is een continu differentieerbare functie op dit segment (f(x)нC 1 ). Als aan deze voorwaarden is voldaan, kan de eenvoudige iteratiemethode worden gebruikt.

2. Op basis van de functie f(x) wordt een functie j(x) geconstrueerd die aan drie voorwaarden voldoet: hij moet continu differentieerbaar zijn (j(x)нC 1 ), zodat de vergelijking x = j(x) is gelijk aan de vergelijking f(x)=0; zou ook segment vertalen in jezelf.

We zullen zeggen dat de functie j ( x ) vertaalt het segment [ a , b ] in zichzelf als voor enige x Î [ a , b ], ja = j ( x ) hoort ook bij[ a , b ] ( ja Î [ a , b ]).

De derde voorwaarde wordt gesteld aan de functie j(x):

Methode formule: x n +1 = j(xn).

3. Wanneer aan deze drie voorwaarden is voldaan, geldt voor elke initiële benadering x 0 н reeks iteraties x n +1 = j(x n) convergeert naar de wortel van de vergelijking: x = j(x) op het segment ().

In de regel als x 0 een van de uiteinden is geselecteerd.

,

waarbij e de gespecificeerde nauwkeurigheid is

Getal x n +1 onder de voorwaarde van het stoppen van het iteratieve proces is geschatte waarde van de wortel van de vergelijking f(x) = 0 op het segment , gevonden door de methode van eenvoudige iteratie met nauwkeurigheid e .

Bouw een algoritme voor het verfijnen van de wortel van de vergelijking: x 3 + 5x - 1 = 0 op het segment door eenvoudige iteratie met nauwkeurigheid e .

1. Functie f(x) = x 3 +5x-1 is continu differentieerbaar op een segment dat één vergelijkingswortel bevat.

2. De grootste moeilijkheid bij de eenvoudige iteratiemethode is de constructie van een functie j(x) die aan alle voorwaarden voldoet:

Overwegen: .

vergelijking x = j1 (x) is equivalent aan de vergelijking f(x) = 0, maar de functie j 1 (x) is niet continu differentieerbaar op het interval .

Rijst. 2.4. Grafiek van functie j 2 (x)

Aan de andere kant dus. Vandaar: is een continu differentieerbare functie. Merk op dat de vergelijking: x = j 2 (x) equivalent is aan de vergelijking f(x) = 0 . Uit de grafiek (Fig. 2.4) blijkt dat de functie j 2 (x) het segment in zichzelf vertaalt.

De voorwaarde dat de functie j(x) het segment in zichzelf transformeert, kan als volgt worden geherformuleerd: laat het domein zijn van de functie j(x), en het domein van j(x).

Als het segment bij het segment hoort, dan neemt de functie j(x) het segment in zich op.

, .

Aan alle voorwaarden voor de functie j(x) is voldaan.

Formule van het iteratieve proces: x n +1 = j 2(xn).

3. Initiële benadering: x 0 = 0.

4. Voorwaarde voor het stoppen van het iteratieve proces:

Rijst. 2.5. meetkundig gevoel eenvoudige iteratiemethode

.

Wanneer aan deze voorwaarde is voldaan, x n +1 – geschatte waarde van de wortel op het segment, gevonden door eenvoudige iteratie met nauwkeurigheid e. Op afb. 2.5. de toepassing van de eenvoudige iteratiemethode wordt geïllustreerd.

Convergentiestelling en foutenschatting

Laat het segment bevat één wortel van de vergelijking x = j(x), functie j(x ) is continu differentieerbaar op het segment , vertaalt het segment in zichzelf, en de conditie:

.

Dan voor elke initiële benadering x 0 vervolg convergeert naar de wortel van de vergelijking ja = j(x ) op het segment en de foutschatting:

.

Stabiliteit van de eenvoudige iteratiemethode. Onder de voorwaarden van de convergentiestelling is het algoritme van de eenvoudige iteratiemethode stabiel.

De complexiteit van de eenvoudige iteratiemethode. De hoeveelheid computergeheugen die nodig is om de eenvoudige iteratiemethode te implementeren, is verwaarloosbaar. Bij elke stap moet u x n . opslaan , x n +1 , q en e.

Laten we een schatting maken van het aantal rekenkundige bewerkingen dat nodig is om de eenvoudige iteratiemethode te implementeren. Laten we een schatting schrijven voor het getal n 0 = n 0 (e) zodat voor alle n ³ n 0 de volgende ongelijkheid geldt:

Uit deze schatting volgt dat hoe dichter q bij de eenheid ligt, hoe langzamer de methode convergeert.

Commentaar. Bestaat niet algemene regel j(x) construeren uit f(x) op zo'n manier dat aan alle voorwaarden van de convergentiestelling wordt voldaan. De volgende benadering wordt vaak gebruikt: de functie j wordt gekozen als de functie j(x) = x + k × f(x), waarbij k – constante.

Bij het programmeren van een eenvoudige iteratiemethode moet voor het stoppen van een iteratief proces vaak aan twee voorwaarden tegelijk worden voldaan:

en .

Alle andere iteratieve methoden die we zullen beschouwen, zijn speciale gevallen van de eenvoudige iteratiemethode. Bijvoorbeeld, wanneer? De methode van Newton is een speciaal geval van de eenvoudige iteratiemethode.

In deze sectie beschouwen we een stationair iteratieproces wanneer de matrix en iteratieparameter niet afhankelijk zijn van de index , en bewijs de volgende stelling op voldoende voorwaarden voor de convergentie.

Stelling van Samarsky

laten zijn is een self-adjunct positief bepaalde matrix:

,
,

is een positief bepaalde matrix, - positief nummer:

,
.

Dan voor elke keuze van nul benadering een iteratief proces dat wordt gedefinieerd door de recursieve formule , convergeert naar de oplossing van het oorspronkelijke systeem.

Laten we, voordat we overgaan tot het bewijs van de stelling, de belangrijkste vereiste ervan, de positieve bepaaldheid van de matrix, in meer detail bespreken.
. Deze eis kan worden herschreven als:

,
,
.

d.w.z. in het bijzonder wordt ervan uitgegaan dat de matrix is positief bepaald. Bovendien bepaalt de ongelijkheid het interval waarin de parameter kan veranderen :

.

Na deze opmerkingen gaan we over tot het bewijs van de stelling. Laten we uitdrukken vanuit de relatie door :

en substitueer in de terugkerende formule voor de iteratieve reeks. Als resultaat krijgen we:

.

Het verschil tussen de iteratieve formule en is dat deze homogeen is.

Matrix is positief bepaald. Daarom is het niet-gedegenereerd en heeft het een inverse
. Met haar hulp herhalingsrelatie kan worden opgelost met betrekking tot
:

, dus
.

Beide zijden van de gelijkheid aan de linkerkant vermenigvuldigen met de matrix , krijgen we nog een herhalingsrelatie

.

Overweeg de volgorde van positieve functionalen:

.

Laten we een soortgelijke uitdrukking samenstellen voor
en transformeer het met behulp van terugkerende formules en:

Van de zelf-adjunctheid van de matrix en de formules volgen

Als resultaat heeft de formule de vorm:

Dus de volgorde van functionalen onder de voorwaarde
vormt een monotoon niet-toenemende reeks van onderaf begrensd door nul

.

,

waar
is een strikt positieve constante. Dientengevolge, volgens en zullen we hebben

Van deze ongelijkheid en de convergentie van de rij van functionalen volgt dat
Bij
. Op zijn beurt
, dus

De stelling is bewezen.

1. Eenvoudige iteratiemethode.

Deze naam werd gegeven aan de methode waarin, als matrix de identiteitsmatrix is ​​gekozen:
, en de iteratieve parameter verondersteld onafhankelijk te zijn van het iteratiegetal . Met andere woorden, de eenvoudige iteratiemethode is een expliciete stationaire methode wanneer de volgende iteratie
wordt berekend door de recursieve formule

We nemen aan dat de matrix voldoet aan de voorwaarde van de stelling van Samarskii,
, dan de formule die de grens bepaalt van het convergentie-interval met betrekking tot de iteratieve parameter , neemt de vorm aan

.

laten zijn
- orthonormale basis van eigenvectoren van de operator die overeenkomt met de matrix . Door positieve bepaaldheid zijn al zijn eigenwaarden positief. Laten we ze in aflopende volgorde genummerd beschouwen:

Laten we de vector ontleden
volgens de basis van eigenvectoren

Als resultaat volgt uit de formule dat de eenvoudige iteratiemethode convergeert voor elke behorend tot het interval

.

We zullen een verdere studie van de eenvoudige iteratiemethode bouwen op een specifieke analyse van de recursieve formule. Laten we de transitie-operatormatrix introduceren

,

en herschrijf de formule als

.

Tegelijkertijd is de fout
zal voldoen aan een vergelijkbare herhalingsrelatie, alleen homogeen

.

Laten we twee lemma's bewijzen die ons in staat stellen de voorwaarden voor de convergentie van de eenvoudige iteratiemethode vollediger te onderzoeken.

Lemma 1

Laat de operator die de matrix genereert , heeft een eigenvector met eigenwaarde , dan de transitie-operator gegenereerd door de matrix , heeft ook een eigenvector , maar met eigen waarde

.

Het bewijs is elementair. Het wordt uitgevoerd door directe verificatie

Voor een zelf-adjunct-matrix Matrix is ook zelf-adjunct. Daarom wordt de norm bepaald door de grootste eigenwaarde in absolute waarde
:

.

Lemma 2

Om de eenvoudige iteratiemethode te laten convergeren naar de oplossing van het systeem voor elke keuze van initiële benadering, is het noodzakelijk en voldoende dat alle eigenwaarden van de transitie-operator waren modulo kleiner dan één:

,

geschiktheid. De voorwaarde betekent dat de norm van de matrix , volgens, zal minder zijn dan eenheid:
. Als resultaat krijgen we

Bij
.

Behoefte. Laten we aannemen dat onder de eigenwaarden vond er minstens één , die niet voldoet aan de voorwaarde van het lemma, d.w.z.

.

Laten we de nulterm van de iteratieve reeks in de vorm kiezen
, waar oplossing van het systeem, dan zal de nulterm van de foutreeks samenvallen met de eigenvector sprong operator :
. Als gevolg terugkerende formule voor de volgende leden van de reeks fouten zal de vorm aannemen:

,
.

d.w.z.
. De noodzaak om de ongelijkheid voor alle eigenwaarden te vervullen voor de convergentie van de eenvoudige iteratiemethode is bewezen.

Lemma 2 definieert het programma voor verder onderzoek naar de convergentie van de eenvoudige iteratiemethode: het is noodzakelijk om het bereik van parametervariatie in te stellen waaronder alle eigenwaarden voldoen aan de ongelijkheid. Het is gemakkelijk te doen. Op afb. 1 toont grafieken van afnemende lineaire functies
. Ze komen allemaal uit hetzelfde punt
,
en naar beneden gaan als gevolg van negatieve coëfficiënten bij , en de snelst afnemende functie
. Wanneer het betekenis krijgt
, de voorwaarde daarvoor niet langer vervuld is:

, Bij
.

Gevonden waarde is de grens van het convergentie-interval van de eenvoudige iteratiemethode

.

Deze ongelijkheid kennen we al. Het werd eerder verkregen uit de stelling van Samarskii als een voldoende voorwaarde voor convergentie. Een aanvullende analyse op basis van Lemma 2 stelt ons in staat het resultaat te verfijnen. Nu hebben we vastgesteld dat het lidmaatschap van de iteratieparameter interval is een noodzakelijke en voldoende voorwaarde voor de convergentie van de eenvoudige iteratiemethode.

Laten we ons wenden tot de studie van de convergentiesnelheid van de methode. Een schatting van de fout laat zien dat deze afneemt volgens de wet van een meetkundige progressie met een noemer

.

Beschouw afb. 2, wat ons zal helpen deze formule te analyseren. Het is vergelijkbaar met Fig. 1, alleen toont het grafieken van niet-functies
, en hun modules. bij klein alle eigenwaarden
zijn positief, en de grootste daarvan is
, die afneemt met toenemende op de laagste snelheid. Echter, het passeren van de punt
eigenwaarde
, veranderend teken, wordt negatief. Als gevolg hiervan is nu de modulus met een toename neemt niet af, maar neemt toe
de grenswaarde van eenheid nadert.

Zoek op het segment
punt , waarbij de afnemende functie
vergeleken met een toenemende functie
. Het wordt bepaald door de vergelijking

wat geeft

.

Als resultaat krijgen we:

De kleinste waarde is de matrixnorm bereikt bij
:

.

De formule laat zien dat voor een slecht geconditioneerde matrix, zelfs met de optimale keuze van de iteratieparameter
matrixnorm dicht bij de eenheid ligt, zodat de convergentie van de eenvoudige iteratiemethode in dit geval traag blijkt te zijn.

Concluderend merken we op dat de formule die de grens van het convergentie-interval bepaalt , en de formule voor de optimale waarde van de iteratieve parameter zijn in de eerste plaats van theoretisch belang. Gewoonlijk, bij het oplossen van SLAE, de grootste en kleinste karakteristieke getallen van de matrix zijn onbekend, dus bereken de hoeveelheden en vooraf niet mogelijk. Als gevolg hiervan is de iteratieve parameter vaak is het nodig om direct in het proces van berekeningen met vallen en opstaan ​​te selecteren.

Taak 2.

Beschouw een stelsel van twee vergelijkingen met twee onbekenden

en construeer er een benaderende oplossing voor met behulp van de eenvoudige iteratiemethode.

Laten we onmiddellijk de oplossing van het systeem schrijven

,
,

om het vervolgens te kunnen vergelijken met de leden van de iteratieve reeks.

Laten we ons wenden tot de oplossing van het systeem door de methode van eenvoudige iteratie. De matrix van het systeem heeft de vorm

.

Het is aan zichzelf grenzend en positief bepaald, aangezien

Laten we de karakteristieke vergelijking voor de matrix opstellen en vind zijn wortels:

,

,

Ze kunnen worden gebruikt om de grens van het convergentie-interval te bepalen en de optimale waarde van de iteratieparameter :

,
.

Om een ​​iteratieve reeks te construeren, kiezen we een waarde van de iteratieve parameter op het convergentie-interval, bijvoorbeeld,
. In dit geval heeft de terugkerende formule voor de termen van de iteratieve reeks de vorm:

, waar

Neem de eenvoudigste initiële benadering
en schrijf de eerste paar termen van de iteratieve reeks op , berekenen voor elk van hen de discrepantie
. Als resultaat krijgen we:

,
,
,

,
,
,

,
,
,

,
,
.

De norm van residuen, hoewel langzaam, maar neemt af, wat de convergentie van het proces aangeeft. Hetzelfde kan worden gezien uit de vergelijking van de termen van de iteratieve reeks met de oplossing van het systeem. Trage convergentie is te wijten aan slechte conditionaliteit van de matrix :

.