Conditionarea problemei si stabilirea algoritmilor

Subiectul 1 conditionarea problemei si stabilirea algoritmilor. Exemple

Obiectivul analizei numerice este analizarea metodelor numerice dezvoltand pt rezultatele efective a unei probleme stiintifice sau matematice intelegand prin aceasta gasirea unei solutii a problemei. Constructia metodei ofera solitii aproximative de ecuatii. Inlocuieste formula continuta cu cea discreta.

Analizarea convergentei si eroarea metodei

Deseori solutia este gasita pritr-un didtem interactic pt care se stabilesc conditiile de convergenta care solutia exacta. Analizarea erorii consta in stabilirea de formule care sa dea marja pt eroarea solutiei. Fie formulele teoretice, fie formulele care tin de numarul de operatii necesare pt gasirea solutiei precum si pt propagarea erorilor in aceste operatii.

Conditiile probabile si stabilira metodei.

Conditii probabile: semsibilitatea solutiei la mici dchimbari in datele problemei. Daca solutia este sensibila la mici schimbari probabile se zice rau conditionata; in caz contrar se zice bine conditionata.

Eficienta metodei: exista mai multe metode dezvoltata pt aceeasi clasa de ecuatii liniare. Integrarea numeriiica a ecuatiei diferentiala. Utilizatorul alege in functie de caracteristicile metodei, adica precizie, timp de calclul. Factorul uman poate fi hotarator, utilizatorul alege o metoda mai cunoscuta.

Conditionarea problemei F(x,y)=0 (*); x=solutia y=data de care depinde solutia

Exemplu 1 F- functie polinomiala, y-valoarea coeficientului problemei

2 (*)problema cu valori initiate pt o ecuatie diferentiala.

Definitie: problema F(x,y)=0 se zice stsabila sau bine cond daca solutia x depinde continuu de y. O problema care nu e stabila e instabila saiu rau cond.

Numarul deconditie : pt problema de tipul (*) se pote defini numar de conditii care reprezinta o masura a stabilitatii problemei _y, in y asociemmsolutiile lui x. y sufera o perturbarea si devine y=y+ _y x=x+ _x

Def: K(x)=sup[(|| _x||/||x||)/(|| _y||/||y||] =(perturb rel in x)/(perturb rel in y)

_x||/||x||= K(x)(|| _y||/||y||) k=mare=> preoblema rau cond; contrar- bine cond

Stabilirea algoritmului F(x,y)=0 presupunem ca metoda conduce la un numar de rezolvare F_n(y_n,x_n)=0 depinde de n.

Presupunerea conditiilor y_n=/=y =>x_n x n

F_n(z,w)=> F_z(w)

Def.2 K(x)=(supK_n(x_n)) Zicem ca metoda doi e stabila daca nr de conditii K(x) de acelasi ordin cu numarulde conditii K(x) a problemei 1

Subiectul 2 reprezentarea nr in calculator intregi. Reali, reprezentarea in virgula flotanta (FP) modele de reprezentare

Reprezentarea nr in calculator se face conform standard American National Science Institut ANSI/IEEE 754-1985

Standardul este implementat de toate compilatoarele fortran. Datele numerice intregi: integer(n) n=1;2;3;8 Real (n) unde n=4;8;(16) n=(kind)=nr de octeti pe care se reprezinta tipuri de reali de 16 si este implementat fie hard de unele procesoare fie implementate intr-un soft. Reprezentarea nr reale in calc se face in virgula flotanta(FP)

Structura formatelor: tipul intger(n) se reprezinta pe n octeti continui. Cifrele indica:

a)     adresa octetului care contine bitul nr 0, adresa de start a datei reprezentate. S-bitul de semn S=0 =>n>0 si S=1=>n<0

Reguli de stocare. Codul complementului lui 2

O valoare pozitiva se reprezinta ca atare in binare; o valoare negative se poarte reprezenta astfel: sea inverseaza toti biti valorii respective si se scade, pt a regasi o valoare negativa se inverseza toti bitii si se adauga 1

Modul de reprezentare reprezentarea nr reale este una din urmatoarele expresii: x=0;

x=/=0 se utilizeaza reprezentarea sectionala

Reprezentarea in calculator binar in baza 2 S=bitul de semn

