Metoda de iterație

Metodă de iterații simple pentru ecuație f.(x.) \u003d 0 este după cum urmează:

1) Ecuația inițială este convertită în minte, convenabilă pentru iterații:

x. = φ (h.). (2.2)

2) Alegeți aproximarea inițială h. 0 și calculați aproximările ulterioare pe formula iterativă
x K. = φ (x K. -1), k. =1,2, ... (2.3)

Dacă există o limită de secvență iterativă, este rădăcina ecuației f.(x.) \u003d 0, adică f.(ξ ) =0.

y. = φ (h.)

un X. 0 x. 1 x. 2 ξ. b.

Smochin. 2. Obiectul iterații

În fig. 2 prezintă procesul de obținere a unei alte aproximări prin metoda de iterație. Secvența de aproximări converge la rădăcină ξ .

Fundamentele teoretice pentru utilizarea metodei de iterație oferă următoarea teoremă.

Teorema 2.3.. Lăsați condițiile să urmeze:

1) rădăcină de ecuație h.= φ (x)aparține segmentului [ dar, b.];

2) Toate valorile funcției φ (h.) aparțin segmentului [ dar, b.], t. e. dar ≤ φ (h.)≤ B.;

3) Există un număr atât de pozitiv q.< 1 acel derivat φ "(x.) În toate punctele segmentului [ dar, b.] Satisface inegalitatea φ "(x.) | ≤ q..

1) Secvență iterativă x P.= φ (x p- 1)(n \u003d1, 2, 3, ...) converge la orice x. 0 Î [ dar, b.];

2) Limita secvenței iterative este rădăcina ecuației

x \u003d φ.(x.), adică dacă x K.\u003d ξ, apoi ξ \u003d φ (ξ);

3) în mod destul de inegalitate, caracterizând rata de convergență a unei secvențe iterative

| ξ -X K | ≤ (b-a.)× Q k.(2.4)

Evident, această teoremă pune, mai degrabă condiții dure care trebuie verificate înainte de aplicarea metodei de iterație. Dacă funcționează derivată φ (x.) Modulul este mai mare de unul, apoi procesul de iterație este divergent (figura 3).

Y. = φ (x.) y. = x.

Smochin. 3. Procesul de iterații considerate

În ceea ce privește convergența metodelor iterative, inegalitatea este pur utilizată

| x k - x k - 1 | ≤ ε . (2.5)

Metoda Horde. este de a înlocui curba w. = f.(x.) Segmentul de trecere directă prin puncte ( dar, f.(a.)) și ( b., f.(b.)) Smochin. patru). Abscisa Point Intersecție Direct cu axa OH Acceptat pentru următoarea aproximare.

Pentru a obține formula calculată a metodei Horde, vom scrie ecuația unei linii drepte care trece prin puncte ( a., f.(a.)) și ( b., f.(b.)) și echivalarea w. la zero, vom găsi h.:

Þ

Algoritmul metodei horde :

1) k. = 0;

2) Calculați următorul număr de iterație: k. = k. + 1.

Găsește următorul k.-E aproximarea cu formula:

x K.= a.- f.(a.)(b. - a.)/(f.(b.) - f.(a.)).

calculati f.(x K.);

3) Dacă f.(x K.) \u003d 0 (rădăcină găsită), apoi mergeți la clauza 5.

În cazul în care un f.(x K.) × f.(b.)\u003e 0, atunci b.= x K.In caz contrar a. = x K.;

4) Dacă | x k - x k -1 | > ε , apoi du-te la punctul 2;

5) Afișați valoarea rădăcinii x k;

cometariu. Acțiunile celui de-al treilea punct sunt similare cu acțiunile metodei de jumătate de diviziune. Cu toate acestea, în metoda horde la fiecare etapă, același capăt al segmentului (dreapta sau stânga) poate fi mutat în cazul în care graficul funcției în vecinătatea rădăcinii este convex în sus (figura 4, dar) sau concavă în jos (figura 4, b.). Prin urmare, diferența dintre aproximările adiacente este utilizată în criteriile de convergență.

Smochin. patru. Metoda Horde.

4. Metoda Newton.(tangenți)

Să presupunem că a fost găsită valoarea aproximativă a rădăcinii ecuației f.(x.) \u003d 0 și denotă-o x P.. Gata de formulă metoda Newton.pentru a determina următoarea aproximare x N. +1 poate fi obținut în două moduri.

