[PDF] [PDF] CHAPITRE 2 - Cours 2x ? 1 3 1 ALGORITHME

View - Download [PDF] CHAPITRE 2 - Cours

Previous PDF

Next PDF

CHAPITRE2

ÉQUATIONS NON LINÉAIRES

hm@mat.ulaval.ca

TABLE DES MATIÈRES

1 Introduction 2

2 Méthode de la bissection 3

2.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

3 Méthode du point fixe 5

3.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

4 Méthode de Newton 10

4.1 Racines multiples d"ordre m . . . . . . . . . . . . . . . . . . . . . . .

11

5 Méthode de la sécante 12

5.1 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

6 Accélération de la convergence 14

6.1 Procédé d"Aitken . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

6.2 Méthode de Steffensen . . . . . . . . . . . . . . . . . . . . . . . . . .

15 Mat-2910 A-14page 1 de 16

1I NTRODUCTION

Dans ce chapitre nous nous intéressons à la recherche de racines d"une fonc- tion d"une seule variable : f:R!R f(x) =0 En général les solutions explicites sontdifficiles, voirimpossible, à obtenir analytiquement. Donc nous devons trouver desméthodes numériquesqui conduisent à des solutions approchées.

Exemple 1.1-e x1=0une solution

e x+1=0pas de solutions x

24sin(x) =0deux solutions

x

3+5x21=0trois solutions

-cos(x) =0une infinité de solutionsMat-2910 A-14page 2 de 16

2M ÉTHODE DE LA BISSECTION

Théorème 2.1Soit f:[a,b]!R une fonction continue. Si f(a)f(b)<0, alors il éxiste au moins un x2[a,b]tel que f(x) =0. Si de plus f est strictement monotone dans[a,b], alors cette racine est unique. 2.1

A LGORITHME

On posex1=a+b2

Sif(x1) =0, alorsx1est un zéro defet on s"arrête. Sinon, on construira x

2à partir dex1de la manière suivante :

Si f(x1)f(a)>0 alorsfchange de signe entrex1etbet on changea para:=x1. On pose ensuitex2=a+b2 Si f(x1)f(a)<0 alorsfchange de signe entrex1etaet on changeb parb:=x1. On pose ensuitex2=a+b2 n=1qui converge versxtelle quef(x) =0. 2.2

C ONVERGENCE

Soit[a0,b0] = [a,b]avecf(a)f(b)<0.

Soitxn=12

(bn1+an1),n=0,1,.

Il exite x2[a,b]tel que :

jxxnjba2 n De plus, pour atteindre la précisionjxxnjil suffit de choisir nln(ba)ln()ln(2) Le dernier résultat permet de fixer a priori le nombre d"itérations nen le reliant à la précision désirée. Exemple 2.1On cherche une racine de la fonction f(x) =x2+x6=0sur [1,2]

Intervalle initial : [a,b] = [1, 2]

k x f(x)

1 1.7500e+000 -1.1875e+000

2 1.8750e+000 -6.0938e-001

3 1.9375e+000 -3.0859e-001

4 1.9688e+000 -1.5527e-001

5 1.9844e+000 -7.7881e-002

9 1.9990e+000 -4.8819e-003Mat-2910 A-14page 3 de 16

10 1.9995e+000 -2.4412e-003

11 1.9998e+000 -1.2206e-003

12 1.9999e+000 -6.1034e-004

13 1.9999e+000 -3.0517e-004

14 2.0000e+000 -1.5259e-004

17 2.0000e+000 -1.9073e-005

18 2.0000e+000 -9.5367e-006

19 2.0000e+000 -4.7684e-006

20 2.0000e+000 -2.3842e-006Mat-2910 A-14page 4 de 16

3M ÉTHODE DU POINT FIXE

Définition 3.1Soit g une fonction continue sur[a,b]. On appelle point fixe de la fonction g tout point x2[a,b]vérifiant g(x) =x. -Soit g:[a,b]![a,b]une fonction continue. Alors la fonction g(x) admet au moins un point fixe dans[a,b]. P ourapprocher les racines de f(x) =0 par la méthode du point fixe on cherche donc une fonction g telle que f(x) =0()g(x) =x

Exemple 3.1

f(x) =x2x2 g(x) =x22,g(x) =px+2,g(x) =1+2x g(x) =x2+22x1 3.1

A LGORITHME