0.x>0

1..x<0

subiectul reprezentarea nr in calculator reali reprezentarea in virgula flotanta: structura logica a formatului, formate IEEE

tipul real de 4 se reprezinta pe patru octeti asezati continuu si este stocat in asa numitul format simplu

real(4). format simplu (IEEE S Floating)

real(8).fomat dublu (IEEE T Floating)

F in format simplu reprezinta o sompla precizie iar F in format dublu reprez in dubla precizie

Explicatii Primul bit se presupune 1 si nu se mai stocheaza efectiv in camp si se stocheaza fractia. La fiecare exponent se adauga o deplasare astfel incat valoarea stocata sa fie mai mare decat 0. elementele stocate= E+deplasarea E=Estocat-deplasarea

Primul bit al semnnificantului este 1 atata timp cat semnificantul este diferit de 0 .

Formatul dublu extins. Este utilizat intern de catre coprocesorul matematic. Nr reprezentat nu trbuie normalizat si pt stocare se utilizeaza 64 de biti de precizie. Bitul este stocat explicit in locatia 6 a semnificantului.

Subiectul 4 reprezentarea nr in calculator-formatul IEEE: valori speciale; plaja de reprezentare, exceptii aritmetice

Valori speciale: exista anumite combinatiide exponenti si semnificatii care conducmla valorile speciale din tabloul urmatori. Lor li se adauga nr normalizate.

Formate IEEE valori in virgula flotanta

Numere de normalitate (subnormale) se claseaza intre cel mai mic nr neg si cel mai mic nr pozitiv intreacestea ar fi clar nr ±0

s.p: ±0.fx2^-126

d.p. ±0.fx2^-1023

Exceptii aritmetice

CVF-trateaza doua tipuri de exceptii in operatiile aritmetice 1. exceptia in virgual flotanta: zicem ca avem exceptie atunci cand rezultatul unei opereatii FP nu este reprezentabil ca nr normalizai inclusiv cand apare o pierdere de precizie in reprezentarea rezultatului implicit in cazulunei exceptii FP se seteaza in status 1 flag si calculatia se continua cu rezultatul imlicit descris mai jos -nr exacte, imp cu 0 depasiri format, nr invalide

Exceptii matematice intervin in cazul functiilor matematice si pot fi: eroare de argument, depasiri de format, pierdere deprecizie

Subienctul 5 Reprezentarea nr in caslculator-masura erorii de rotunjire:

ULP; -masina; Eroerea de rotunjire a unitatii

ULP Def 1. ULP(x)=este nr care are un 1 in ultimul bit si 2 in restul bitilor si acelasi exponent ca si x. x=b₀b₁.b_p-1x2^E

ULP(x)=0.0. 1 x2^E=(1.0)₂x2^p-1x2^E=2^-p+1x2^E

Proprietate: ULP(x) este cel mai mic nr care adunat la x produce un nr recunoscut de calcule, si nr mai mare decat x.

Un nr mai mare decat x se pote obtine: x=b₀ b₁.b_p-2(b_p-1+2) x 2^E >x |

x+ULP(x)=b₀.b₁.b_p-1+2(x2^E) > x

-masina

err (f(x)) ≤1/2ULP(x)

½ 2^-P ≤|Rel(fl(x))|≥ 2^-P

demonstram exemplu tinand cont de P1

Def 2: Marginea superioara a erorii relatrive in modul se numeste -masina

p=precizia reprezentarii; -masina =2^-P

Eroare de rotunjire a unitatii err de rotunjire a unitatii este cel mai mic nr FP ccare adunat la 1.0 produce un nr mai mare decat 1.0 exemplu: F.S.:EPS=ULP(1.0)=2^-23

F.D.:EPS=ULP(1.0)=2^-52

Zecimal F.S:EPS=1.192. x10^-7 F.D:EPS=2.220. x10^-16

Subiectul 6 Erori, surse si propagare:

Eroare; Eroare relativa; Cifre semnificative; Relatia cu eroarea relativa.

1.erori. Vom nota cu x_T valoarea adevarata a lui x. x_A=valoare aproximativa

Def 1. Eroarea "in x_A" ; err x_A=x_T-x_A; |err(x_A)=|x_T-x_A| err absoluta (in x_A a valorii x_A)

