Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice...

108
1/43 Ecua¸ tii algebrice neliniare - formularea problemei Metode de rezolvare numeric˘ a Sisteme de ecua¸ tii algebrice neliniare Rezolvarea ecua¸ tiilor ¸ si sistemelor de ecua¸ tii algebrice neliniare Prof.dr.ing. Gabriela Ciuprina Universitatea "Politehnica" Bucure¸ sti, Facultatea de Inginerie Electric˘ a Suport didactic pentru disciplina Metode numerice, 2017-2018 Gabriela Ciuprina Ecua¸ tii ¸ si sisteme algebrice neliniare

Transcript of Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice...

Page 1: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

1/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Rezolvarea ecuatiilor si sistemelor de ecuatiialgebrice neliniare

Prof.dr.ing. Gabriela Ciuprina

Universitatea "Politehnica" Bucuresti, Facultatea de Inginerie Electrica

Suport didactic pentru disciplina Metode numerice, 2017-2018

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 2: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

2/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Cuprins

1 Ecuatii algebrice neliniare - formularea problemeiEnunt si buna formulareExemple

2 Metode de rezolvare numericaMetoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

3 Sisteme de ecuatii algebrice neliniareEnuntIteratii simpleNewton

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 3: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

3/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

4/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

4/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

4/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

5/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

5/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

5/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

6/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

7/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Enunt si buna formulareExemple

Exemplul 1

E

R

I=?

U=?

Se dau: E , R sicaracteristica diodeii = 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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

7/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

8/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

9/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

10/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

10/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

10/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

10/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

10/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

10/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

11/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

12/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

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 si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

13/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

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

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

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

g se numeste functie de iteratie

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 24: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

13/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

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

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

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

g se numeste functie de iteratie

1 g =?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 25: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

13/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

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

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

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

g se numeste functie de iteratie

1 g =?

2 x0 =?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 26: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

13/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

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

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

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

g se numeste functie de iteratie

1 g =?

2 x0 =?

3 Sirul este convergent?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 27: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

13/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Ideea metodei iteratiei simple

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

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

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

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 28: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

14/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - constructia lui g

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

xk = x (3)

x = g(x) (4)

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 29: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

15/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - constructia lui g

f (x) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 30: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

15/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 31: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

15/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 32: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

15/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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) (5)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 33: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

15/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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) (5)

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

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 34: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

16/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

g(x) = x + cf (x) (7)

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

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

Teorema - conditie suficienta de convergenta

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

g este contractie, daca:

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

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 35: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

16/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

g(x) = x + cf (x) (7)

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

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

Teorema - conditie suficienta de convergenta

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

g este contractie, daca:

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

L < 1 (strict!)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 36: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

17/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1, atunci sirul iteratiilor esteconvergent.

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

0

1

2

3

4

5

6

x

g(x) = x

ConvergentGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 37: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

17/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1, atunci sirul iteratiilor esteconvergent.

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

0

1

2

3

4

5

6

x

g(x) = x

ConvergentGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 38: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

17/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1, atunci sirul iteratiilor esteconvergent.

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

0

1

2

3

4

5

6

x

g(x) = x

ConvergentGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 39: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

17/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1, atunci sirul iteratiilor esteconvergent.

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

0

1

2

3

4

5

6

x

g(x) = x

ConvergentGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 40: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

17/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1, atunci sirul iteratiilor esteconvergent.

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

0

2

4

6

8

10

x

g(x) = x

DivergentGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 41: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

17/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1, atunci sirul iteratiilor esteconvergent.

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

0

2

4

6

8

10

x

g(x) = x

DivergentGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 42: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

17/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1, atunci sirul iteratiilor esteconvergent.

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

0

2

4

6

8

10

x

g(x) = x

DivergentGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 43: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

17/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Teorema - conditie suficienta de convergenta

Daca f este derivabila si |g′| < 1, atunci sirul iteratiilor esteconvergent.

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

0

2

4

6

8

10

x

g(x) = x

DivergentGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 44: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

18/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda iteratiei simple - convergenta

Conditia |g′| < 1 este echivalenta cu:

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

⇒ importanta constantei cCu 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∗| (11)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 45: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

19/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 46: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

20/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 47: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

21/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 )

. (12)

xk+1 = xk − f (xk )

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

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 48: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

22/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 49: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

22/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 50: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

22/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 51: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

22/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 52: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

22/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 53: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

23/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda Newton

Justificare: Ecuatia dreptei tangente:

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

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 54: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

24/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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)(15)

Semnificatia geometrica?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 55: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

25/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 56: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

25/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 57: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

25/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 58: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

25/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 59: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

25/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 60: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

25/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 61: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

25/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 62: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

25/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 63: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

25/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 64: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

26/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 65: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

26/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 66: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

26/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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

Ramâne necesitatea de a avea o expresie analitica pentru derivata f ′(x).

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 67: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

26/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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

Ramâ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 68: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

27/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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, (16)

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

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

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 69: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

28/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 70: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

28/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 71: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

28/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 72: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

28/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 73: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

28/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 74: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

28/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 75: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

28/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 76: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

28/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 77: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

29/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 78: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

29/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 79: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

29/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 80: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

29/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 81: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

29/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 82: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

29/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 83: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

30/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata, se alege secanta corespunzatoareunei 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 84: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

30/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata, se alege secanta corespunzatoareunei 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 85: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

30/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata, se alege secanta corespunzatoareunei 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 86: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

30/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata, se alege secanta corespunzatoareunei 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 87: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

30/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Metoda secantelor

