Zros des fonctions

Exo7

Vido partie 1. La dichotomieVido partie 2. La mthode de la scanteVido partie 3. La mthode de Newton

Dans ce chapitre nous allons appliquer toutes les notions prcdentes sur les suites et les fonctions, la recherche des zros des fonctions. Plus prcisment, nous allons voir trois mthodes afin detrouver des approximations des solutions dune quation du type ( f (x)= 0).

1. La dichotomie

1.1. Principe de la dichotomie

Le principe de dichotomie repose sur la version suivante du thorme des valeurs interm-diaires :

Thorme 1

Soit f : [a,b]R une fonction continue sur un segment.

Si f (a) f (b) 0, alors il existe ` [a,b] tel que f (`)= 0.

La condition f (a) f (b) 0 signifie que f (a) et f (b) sont de signes opposs (ou que lun des deux estnul). Lhypothse de continuit est essentielle !

x

y

a

f (a)< 0

b

f (b)> 0

`x

y

a

f (a)> 0

b

f (b)< 0

`

Ce thorme affirme quil existe au moins une solution de lquation ( f (x) = 0) dans lintervalle[a,b]. Pour le rendre effectif, et trouver une solution (approche) de lquation ( f (x)= 0), il sagitmaintenant de lappliquer sur un intervalle suffisamment petit. On va voir que cela permet dobte-nir un ` solution de lquation ( f (x)= 0) comme la limite dune suite.Voici comment construire une suite dintervalles embots, dont la longueur tend vers 0, et conte-nant chacun une solution de lquation ( f (x)= 0).On part dune fonction f : [a,b]R continue, avec a< b, et f (a) f (b) 0.

1

2Voici la premire tape de la construction : on regarde le signe de la valeur de la fonction fapplique au point milieu a+b2 .

Si f (a) f ( a+b2 ) 0, alors il existe c [a, a+b2 ] tel que f (c)= 0. Si f (a) f ( a+b2 ) > 0, cela implique que f ( a+b2 ) f (b) 0, et alors il existe c [ a+b2 ,b] tel quef (c)= 0.

x

y

aba+b

2

f ( a+b2 )> 0x

y

ab

a+b2

f ( a+b2 )< 0

Nous avons obtenu un intervalle de longueur moiti dans lequel lquation ( f (x)= 0) admet unesolution. On itre alors le procd pour diviser de nouveau lintervalle en deux.Voici le processus complet :

Au rang 0 :On pose a0 = a, b0 = b. Il existe une solution x0 de lquation ( f (x) = 0) dans lintervalle[a0,b0].

Au rang 1 : Si f (a0) f ( a0+b02 ) 0, alors on pose a1 = a0 et b1 = a0+b02 , sinon on pose a1 = a0+b02 et b1 = b. Dans les deux cas, il existe une solution x1 de lquation ( f (x)= 0) dans lintervalle [a1,b1].

... Au rang n : supposons construit un intervalle [an,bn], de longueur ba2n , et contenant une

solution xn de lquation ( f (x)= 0). Alors : Si f (an) f ( an+bn2 ) 0, alors on pose an+1 = an et bn+1 = an+bn2 , sinon on pose an+1 = an+bn2 et bn+1 = bn. Dans les deux cas, il existe une solution xn+1 de lquation ( f (x) = 0) dans lintervalle

[an+1,bn+1]. chaque tape on a

an xn bn.On arrte le processus ds que bnan = ba2n est infrieur la prcision souhaite.Comme (an) est par construction une suite croissante, (bn) une suite dcroissante, et (bnan) 0lorsque n+, les suites (an) et (bn) sont adjacentes et donc elles admettent une mme limite.Daprs le thorme des gendarmes, cest aussi la limite disons ` de la suite (xn). La continuit def montre que f (`)= limn+ f (xn)= limn+0= 0. Donc les suites (an) et (bn) tendent toutes lesdeux vers `, qui est une solution de lquation ( f (x)= 0).

1.2. Rsultats numriques pourp

10

Nous allons calculer une approximation dep

10. Soit la fonction f dfinie par f (x)= x210, cestune fonction continue sur R qui sannule en p10. De plus p10 est lunique solution positive delquation ( f (x)= 0). Nous pouvons restreindre la fonction f lintervalle [3,4] : en effet 32 = 9 10donc 3p10 et 42 = 16 10 donc 4p10. En dautre termes f (3) 0 et f (4) 0, donc lquation

3( f (x)= 0) admet une solution dans lintervalle [3,4] daprs le thorme des valeurs intermdiaires,et par unicit cest

p10, donc

p10 [3,4].

Notez que lon ne choisit pas pour f la fonction x 7 xp10 car on ne connat pas la valeur de p10.Cest ce que lon cherche calculer !

x

y

3 4

3.5

3.25

3.125

Voici les toutes premires tapes :

1. On pose a0 = 3 et b0 = 4, on a bien f (a0) 0 et f (b0) 0. On calcule a0+b02 = 3,5 puis f ( a0+b02 ) :f (3,5)= 3,5210= 2,25 0. Donc p10 est dans lintervalle [3;3,5] et on pose a1 = a0 = 3 etb1 = a0+b02 = 3,5.

2. On sait donc que f (a1) 0 et f (b1) 0. On calcule f ( a1+b12 ) = f (3,25) = 0,5625 0, on posea2 = 3 et b2 = 3,25.

3. On calcule f ( a2+b22 )= f (3,125)=0,23. . . 0. Comme f (b2) 0 alors cette fois f sannule surle second intervalle [ a2+b22 ,b2] et on pose a3 = a2+b22 = 3,125 et b3 = b2 = 3,25.

ce stade, on a prouv : 3,125p10 3,25.Voici la suite des tapes :

a0 = 3 b0 = 4a1 = 3 b1 = 3,5a2 = 3 b2 = 3,25a3 = 3,125 b3 = 3,25a4 = 3,125 b4 = 3,1875a5 = 3,15625 b5 = 3,1875a6 = 3,15625 b6 = 3,171875a7 = 3,15625 b7 = 3,164062. . .a8 = 3,16015. . . b8 = 3,164062. . .

Donc en 8 tapes on obtient lencadrement :

3,160p

10 3,165

En particulier, on vient dobtenir les deux premires dcimales :p

10= 3,16. . .

1.3. Rsultats numriques pour (1,10)1/12

Nous cherchons maintenant une approximation de (1,10)1/12. Soit f (x)= x121,10. On pose a0 = 1et b0 = 1,1. Alors f (a0)=0,10 0 et f (b0)= 2,038. . . 0.

4a0 = 1 b0 = 1,10a1 = 1 b1 = 1,05a2 = 1 b2 = 1,025a3 = 1 b3 = 1,0125a4 = 1,00625 b4 = 1,0125a5 = 1,00625 b5 = 1,00937. . .a6 = 1,00781. . . b6 = 1,00937. . .a7 = 1,00781. . . b7 = 1,00859. . .a8 = 1,00781. . . b8 = 1,00820. . .

Donc en 8 tapes on obtient lencadrement :

1,00781 (1,10)1/12 1,00821

1.4. Calcul de lerreur

La mthode de dichotomie a lnorme avantage de fournir un encadrement dune solution ` delquation ( f (x)= 0). Il est donc facile davoir une majoration de lerreur. En effet, chaque tape,la taille lintervalle contenant ` est divise par 2. Au dpart, on sait que ` [a,b] (de longueurba) ; puis ` [a1,b1] (de longueur ba2 ) ; puis ` [a2,b2] (de longueur ba4 ) ; ... ; [an,bn] tant delongueur ba2n .Si, par exemple, on souhaite obtenir une approximation de ` 10N prs, comme on sait quean ` bn, on obtient |`an| |bnan| = ba2n . Donc pour avoir |`an| 10N , il suffit de choisirn tel que ba2n 10N .Nous allons utiliser le logarithme dcimal :

ba2n

10N (ba)10N 2n

log(ba)+ log(10N ) log(2n) log(ba)+N n log2

n N+ log(ba)log2

Sachant log2= 0,301. . ., si par exemple ba 1, voici le nombre ditrations suffisantes pour avoirune prcision de 10N (ce qui correspond, peu prs, N chiffres exacts aprs la virgule).

1010 ( 10 dcimales) 34 itrations10100 ( 100 dcimales) 333 itrations101000 ( 1000 dcimales) 3322 itrations

Il faut entre 3 et 4 itrations supplmentaires pour obtenir une nouvelle dcimale.

Remarque

En toute rigueur il ne faut pas confondre prcision et nombre de dcimales exactes, parexemple 0,999 est une approximation de 1,000 103 prs, mais aucune dcimale aprs lavirgule nest exacte. En pratique, cest la prcision qui est la plus importante, mais il est plusfrappant de parler du nombre de dcimales exactes.

51.5. Algorithmes

Voici comment implmenter la dichotomie dans le langage Python. Tout dabord on dfinit unefonction f (ici par exemple f (x)= x210) :Algorithme . dichotomie.py (1)

def f(x):

return x*x - 10

Puis la dichotomie proprement dite : en entre de la fonction, on a pour variables a,b et n lenombre dtapes voulues.

Algorithme . dichotomie.py (2)

def dicho(a,b,n):

for i in range(n):

c = (a+b)/2

if f(a)*f(c) prec:

c = (a+b)/2

if f(a)*f(c)

6 return dichotomie(c,b,prec)

Mini-exercices

1. la main, calculer un encadrement 0,1 prs dep

3. Idem avec 3p

2.

2. Calculer une approximation des solutions de lquation x3+1= 3x.3. Est-il plus efficace de diviser lintervalle en 4 au lieu den 2 ? ( chaque itration, la

dichotomie classique ncessite lvaluation de f en une nouvelle valeur a+b2 pour uneprcision amliore dun facteur 2.)

4. crire un algorithme pour calculer plusieurs solutions de ( f (x)= 0).5. On se donne un tableau tri de taille N, rempli de nombres appartenant {1, . . . ,n}.

crire un algorithme qui teste si une valeur k apparat dans le tableau et en quelleposition.

2. La mthode de la scante

2.1. Principe de la scante

Lide de la mthode de la scante est trs simple : pour une fonction f continue sur un intervalle[a,b], et vrifiant f (a) 0, f (b)> 0, on trace le segment [AB] o A = (a, f (a)) et B= (b, f (b)). Si lesegment reste au-dessus du graphe de f alors la fonction sannule sur lintervalle [a,b] o (a,0)est le point dintersection de la droite (AB) avec laxe des abscisses. La droite (AB) sappelle lascante. On recommence en partant maintenant de lintervalle [a,b] pour obtenir une valeur a.

x

y

a b

A

B

a

A

a

A

7Proposition 1

Soit f : [a,b]R une fonction continue, strictement croissante et convexe telle que f (a) 0,f (b)> 0. Alors la suite dfinie par

a0 = a et an+1 = an banf (b) f (an)f (an)

est croissante et converge vers la solution ` de ( f (x)= 0).

Lhypothse f convexe signifie exactement que pour tout x,x dans [a,b] la scante (ou corde)entre (x, f (x)) et (x, f (x)) est au-dessus du graphe de f .

x

y

xx

(x, f (x))

(x, f (x))

Dmonstration

1. Justifions dabord la construction de la suite rcurrente.

Lquation de la droite passant par les deux points (a, f (a)) et (b, f (b)) est

y= (xa) f (b) f (a)ba + f (a)

Cette droite intersecte laxe des abscisses en (a,0) qui vrifie donc 0 = (a a) f (b) f (a)ba + f (a),donc a = a baf (b) f (a) f (a).

2. Croissance de (an).Montrons par rcurrence que f (an) 0. Cest vrai au rang 0 car f (a0)= f (a) 0 par hypothse.Supposons vraie lhypothse au rang n. Si an+1 < an (un cas qui savrera a posteriori jamais ra-lis), alors comme f est strictement croissante, on a f (an+1)< f (an), et en particulier f (an+1) 0.Sinon an+1 an. Comme f est convexe : la scante entre (an, f (an)) et (b, f (b)) est au-dessusdu graphe de f . En particulier le point (an+1,0) (qui est sur cette scante par dfinition an+1)est au-dessus du point (an+1, f (an+1)), et donc f (an+1) 0 aussi dans ce cas, ce qui conclut larcurrence.

Comme f (an) 0 et f est croissante, alors par la formule an+1 = an banf (b) f (an) f (an), on obtientque an+1 an.

3. Convergence de (an).La suite (an) est croissante et majore par b, donc elle converge. Notons ` sa limite. Parcontinuit f (an) f (`). Comme pour tout n, f (an) 0, on en dduit que f (`) 0. En parti-culier, comme on suppose f (b)> 0, on a `< b. Comme an `, an+1 `, f (an) f (`), lgalitan+1 = an banf (b) f (an) f (an) devient la limite (lorsque n +) : ` = `

b`f (b) f (`) f (`), ce qui

implique f (`)= 0.Conclusion : (an) converge vers la solution de ( f (x)= 0).

82.2. Rsultats numriques pourp

10

Pour a= 3, b= 4, f (x)= x210 voici les rsultats numriques, est aussi indique une majorationde lerreur n =

p10an (voir ci-aprs).

a0 = 3 0 0,1666. . .a1 = 3,14285714285. . . 1 0,02040. . .a2 = 3,16000000000. . . 2 0,00239. . .a3 = 3,16201117318. . . 3 0,00028. . .a4 = 3,16224648985. . . 4 3,28. . . 105a5 = 3,16227401437. . . 5 3,84. . . 106a6 = 3,16227723374. . . 6 4,49. . . 107a7 = 3,16227761029. . . 7 5,25. . . 108a8 = 3,16227765433. . . 8 6,14. . . 109

2.3. Rsultats numriques pour (1,10)1/12

Voici les rsultats numriques avec une majoration de lerreur n = (1,10)1/12 an, avec f (x) =x121,10, a= 1 et b= 1,1

a0 = 1 0 0,0083. . .a1 = 1,00467633. . . 1 0,0035. . .a2 = 1,00661950. . . 2 0,0014. . .a3 = 1,00741927. . . 3 0,00060. . .a4 = 1,00774712. . . 4 0,00024. . .a5 = 1,00788130. . . 5 0,00010. . .a6 = 1,00793618. . . 6 4,14. . . 105a7 = 1,00795862. . . 7 1,69. . . 105a8 = 1,00796779. . . 8 6,92. . . 106

2.4. Calcul de lerreur

La mthode de la scante fournit lencadrement an l b. Mais comme b est fixe cela ne donnepas dinformation exploitable pour |lan|. Voici une faon gnrale destimer lerreur, laide duthorme des accroissements finis.

Proposition 2

Soit f : IR une fonction drivable et ` tel que f (`)= 0. Sil existe une constante m> 0 telleque pour tout x I, | f (x)| m alors

|x`| | f (x)|m

pour tout x I.

Dmonstration

Par lingalit des accroissement finis entre x et ` : | f (x) f (`)| m|x `| mais f (`) = 0, do lamajoration.

9Exemple 1. Erreur pourp

10

Soit f (x)= x210 et lintervalle I = [3,4]. Alors f (x)= 2x donc | f (x)| 6 sur I. On pose doncm= 6, `=p10, x= an. On obtient lestimation de lerreur :

n = |`an| | f (an)|m =|a2n10|

6

Par exemple on a trouv a2 = 3,16... 3,17 doncp

10a2 |3,17210|6 = 0,489.

Pour a8 on a trouv a8 = 3,1622776543347473. . . doncp

10a8 |a2810|6 = 6,14. . . 109. On a

en fait 7 dcimales exactes aprs la virgule.

Dans la pratique, voici le nombre ditrations suffisantes pour avoir une prcision de 10n pourcet exemple. Grosso-modo, une itration de plus donne une dcimale supplmentaire.

1010 ( 10 dcimales) 10 itrations10100 ( 100 dcimales) 107 itrations101000 ( 1000 dcimales) 1073 itrations

Exemple 2. Erreur pour (1,10)1/12

On pose f (x)= x121,10, I = [1;1,10] et `= (1,10)1/12. Comme f (x)= 12x11, si on pose de plusm= 12, on a | f (x)| m pour x I. On obtient

n = |`an| |a12n 1,10|

12.

Par exemple a8 = 1.0079677973185432. . . donc

|(1,10)1/12a8| |a128 1,10|

12= 6,92. . . 106.

2.5. Algorithme

Voici lalgorithme : cest tout simplement la mise en uvre de la suite rcurrente (an).

Algorithme . secante.py

def secante(a,b,n):

for i in range(n):

a = a-f(a)*(b-a)/(f(b)-f(a))

return a

Mini-exercices

1. la main, calculer un encadrement 0,1 prs dep

3. Idem avec 3p

2.

2. Calculer une approximation des solutions de lquation x3+1= 3x.3. Calculer une approximation de la solution de lquation (cosx= 0) sur [0,pi]. Idem avec

(cosx= 2sinx).

10

4. tudier lquation (exp(x) = ln(x)). Donner une approximation de la (ou des) solu-tion(s) et une majoration de lerreur correspondante.

3. La mthode de Newton

3.1. Mthode de Newton

La mthode de Newton consiste remplacer la scante de la mthode prcdente par la tangente.Elle est dune redoutable efficacit.Partons dune fonction drivable f : [a,b] R et dun point u0 [a,b]. On appelle (u1,0) linter-section de la tangente au graphe de f en (u0, f (u0)) avec laxe des abscisses. Si u1 [a,b] alorson recommence lopration avec la tangente au point dabscisse u1. Ce processus conduit ladfinition dune suite rcurrente :

u0 [a,b] et un+1 = un f (un)f (un).

Dmonstration

En effet la tangente au point dabscisse un a pour quation : y= f (un)(xun)+ f (un). Donc le point (x,0)appartenant la tangente (et laxe des abscisses) vrifie 0= f (un)(xun)+ f (un). Do x= un f (un)f (un) .

f (un)

unun+1

3.2. Rsultats pourp

10

Pour calculerpa, on pose f (x) = x2a, avec f (x) = 2x. La suite issue de la mthode de Newton

est dtermine par u0 > 0 et la relation de rcurrence un+1 = un u2na

2un. Suite qui pour cet exemple

sappelle suite de Hron et que lon rcrit souvent

u0 > 0 et un+1 = 12(un+ aun

).

11

Proposition 3

Cette suite (un) converge verspa.

Pour le calcul dep

10, on pose par exemple u0 = 4, et on peut mme commencer les calculs lamain :

u0 = 4u1 = 12

(u0+ 10u0

)= 12(4+ 104

)= 134 = 3,25u2 = 12

(u1+ 10u1

)= 12(

134 + 1013

4

)= 329104 = 3,1634. . .

u3 = 12(u2+ 10u2

)= 21640168432 = 3,16227788. . .

u4 = 3,162277660168387. . .Pour u4 on obtient

p10= 3,1622776601683. . . avec dj 13 dcimales exactes !

Voici la preuve de la convergence de la suite (un) verspa.

Dmonstration

u0 > 0 et un+1 = 12(un+ aun

).

1. Montrons que un pa pour n 1.

Tout dabord

u2n+1a=14

(u2n+aun

)2a= 1

4u2n(u4n2au2n+a2)=

14

(u2na)2u2n

Donc u2n+1 a 0. Comme il est clair que pour tout n 0, un 0, on en dduit que pour toutn 0, un+1

pa. (Notez que u0 lui est quelconque.)

2. Montrons que (un)n1 est une suite dcroissante qui converge.Comme un+1un =

12

(1+ a

u2n

), et que pour n 1 on vient de voir que u2n a (donc au2n 1), alorsun+1

un 1, pour tout n 1.

Consquence : la suite (un)n1 est dcroissante et minore par 0 donc elle converge.

3. (un) converge verspa.

Notons ` la limite de (un). Alors un ` et un+1 `. Lorsque n+ dans la relation un+1 =12

(un+ aun

), on obtient ` = 12

(`+ a

`

). Ce qui conduit la relation `2 = a et par positivit de la

suite, `=pa.

3.3. Rsultats numriques pour (1,10)1/12

Pour calculer (1,10)1/12, on pose f (x)= x12a avec a= 1,10. On a f (x)= 12x11. On obtient un+1 =un u

12n a

12u11n. Ce que lon reformule ainsi :

u0 > 0 et un+1 = 112(11un+ a

u11n

).

Voici les rsultats numriques pour (1,10)1/12 en partant de u0 = 1.u0 = 1u1 = 1,0083333333333333. . .u2 = 1,0079748433368980. . .u3 = 1,0079741404315996. . .u4 = 1,0079741404289038. . .

12

Toutes les dcimales affiches pour u4 sont exactes : (1,10)1/12 = 1,0079741404289038. . .

3.4. Calcul de lerreur pourp

10

Proposition 4

1. Soit k tel que u1pa k. Alors pour tout n 1 :

unpa 2pa

(k

2pa

)2n12. Pour a= 10, u0 = 4, on a :

unp

10 8(

124

)2n1

Admirez la puissance de la mthode de Newton : 11 itrations donnent dj 1000 dcimales exactesaprs la virgule. Cette rapidit de convergence se justifie grce au calcul de lerreur : la prcisionest multiplie par 2 chaque tape, donc chaque itration le nombre de dcimales exactes double !

1010 ( 10 dcimales) 4 itrations10100 ( 100 dcimales) 8 itrations101000 ( 1000 dcimales) 11 itrations

Dmonstration

1. Dans la preuve de la proposition 3, nous avons vu lgalit :

u2n+1a=(u2na)2

4u2ndonc (un+1

pa)(un+1+

pa)= (un

pa)2(un+

pa)2

4u2n

Ainsi comme un pa pour n 1 :

un+1pa= (un

pa)2 1

un+1+pa 1

4

(1+

pa

un

)2 (un

pa)2 1

2pa 1

4(1+1)2 = 1

2pa

(unpa)2

Si k vrifie u1pa k, nous allons en dduire par rcurrence, pour tout n 1, la formule

unpa 2pa

(k

2pa

)2n1Cest vrai pour n= 1. Supposons la formule vraie au rang n, alors :

un+1pa 1

2pa

(unpa)2 = 1

2pa

(2pa)2((

k2pa

)2n1)2= 2pa

(k

2pa

)2nLa formule est donc vrai au rang suivant.

2. Pour a= 10 avec u0 = 4 on a u1 = 3,25. Comme 3p

10 4 alors u1p

10 u13 14 . On fixedonc k= 14 . Toujours par lencadrement 3

p10 4, la formule obtenue prcdemment devient

unpa 2 4

( 14

2 3

)2n1= 8(

124

)2n1.

13

3.5. Algorithme

Voici lalgorithme pour le calcul depa. On prcise en entre le rel a 0 dont on veut calculer la

racine et le nombre n ditrations.

Algorithme . newton.py

def racine_carree(a,n):

u=4 # N'importe qu'elle valeur > 0

for i in range(n):

u = 0.5*(u+a/u)

return u

En utilisant le module decimal le calcul de un pour n= 11 donne 1000 dcimales dep

10 :

3,1622776601683793319988935444327185337195551393252168268575048527925944386392382213442481083793002951873472841528400551485488560304538800146905195967001539033449216571792599406591501534741133394841240853169295770904715764610443692578790620378086099418283717115484063285529991185968245642033269616046913143361289497918902665295436126761787813500613881862785804636831349524780311437693346719738195131856784032312417954022183080458728446146002535775797028286440290244079778960345439891633492226526120677926516760310484366977937569261557205003698949094694218500073583488446438827311092891090423480542356534039072740197865437259396417260013069900009557844631096267906944183361301813028945417033158077316263863951937937046547652206320636865871978220493124260534541116093569798281324522970007988835237595853285792513629646865114976752171234595592380393756251253698551949553250999470388439903364661654706472349997961323434030218570521878366763457895107329828751579452157716521396263244383990184845609357626020

Mini-exercices

1. la calculette, calculer les trois premires tapes pour une approximation dep

3, sousforme de nombres rationnels. Idem avec 3

p2.

2. Implmenter la mthode de Newton, tant donnes une fonction f et sa drive f .

3. Calculer une approximation des solutions de lquation x3+1= 3x.4. Soit a> 0. Comment calculer 1a par une mthode de Newton ?5. Calculer n de sorte que un

p10 10` (avec u0 = 4, un+1 = 12

(un+ aun

), a= 10).

14

Auteurs

Auteurs : Arnaud Bodin, Niels Borne, Laura DesideriDessins : Benjamin Boutin

La dichotomiePrincipe de la dichotomieRsultats numriques pour 10Rsultats numriques pour (1,10)1/12Calcul de l'erreurAlgorithmes

La mthode de la scantePrincipe de la scanteRsultats numriques pour 10Rsultats numriques pour (1,10)1/12Calcul de l'erreurAlgorithme

La mthode de NewtonMthode de NewtonRsultats pour 10Rsultats numriques pour (1,10)1/12Calcul de l'erreur pour 10Algorithme