[PDF] Itérations - suites et accélération de convergence

View - Download Itérations - suites et accélération de convergence

Previous PDF

Next PDF

Universite de Picardie Jules Verne

Licence 2

Langage de programmation - Scilab

2019-2020

Iterations - suites et acceleration de convergence

1 Rappels

1.1 Conditionnement d'un probleme

Les problemes ne sont jamais resolus exactement et, ce, pour de multiples raisons : dans un processus

iteratif on ne peut pas attendre quek! 1; plus generalement, les calculs sont eectues sur ordinateur

en precision nie et les erreurs d'arrondis (de troncature ou de cancellation) s'accumulent. Une question

cruciale pour la abilite des resultats est de savoir si ces erreurs restent "connees" durant les calculs

ou, au contraire, si elles peuvent se propager. La notion deconditionnement d'un problemepermet de caracteriser ce phenomene mais aussi de le quantier.

Considerons l'equation

f(x)a= 0:

Icifsera supposee aussi reguliere que necessaire, par exempleC1(I). Nous nous interessons aux variations

de la solution lorsque la donneeavarie : dans un monde ideal la solution de l'equation change peu sia

varie faiblement. Supposons quefadmette une fonction reciproque surI. On a alors f

1(a) =et (f1)0(a) =1f

0(): Soienta0=a+het0la solution def(0)a0= 0. Nous avons

0=f1(a0)f1(a)'(a0a)(f1)0(a):

Ainsi 0'hf 0():

La quantite

1jf0()jmesure donc la variation relative de la solution et des donnees. On se donne la

Denition 1Les conditionnements absolus et relatifs du problemes sont respectivement les nombres K abs(a) =1jf0()j; Krel=ajjjf0()j: 1

Exemple(voir aussi [3])

Soitf(x) = (x1)4etf(x) = (x1)4. Les racines defsont= 1 avec multiplicite egale a 4, celles defsont = 1 +4p

Si= 104, on trouve comme racines

1= 1:1; 2= 1 +i0:1; 2= 1i0:1; 4= 0:9 oui=p1:

La recherche des racines d'un polyn^ome est un probleme mal conditionne : lorsque la perturbationvaut

10

4la variation relative du resultat vaut 101, soit une erreur de 10% .

1.2 Vitesse de convergence

Denition 2Une suitex(k)converge versa l'ordrepsi

9C >0;9k02IN=limk!+1jx(k+1)jjx(k)jpC;8kk0

C est le facteur de convergence.

Lorsque lim

k!+1jx(k+1)jjx(k)j=c <1, on parle deconvergence geometriqueoulineaireet deconverge su- perlineairequandp >1. La suitex(k)convergequadratiquementpourp= 2 etcubiquementpourp= 3. Toutes ces suites convergent relativement raisonnablement, c'est a dire qu'on peut esperer obtenir

numeriquement une bonne approximation de la solution en iterant assez. Il existe pourtant des suites qui

convergent tellement lentement, que le calcul numerique de leur limite est ent^ache des erreurs d'arrondis

ou tout simplement ne converge pas. Ces suites correspondent au casp= 1 etc= 1, elles sont dites logarithmiques, on pourra consulter [1].

ExempleIllustration de la vitesse convergence.

Donnons-nous tout d'abord un critere pratique. Supposons que lim k!+1x (k+1)x (k)=c2]0;1[: On ne conna^t pasen general. Pour calculer numeriquement le facteur de convergence, on considere le rapport x (k+1)x(k)x (k)x(k1) dont la limite vautc(exercice). Une autre technique consiste a supposer quex(N)est une bonne approximation de la limite pourNassez grand et d'etudier le rapport x (k+1)x(N)x (k)x(N): Voici une suite convergeant lineairement : la serie harmonique S n=NX k=11k 2; 2

0 10 20 30 40 50 60 70 80 90 100

Iterations

0.40.50.60.70.80.91

Facteur

Facteur de Convergence (Serie harmonique)

Facteur numerique

Facteur exact

0 10 20 30 40 50 60 70 80 90 100

Iterations10-310

-210 -110 0

Erreur

Historique de Erreur Figure 1: Facteurs de convergence exact et numerique pour la serie harmonique (gauche). Historique de

l'erreur (droite) de limite 26