|x_T-x_A| ≤ - ≤ x_T-x_A ≤ x_A- ≤ x_T ≤ x_A+

Def 2. Eroare relativa

Rela (x_A)=err(x_A)/x_T= (x_T- x_A)/x_T

Numar de cifre semnificatrive alternativ la err in x_Ase poate masura precizia cu care x_A aproximeaza pe x_T cu numar de cifre semnificative saucorecte in x_A. Acest nr se pune in relatie cu err relativa x_A .

Cifrele semnificative ale unui nr reprezentat in baza β

X=a_n βⁿ+ a_n-1 β^n-1+...+ a β+a₀+ a_-1 β^-1+ a_-2 β^-2+..

Conventional nr x se scrie in reprezentarea pozitionala

x=a_na_n-1..a₁a₀ |pct b|a_-1a_-2.

Def | cifre semnificative (in reprezentarea nr x)

-sunt oricare dintre cifrele 1 .( +1) care intervin in reprezentarea pozitionala a nr. 0-este semnificativa daca nu are rolul de a fixa pctul p -adica de a inlocui cifrele necunoscute sau inexistente.

Subiectul 7 Erori, surse si propagare:

Surse de erori; Eroarea de rotunjire; Cazul trunchierii. Exemple pentru β = 10; 2; 16.

Surse de erori :-modulare matematica, greseli sau scapari, incertitudine in date, rotunjire (trunchere) formule de aproximare matematica

1.oricare modulare a unui fenomen real introduce ipoteze simplificatoarea anumite erori

2. sunt caracteristice calculului manual se elimina prin utilizarea calculkatorului. Pot exista erori de programare, eliminandu-se prin testareas progr cu un exercitiu la care se cunoaste rezultatul corect.

3. analiza num nu poate elimina err, poate recomanda o metoda numerica ce sa minimizeze efectul acestor valori pana la rezultatul final.

4. apare la reprezentarea nr in virgula flotanta si constituie sursa majora de erori pt unele probleme.

5. sunt formulele care in general inlocuiesc un proces infinit cu unul finit. Acest tip de erori constituie principalul obiect de studiu in analiza matematica.

Eroarea de rotunjire x.β

x= σ(a₁a₂..a_na_n+1)xβ^e

a_j=cifre in baza β a₁=/=0 ipoteza β=par

Def 1: regula de rotunjire (la un nr cu n cifre in mantisa)

fl(x)=| σ((a₁a₂..a_n)xβ^e a_n+1. <

| σ((a₁a₂..(a_n+1))xβ^e a_n+1.

fl(x) -desemneaza nr reprezentat in virgula flotanta

a_n+1. < rotunjire in jos

a_n+1. rotunjire in sus

Def 2 truncherea

fl(x)= σ(a₁a₂..a_n)xβ^e indiferent de cifra a_n+1

eroarea de rotunjire |Err(x_A)| = |x_T-x_A| x_T; x_A ; Err(x_A) = x_T-x_A ; rel (x_A)= (x_T-x_A)/x_T

x; fl(x); Err(fl(x)) =x-fl(x) rel(fl(x))=(x-fl(x))/x

a)     a_n+1. <

x-fl(x)= σ(.000a_n+1..)x β^e x-fl(x)=a_n+1a_n+2x β^e-(n+1)< β/2 β^e-n-1

|x-fl(x)|<1/2 β^e-n

b)     a_n+1. =>|x-fl(x)| β^e-n

trunchierea se arata in acelasi mod ca la rotunjire ca marginile erorii sunt dublu ca cele la rotunjire |x-fl(x)| β^e-n

obs la err relativa: rotunjire:eroarea relativa poate avea orice semn

trunchierea: x>0 x-fl(x) >0 x<0 0<(x-fl(x))/x < β^-n+1

exemple pt β= 10 5 cifre semnificative

subiectul 8 Erori, surse si propagare - Propagarea erorilor:

Eroarea propagata; Inmultire; Impartire; Evaluarea functiilor.

Propagarea erorilor x;y =numere (operatii)

*= operatia: +; -; x'; /;

vrem sa calculam: x*y efectiv in calculator: x_A#y_A unde x_A=fl(x) y_A=fl(y) si