Prima metodă exprimă semnificația geometrică metoda Newton. și este că în loc de punctul de intersecție al graficului w.= f.(x.) cu axa Boucăutăm un punct de intersecție cu axa Boutangențială pentru funcția grafică la punct ( x N., F.(x N.), așa cum se arată în fig. 5. Ecuația tangentului are forma u - F.(x N.)= f "(x N.)(x.- x N.).

Smochin. cinci. Metoda Newton (tangentă)

La punctul de intersecție al tangentei cu axa Bouvariabil w.\u003d 0. Equity. w.la zero, exprimă h.Și avem o formulă metoda tangentă :

(2.6)

A doua cale: Funcția de răspândire f.(x.) într-o serie de Taylor în vecinătatea punctului x \u003d x n:

Ne limităm termenii liniari relativ ( h.- x P.), echivalează cu zero f.(x.) și, exprimându-se necunoscută din ecuația rezultată h.denotă-o prin ea x N. +1 Obținem formula (2.6).

Acordăm condiții suficiente pentru convergența metodei Newton.

Teorema 2.4.. Lăsați pe segment [ dar, b.] Termenii sunt îndeplinite:

1) Funcția. f.(x.) și derivații săi f "(h.)și f ""(x.) continuu;

2) derivați f "(x) și f.""(x.) sunt diferite de la zero și păstrează anumite semne constante;

3) f.(a.)× F.(b.) < 0 (funcția. f.(x.) Modifică semnul pe segment).
Apoi există un segment [ α , β ] conținând rădăcina dorită a ecuației f.(x.) = 0, unde secvența iterativă (2.6) converge. Dacă ar fi aproximarea zero h. 0 Selectați punctul de frontieră [ α , β ], în care semnul funcției coincide cu semnul celui de-al doilea derivat,

acestea. F.(x. 0)× f "(x. 0)\u003e 0, apoi secvența iterativă converge în mod monoton

cometariu. Trebuie remarcat faptul că metoda coardei vine doar din partea opusă, iar ambele metode se pot completa reciproc. Posibil și combinat metoda hord-tangentă.

5. Metodă de secvență

Metoda de partiție poate fi obținută din metoda lui Newton la înlocuirea unei expresii aproximative derivate - o formulă de diferență:

, ,

. (2.7)

Formula (2.7) Sunt utilizate două aproximări anterioare x P.și x n - 1. Prin urmare, cu o aproximare inițială dată h. 0 trebuie calculată următoarea aproximare x. 1 , de exemplu, metoda Newton cu o înlocuire aproximativă a derivatului conform formulei

,

Algoritmul metodei secvențiale:

1) Valoarea inițială este dată. h. 0 și eroare ε . calculati

;

2) pentru n \u003d1, 2, ... în timp ce condiția este satisfăcută x N. – x N. -1 | > ε , calculati x p +. 1 conform formulei (2.7).

3. Metoda Horde.

Lăsați o ecuație f (x) \u003d 0, unde f (x) este o funcție continuă având un derivat al primei și a doua comenzi în intervalul (A, B). Rădăcina este considerată separată și este pe segment.

Ideea metodei coardei este că, la un decalaj suficient de mic, o curbă arc y \u003d f (x) poate fi înlocuită cu coardă și ca o valoare aproximativă a rădăcinii, ia punctul de intersecție cu axa Abscisa. Luați în considerare cazul (figura 1), când primul și al doilea derivat au aceleași semne, adică. f "(x) f ² (x)\u003e 0. Apoi ecuația coardei care trece prin puncte A0 și B are forma

Apropierea rădăcinii x \u003d x1, pentru care Y \u003d 0, este definită ca

.

În mod similar, pentru coarda care trece prin punctele A1 și B, se calculează următoarea armonizare a rădăcinilor.

.

În cazul general, formula metodei coardei are forma:

. (2)

Dacă primul și al doilea derivat au semne diferite, adică.

f "(x) f" (x)< 0,

că toate aproximările cu rădăcina X * sunt efectuate de marginea dreaptă a segmentului, așa cum se arată în fig. 2 și sunt calculate prin formula:

. (3)

Alegerea formulei din fiecare caz particult depinde de tipul de funcție f (x) și se efectuează în conformitate cu regula: este încă limita segmentului de izolare a rădăcinii, pentru care semnul funcției coincide cu semnul al doilea derivat. Formula (2) este utilizată în cazul în care F (b) f "(b)\u003e 0. Dacă inegalitatea f (a) f" (a)\u003e 0 este valabilă, atunci este recomandabil să se utilizeze formula (3).

