Download - Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

Transcript
Page 1: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

1/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Rezolvarea ecuatiilor algebrice neliniare

Prof.dr.ing. Gabriela Ciuprina

Universitatea "Politehnica" Bucuresti, Facultatea de Inginerie Electrica

Suport didactic pentru disciplina Algoritmi Numerici, 2017-2018

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 2: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

2/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Cuprins1 Ecuatii algebrice neliniare - formularea problemei2 Metode de rezolvare numerica - prin încadrare

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

3 Metode de rezolvare numerica - prin interpolareInterpolare directaInterpolare inversa... de ordinul 1... de ordinul 2

4 Metode de rezolvare numerica - prin iteratii de punct fixMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

5 Metode hibride...fara evaluarea derivatei...cu evaluarea derivatei

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 3: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

3/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Formularea problemei

Enunt

Se da f : [a,b] → IR, continua.Se cere x pentru care

f (x) = 0

Buna formulare matematica

Exista o solutie x∗ ∈ [a,b] siaceasta este unica.

f (x∗) = 0-1 -0.5 0 0.5 1 1.5 2

-6

-4

-2

0

2

4

6

x

y = f(x)

0

y

xx*

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 4: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

4/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Formularea problemei

Exemple de probleme prost formulate:

-6 -5 -4 -3 -2 -1 0 1 2-10

-5

0

5

10

15

x

y = f(x)

0

-6 -5 -4 -3 -2 -1 0 1 20

5

10

15

20

25

x

y = f(x)

0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 5: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

4/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Formularea problemei

Exemple de probleme prost formulate:

-6 -5 -4 -3 -2 -1 0 1 2-10

-5

0

5

10

15

x

y = f(x)

0

Solutia nu este unica.

-6 -5 -4 -3 -2 -1 0 1 20

5

10

15

20

25

x

y = f(x)

0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 6: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

4/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Formularea problemei

Exemple de probleme prost formulate:

-6 -5 -4 -3 -2 -1 0 1 2-10

-5

0

5

10

15

x

y = f(x)

0

Solutia nu este unica.

-6 -5 -4 -3 -2 -1 0 1 20

5

10

15

20

25

x

y = f(x)

0

Nu exista solutie.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 7: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

5/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Conditionarea problemei

Conditionarea depinde de panta lui f în apropierea solutiei.

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2-4

-3

-2

-1

0

1

2

3

4

5

6

x

y = f(x)

0x*

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2-6

-4

-2

0

2

4

6

x

y = f(x)0

x*

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 8: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

5/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Conditionarea problemei

Conditionarea depinde de panta lui f în apropierea solutiei.

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2-4

-3

-2

-1

0

1

2

3

4

5

6

x

y = f(x)

0x*

Bine conditionata.

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2-6

-4

-2

0

2

4

6

x

y = f(x)0

x*

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 9: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

5/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Conditionarea problemei

Conditionarea depinde de panta lui f în apropierea solutiei.

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2-4

-3

-2

-1

0

1

2

3

4

5

6

x

y = f(x)

0x*

Bine conditionata.

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2-6

-4

-2

0

2

4

6

x

y = f(x)0

x*

Prost conditionata.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 10: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

6/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Conditionarea problemei

Numarul de conditionare (revedeti cursul despre erori):Formulare implicita

f (x) = y

(y - date, x - rezultat), aici y = 0Formulare explicita

x = g(y)

(g = f−1)

k = ‖J(g(y))‖ = |g′(y)|= 1|f ′(x)|

Daca |f ′(x∗)| ≈ 0 ⇒ k e mare ⇒ prost conditionata.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 11: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

7/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Exemplul 1

E

R

I=?

U=?

Se dau: E , R sicaracteristica i = g(u)

Figura este preluata de la

https://www.technologyuk.net/physics/

Se cere: punctul static defunctionare al diodei (I,U)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 12: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

7/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Exemplul 1

E

R

I=?

U=?

u = −Ri + E

i = g(u)

u + Rg(u)− E = 0

f (u) = 0

unde

f (u) = u + Rg(u)− E

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 13: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

8/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Enunt si buna formulareExemple