# =versiunea in calculator a operatiei *

eroarea: x*y- : x_A#y_A = (x*y-: x_A*y_A )+(x_A*y_A - x_A#y_A)

err propagata err de calcul

de cele mai multe ori err vde calcul=err de rotunjire sau trunchere.

obisnuit operatia iuntre x_A si y_A se face in format dublu extind in coprocesor iar rezultatul se rotunjeste le precizia tipului de data

eroare propagata: x_T =x_A+ y_T=y_A+

1)inmulturea rel x_{A x} y_A rel (x_A) rel(y_A)

2)impartirea rel x_{A /} y_A rel (x_A) - rel(y_A)

subiectul 9 Erori, surse si propagare - Propagarea erorilor:

Pierdere de semnificatie.Adunare si scadere. Propagarea erorilor intr-o suma.???Sumarea(in calcului stiintific)????

Adunarea si scaderea err (x_A y_A) = er(x_A) + er(y_A)

daca la inmultire si impartirea erorilor relatiei ale rezultatelor sunt de ordinul erorilor ale operatiilor

in schimbla adunare si scadere valoarea rel a rezult poate fi mai mare ca la eroarea termenilor

Propagarea err 1. operatori aritmetici: x; /; +; -;

2. calculul unei fctii x_T*y_T - x_A*y_A - err propagata x_Tξ..x_A

f(x_T) f(x_A) f(x_T) - f(x_A) = f'(ξ)(x_T - x_A) ≈ f'(x_A)(x_T - x_A)

Propagarea err intr-o suma S_n=x₁+x₂+.x_n in calcul : x_i fl(x_i) S_n

Concluzie: 1.- S_n = _n(x₁+x₂+.x_n) + _n-1(x₁+x₂+.x_n-1) +.+= (x₁+x₂+x₃ ) + (x₁+x₂ )

- S_n = x₁ ( _n) + x₂ ( _n) + x₃ (  _n)++ x_{n n}

exemplu: _j > 0 | x₁| ≤ |x₂| ≤ |x₃| ≤. ≤|x_n|

obs: daca _j nu sunt de acelasi semn pot aparea readuceri in pranteza si se poate ca regula anterioara sa nu mai fie valabila. Putem afirma insa urmatoarea concluzie: in grneral cea mai buna cale de a aduna este de la cel mai mic la ce mai mare. Diferentele sensibile apar numai la n "mare" intre cele noua moduri de calcul _j

|- S_n| ≤ | _n||S_n|++ | ||S₂| ≤ (|S_n|+| S_n-1|+ |S₂|

presupunem ca toti x_j de acelasi semn ex: x_j

obs: ex (cherry & word) |Rel()| ≤ (1+ )^n-1 - 1 +(n-1) + neglijent

Aplicatii: Ciclul Do controlat de control real.

Do x=a.b.h ! b>a | x=a

! calcule asupra lui x | x=x+h

End Do | Go To 100

Do i=1,n x=a+i*h

Pierderile de semnificatie: apar la scaderea a doua nr cu valori apropiate eroarea consta in aceea ca rezultatul are un nr de cifre semnificative mai mic decat nr considerat. Asemenea valori sunt inerente calculului cu nr reprezentate in virgula totala. Intr-un astfel de caz se spune ca cifrele semnificative s-au pierdut.

(Π)_A=3.1416

(22/7)_A=3.1429

Π)_A - (22/7)_A = -0.0013 =>2 cifre semnificative

ex 2: x="mare" :x=10^j j=1,2

x=10⁷ f(x)=2441.40 | f(x)=1581.138 | f(x)=1581.139 |

simpla precizie | dubla precizie |simpla precizie |

obs: ca in exemplul 2 uneori prin reformularea problemei se pot evita eroarea de pierdere de semnificatie.

Subiectul 10 Ecuatii neliniare:

Metoda si analiza metodei; Ordin de convergenta. Convergenta liniara. Variante la definitia ordinului de convergenta.

Metoda : x₀, x₁, x₂, x_n, x_n, (pt n ∞) x_i = itrerare

Analiza metodei :

1)daca iteratia e convergenta

2) daca iteratia e convergenta, care e repiditatea convergentei

3)err radacinilor calculate

4)eficienta metodei