Smochin. 1 Fig. 2.

Smochin. 3 Fig. patru.

Procesul iterativ al metodei coardei continuă până când se obține o rădăcină aproximativă cu un anumit grad de precizie. La evaluarea erorii de precizie, puteți utiliza relația:

.

Apoi, starea de calcul este scrisă sub formă:

unde e este o eroare de calcul dată. Trebuie remarcat faptul că atunci când găsiți rădăcina, metoda coardei oferă adesea o convergență mai rapidă decât metoda de jumătate de diviziune.

4. Metoda Newton (tangentă)

Lăsați ecuația (1) să aibă o rădăcină pe segment și f "(x) și f" (x) sunt continue și păstrează semne constante pe tot parcursul intervalului.

Semnificația geometrică a metodei Newton este că arcul curbei Y \u003d F (X) este înlocuit de tangent. Pentru a face acest lucru, o aproximare inițială a rădăcinii x0 este selectată pe interval și tangentul la punctul C0 (x0, F (x0)) se efectuează la curba y \u003d f (x) la intersecția cu axa Abscisa (Fig.3). Ecuația tangentă la punctul C0 este

Apoi este testat printr-un nou punct C1 (x1, F (x1)), iar punctul X2 al intersecției sale cu axa 0x este determinat etc. În cazul general, formula metodei tangente are forma:

Ca urmare a calculelor, secvența de valori aproximative x1, x2, ..., xi, fiecare element ulterior este mai aproape de rădăcina x * decât cea anterioară. Procesul iterativ se oprește, de obicei, atunci când funcționează (4).

Aproximarea inițială X0 trebuie să satisfacă condiția:

f (x0) F ¢ ¢ (x0)\u003e 0. (6)

În caz contrar, convergența metodei lui Newton nu este garantată, deoarece tangentul va traversa axa Abscisa într-un punct care nu aparține segmentului. În practică, ca armonizare inițială a rădăcinii X0, una dintre limitele intervalului este de obicei selectată, adică. X0 \u003d A sau X0 \u003d B, pentru care semnul funcției coincide cu semnul celui de-al doilea derivat.

Metoda Newton oferă o viteză mare de convergență în rezolvarea ecuațiilor pentru care valoarea modulului este derivatul de ½f ¢ (x) ½ frânghie de rădăcină este destul de mare, adică. Graficul funcției y \u003d f (x) în vecinătatea rădăcinii are o abruptură mare. Dacă Y \u003d F (x curba) este aproape orizontală în interval, atunci nu se recomandă aplicarea metodei tangente.

Dezavantajul esențial al metodei considerate este necesitatea de a calcula instrumentele derivate pentru organizarea procesului de iterație. Dacă valoarea F ¢ (x) se modifică puțin pe interval, atunci formula poate fi utilizată pentru a simplifica calculele.

, (7)

acestea. Valoarea derivatului este suficientă pentru a calcula o singură dată la punctul de plecare. Acest lucru înseamnă geometric că tangenții la punctele CI (Xi, F (xi)), unde i \u003d 1, 2, ... este înlocuită cu tangentă dreaptă, paralelă, efectuată la curba y \u003d f (x) la punctul de pornire C0 (x0, F (x0)), așa cum se arată în fig. patru.

În concluzie, trebuie remarcat faptul că toate cele de mai sus sunt adevărate atunci când armonizarea inițială a lui X0 este selectată cea mai apropiată de adevărata rădăcină a ecuațiilor X *. Cu toate acestea, acest lucru nu este întotdeauna foarte fezabil. Prin urmare, metoda lui Newton este adesea folosită în etapa finală de rezolvare a ecuațiilor după funcționarea unui algoritm fiabil convergent, de exemplu, metoda de jumătate de diviziune.

5. Metoda de iterație simplă

Pentru a aplica această metodă pentru a rezolva ecuația (1), este necesar să o convertiți sub formă. Apoi, aproximarea inițială este selectată și x1 este calculată, apoi x2, etc.:

x1 \u003d J (x0); x2 \u003d j (x1); ...; xk \u003d j (xk-1); ...

rădăcină de ecuație algebrică neliniară

Secvența rezultată converge la rădăcină la efectuarea următoarelor condiții:

1) Funcția J (X) este diferențiată pe interval.

2) În toate punctele acestui interval j ¢ (x) satisface inegalitatea:

0 £ £ 1. (8)

În astfel de condiții, rata de convergență este liniară, iar iterațiile trebuie efectuate până când devine o condiție echitabilă:

.

Criteriul tipului.

acesta poate fi utilizat numai la 0 £ £ ½. În caz contrar, iterațiile se încheie prematur fără a asigura o anumită precizie. Dacă calculul Q este dificil, atunci puteți utiliza criteriul de încheiere

; .

Posibil diverse metode Conversia ecuației (1) în minte. Ar trebui să fie aleasă astfel încât să satisfacă condiția (8), care generează un proces iterativ similar, cum ar fi, de exemplu, este prezentat în fig. 5, 6. În caz contrar, în particular, la ½j ¢ (x) ½\u003e 1, procesul iterativ se scurge și nu permite obținerea unei soluții (figura 7).

Smochin. cinci

Smochin. 6.

Smochin. 7.

Concluzie

Problema îmbunătățirii calității calculelor ecuațiilor neliniare cu o varietate de metodeDeoarece inconsecvența dintre cele dorite și valabile există și va exista în viitor. Decizia ei va contribui la dezvoltare tehnologia Informatieicare este de a îmbunătăți metodele de organizare a proceselor de informare și implementarea acestora utilizând instrumente specifice - medii și limbi de programare.

Lista surselor utilizate

1. Alekseev V. E., Vaulin A.S., Petrov G. B. - Echipamente informatice și programare. Atelier de programare: Pratty. Adresa / m.: Mai mare. SHK. , 1991. - 400 p.

2. Abramov S.A., ZIMA E.V. - începutul programării în Pascal. - M.: ȘTIINȚĂ, 1987. -112 p.

3. Echipamente și programare de calcul: Studii. pentru Tech. Universități / A.V. Petrov, V.e. Alekseev, A.S. Vaulin și colab. - M.: Mai mare. Shk., 1990 - 479 p.

4. Gusev V.A., Mordkovich a.g. - Matematica: Ref. Materiale: kn. Pentru studenti. - A doua ed. - M.: Iluminare, 1990. - 416 p.

Punctul de soluționare aproximativă, adică aproximări consecutive (4) sunt construite prin formule:, (9) unde este aproximarea inițială față de soluția exactă. 4.5 Metoda Zeidel bazată pe ecuația liniarizată, formula iterativă pentru construirea unei soluții aproximative ale ecuației neliniare (2) pe baza ecuației liniarizate (7) are forma: 4.6 Metoda de metode pre-rezervate ...

Lăsați la tăietură Funcția este continuă, ia valoarea diferitelor caractere la capetele segmentului și derivatul f "(x) Salvează un semn. În funcție de semnul celui de-al doilea derivat, sunt posibile următoarele cazuri de localizare a curbelor (figura 1).

Smochin. unu.

Algoritm pentru calculul aproximativ al metodei rădăcinii de coardă.

Datele inițiale: f (x) -funcţie ; e. - precizia necesară; x. 0 - aproximarea inițială.

Rezultat: XPR. - Ecuația aproximativă a rădăcinilor f (x)= 0.

Metoda deciziei:

Smochin. 2. f "(x) f "" (x)\u003e 0.

Luați în considerare cazul când f "(x) și f "" (x) Au aceleași semne (figura 2).

Programul de funcții trece prin puncte A. 0 (A, f (a)) și B. 0 (B, F (b)). Rădăcina dorită a ecuației (punct x *) Suntem necunoscuți, în schimb, luăm un punct h. 1 Traversând coarda DAR 0 ÎN 0 Cu o axă Abscisa. Aceasta va fi valoarea aproximativă a rădăcinii.

În geometria analitică, o formulă este derivată definind ecuația de trecere directă prin două puncte cu coordonate. (x1; U1) și (x2; U2): .

Apoi ecuația chordului DAR 0 ÎN 0 Greșit în formularul :.

Găsiți valoarea x \u003d x. 1 , pentru care y \u003d 0.:. Acum, rădăcina se află pe segment . Aplicați metoda coardei la acest segment. Tăiați punctele de conectare a coardei A. 1 (X. 1 , f (x 1 )) și B. 0 (B, F (b)), si gaseste h. 2 - punctul de trecere a coardei DAR 1 ÎN 0 cu axa Oh: x. 2 \u003d X. 1 .

Continuând acest proces, găsim

x. 3 \u003d X. 2 .

Avem o formulă recurentă pentru calcularea aproximațiilor la rădăcină

x. n + 1. \u003d X. n. .

În acest caz, sfârșitul b. A tăia rămâne fixă \u200b\u200bși sfârșitul a. mișcări.