Obs: varianta modificata, se alege secanta corespunzatoareunei 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 88: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

31/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 ≤ nit

scrie xnouretur

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 89: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

31/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 ≤ nit

scrie xnouretur

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 90: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

31/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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)/fdd = |xnou − xvechi|xvechi = xnou

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

daca k ≤ nit

scrie xnouretur

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 91: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

31/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 = b

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

xv = xnou

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

scrie xnou

returGabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 92: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

32/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 iteratie

Bisectiei 2 pentru f (poate fi redusa la o evaluare)Iteratia simpla 1 pentru f

Tangente 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 93: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

33/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Comparatie - convergenta

Bisectia

garantat convergenta în ipoteza schimbarii semnului;

deoarece ak = 1/2ak−1 se spune ca are convergentaliniara.ak = marginea erorii absolute - revedeti cursul despre erori.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 94: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

34/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda iteratiei simpleMetoda Newton (a tangentelor)Metoda secantelor

Comparatie - convergenta

Metodele bazate pe iteratii

nu 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 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 95: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

35/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 96: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

35/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 97: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

35/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 98: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

35/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 99: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

35/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 (18)

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 100: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

35/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

Metoda bisectieiMetoda 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 (18)

q.e.d.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 101: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

36/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

EnuntIteratii simpleNewton

Enunt

Se dau fk : IRn → IR, continue, k = 1, . . . ,n.

Se cer xk pentru care

f1(x1, x2, . . . , xn) = 0

f2(x1, x2, . . . , xn) = 0...

fn(x1, x2, . . . , xn) = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 102: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

37/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

EnuntIteratii simpleNewton

Enunt

Se da F : IRn ⇒ IR

n, continua.Se cere x ∈ IR

n pentru care

F(x) = 0 (19)

undeF = [f1, f2, . . . , fn]

T ∈ IRn

x = [x1, x2, . . . , xn]T ∈ IR

n

Exemplu: - circuite rezistive neliniare. Altele?

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 103: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

38/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

EnuntIteratii simpleNewton

Iteratii simple

Bisectia - nu se poate generalizaIteratia simpla:

x(k+1) = G(x(k)) (20)

G(x) = x + CF(x) (21)

unde C ∈ IRn×n

Procedura este convergenta daca

‖G‖ < 1

⇔‖I + CF′(x)‖

unde F′ este matricea Jacobian.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 104: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

39/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

EnuntIteratii simpleNewton

Iteratii simple

Matricea Jacobian

F′ =

∂f1∂x1

∂f1∂x2

· · · ∂f1∂xn

∂f2∂x1

∂f2∂x2

· · · ∂f2∂xn

...∂fn∂x1

∂fn∂x2

· · · ∂fn∂xn

(22)

Procedura e cu atât mai rapid convergenta cu cât ‖I + CF′(x)‖este mai mica.

⇒Viteza maxima de convergenta corespunde alegerii

‖I + CF′(x)‖ = 0

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 105: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

40/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

EnuntIteratii simpleNewton

Newton

Newton:C = −(F′(x))−1 (23)

Iteratii Newton:

x(k+1) = x(k) − (F′(x(k)))−1F(x(k)) (24)

Metoda esueaza daca se întâlneste o matrice Jacobiansingulara.

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 106: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

41/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

EnuntIteratii simpleNewton

Newton - algoritm

Nu se implementeaza formula

x(k+1) = x(k) − (F′(x(k)))−1F(x(k)) (25)

Daca notam z corectia:

x(k+1) = x(k) + z (26)

atunciz = −(F′(x(k)))−1F(x(k))

(F′(x(k)))z = −F(x(k)) (27)

La fiecare iteratie neliniara

1 se calculeaza corectia prin rezolvarea sist. algebric liniar (27);

2 se actualizeaza solutia cu (26).

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 107: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

42/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

EnuntIteratii simpleNewton

Alte variante

Newton-Kantorovich (tangente paralele)

(F′(x(0))z = −F(x(k)) (28)

x(k+1) = x(k) + z (29)

Sistemul de rezolvat are întotdeauna aceeasi matrice acoeficientilor ⇒ este eficienta folosirea factorizarii.Secante - derivatele partiale din formula Jacobianului secalculeaza numeric, cu formule de derivare regresiva deordinul 1.

∂fi

∂xj

=fi (x

(k−1)1 , x

(k−1)2 , . . . , x

(k)j

, . . . , x(k−1)n ) − fi (x

(k−1)1 , x

(k−1)2 , . . . , x

(k−1)j

, . . . , x(k−1)n )

x(k)j

− x(k−1)j

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare

Page 108: Rezolvarea ecuatiilor si sistemelor de ecuatii algebrice ...mn.lmn.pub.ro/2017/Slideuri2017/curs12_MN.pdf · Enun¸t s¸i buna formulare Exemple 2 Metode de rezolvare numerica ˘

43/43

Ecuatii algebrice neliniare - formularea problemeiMetode de rezolvare numerica

Sisteme de ecuatii algebrice neliniare

EnuntIteratii simpleNewton

Referinte

Pseudocod si complexitate - Cap.9 din[1] Gabriela Ciuprina, Mihai Rebican, Daniel Ioan - Metode numerice in ingineria electrica - Indrumar de

laborator pentru studentii facultatii de Inginerie electrica, Editura Printech, 2013, disponibil la

http://mn.lmn.pub.ro/indrumar/IndrumarMN_Printech2013.pdf

Gabriela Ciuprina Ecuatii si sisteme algebrice neliniare