Exemplul 2Se dau:g0, A, tdk , εr

V

Se cere: g

k(g0−g) =ε0AV 2

2(

g + tdεr

)2

f (g) = 0

unde

f (g) = (g − g0)

(

g +tdεr

)2

+ε0AV 2

2k

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 14: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

9/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda bisectiei - ideea

Ipoteza suplimentara:

f (a)f (b) < 0

Ideeax0, x1, . . . , xk , . . . → x∗

Prin înjumatatirea intervalului:1 xm = (a + b)/22 se va selecta dintre intervalele [a, xm] si [xm,b] pe acela

care contine solutia3 se renoteaza cu [a,b] jumatatea aleasa si se reia de la

pasul 1.Algoritmul se opreste atunci când |b − a| < εε este o eroare absoluta impusa de utilizator.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 15: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

10/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda bisectiei - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 16: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

10/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda bisectiei - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 17: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

10/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda bisectiei - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 18: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

10/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda bisectiei - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 19: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

10/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda bisectiei - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 20: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

10/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda bisectiei - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 21: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

11/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metodei bisectiei - algoritm

functie bisectie (a, b, eps, nit)real a, b ; domeniul de definitie al functiei freal ε ; eroarea impusaîntreg nit ; numar maxim de iteratiireal xm ; solutiaîntreg k = 0 ; contor iteratiirepeta

k = k + 1xm = (a + b)/2daca f (xm)f (a) > 0 atunci

a = xmaltfel

b = xmpâna când (b − a) < eps sau k > nitdaca k > nit

scrie Eroarea impusa nu a fost atinsa.întoarce xm ; solutie

retur

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 22: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

12/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda bisectiei - erori

La fiecare iteratie, eroarea absoluta se înjumatateste:

|x0 − x∗| < l

|x1 − x∗| < l/2

|x2 − x∗| < l/22

...

|xk − x∗| < l/2k

...

l = b − a

În ipotezele facute, procedura este garantat convergenta!

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 23: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

13/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda falsei pozitii (regula falsi) - ideea

Ideea: similara cu a bisectiei - alegerea unui interval în carefunctia îsi schimba semnul

DAR nu se înjumatateste intervalul

Intervalul se împarte în doua parti, determinate de intersectiacoardei determinata de punctele (a, f (a)) si (b, f (b)) cu axa Oy.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 24: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

14/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda falsei pozitii (regula falsi) - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 25: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

14/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda falsei pozitii (regula falsi) - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 26: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

14/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda falsei pozitii (regula falsi) - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 27: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

14/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda falsei pozitii (regula falsi) - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 28: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

14/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda falsei pozitii (regula falsi) - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 29: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

14/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda falsei pozitii (regula falsi) - ideea

-1 0 1 2 3 4-4

-2

0

2

4

6

8

10

12

x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 30: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

15/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda falsei pozitii (regula falsi) - algoritm

y(x) =f (b)− f (a)

b − a(x − a) + f (a)

y(x) = 0 ⇒ x =af (b)− bf (a)

f (b)− f (a)

1 xm = (af (b)− bf (a))/(f (b)− f (a))

2 se va selecta dintre intervalele [a, xm] si [xm,b] pe acelacare contine solutia

3 se renoteaza cu [a,b] intervalul ales si se reia de la pasul1.

Algoritmul se opreste atunci când |b − a| < εε este o eroare absoluta impusa de utilizator.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 31: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

16/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda bisectiei (a înjumatatirii intervalului)Metoda falsei pozitii (a coardei)

Metoda falsei pozitii (regula falsi) - convergenta

Convergenta este asigurata daca functia este continua siîsi schimba semnul pe intervalul [a,b];Convergenta ar putea fi mai rapida decât la bisectie dacaîntotdeauna intervalul ales este mai mic decât jumatate dinintervalul anterior;Ideea poate fi folosita în combinatie cu metoda secantelor1

pentru a preveni divergenta acesteia din urma.O varianta mai rapid convergenta a acestei metode estecunoscuta sub numele de metoda lui Ridder detalii aici. Sefoloseste valoarea functiei f la mijlocul intervalului pentru adetermina o alta functie h care are aceeasi radacina ca sif . Metoda falsei pozitii se aplica pentru h.

