Itérations - suites et accélération de convergence
La suite x(k) converge quadratiquement pour p = 2 et cubiquement pour p = 3. Toutes ces suites convergent relativement raisonnablement c'est `a dire qu'on peut
Itérations - suites et accélération de convergence
Itérations - suites et accélération de convergence. 1 Rappels. 1.1 Conditionnement d'un probl`eme. Les probl`emes ne sont jamais résolus exactement et ce
Chapitre 4: Croissance divergence et convergence des suites - 4.1
Chapitre 4: Croissance divergence et convergence des suites. 4.1 Quelques définitions. Définitions : • Une suite est croissante si chaque terme est
Convergence de suites
Nov 5 2010 Conclusion
M41 Suites et séries de fonctions
?? f pour exprimer que (fn)n?N converge uniformément vers f (sur D). Exercice de cours 2. 1. Représenter graphiquement la notion de convergence uniforme à l'
Chapitre 1 Suites réelles et complexes
Une méthode naturelle est de construire une suite (un) dont on sait calculer les termes et qui converge vers ?. Alors par définition de la convergence
1. Suites et séries
Suites. 2. Séries. Convergence et divergence d'une suite. Une suite {an} admet une limite L et l'on écrit lim n?? an = L ou bien an ? L lorsque n ? ?
Convergence des suites numériques
Si les suites (un) et (wn) convergent vers une même limite finie l alors la suite (vn) est convergente et converge vers cette même limite l. Page 7. 14.
08 - Suites et séries de fonctions Cours complet
Définition 1.1 : suite de fonctions. Définition 1.2 : convergence simple d'une suite de fonctions sur un intervalle. Définition 1.3 : limite simple d'une
Chapitre 10 :Suites et séries de fonctions
converge simplement sur A. • Domaine de convergence simple : Il peut arriver qu'il n'y ait pas convergence simple sur tout le domaine de.
Universite de Picardie Jules Verne
Licence 2
Langage de programmation - Scilab
2019-2020
Iterations - suites et acceleration de convergence1 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 ordinateuren 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 f1(a) =et (f1)0(a) =1f
0(): Soienta0=a+het0la solution def(0)a0= 0. Nous avons0=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: 1Exemple(voir aussi [3])
Soitf(x) = (x1)4etf(x) = (x1)4. Les racines defsont= 1 avec multiplicite egale a 4, celles defsont = 1 +4pSi= 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
104la 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 obtenirnumeriquement 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; 20 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 0Erreur
Historique de Erreur Figure 1: Facteurs de convergence exact et numerique pour la serie harmonique (gauche). Historique de
l'erreur (droite) de limite 26On gagne un chire signicatif a chaque iteration, ceci est caracteristique des convergences lineaires.kS
njSn26981.6347818697798321.015219706839487e-02
991.6348839001848921.005016666333414e-02
Table 1: Valeurs approchees de
26par 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 32 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7
Iterations10-610
-510 -410 -310 -210 -110 0Facteur
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 0Erreur
Historique de Erreur
ErreurFigure 2: Facteurs de convergence exact et numerique pour la suite de Heron (gauche). Historique de
l'erreur (droite)kxTable 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: 4Les 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 51.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 et2sont 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))22x(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!11((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 du2, 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())2Ainsi siG() =alorsF() =.
Reciproquement, supposons queF() =etF0()6= 1. On peut appliquer la regle de l'H^ospital, il vientG() =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 100ité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 80510152010-8
10-7 10-6 10-5 10-4 10-3 10-2 10-1 100ité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
91.3.3 Extrapolation de Richardson
SoitA(h) une suite de nombres reels convergeant versa0lorsquehtend vers 0. Supposons queQ(h) admette le developpementA(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 formeB(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 106et 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 audela 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 113 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=11k2,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 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