On gagne un chire signicatif a chaque iteration, ceci est caracteristique des convergences lineaires.kS

njSn26

981.6347818697798321.015219706839487e-02

991.6348839001848921.005016666333414e-02

Table 1: Valeurs approchees de

26
par la la serie harmonique

Voici une suite convergeant quadratiquement vers

p2 : la suite de Heron x (k+1)=12 x (k)+2x (k)

On gagne deux chires signicatifs a chaque iteration, ceci est caracteristique des convergences quadra-

tiques. Plus generalement et de la m^eme fa con, nous pouvons calculer numeriquement la racine n-iemed'un reela >0 en construisant la suite x k+1=xkxnkanx n1 k=xk 1 +1n ax nk1 = (11n )xk+1n ax n1 k: Les iterations de point xex(k+1)=f(x(k)) convergent en general lineairement. Nous avons plus precisement le 3

2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7

Iterations10-610

-510 -410 -310 -210 -110 0

Facteur

Facteur de Convergence (Suite de Heron)

Facteur numerique

Facteur exact

1 2 3 4 5 6 7

Iterations10-1610

-1410 -1210 -1010 -810 -610 -410 -210 0

Erreur

Historique de Erreur

ErreurFigure 2: Facteurs de convergence exact et numerique pour la suite de Heron (gauche). Historique de

l'erreur (droite)kx

Table 2: Valeurs approchees de

p2 par la methode de Newton,x0= 5 Theoreme 3SoitI= [a;b]un intervalle ferme et borne etfune fonction telle que i8x2[a;b];f(x)2[a;b] iif2 C1([a;b]) iii92]0;1[=jf0(x)j ;8x2[a;b] Alorsfa un unique point xexdans[a;b]et la suitex(k)converge versxpour toutx(0)2[a;b]. De plus, nous avons lim k!+1x (k+1)xx (k)x=f0(x) Preuve.L'hypotheseiiiimplique quefest fortement contractante, c'est une consequence du theoreme des accroissements nis. En eet, pour toutx;ydeI, il existe undeItel que f(x)f(y) =f0()(xy):

Il en decoule que

jf(x)f(y)j jxyj: 4

Les hypotheses du theoreme precedent sont satisfaites, nous sommes assures de l'existence et de l'unicite

du point xexdefainsi que de la convergence de la suitex(k). Pour etablir le resultat de vitesse de convergence, on ecrit x (k+1)x=f(x(k))f(x) =f0((k))(x(k)x) Commex(k)converge versxet que(k)est compris entrex(k)etx,(k)converge versxet, puis que festC1([a;b]), limk!+1f0((k)) =f0(x), d'ou le resultat.1.3 Acceleration de convergence Etant donnee une suitex(k)convergente vers, l'acceleration de convergence consiste a construire a partir dex(k)une suitey(k)congergente aussi vers, mais a un ordre superieur. Plus precisement, nous avons la Denition 4Soit(x(k))kune suite de reels convergente vers. On dit que la suite(y(k))kconstruire a partir de(x(k))kaccelere(x(k))ksi limk!+1y(k)= lim k!+1y (k)x (k)= 0 5

1.3.1 Methodes d'Aitken et de Steensen

Aitken

Considerons une suitex(k)qui converge geometriquement vers, c'est a dire que pourkassez grand, on peut ecrire (avec une faible erreur) x (k+1)=(x(k));avec2]1;1[: En ecrivant cette relation a l'etape suivante, il vient x (k+2)=(x(k+1)) si bien quepeut ^etre determine a partir des valeursx(k+j); j= 0;1;2 =x(k+2)x(k+1)x (k+1)x(k) et, en remplaantpar cette expression dans le premiere relation, nous trouvons =x(k)x(k+2)(x(k+1))2x (k+2)2x(k+1)+x(k)=x(k)(x(k))2 2x(k) ou et

2sont les operateurus aux dierences

x(k)=x(k+1)x(k);2x(k)= x(k+1)x(k)=x(k+2)2x(k+1)+x(k)

La methode du

2d'Aitken consiste a construire la suitey(k)par

Methode du2d'AitkenInitialisationx0etx1donnesPourk= 0;posery(k)=x(k)(x(k))2

2x(k)On montre le

Theoreme 5On suppose qu'il existe2]1;1[tel que la suite(x(k))k,x(k)6=verie x (k+1)= (+k)(x(k));aveclimk!+1k= 0 alors la suite(y(k))est bien denie et lim k!+1y (k)x (k)= 0:

Preuve.Par hypothese l'erreure(k)=x(k)verie

e (k+1)= (+k)e(k) 6 il s'ensuit que, d'une part,

2x(k)=e(k+2)2e(k+1)+e(k)

= ((+k+1)(+k)2(+k) + 1)e(k) =(1)2+k ou limk= 0. D'autre part x(k)=e(k+1)e(k) = ((1) +k)e(k)

Nous en deduisons que

2x(k)6= 0 pourkassez grand puisque (1)26= 0,e(k)6= 0 etk!0. Du coup,

y (k)est bien denie et nous pouvons ecrire y (k)=e(k)e(k)((1) +k)2 (1)2+k il s'ensuit que lim k!1y (k)x (k)= limk!1

1((1) +k)2(1)2+k!

= 0Considerons une suite a convergence geometrique, generee par exemple par une methode de point xe x (k+1)=F(x(k))

Steensen

La methode de Steensen consiste a reutiliser la suitey(k)dans le 2d'Aitken en remplacantx(k)par y

(k). Plus precisement soitFla fonction d'iteration de la suitex(k), c'est a dire la fonction liantx(k+1)a

x (k)par la relation x (k+1)=F(x(k))

La methode du

2s'ecrit comme

k=F(x(k)); k=F(k) y (k+1)=x(k)(kx(k))2 k2k+x(k): La methode de Steensen s'obtient prenant comme nouvelle fonction d'iteration, celle du

2, c'est a dire

G:x7!x(F(x)x)2F(F(x))2F(x) +x

Methode de SteffensenInitialisationx0etx1donnesPourk= 0;poserx(k+1)=G(x(k)) =x(k)F(F(x(k)))F(x(k))2F(F(x(k))2F(x(k)) +x(k)La methode de Steensen est donc une methode de point xe avec une nouvelle fonction d'iteration. Pour

autant, ces deux fonctions ont-elles toujours le m^eme point xe ? En general oui, c'est a dire sous une

condition simple portant surF0. On peut demontrer le 7 Theoreme 6SiG() =alorsF() =. Inversement, siF() =etF0()6= 1alorsG() =.

Preuve.Nous avons

(G())(F(F())2F() +) = (F())2

Ainsi siG() =alorsF() =.

Reciproquement, supposons queF() =etF0()6= 1. On peut appliquer la regle de l'H^ospital, il vient

G() =F(F()) +F0(F())F0()2F()F0()F

0(F())F0()2F0() + 1=+F0()22F0()1 +F0()22F0()=:1.3.2 Illustration0510152010-7

10-6 10-5 10-4 10-3 10-2 10-1 100
itérations erreur

Comparaison des méthodes

Suite originale

Δ2Figure 3: Comparaison des erreurs produite par la methode de point xe et par son acceleree par le

2 d'Aitken 8

0510152010-8

10-7 10-6 10-5 10-4 10-3 10-2 10-1 100
itérations erreur

Comparaison des méthodes

Suite originale

Δ2 SteffensenFigure 4: Comparaison des erreurs produites par la methode de point xe,

2d'Aitken et Steensen

9

1.3.3 Extrapolation de Richardson

SoitA(h) une suite de nombres reels convergeant versa0lorsquehtend vers 0. Supposons queQ(h) admette le developpement

A(h) =a0+a1h+a2h2+anhn+Rn+1(h)

Sia16= 0, la suiteA(h) approchea0au premier ordre. De maniere generale, soitk0le plus petit indice tel queak06= 0. AlorsA(h) approchea0a l'ordrek0. Pour rendre la convergence plus rapide, il faudrait pouvoir "eliminer" les coecients successifs deak0. A cet eet, on construit de proche en proche une suiteB(h) convergeant aussi versa0mais plus vite puisqu'avec un developpement en 0 sous la forme

B(h) =a0+bk1hk1+

aveck1>> k0.

Remarquons qu'en remplacanthparh, nous avons

A(h) =a0+a1h+a22h2+annhn+Rn+1(h)

Ainsi, en denissantB(h) par

B(h) =A(h)A(h)1=a0+b2h2++

La nouvelle suiteB(h) approchea0a l'ordre 2. Nous pouvons generaliser ce procede comme suit :

Methode de RombergInitialisationAm;0=A(mh); m= 0;;nPourk= 0;;poserAm;k+1=Am;k2(k+1)Am1;k12(k+1)2 Quelques criteres pratiques

2.1 Calcul de serie

2.1.1 Criteres analytiques

Il faut evidemment, avant tout, exploiter les proprietes eventuelles de la serie +1X i=1a i. Si par exemple la serie est alternee (ai= (1)ibi; bi>0; bi+1< bi;8i1), on verie aisement que jSSnj bn+1. On pourra alors determiner a l'avance, pourdonne, la valeur de n telle quejSSnj< .

2.1.2 Criteres numeriques

Bien evidemment, on ne dispose pas toujours de critere d'arr^et eta fortioripas d'estimation d'erreur (ce

qui implique que l'on somme a l'endroit en general). On peut neanmoins arr^eter les iterations lorsque la

quantite ajoutee est consideree comme "petite" i.e. si janj< oujanjjSnj< 10 Si on dispose d'une estimation d'erreur (dejSSnj), il convient de sommer la serie "a l'envers", pour eviter les eets de cumul, comme le montre l'exemple suivant :

Application :Sn= 112

+13 ++(1)n+1n . Calculer (en simple precision) cette serie en partant du debut, en partant de la n, avec une precision de 10

6et comparer le resultat obtenu aveclog(2.0).

2.2 Les suites

2.2.1 Criteres analytiques

M^eme remarque que pour le cas des series.

2.2.2 Criteres numeriques

On peut considerer les criteresjxn+1xnj< oujxn+1xnjjxnj<

2.2.3 Autres tests

Lorsque l'on met en uvre une methode iterative, il faut se donner un nombre maximal d'iterations au

dela duquel on decide qu'il est inutile de poursuivre le processus. En eet, dans le cas contraire, une

erreur de programmation peut conduire a une boucle eectuee indeniment.

2.3 Contr^olesa posteriori

Prendre des precautions dans la construction du programme ne sut pas toujours. Il faut pouvoir analyser

les resultats obtenus, ce qui permet de detecter des erreurs (s'il y en a).

2.3.1 Nombre de chires exacts

Soitxnune suite convergente versx. On mesure le nombre de chires decimaux exacts par e(xn;x) = log10jxjjxnxj Le nombre de chires exacts gagnes dexnaxn+1est alors donne par d n=e(xn+1;x)e(xn;x) = log10jxnxjjxn+1xj:

Sixnest une suite d'ordreri.e. si

0< limjxn+1xjjxnxjrlim

jxn+1xjjxnxjr<+1 alors le nombre de chires exacts est a peu pres multiplie parra chaque iteration. Exercice : comparer les resultats intermediaires dans les exercices 11

3 Exercices

Exercice 1On considere la suite

x (k+1)=12 x (k)+2x (k) oua >0.

1. Montrer que cette suite est convergente pour toutx(0)>0. Quelle est sa limite ?

2. Calculerx(k+1)paen fonction dex(k)pa.

Exercice 2 (Calcul de series)On considere les series suivantes Sn=nX k=11k

2,limn!+1Sn=26

Tn=nX k=1(1)k+1k ,limn!+1Tn= ln(2)

La formule de Gregory-LeibnitzUn= 4nX

k=1(1)k+12k1,limn!+1Un=

Vn= 8nX

k=01(4k+ 1)(4k+ 3),limn!+1Vn=

La (fameuse) formule de Simon Ploue

=1X i=048i+ 128i+ 418i+ 518i+ 616 i:quotesdbs_dbs10.pdfusesText_16

[PDF] Suites et démonstration par récurrence

[PDF] Suites et encadrement

[PDF] Suites et encore suites !

[PDF] Suites et exponentielle TL

[PDF] Suites et fonctions

[PDF] Suites et fonctions exponentielles

[PDF] Suites et fonctions Terminale

[PDF] suites et fonctions TS

[PDF] suites et intégrales exercices corrigés

[PDF] suites et intégrales Terminale s

[PDF] suites et limite et convergence

[PDF] Suites et limites : récurrence

[PDF] Suites et limites exercice

[PDF] Suites et loi binomiale

[PDF] Suites et Quantités