1Metoda secantelor este prezentata în slide-urile care urmeazaGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 32: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

17/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Interpolare directaInterpolare inversa... de ordinul 1... de ordinul 2

Ideea metodelor bazate pe interpolare

Interpolare directa:

Se folosesc valorile functiei deja calculate pentru a gasi ointerpolare g a functiei f .

Aproximatia radacinii este data de zeroul polinomului deinterpolare g.

f (x) ≈ g(x)f (x∗) = 0 ⇒ g(x∗) ≈ 0Algoritm:g(xk ) = 0 ⇒ f (xk ) ≈ 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 33: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

18/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Interpolare directaInterpolare inversa... de ordinul 1... de ordinul 2

Ideea metodelor bazate pe interpolare

Interpolare inversa:

Se folosesc valorile functiei deja calculate pentru a gasi ointerpolare h a functiei f−1.

Aproximatia radacinii este data de h(0).

f (x) = y ⇒ x = f−1(y)f (x∗) = 0 ⇒ x∗ = f−1(0)f−1(y) ≈ h(y) ⇒ x∗ ≈ h(0)Algoritm:xk = h(0) ⇒ xk ≈ x∗

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 34: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

19/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Interpolare directaInterpolare inversa... de ordinul 1... de ordinul 2

Metode bazate pe interpolare liniara

Metode care folosesc interpolari de ordinul 1 (doua puncte)

1 Metoda falsei pozitii2 - cele doua puncte nu sunt neaparatultimele doua aproximatii calculate.

2 Metoda secantelor3 - cele doua puncte sunt exact ultimeledoua aproximatii calculate.

2Prezentata anterior, ca o metoda de încadrare3Prezentata în slide-urile urmatoare, ca o metoda de punct fix

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 35: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

20/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Interpolare directaInterpolare inversa... de ordinul 1... de ordinul 2

Metode bazate pe interpolarea patratica

Metode care folosesc interpolari de ordinul 2 (trei puncte)1 Metoda Muller

Se aproximeaza f cu o parabola folosind ultimele treiaproximatii calculate.Se calculeaza o radacina a acestei parabole, cea maiapropiata de ultima aproximatie calculata.Detalii la

Eric W. "Muller‘s Method." From MathWorld–A Wolfram Web Resource.

http://mathworld.wolfram.com/MullersMethod.html2 Interpolarea patratica inversa

Se aproximeaza f−1 cu o parabola folosind ultimele treiaproximatii calculate.Se evalueaza acest polinom de interpolare în 0.Este folosita mai des în combinatie cu alte metode.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 36: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

21/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Interpolare directaInterpolare inversa... de ordinul 1... de ordinul 2

Interpolarea patratica inversa

Polinomul de interpolare pentru f−1, folosind punctele:(xk−2, fk−2), (xk−1, fk−1), (xk , fk ) este:

f−1(y) =(y − fk−1)(y − fk )

(fk−2 − fk−1)(fk−2 − fk )xk−2 +

(y − fk−2)(y − fk )

(fk−1 − fk−2)(fk−1 − fk )xk−1 +

+(y − fk−2)(y − fk−1)

(fk − fk−2)(fk − fk−1)xk

Aproximatia urmatoare xk+1 = f−1(0)

xk+1 =fk−1fk

(fk−2 − fk−1)(fk−2 − fk )xk−2 +

fk−2fk

(fk−1 − fk−2)(fk−1 − fk )xk−1 +

+fk−2fk−1

(fk − fk−2)(fk − fk−1)xk (1)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 37: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

22/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

Ecuatia de rezolvat:f (x) = 0 (2)

Ideea:x0, x1, . . . , xk , . . . → x∗

Calcul recursiv:xk = g(xk−1), (3)

g se numeste functie de iteratie

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 38: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

22/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

Ecuatia de rezolvat:f (x) = 0 (2)

Ideea:x0, x1, . . . , xk , . . . → x∗

Calcul recursiv:xk = g(xk−1), (3)

g se numeste functie de iteratie

1 g =?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 39: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

22/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

Ecuatia de rezolvat:f (x) = 0 (2)