La méthode du point fixe consiste à construire à partir d"une approximation initialex0la suite des nombresxntel que : x n+1=g(xn),n=0,1, x

02[a,b]

-Choix de la fonctiong?

L asuite (xn)converge-t-elle?

Si la suite converge, sa limite xvérifie-t-ellex=g(x)? Comment estimer l"évolution de l"erreur en=xnxau cours des itérations? 3.2

C ONVERGENCE

Si dans [a,b],gvérifie

(i)x2[a,b] =)g(x)2[a,b] (ii)gune fonction continue, alors

1.gpossède au moins un point fixex2[a,b].

2. Si gest strictement contractante, c"est à dire qu"il éxistek, 0k<1 tel que

8x2[a,b],8y2[a,b]jg(x)g(y)jkjxyj

alors :Mat-2910 A-14page 5 de 16 (a)xest unique. (b)8x02[a,b], la suite(xn)définie parxn+1=g(xn)convergex Sigestd érivable, il est souvent plus commode d"exprimer unec ondition suffisante sur la dérivéeg0que de vérifier directement quegest une application contractante. -Soit g une fonction dérivable sur[a,b]. Si g0vérifiejg0(x)j<1,8x2 [a,b], alors g est strictement contractante dans[a,b]. -Soit g:[a,b]!Rune fonction donnée tels que : a) g est une contraction stricte sur[a,b]. b) g([a,b])[a,b], c"est à dire8x2[a,b],g(x)2[a,b]. Alors 1. La fonction g (x)admet un unique point fixe xdans[a,b]. 2.

P ourtoutx

02[a,b],lasuite(xn)n2Ndéfiniepar: xn+1=g(xn),(n

0)converge vers xlorsque n! 1.

Vitesse de convergence

On cherche à quantifier la vitesse de convergence de la suitexnen compa- rant la valeur absolue de l"erreuren=xnxentre deux itérations successives. La méthode du point fixe xn+1=g(xn)est dite d"ordrersijen+1jjenjra une limite finie quandntend vers+1. On dit que la suite (en)converge avec unordre de convergenceégal à rs"il existe une constanteC>0 telle que : jen+1jjenjrC, pournassez grand r=1 l" ordre de convergence est dit linéaire ou géométrique r>1 superlinéaire r=2 quadratique Il est souvent délicat de déterminer un intervalle[a,b]dans lequel les hy- pothèses (a) et (b) du théorème du point fixe sont vérifiées. Soit g:R!Rune fonction de classeC1et soitxun point fixe deg tel quejg0(x)j<1. Alors, il existe un voisinageIdextel que la suite (xn)n2Ndéfinie parxn+1=g(xn)avecx02I, converge versx.

De plus

1.

Si g0(x)6=0, la convergence est géométrique

2. S"il existe un entier r2 tel quegsoit de classeCrau voisinage dex et si g

0(x) ==g(r1)(x) =0,g(r)(x)6=0

alors, la convergence est d"ordrer.Mat-2910 A-14page 6 de 16

Interprétation géométrique

Exemple 3.2:

f(x) =x2+x6=0 1. x=g(x) =6x+1;x0=5 2. x=g(x) =p6x;x0=5 3. x=g(x) =6x2;x0=5

Exemple:

y= 6/(x+1); x_0 =5.000000E+00 k x eabsolue erelative

0 5.0000e+000 1.0000e+000 1.0000e+000

1 1.0000e+000 4.0000e+000 4.0000e+000

2 3.0000e+000 2.0000e+000 6.6667e-001

3 1.5000e+000 1.5000e+000 1.0000e+000

4 2.4000e+000 9.0000e-001 3.7500e-001

5 1.7647e+000 6.3529e-001 3.6000e-001

6 2.1702e+000 4.0551e-001 1.8685e-001

7 1.8926e+000 2.7760e-001 1.4667e-001

8 2.0742e+000 1.8163e-001 8.7564e-002

9 1.9517e+000 1.2255e-001 6.2790e-002

10 2.0327e+000 8.1030e-002 3.9863e-002

11 1.9784e+000 5.4312e-002 2.7452e-002

12 2.0145e+000 3.6077e-002 1.7908e-002

13 1.9904e+000 2.4109e-002 1.2113e-002

14 2.0064e+000 1.6047e-002 7.9976e-003

15 1.9957e+000 1.0709e-002 5.3661e-003

16 2.0029e+000 7.1344e-003 3.5621e-003

17 1.9981e+000 4.7585e-003 2.3815e-003