Detaliem: 1) x_n pt n ∞ ;

( x_n )_n≥0; x₀=det | => aproximativ in

( x_n )_n≥0; x₀ six₁ = date | initiale ale radacinii " "

-converge deseori

1') Cat de aproape. ? In general de ref f '(x) in

2) rapiditatea convergentei: -se masoara in nr de pasi necesari pt obtinerea solutiei dorite

- metoda care converge independent; - met

3) err radacinilor calculate n: Rad = x_n |x_n- | < ?

err radacinilor calculate va depinde numai de err operatiilor necesare pt a calcula iteratia la un paas al iteratiei

4) eficienta metodei -nr de calcule necesare pt a obtine solutia dorita

a)metoda independentei aproximative: Ef rapiditate

b)metoda care nu converge independent de aproximarea initiala, atunci poate proceda:

1)o metoda care este lenta si converge independent de aproximare

2)se continua cu metoda mai rapida

Ordin de convergenta

Definitie 1: fie sirul iteratiilor (x_n)_n≥0 unde x_n daca exista un p R , p ≥ 1

Exista un c>0 a.i. | - x_n+1| ≤ c| - x_n|^p

Atunci x_n cu ordin de convergenta "p" c= rata de convergenta

Definitie 1 (continuare): p=1 -biliniara; p=2 -patratica; p=3 -cubica

Definita 2. convergenta liniara - cazul in care p=1

Fie (x_n)_n≥0 ; Daca exista c R 0<c<1 a.i. | - x_n+1| ≤ c| - x_n| oricare n≥0

Atunci x_n ( si convergenta e liniara)

Obs: c<1 | daca p=/=1 nu cerem ca c<1)

- x₁| ≤ c - x₀| .n=0

- x₂| c | - x₁|

- x_n| ≤ c - x_n-1|

- x_n| ≤ cⁿ - x₀| * 0<c<1 =>cⁿ 0 =>| - x_n|

obs: exista metode unde are loc relatia * (c<1) fara sa aiba loc relatiile anterioare. Vom zice ca si in acest caz ca metoda converge l;iniar cu rata convergentei liniare =c

obs: rapiditatea coonvergentei depinde atat de p (ordin) cat si de c (rata). Metodele care au un ordin mai mare converg maii rapoid.

Varianta la definirea ordinului de convergenta lui (Relston si

C=consta in erori asimptotice

Definitia 3. (x_n)_n≥0 unde x_n daca unde C =/=0 atunci se zice ca ordinul de conergenta este p

Obs: C=/=0 f(x)..C=/=0

Cazul p=1 Convergenta liniara

P1: Daca (p=1) x_n ∞ p=1 =>C<1

Demo=contradictie

P2: daca p=1 C<1 , x₀ suficient de apropiat de definitei => x_n

Subiectul 11Radacinile unei ecuatii f(x) = 0:

Metoda bisectiei.(injumatatirii intervalului) Metoda falsei pozitii.

Metoda bisectiei

Ipoteza f - continu [a,b] f(a)f(b) < 0 (fctia ia valori de sdemn contrar la capetele intervalului) [a,b] o singura radacina

c₁ ,c₂ , .. c_n

| -c₁|<

| -c₂|<.

| -c_n|<

a₀ =a b₀=b c_{1 [}a₀; b₀

a₁   b₁ c₂₌ a₁; b

a₂ b_{2 ..}

c_j (a_j-1; b_j-1)

convergenta | -c_n|< (1/2)ⁿ(b-a) (*)

n ∞ 0 | -c_n|

(*)=> p=1 rata convergentei =1/2 -c_n|≤

este suficient: n ≥ log₂()

Bisectia este o metoda foarte robusta si u control foarte bun al err. Singurul dezavantaj este ca metoda converge incet

Metoda falsei pozitii (regual falsei, interpolarii liniare)

Ipoteza: f - continu [a,b] f(a)f(b) < 0 (fctia ia valori de sdemn contrar la capetele intervalului) [a,b] o singura radacina

Falsa metoda: y-f(b) =

C= b-f(b)

Observatii: f[a,b] = c=b -

Convergenta: daca exista f' si f'' continue pe f'( )=/=0 atunci metoda converge

c_n ; p=1 -rata convergentei depinde de f cat si de alegerea intervalului [a,b]

dezavantaje: c₁ c₂ c_n fiind situat de aceeasi parte a lui

-c_i| |c_i+1 - c_i |

test de apropiere a iteratiei : |c_ir - c_i| < | -c_i|<

Subiectul 12 Radacinile unei ecuatii f(x) = 0:

. Metoda secantei.

metoda secantei

ipoteza: f - continua pe V(

secanta prin se determina

x₀ x₁ x₂

x0

x₁ x₂c x₃

..........

y-f(x₁) =

x_n+1=x_n - f(x_n) n ≥ 1 x₀ si x₁ = date

x_n+1=x_n -

obs:in metoda secantei nu se cere ca aproxiamrea initiala sa incadreza radacina.

Convergenta: daca: 1) exista f' si f'' continute pe V (

2)f'( ) =/=0 3) x₀ si x₁ =sunt suficient de apropiate de

atunci: a)x_n b)p=≈1.618