Astfel, ajungem formulele estimate Metode Horde:

x. n + 1. \u003d X. n. ; x. 0 \u003d A.. (4)

Calculele următoarelor aproximări față de rădăcina exactă a ecuației continuă până când ajunge la o anumită precizie, adică. Trebuie efectuată condiția: | X. n + 1. -X. n. |< unde - acuratețea specificată.

Acum, luați în considerare cazul în care primul și al doilea derivate au semne diferite, adică. f "(x) f "" (x)<0 . (Fig.3).

Smochin. 3. Interpretarea metodei geometrice pentru caz f "(x) f "" (x)<0 .

Conectați punctele A. 0 (A, f (a)) și B. 0 (B, F (b)) Chordoy. DAR 0 ÎN 0 . Punctul de intersecție de coarde cu axă Oh Vom lua în considerare prima armonizare a rădăcinilor. În acest caz, capătul fix al segmentului va fi sfârșitul dar.

Ecuația Horde. DAR 0 ÎN 0 :. De aici vom găsi x. 1 , a crezut y \u003d 0.: x. 1 \u003d B.. Acum ecuația rădăcină x.. Aplicând metoda coardei la acest segment, ajungem x. 2 \u003d X. 1 . Continuând, etc., ajungem x. n + 1. \u003d X. n. .

Metodele estimate ale metodei:

x. n + 1. \u003d X. n. , x. 0 =0 . (5)

Starea sfârșitului calculelor: | X. n + 1. -X. n. |< . Atunci cPR \u003d XN + 1 Cu precizie, deci dacă f "(x) f "" (x)\u003e 0 Valoarea aproximativă a rădăcinii se găsește prin formula (4) dacă f "(x) f "" (x)<0 , apoi conform formulei (5).

Alegerea practică a uneia sau a unei alte formule se efectuează utilizând următoarea regulă: capătul fix al segmentului este cel pentru care semnul funcției coincide cu semnul celui de-al doilea derivat.

Exemplu. Ilustrează acțiunea acestei reguli asupra ecuației

(x - 1) ln (x) -1 \u003d 0Dacă segmentul de izolare a rădăcinii .

Decizie. Aici f (x) \u003d (x - 1) ln (x) -1.

f "(x) \u003d ln (x) +;

f "" (x) \u003d.

Al doilea derivat din acest exemplu este pozitiv pe segmentul izolației rădăcinii : f "" (x)\u003e 0, f (3)\u003e 0, adică f (b) f "" (x)\u003e 0. Astfel, în rezolvarea acestei ecuații, coarda este aleasă pentru a clarifica rădăcina cu formula (4).

var E, C, A, B, Y, YA, YB, YN, X, X1, X2, XN, X1, X2, XN, F1, F2: Real;

Începe E: \u003d 0,0001;

writeln ("VVEDI NACHALA OTREZKA");

writeln ("VVEDI KONEC OTREZKA");

y: \u003d ((x - 1) * ln (x)) - 1;

y: \u003d ((x - 1) * ln (x)) - 1;

yb: \u003d y; C: \u003d (A + B) / 2; x: \u003d c;

y: \u003d ((x - 1) * ln (x)) - 1;

f1: \u003d ln (x) + (x-1) / x;

f2: \u003d 1 / x + 1 / (x * x);

dacă (ya * yb< 0) and (f1*f2 > 0)

apoi începeți x1: \u003d a; În timp ce ABS (X2 - X)\u003e E do

x2: \u003d x1 - (yn * (b - x1)) / (yb-yn);

writeln ("Koren Uravneniya xn \u003d", X2)

sfârșitul altceva x1: \u003d B;

În timp ce ABS (X2 - X)\u003e E do

începeți x: \u003d x1; Y: \u003d ((x - 1) * ln (x)) - 1; yn: \u003d y;

x2: \u003d x1 - (Yn * (x1- A)) / (YN - YA);

writeln ("Koren Uravneniya xn \u003d", X2);

Metodă de iterații simple

Luați în considerare ecuația f (x) \u003d 0 (1) cu o rădăcină separată X.. Pentru a rezolva ecuația (1) prin metoda de iterație simplă, le oferim formei echivalente: x \u003d C (x). (2)

Se poate face întotdeauna, cu multe feluri. De exemplu:

x \u003d g (x) · f (x) + x? c (x)Unde g (x.) - o funcție continuă arbitrară care nu are rădăcini pe segment .