18 2.0013e+000 3.1713e-003 1.5847e-003

19 1.9992e+000 2.1147e-003 1.0578e-003Mat-2910 A-14page 7 de 16

20 2.0006e+000 1.4096e-003 7.0459e-004

21 1.9996e+000 9.3981e-004 4.6999e-004

22 2.0003e+000 6.2650e-004 3.1321e-004

23 1.9998e+000 4.1769e-004 2.0886e-004

24 2.0001e+000 2.7845e-004 1.3922e-004

25 1.9999e+000 1.8564e-004 9.2822e-005

29 2.0000e+000 3.6669e-005 1.8334e-005

30 2.0000e+000 2.4446e-005 1.2223e-005

Fonction :

y= sqrt(6-x); x_0 =5.000000E+00 k x eabsolue erelative

0 5.0000e+000 1.0000e+000 1.0000e+000

1 1.0000e+000 4.0000e+000 4.0000e+000

2 2.2361e+000 1.2361e+000 5.5279e-001

3 1.9401e+000 2.9598e-001 1.5256e-001

4 2.0149e+000 7.4837e-002 3.7142e-002

5 1.9963e+000 1.8657e-002 9.3460e-003

6 2.0009e+000 4.6676e-003 2.3327e-003

7 1.9998e+000 1.1667e-003 5.8341e-004

8 2.0001e+000 2.9168e-004 1.4584e-004

9 2.0000e+000 7.2920e-005 3.6460e-005

Fonction :

y= 6-x^2; x_0 =5.000000E+00 k x eabsolue erelative

0 5.0000e+000 1.0000e+000 1.0000e+000Mat-2910 A-14page 8 de 16

1 -1.9000e+001 2.4000e+001 1.2632e+000

2 -3.5500e+002 3.3600e+002 9.4648e-001

3 -1.2602e+005 1.2566e+005 9.9718e-001

4 -1.5881e+010 1.5881e+010 9.9999e-001

5 -2.5220e+020 2.5220e+020 1.0000e+000

6 -6.3605e+040 6.3605e+040 1.0000e+000

7 -4.0455e+081 4.0455e+081 1.0000e+000

8 -1.6366e+163 1.6366e+163 1.0000e+000

9 -Inf Inf NaN

10 -Inf NaN NaN

11 -Inf NaN NaN

12 -Inf NaN NaN

13 -Inf NaN NaNMat-2910 A-14page 9 de 16

4M ÉTHODE DENEWTON

Soit f:[a,b]!Rcontinue et dérivable

On cherche toujours à résoudref(x) =0.

Il est évident que sih(x)est une fonction non nulle, alorsxest une solution def(x) =0 si et seulement sixest un point fixe de g(x) =x+h(x)f(x) La méthode de Newton consiste alors à choisir la fonctionh(x)de telle sorte que la méthode des approximations successives appliquée à la fonctiong(x)soit d"ordre deux. C"est à dire tel queg0(x) =0. Ceci serait le cas si on choisit par exempleh(x) =1f

0(x)On a alors l" algorithme de Newton suivant :

x

0donné

x n+1=xnf(xn)f 0(xn)

Exemple 4.1f(x) =x2a=0

x n+1=12 (xn+ax n)

Convergence

On a le résultat de convergence suivant :

Théorème 4.1Soit f:[a,b]!Rune fonction de classe C3et soit x2]a,b[ un zéro de f(x). a) Si f

0(x)6=0, alors il existe un voisinage I de xtelle que la suite(xn)n2N

définie par : x

02I,8n2N,xn+1=xnf(xn)f

0(xn) existe et converge vers x de manière quadratique avec un taux de conver- gence égal àjf00(x)2f0(x)jlorsque f0(x)6=0. b) Si f

0(x) =0et f00(x)6=0, la suite(xn)n2Npeut encore être définie dans

un voisinage de x : si elle prend la valeur x, alors la construction s"arrête, sinon elle converge vers x géomètriquement.Mat-2910 A-14page 10 de 16

4.1R ACINES MULTIPLES D"ORDRE M

Sixest une racine de multiplicitémdef(x) =0, c"est à dire si f(x) =0,,f(m1)(x) =0,f(m)(x)6=0 alors on a : Théorème 4.2Soit xune racine de multiplicité m. Alors : 1. La convergence de la méthode de Newton classique appliquée à f (x) x n+1=xnf(xn)f 0(xn) est d" ordre 1. 2.