consideratii asupra metodei secantei: p= 1.618. (1.618)³ ≈ 4.2 ; 2² = 4;

3 pasi in metoda secantei ≈ 2 pasi in metoda cu p =2

dezavantaje: fractia din formula metodei poate da valori imprecise in apropierea radacinii datorita pierderilor de semnificatie care apar la numitor si numarator.

x_n+1 = x_n + corectie ; corectia : -f(x_n).

x_n+1 va fi foarte apropiat de x_n chiar cu putine cifre semnificative carea sunt utilizate intr-o corectie mica formula permite determinarea lui x_n+1 cu precizia adoptata in calcule (in ciu da pierderilor de semnificatie din fractie) La un pas metoda secantei ar evalua o singura data afunctiei f .. a valorii x_n . Poate as nu convearga daca x₀ si x₁ nu sunt suficient de aproape de radacina. Algoritm BRENT-bisectoare; -secanta => convergenta

subiectul 13 Radacinile unei ecuatii f(x) = 0 - Metoda Newton:

Metoda; Convergenta.

Obs: metodele anterioare se pot descrie in modul urmator: aproximarea radaciniieste linia dreapta intersectata cu axa ox.

Ipoteza: f - continua si exista f' continua in V(

Formula metodei : y - f(x₀) =f'(x₀)(x-x₀)

y=0 x=x₁

-f(x₀)-f'(x₀)(x₁-x₀)

x₁=x₀ - ; x₀ x_n ; x₁ x_n+1

x_n+1 = x_n - ;n ≥ 0 x₀ - dat

convergenta f.x_n f(x) = f(x_n) + f'(x_n)(x-x_n) + f''( ξ_n)

x = 0 = f(x_n) + f'(x_n)( -x_n) + f''( -x_n)²

0= 0= -(x₄ - )+

-x_n+1|≤ M | - x_n|²

teorema de convergente daca 1) exista f,f', f'' continue pe I = [

2)f'( )=/=0 3)x₀ I si x₀ e "suficient de apropiat de

atunci a)x_n I oricare ar fi n b)x_n si p=2 c)lim

subiectul 14 Radacinile unei ecuatii f(x) = 0 - Metoda Newton:

Estimarea erorii; Algoritmul; Comparatie cu metoda secantei.????Apelul subrutinei NEWTON????

Estimarea err

Test de orpire a iteratiei | - x_n| eps radacina =x_n

Testul |x_n+1 - x_n | XTOL ==> | - x_n| ≤ EPS

La metoda Newton: f-x_n ≈ x_n+1 - x_n

|x_n+1 - x_n | <Eps -x_n| < eps

0=f(x_n) + f'(ξ_n)( -x_n) => -x_n = -

comparatia cu metoda secantei

1) p_n=2 p_s=1.618 2) nr de fctii -sec: 1..f(x_n); - newton: 2f(x_n) f'(x_n)

seemonatreaza T cu f'(x) ≤ 0.44 T cu f(x)

3)daca f'(x).numeric; f'(x_n)≈ => met Newton se reduce la met seca.

Subiect 15 Metoda punctului fix:

Teoreme de punct fix.

Teorema 1: lema:

Daca 1) g:[a,b] [a,b]continuu pe [a,b] atunci g are un pct fix in [a,b]