Lasa x. (0) - Obținut în orice mod apropiindu-se de rădăcină x. (în cel mai simplu caz x. (0) \u003d (A + b) / 2).Metoda de iterație simplă este un calcul consecvent al membrilor secvenței iterative:

x. (K + 1) \u003d C (x (k) ), k \u003d 0, 1, 2, ... (3)

Începând cu aproximarea x. (0) .

Approval: 1 Dacă secvența (X (K)) a metodei de iterație simple convergează și funcția C este continuă, limita de secvență este rădăcina ecuației x \u003d C (x)

Dovada: Lăsați. (patru)

Mutarea la limita în egalitate x. (K + 1) \u003d C (x (k) ) Obținem de la o parte a software-ului (4), care, pe de altă parte, datorită continuității funcției c. și (4) .

Ca rezultat, ajungem x. * \u003d C (x * ). Prin urmare, x. * - rădăcina ecuației (2), adică X \u003d x. * .

Pentru a vă bucura de această declarație, aveți nevoie de o convergență a unei secvențe (X. (k) }. O condiție suficientă a convergenței dă:

Teorema 1: (despre convergență) Lăsați ecuația x \u003d c (x)are singura rădăcină pe segment Și condițiile sunt finalizate:

• 1) c (x) c 1 ;
• 2) c (x) "X;
• 3) Există o constantă q\u003e 0: | c "(x) |? q . Tide Secvența iterativă (X. (k) }, Formula specificată x. (K + 1) \u003d C (x (k) ), k \u003d 0, 1, ... converge cu orice aproximare inițială x. (0) .

Dovada: Luați în considerare două membri vecini vecini (X. (k) ): X. (k) \u003d C (x (K-1) ) și x. (K + 1) \u003d C (x (k) ) Tak ca în condiția 2) x. (k) și X. (K + 1) Situată în interiorul tăieturii , că utilizarea teoremei Lagrange privind valorile medii obținem:

x. (K + 1) - X. (k) \u003d C (x (k) ) - c (x (K-1) ) \u003d C "(c k. ) (X. (k) - X. (K-1) ), unde c k. (X. (K-1) , X. (k) ).

De aici primim:

| X. (K + 1) - X. (k) | \u003d | C "(c k. ) · | X. (k) - X. (K-1) | ? Q | X. (k) - X. (K-1) | ?

? Q (Q | x (K-1) - X. (K-2) |) \u003d Q 2 | X. (K-1) - X. (K-2) | ? ...? Q. k. | X. (1) - X. (0) |. (5)

Luați în considerare rândurile

S. ? \u003d X. (0) + (X. (1) - X. (0) ) + ... + (x (K + 1) - X. (k) ) + ... . (6)

Dacă demonstrăm că această serie convergează, înseamnă că secvența sumelor sale parțiale convergează

S. k. \u003d X. (0) + (X. (1) - X. (0) ) + ... + (x (k) - X. (K-1) ).

Dar este ușor să calculați acest lucru

S. k. \u003d X. (k)) . (7)

Prin urmare, suntem, prin urmare, dovediți și convergența unei secvențe iterative (X. (k) }.

Pentru a dovedi convergența PJ (6), comparați-o în spate (fără primul termen x. (0) ) cu aproape

q. 0 | X. (1) - X. (0) | + Q. 1 | X. (1) - X. (0) | + ... + | x (1) - X. (0) | + ..., (8)

care converge ca o progresie geometrică în mod infinit (de la o condiție q.< 1 ). În virtutea inegalității (5), valorile absolute ale seriei (6) nu depășesc membrii corespunzători ai seriei convergente (8) (adică seria (8) majorizează un număr (6). În consecință, seria (6) converge, de asemenea, secvența convergentă a tabelului (X. (0) }.

Obținem o formulă care oferă o metodă de evaluare a erorii | X - x (K + 1) |

metodă de iterație simplă.

X - X. (K + 1) \u003d X - s k + 1. \u003d S. ? - S. k + 1. \u003d (X. (K + 2) - (K + 1) ) + (x (K + 3) - X. (K + 2) ) + ... .

Prin urmare

| X - x (K + 1) | ? | X. (K + 2) - (K + 1) | + | X. (K + 3) - X. (K + 2) | + ...? Q. k + 1. | X. (1) - X. (0) | + Q. k + 2. | X. (1) - X. (0) | + ... \u003d q k + 1. | X. (1) - X. (0) | / (1-q).

Ca rezultat, obținem o formulă

| X - x (K + 1) | ? Q. k + 1. | X. (1) - X. (0) | / (1-q).(9)

Luând x. (0) valoare x. (k) , pe x. (1) - valoare x. (K + 1) (De când efectuează condițiile teoremei, această alegere este posibilă) și având în vedere că atunci când există inegalitate q. k + 1. ? Q. Depozit:

| X - x (K + 1) | ? Q. k + 1. | X. (K + 1) - X. (k) | / (1-q)? Q | X. (K + 1) - X. (k) | / (1-q).

Deci, în cele din urmă avem:

| X - x (K + 1) | ? Q | X. (K + 1) - X. (k) | / (1-q). (10)

Utilizați această formulă pentru a scoate criteriul de capăt al secvenței iterative. Lăsați ecuația x \u003d c (x) rezolvată prin metoda de iterație simplă, iar răspunsul trebuie găsit cu precizie e, adică

| X - x (K + 1) | ? e.

Luând în considerare (10) obținem această precizie e. vor fi realizate dacă inegalitatea

| X. (K + 1) -X. (k) | ? (1-q) / q.(11)

Astfel, pentru a găsi rădăcinile ecuației x \u003d c (x) Metoda de iterație simplă este acuratețea continuării iterații până când modulul diferențe între cele mai recente aproximări adiacente rămâne mai mare decât numărul e (1-Q) / Q.

Nota 1: Ca o constantă q ia de obicei o estimare de sus pentru magnitudine

Interpretarea geometrică

Luați în considerare un grafic al funcției. Aceasta înseamnă că soluția ecuației este punctul de intersecție cu o linie dreaptă:

Imaginea 1.

Iar următoarea iterație este coordonarea intersecției unui punct direct orizontal, cu o linie dreaptă.

Figura 2.

Din imagine, cerința de convergență este vizibilă în mod clar. Cu cât este mai apropiat derivatul de 0, cu atât mai repede se conversează algoritmul. În funcție de semnul derivatului în apropierea soluției, aproximarea poate fi construită în moduri diferite. Dacă, fiecare apropiere de aproximare este construită pe cealaltă parte a rădăcinii:

Figura 3.

Concluzie

Problema îmbunătățirii calității calculelor, ca o nepotrivire între cele dorite și valabile, există și va exista în viitor. Decizia sa va fi promovată de dezvoltarea tehnologiilor informaționale, care este de a îmbunătăți metodele de organizare a proceselor de informare și implementarea acestora utilizând instrumente specifice - medii și limbi de programare.

Rezultatul lucrării poate fi considerat modelul funcțional creat de găsire a rădăcinilor ecuației prin metodele de iterație simplă, Newton, Chore și Half-Divizia. Acest model este aplicabil sarcinilor deterministe, adică. Acuratețea calculului experimental al cărui poate fi neglijată. Modelul funcțional creat și implementarea acestuia poate servi drept o parte organică a rezolvării sarcinilor mai complexe.

Realizarea cercetării pe această temă termen de hârtie "Metode numerice. Soluția ecuațiilor neliniare", am realizat obiectivele stabilite în introducere. Metodele de clarificare a rădăcinilor au fost luate în considerare în detaliu. Câteva exemple au fost date fiecărei definiții și teoreme. Toate teoremele sunt dovedite.

Utilizarea diferitelor surse a făcut posibilă dezvăluirea completă a subiectului.

Metoda examinată este aceeași cu metoda de jumătate de diviziune, este concepută pentru a clarifica rădăcina de pe interval

Ia valori de caractere diferite. O altă aproximare, spre deosebire de metoda de jumătate de diviziune, nu luăm în mijlocul segmentului, dar la punct care intersectează linia dreaptă a axei abscisa (coardă) efectuată prin puncte DARși ÎN(Fig.2.6).

Noi scriem ecuația directă prin puncte DARși ÎN:

.

Pentru punctul de intersecție, linia cu axa Abscisa (
) Primim ecuația

. (2.13)

Ca un interval nou pentru a continua procesul iterativ, alegeți unul dintre cele două
și
la capătul căruia funcția
Ia valori de caractere diferite. Pentru cazul în cauză (figura 2.6) alegeți un segment
, la fel de
. Următoarea iterație este de a determina noua aproximare. cum ar fi punctele de intersecție a coardei
Cu o axă Abscisa etc.

Finalizăm procesul de clarificare a rădăcinii, când distanța dintre următoarele aproximări va fi mai mică decât acuratețea specificată, adică.

(2.14)

sau când se desfășoară condiția (2.12).

Ø Cometariu. Metoda de divizare și metoda coardei este foarte asemănătoare, în special, procedura de verificare a semnelor funcției la capetele segmentului. În același timp, al doilea dintre ele, în unele cazuri, oferă o convergență mai rapidă a procesului iterativ. Cu toate acestea, în unele cazuri, metoda coardei poate converga semnificativ mai lentă decât metoda de jumătate de diviziune. Această situație este prezentată în fig. 2.7. Ambele metode luate în considerare nu necesită cunoașterea informațiilor suplimentare despre funcția.
. De exemplu, nu este necesar ca funcția să fie diferențiată. Chiar și pentru funcții discontinue, metodele considerate au convergență garantată. Metode de definiție mai complexe de rădăcină Utilizați informații suplimentare despre funcția.
În primul rând, proprietățile diferențiabilității. Drept urmare, ele au de obicei o convergență mai rapidă, dar în același timp, aplicabilă pentru o clasă mai îngustă de funcții, iar convergența lor nu este întotdeauna garantată. Un exemplu al acestei metode este metoda Newton.<

1. Metoda Newton (metoda tangentă)

Spuneți-ne abordarea inițială a rădăcinii (Selecția aproximării inițiale va fi discutată în detaliu mai jos). Vom petrece la acest punct tangentă la curbă
(Fig. 2.8). Acest tangent va traversa axa Abscisa la acest punct care va fi considerată ca următoarea aproximare. Valoare Ușor de găsit din imagine:

,

exprimând de aici , obține

.

În mod similar, pot fi găsite următoarele aproximări. Formula pentru k.+ Prima aproximare este

,
(2.15)

Formula (2.15) implică condiția de aplicabilitate a metodei: funcția
trebuie să fie diferențiată și
În vecinătatea rădăcinii nu ar trebui să schimbe semnul.

Pentru a încheia procesul iterativ, pot fi utilizate condiții (2.12) sau (2.14).

Ø SET 1. În metoda Newton, spre deosebire de metodele anterioare, nu este necesar să setați segmentul
conținând rădăcina ecuației, dar este suficientă pentru a găsi o apropiere inițială a rădăcinii .<

Ø SET 2. Formula metodei Newton poate fi obținută din alte considerente. Dă-mi o abordare inițială a rădăcinii
. Înlocuiți funcția f.(x.) în vecinătatea punctului Segmentul seriei Taylor:

și în loc de o ecuație neliniară
Lăsați ecuația liniară

având în vedere decizia sa ca fiind următoarea (mai întâi) apropierea de valoarea rădăcinii dorită. Soluția la această ecuație este evidentă:

Repetarea acestui proces vine la formula lui Newton (2.15).<

Convergența lui Newton. Aflăm principalele condiții pentru convergența secvenței de valori
calculată cu formula (2.15), la rădăcina ecuației (2.1). Asumand
de două ori mai diferențiată, se descompune
Într-o serie de Taylor în împrejurimi k.-HO aproximare

Partajarea ultimului raport pe
și a mutat partea componentelor din partea stângă spre dreapta, obținem:

.

Având în vedere că expresia în paranteze pătrate conform (2.15) este egală
, rescrieți acest raport în formă

.

. (2.16)

De la evaluarea (2.16) urmează

, (2.17)

unde
,
.

Evident, eroarea scade dacă

. (2.18)

Starea rezultată înseamnă că convergența depinde de selectarea aproximării inițiale.

Evaluarea (2.17) caracterizează rata de descendentă a erorii pentru metoda Newton: la fiecare etapă, eroarea este proporțională cu pătratul erorii în etapa anterioară. În consecință, metoda lui Newton are o convergență patrată.

ÎN aproximarea inițială în metoda lui Newton.După cum rezultă din condiții (2.18), convergența secvenței iterative obținute în metoda Newton depinde de selectarea aproximării inițiale . Acest lucru poate fi văzut și din interpretarea geometrică a metodei. Deci, dacă luați un punct ca o aproximare inițială (Fig.2.9), atunci convergența procesului iterativ nu se ia în considerare.

Dacă alegeți un punct ca o aproximare inițială , Am o secvență convergentă.

În general, dacă se separă segmentul
conținând rădăcina și se știe că funcția
Monotonna pe acest segment, apoi ca o aproximare inițială Puteți alege această margine a segmentului
unde semnele funcției coincid
și al doilea derivat
. O astfel de selecție a apropierii inițiale garantează convergența metodei Newton, sub rezerva monotoniei funcției pe segmentul localizării rădăcinilor.