La méthode de Newton modifiée

x n+1=xnmf(xn)f 0(xn) converge quadratiquement.

Methode de Newton

Fonctions :

y= x^2 +x -6; y= 2*x +1;

Estimation initiale : x_0 = 5.000000E+00

Iter. x_i f(x_i)

0 5.0000000000E+00 2.400000E+01

1 2.8181818182E+00 4.760331E+00

2 2.1008717310E+00 5.145338E-01

3 2.0019560953E+00 9.784303E-03

4 2.0000007647E+00 3.823318E-06

5 2.0000000000E+00 5.844214E-13

6 2.0000000000E+00 0.000000E+00

Interprétation géométrique:

f(x) =x2+x6=0 ;x0=5 Convergence atteinte enn=5 :x5=2.000000000,=5.844214E13.Mat-2910 A-14page 11 de 16

5M ÉTHODE DE LA SÉCANTE

f:[a,b]!R, continue La méthode de la sécante est une variante de la méthode de Newton. En effet, la dérivéef0(xn)est remplacée par la pente f(xn)f(xn1)x nxn1

On obtient la méthode itérative suivante :

x

0,x12[a,b],x16=x0donnés

x n+1=xnf(xn)(xnxn1)f(xn)f(xn1),n=1,2, 5.1

C ONVERGENCE

Théorème 5.1Soit f:R!Rune fonction de classe C2et xun zéro de f(x) tel que f

0(x)6=0. Alors il existe un voisinage I de xtel que la suite(xn)n2N

définie par x

0,x12I,x16=x08n1

x n+1=xnf(xn)(xnxn1)f(xn)f(xn1) existe et converge vers x

De plus, si f

00(x)6=0, alors

lim n!1x f

00(x)f

0(x)‹

p1 où p=12 (1+p5).

Methode de la secante

Fonction :

y= x^2 +x -6;Mat-2910 A-14page 12 de 16

Estimations initiales : x_0 = 1.000000E+00

x_1 = 5.000000E+00

Iter. x_i f(x_i)

0 1.0000000000E+00 -4.000000E+00

1 5.0000000000E+00 2.400000E+01

2 1.5714285714E+00 -1.959184E+00

3 1.8301886792E+00 -8.202207E-01

4 2.0165339865E+00 8.294331E-02

5 1.9994207100E+00 -2.896115E-03

6 1.9999980905E+00 -9.547504E-06

7 2.0000000002E+00 1.106284E-09

8 2.0000000000E+00 0.000000E+00

9 2.0000000000E+00 0.000000E+00

Interprétation géométrique:

f(x) =x2+x6=0 ;x0=1,x1=5 Convergenceatteinteenn=7 :x7=2.0000000002E+00,=1.106284E

09.Mat-2910 A-14page 13 de 16

6A CCÉLÉRATION DE LA CONVERGENCE

Il y a deux façons pour accélélerer la convergence : -(Procédé d"Aitken). On peut transformer la suite(xn)en une suite(yn)qui converge vers la même limite et cela plus vite que la suite(xn). -(Méthode de Steffenson). On transforme la fonctiong(x)de façon à obtenir une méthode d" ordre plus élevée. 6.1

P ROCÉDÉ D"AITKEN

xn=xn+1xn,n=0,1, Théorème 6.1Soit x2Ret(xn)n2Nune suite réelle dont les termes ne sont jamais égaux à x

Alors la suite((yn)n2Ntelle que

y n=xn(xn)2

2xn=xnx2

n+12xn+1xn+x2 nx n+22xn+1+xn est bien définie pour n assez grand et vérifie lim n!1y nxx nx=0 Il faut remarquer içi que si la suite(yn)converge bien plus vite que la suitequotesdbs_dbs10.pdfusesText_16

[PDF] théorème de point fixe de schauder

[PDF] point fixe avion

[PDF] le fos définition

[PDF] le public du fos

[PDF] théorème du rang exercices

[PDF] cours de français sur objectif universitaire

[PDF] le fos et le fou

[PDF] théorème du rang dimension infinie

[PDF] exercices corrigés sur le théorème de l'énergie cinétique

[PDF] theoreme de derivation des integrales a parametres

[PDF] theoreme de l'hospital demonstration

[PDF] règle de l'hospital exercices corrigés

[PDF] théorème de l'hospital exercices

[PDF] règle de l'hopital en l'infini

[PDF] regle de l'hospital pdf