Ideea:x0, x1, . . . , xk , . . . → x∗

Calcul recursiv:xk = g(xk−1), (3)

g se numeste functie de iteratie

1 g =?

2 x0 =?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 40: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

22/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

Ecuatia de rezolvat:f (x) = 0 (2)

Ideea:x0, x1, . . . , xk , . . . → x∗

Calcul recursiv:xk = g(xk−1), (3)

g se numeste functie de iteratie

1 g =?

2 x0 =?

3 Sirul este convergent?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 41: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

22/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

Ecuatia de rezolvat:f (x) = 0 (2)

Ideea:x0, x1, . . . , xk , . . . → x∗

Calcul recursiv:xk = g(xk−1), (3)

g se numeste functie de iteratie

1 g =?

2 x0 =?

3 Sirul este convergent?4 Care este criteriul de oprire?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 42: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

23/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - constructia lui g

xk = g(xk−1), limk→∞

xk = x (4)

x = g(x) (5)

Solutia ecuatiei f (x) = 0 este punct fix al aplicatiei g

-2 -1 0 1 2 3 4 5 6 7-4

-2

0

2

4

6

8

10

12

x

f(x) = 0

-2 -1 0 1 2 3 4 5 6 7-2

-1

0

1

2

3

4

5

6

7

x

g(x) = x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 43: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

24/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - constructia lui g