Observatie = g( =pct fix al aplicatiei g

demo

oricare ar fi x (a,b) a ≤ g(x) ≤ b

G(x) = g(x) - x continut pe [a,b]

G(a) = g(a) - a ≥ 0

G(b) = g(b) - b ≤ 0

G(x) = 0

Teorema 2: aplicatie contractanta

Dac: 1) g:[a,b ] [a,b], continut pe [a,b]

exista λ 0< λ <1

oricare ar fgi x , x' [a,b] |g(x) - g(x')| ≤ λ (x - x')

atunci: a)x=g(x) are o tadacina unica in [a,b]

b)sirul x_n (x_n+1 = g(x_n), n>0) p=1 p-ordin de convergenta

c) -x_n |≤ (x₁ - x₀)

demonstratie: a) din ipoteza 1 conform lemei => ca exista o radacina in [a,b] , exista =/= β , , β apartine [a,b]

teorema 2'

1. g - continut si derivat pe [a,b] 2. g' - marginit pe [a,b] |g'(x)| ≤ λ-1

atunci : a)x=g(x) are o tadacina unica in [a,b]

b)sirul x_n (x_n+1 = g(x_n), n>0) p=1 p-ordin de convergenta

c) -x_n |≤ (x₁ - x₀)

presupunem ca in plus ca g' este constant pe [a,b]

teorema 2''

λ = | < 1

1. g constanta si cu derivata continua pe [a,b]

2. λ = max|g'(x)| < 1

atunci: a)x=g(x) are o tadacina unica in [a,b]

b)sirul x_n (x_n+1 = g(x_n), n>0) p=1 p-ordin de convergenta

c) -x_n |≤ (x₁ - x₀) d) =g'(x)

demonstratie = g( ) - g(x_n) =g'(ξ)( - x_n) 

alte teoreme:

g: [a,b] => R -se relaxeaza aceasta conditie

g: I R

teorema 3 I=[x₀ - ρ, x₀ + ρ], x₀ - aproximatia initiala

demo:1. I=[x₀ - ρ, x₀ + ρ], g:I R , continuta pe I

2. oricare x,x' apartien lui I | g(x)+ g(x') |≤ λ |x-x'|

3. |x₁ - x₀| ≤ (1- |g(x₀)-x₀ |≤ (1-x) ρ

atunci: a) x_n I b) x_n I ; x=g( ) | - x_n |< λⁿ ρ c) = unic in E

daca exista g': 2' |g'(x)| ≤ λ <1 g' este constant 2''

subiectul 16 Metoda punctului fix:

Interpretare geometrica.

x=g(x) y=x; y=g(x)

convergenta |g'(x)|<1 , -1<g'(x) <1

a)     0<g'(x)<1 | cazuri de

b)-1<g'(x)<0 | convergenta

c)g'(x)>1 | cazuri de

d)g'(x)<1 | divergenta

a) 0<g'(x)<1 x₁=s(x₀) b)-1<g'(x)<0 c)g'(x)>1

d)g'(x)<1

m=1

x2 x0 x1

subiectul 17 Metoda punctului fix:

Metode de punct fix de ordin mai inalt decat 1; Aplicatie: Metoda Newton.

Metoda pctului fix de ordin mai mare dacat 1

X_n+1 = g(x_n) ; n ≥ 0 , x₀ = det p=1

Teorema6. daca: 1. daca g continua pe [a,b]= [ ] si derivabila p ≥ 2

2. g'( )=g''( )=..=g^(p-1)( )=0 g^p(

3.

4. ρ^p-1M ≤ λ<1  (ρ^p-1M <1)

atunci: oricare x₀ I: a) x_n I, n≥0 b) x_n c) ordinul de convergenta =p

observatii: ipoteza 4 arata cat de aproapa de trebuie sa fie aproximatia initiala

exemplu: cazul p=2 (exista g' si g'' g'( )=0 g''(

|X_n+1- | ≤ M|X_n - |² ≤ ≤

en = |X_n+1- | e₀ = |x₀ - | en ≤

aplicatie metoda newton

x_n+1 = x_n - g(x)=x - g'(x) = 1-

S''(x) = (f S''()=

Concluzie: f'() =/=0 si f''()=/=0 => met Newton are ordinul p=2