f (x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 44: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

24/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - constructia lui g

f (x) = 0

cf (x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 45: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

24/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - constructia lui g

f (x) = 0

cf (x) = 0

x + cf (x) = x

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 46: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

24/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - constructia lui g

f (x) = 0

cf (x) = 0

x + cf (x) = x

g(x) = x + cf (x) (6)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 47: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

24/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - constructia lui g

f (x) = 0

cf (x) = 0

x + cf (x) = x

g(x) = x + cf (x) (6)

xk = xk−1 + cf (xk−1) k = 1,2, . . . ,n. (7)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 48: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

25/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

g(x) = x + cf (x) (8)

xk = xk−1 + cf (xk−1) k = 1,2, . . . ,n. (9)

Initializare arbitrara x0 ∈ [a,b].Obs: Constanta c influenteaza puternic convergenta.

Teorema - conditie suficienta de convergenta

Daca g este o contractie, atunci sirul iteratiilor este convergent.

g este contractie, daca:

|g(x1)− g(x2)| < |x1 − x2|,∀x1, x2 ∈ [a,b] (10)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 49: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

25/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

g(x) = x + cf (x) (8)

xk = xk−1 + cf (xk−1) k = 1,2, . . . ,n. (9)

Initializare arbitrara x0 ∈ [a,b].Obs: Constanta c influenteaza puternic convergenta.

Teorema - conditie suficienta de convergenta

Daca g este o contractie, atunci sirul iteratiilor este convergent.

g este contractie, daca:

|g(x1)− g(x2)| ≤ L|x1 − x2|,∀x1, x2 ∈ [a,b] (10)

L < 1 (strict!)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 50: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

26/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1 ⇒ iteratii convergente.

-2 -1 0 1 2 3 4 5 6 7-1

0

1

2

3

4

5

6

x

g(x) = x

Convergent

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 51: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

26/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1 ⇒ iteratii convergente.

-2 -1 0 1 2 3 4 5 6 7-1

0

1

2

3

4

5

6

x

g(x) = x

Convergent

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 52: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

26/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1 ⇒ iteratii convergente.

-2 -1 0 1 2 3 4 5 6 7-1

0

1

2

3

4

5

6

x

g(x) = x

Convergent

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 53: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

26/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1 ⇒ iteratii convergente.

-2 -1 0 1 2 3 4 5 6 7-1

0

1

2

3

4

5

6

x

g(x) = x

Convergent

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 54: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

26/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1 ⇒ iteratii convergente.

-2 -1 0 1 2 3 4 5 6 7-2

0

2

4

6

8

10

x

g(x) = x

Divergent

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 55: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

26/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1 ⇒ iteratii convergente.

-2 -1 0 1 2 3 4 5 6 7-2

0

2

4

6

8

10

x

g(x) = x

Divergent

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 56: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

26/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1 ⇒ iteratii convergente.

-2 -1 0 1 2 3 4 5 6 7-2

0

2

4

6

8

10

x

g(x) = x

Divergent

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 57: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

26/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1 ⇒ iteratii convergente.

-2 -1 0 1 2 3 4 5 6 7-2

0

2

4

6

8

10

x

g(x) = x

Divergent

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 58: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

27/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Conditia |g′| < 1 este echivalenta cu:

|1 + cf ′(x)| < 1, x ∈ [a, b]. (11)

⇒ importanta constantei c

Cu cât |g′| = |1 + cf ′(x)| este mai mic, cu atât sirul iterativ este mairapid convergent.Notam L o margine a derivatei |g′|(x) ≤ L.

|x1 − x∗| = |g(x0)− g(x∗)| = |g′(ζ)(x0 − x∗)| ≤ L|x0 − x∗||x2 − x∗| ≤ L|x1 − x∗| ≤ L2|x0 − x∗||x3 − x∗| ≤ L|x2 − x∗| ≤ L3|x0 − x∗|

...

|xk − x∗| ≤ Lk |x0 − x∗| (12)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 59: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

28/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - conditia de oprire

Eroarea |xn − x∗| - nu se poate calculaReziduul |f (xn)| - se poate calcula, dar trebuie corelat cunumarul de conditionare

f (xn)− f (x∗) = f ′(ζ)(xn − x∗)

|xn − x∗| = 1f ′(ζ)

|f (xn)|

|xn − x∗| ≤ k |f (xn)|

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 60: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

29/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - conditia de oprire

Dar

|xn−xn−1| = |g(xn−1)−xn−1| = |xn−1+cf (xn−1)−xn−1| = |cf (xn−1)|

Daca c e corelat cu inversa derivatei, atunci cel mai naturalcriteriu de oprire este

|xn − xn−1| < ε

unde ε este parametru de intrare (impus de utilizator).

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 61: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

30/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda Newton

c se alege a.î. viteza de convergenta sa fie maxima:

1 + ck f ′(xk ) = 0

ck = − 1f ′(xk )

. (13)

xk+1 = xk − f (xk )

f ′(xk )k = 1,2, . . . (14)

Semnificatie geometrica: La fiecare iteratie graficul functiei esteaproximat cu tangenta dusa în punctul de coordonate xk , f (xk ).OBS: Metoda esueaza daca tangenta are panta zero.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 62: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

31/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda Newton

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 63: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

31/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda Newton

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 64: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

31/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda Newton

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 65: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

31/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda Newton

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 66: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

31/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda Newton

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 67: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

32/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda Newton

Justificare: Ecuatia dreptei tangente:

y = f ′(x)(x − xk ) + f (xk ), (15)

Intersectia tangentei cu axa orizontala:

y = 0 ⇒ x = xk+1 = xk − f (xk )

f ′(xk )

Obs: la fiecare iteratie trebuie evaluata derivata f ′(xk ), ceea cepoate necesita un efort mare de calcul.:(Ce se poate face pentru diminuarea efortului de calcul?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 68: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

33/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

Varianta simplificata metoda Newton-Kantorovici (a

tangentelor paralele)

c = −1/f ′(x0)

xk+1 = xk − f (xk )

f ′(x0)(16)

Semnificatia geometrica?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 69: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

34/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 70: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

34/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 71: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

34/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 72: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

34/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 73: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

34/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 74: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

34/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 75: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

34/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 76: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

34/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 77: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

34/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 78: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

35/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 79: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

35/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

S-a redus efortul de calcul, dar doar pentru o iteratie

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 80: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

35/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

S-a redus efortul de calcul, dar doar pentru o iteratieRamâne necesitatea de a avea o expresie analitica pentru derivata f ′(x).

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 81: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

35/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda tangentelor paralele

-1 -0.5 0 0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

S-a redus efortul de calcul, dar doar pentru o iteratieRamâne necesitatea de a avea o expresie analitica pentru derivata f ′(x).

Ce se poate face daca nu exista o astfel de expresie?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 82: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

36/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Foloseste o aproximare numerica a derivatei

f ′(xk ) ≈f (xk )− f (xk−1)

xk − xk−1, (17)

xk+1 = xk − f (xk )(xk − xk−1)

f (xk )− f (xk−1)k = 1,2, . . . (18)

Semnificatie geometrica: La fiecare iteratie graficul functiei esteaproximat cu secanta ce uneste ultimele doua puncte din siruliterativ, având coordonatele xk−1, f (xk−1) si respectiv xk , f (xk ).OBS: Metoda esueaza daca secanta are panta zero.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 83: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

37/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: functia de iteratie are doua variabile xk+1 = g(xk , xk−1),deci necesita o initializare dubla x0, x1 (ex: x0 = b, x1 = a).

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 84: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

37/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: functia de iteratie are doua variabile xk+1 = g(xk , xk−1),deci necesita o initializare dubla x0, x1 (ex: x0 = b, x1 = a).

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 85: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

37/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: functia de iteratie are doua variabile xk+1 = g(xk , xk−1),deci necesita o initializare dubla x0, x1 (ex: x0 = b, x1 = a).

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 86: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

37/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: functia de iteratie are doua variabile xk+1 = g(xk , xk−1),deci necesita o initializare dubla x0, x1 (ex: x0 = b, x1 = a).

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 87: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

37/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: functia de iteratie are doua variabile xk+1 = g(xk , xk−1),deci necesita o initializare dubla x0, x1 (ex: x0 = b, x1 = a).

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 88: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

37/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: functia de iteratie are doua variabile xk+1 = g(xk , xk−1),deci necesita o initializare dubla x0, x1 (ex: x0 = b, x1 = a).

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 89: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

37/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: functia de iteratie are doua variabile xk+1 = g(xk , xk−1),deci necesita o initializare dubla x0, x1 (ex: x0 = b, x1 = a).

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 90: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

37/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: functia de iteratie are doua variabile xk+1 = g(xk , xk−1),deci necesita o initializare dubla x0, x1 (ex: x0 = b, x1 = a).

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 91: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

38/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: daca: x0 = a, x1 = b.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 92: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

38/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: daca: x0 = a, x1 = b.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 93: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

38/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: daca: x0 = a, x1 = b.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 94: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

38/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: daca: x0 = a, x1 = b.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 95: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

38/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: daca: x0 = a, x1 = b.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 96: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

38/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: daca: x0 = a, x1 = b.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 97: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

39/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata (pentru a preveni divergenta), sealege secanta corespunzatoare unei schimbari a semnului.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 98: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

39/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata (pentru a preveni divergenta), sealege secanta corespunzatoare unei schimbari a semnului.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 99: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

39/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata (pentru a preveni divergenta), sealege secanta corespunzatoare unei schimbari a semnului.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 100: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

39/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata (pentru a preveni divergenta), sealege secanta corespunzatoare unei schimbari a semnului.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 101: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

39/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata (pentru a preveni divergenta), sealege secanta corespunzatoare unei schimbari a semnului.

0.5 1 1.5 2 2.5 3-4

-3

-2

-1

0

1

2

3

4

5

x

f(x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 102: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

40/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Algoritmiprocedura iteratie simpla (x0, eps, nit)real x0 ; initializare solutiereal eps ; eroarea impusaîntreg nit ; numar maxim de iteratiiîntreg k = 0 ; contor iteratiireal xvechi = x0 ; initializarea solutieirepeta

k = k + 1xnou = g(xvechi) ; unde g(x)=x+cf(x)d = |xnou − xvechi|xvechi = xnou

pâna când d < eps sau k > nit

daca k ≤ nitscrie xnou

retur

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 103: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

40/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Algoritmiprocedura Newton (x0, eps, nit)real x0 ; initializare solutiereal eps ; eroarea impusaîntreg nit ; numar maxim de iteratiiîntreg k = 0 ; contor iteratiireal xvechi = x0 ; initializarea solutieirepeta

k = k + 1xnou = xvechi − f (xvechi)/fder(xvechi)d = |xnou − xvechi|xvechi = xnou

pâna când d < eps sau k > nit

daca k ≤ nitscrie xnou

retur

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 104: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

40/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Algoritmiprocedura tangente paralele (x0, eps, nit)real x0 ; initializare solutiereal eps ; eroarea impusaîntreg nit ; numar maxim de iteratiireal xvechi = x0 ; initializarea solutieireal fd = fder(x0) ; valoarea derivatei în x0

repetak = k + 1xnou = xvechi − f (xvechi)/fd

d = |xnou − xvechi|xvechi = xnou

pâna când d < eps sau k > nit

daca k ≤ nitscrie xnou

retur

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 105: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

40/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Algoritmiprocedura secante (a, b, eps, nit)real a, b ; domeniul de definitie al functieireal eps ; eroarea impusaîntreg nit ; numar maxim de iteratiiîntreg k = 0 ; contor iteratiireal xv = a ; initializari ale solutieireal xvv = brepeta

k = k + 1xnou = xv − (xv − xvv)f (xv)/(f (xv)− f (xvv))d = |xnou − xv |xvv = xv

xv = xnoupâna când d < eps sau k > nit

daca k ≤ nitscrie xnou

retur Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 106: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

41/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Comparatie - efortul de calcul

Depinde de eroarea impusa solutiei.

Efortul pentru o iteratie depinde de metoda.

Operatiile de referinta: evaluarea functiei f sau a derivateiacesteia.

Metoda Numar de evaluari pe iteratieBisectiei 2 pentru f (poate fi redusa la o evaluare)Falsei pozitii 2 pentru f (poate fi redusa la o evaluare)Muller 3 pentru f (poate fi redusa la o evaluare)Interpolarea patratica inversa 3 pentru f (poate fi redusa la o evaluare)Iteratia simpla 1 pentru fTangente paralele 1 pentru f

Newton 1 pentru f si 1 pentru f ′

Secante 2 pentru f (poate fi redusa la o evaluare)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 107: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

42/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Comparatie - convergenta

Bisectia

garantat convergenta în ipoteza schimbarii semnului;

deoarece4ak = 1/2ak−1 se spune ca are convergentaliniara.

Metoda falsei pozitii

garantat convergenta în ipoteza schimbarii semnului;

convegenta liniara, poate converge mai repede decâtmetoda bisectiei pentru ca alegerea punctului care împarteintervalul depinde de valorile functiei.

4ak = marginea erorii absolute - revedeti cursul despre eroriGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 108: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

43/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Comparatie - convergenta

Metodele bazate pe iteratiinu sunt garantat convergente;viteza de convergenta difera de la o metoda la alta;metoda Newton e cea mai rapid convergenta, areconvergenta patratica (demo pe slide-ul urmator).metoda secantelor are o viteza de convergenta între cealiniara si cea patratia ("superliniara"):ak ≈ Caα

k−1, α = (1 +√

5)/2 ≈ 1.61. [Cheney]metoda Muller are o viteza de convergenta superliniara,între secante si Newton: α ≈ 1.84.metoda interpolarii patratice inverse are o viteza deconvergenta superliniara, între secante si Newton: α ≈ 1.8.

Metoda Newton ar putea avea o eficienta globala superioara,chiar daca la fiecare iteratie timpul de calcul este mai mare.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 109: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

44/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Convergenta metodei Newton - demonstratie

Functia de iteratie g(x) = x − f (x)f ′(x)

Se verifica usor ca g′(x∗) = 0

g(x) = g(x∗) + (x − x∗)g′(x∗) + (x − x∗)2g′′(ζ)/2

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 110: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

44/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Convergenta metodei Newton - demonstratie

Functia de iteratie g(x) = x − f (x)f ′(x)

Se verifica usor ca g′(x∗) = 0

g(x) = g(x∗) + (x − x∗)g′(x∗) + (x − x∗)2g′′(ζ)/2

g(x) = g(x∗) + (x − x∗)2g′′(ζ)/2

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 111: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

44/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Convergenta metodei Newton - demonstratie

Functia de iteratie g(x) = x − f (x)f ′(x)

Se verifica usor ca g′(x∗) = 0

g(x) = g(x∗) + (x − x∗)g′(x∗) + (x − x∗)2g′′(ζ)/2

g(x) = g(x∗) + (x − x∗)2g′′(ζ)/2

g(xk−1) = g(x∗) + (xk−1 − x∗)2g′′(ζ)/2

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 112: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

44/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Convergenta metodei Newton - demonstratie

Functia de iteratie g(x) = x − f (x)f ′(x)

Se verifica usor ca g′(x∗) = 0

g(x) = g(x∗) + (x − x∗)g′(x∗) + (x − x∗)2g′′(ζ)/2

g(x) = g(x∗) + (x − x∗)2g′′(ζ)/2

g(xk−1) = g(x∗) + (xk−1 − x∗)2g′′(ζ)/2

xk = x∗ + (xk−1 − x∗)2g′′(ζ)/2

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 113: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

44/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Convergenta metodei Newton - demonstratie

Functia de iteratie g(x) = x − f (x)f ′(x)

Se verifica usor ca g′(x∗) = 0

g(x) = g(x∗) + (x − x∗)g′(x∗) + (x − x∗)2g′′(ζ)/2

g(x) = g(x∗) + (x − x∗)2g′′(ζ)/2

g(xk−1) = g(x∗) + (xk−1 − x∗)2g′′(ζ)/2

xk = x∗ + (xk−1 − x∗)2g′′(ζ)/2

|xk − x∗| ≤ M|(xk−1 − x∗)|2 (19)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 114: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

44/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

Metoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Convergenta metodei Newton - demonstratie

Functia de iteratie g(x) = x − f (x)f ′(x)

Se verifica usor ca g′(x∗) = 0

g(x) = g(x∗) + (x − x∗)g′(x∗) + (x − x∗)2g′′(ζ)/2

g(x) = g(x∗) + (x − x∗)2g′′(ζ)/2

g(xk−1) = g(x∗) + (xk−1 − x∗)2g′′(ζ)/2

xk = x∗ + (xk−1 − x∗)2g′′(ζ)/2

|xk − x∗| ≤ M|(xk−1 − x∗)|2 (19)

q.e.d.Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 115: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

45/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

...fara evaluarea derivatei

...cu evaluarea derivatei

Metode hibride

Metoda Brent-Dekker

Combina 3 metode: bisectia, secantelor si interpolareapatratica inversa;

Are robustetea data de bisectie dar poate fi rapidconvergenta ca metoda secantelor sau interpolareapatratica inversa.

Pentru detalii consultatihttps://en.wikipedia.org/wiki/Brent%27s_methodAceasta metoda este implementata în functia fzero dinMatlab.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 116: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

46/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

...fara evaluarea derivatei

...cu evaluarea derivatei

Metode hibride

Cea mai rapid convergenta metoda este metoda Newton, darea necesita:

1 o initializare in interiorul razei de convergenta (suficient deaproape de solutie);

2 o expresie pentru evaluarea derivatei.

Presupunând ca exista o expresie care permite evaluareaderivatei, o alta idee de a combina metodele prezentate este dea folosi la început un algoritm care nu necesita evaluareaderivatei (metode de ordin zero), urmând a comuta în final peiteratii Newton (metode de ordinul unu).

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 117: Rezolvarea ecuatiilor algebrice neliniarean.lmn.pub.ro/slides2017/05a_AN.pdf · 1/47 Ecua¸tii algebrice neliniare - formularea problemei Metode de rezolvare numerica - prin încadrare˘

47/47

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica - prin încadrare

Metode de rezolvare numerica - prin interpolareMetode de rezolvare numerica - prin iteratii de punct fix

Metode hibride

...fara evaluarea derivatei

...cu evaluarea derivatei

Referinte

[Ioan98] D. Ioan et al., Metode numerice în ingineria

electrica, Ed. Matrix Rom, Bucuresti, 1998. (Capitolul 16)

[Cheney] Ward Cheney and David Kincaid, Numerical

Mathematics and Computing, Brooks/Cole publishingCompany,2000.

[Heath] Michael Heath, Scientific computing. An

Introductory Survey, McGraw Hill 2002 (capitolul 5 dincarte) si alte resurse de ladisponibila la http://heath.cs.illinois.edu/scicomp/

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare