View
212
Download
0
Category
Preview:
Citation preview
C. R. Acad. Sci. Paris, t. 326, SCrie I, p. 101 l-1014, 1998
Analyse num&ique/Numerical Analysis
Acc6Gration de la convergence par le CLalgorithrne
Abdelhaq FDIL
DCpartement de mathimatiques, &ole normale sup&ieure de Marrakech, B.P. no S 41,400OO Marrakech,
Maroc
(ReCu le 26 janvier 1998, accept& le 2 mars 1998)
R&urn& Des rksultats _d’accClCration de la convergence pour le 6algorithme (voir [3]) sont obtenus. Le O-algorithme est appliquk 2 la rksolution des equations non lirkaires et au calcul des dCrivCes d’une fonction en un point donnC. 0 Acadkmie des ScienceUElsevier, Paris
Convergence acceleration by the O-algorithm
Abstract. Some results of convergence acceleration for the B-algorithm (see [3]) are obtained. The G-algorithm is applied for solving nonlinear equations, and for computing function’s derivatives at a given point.O Acadtmie des Sciences/Elsevier, Paris
De nombreuses mCthodes d’analyse numkique conduisent B des suites (s,) telles que sn - s admette un dkveloppement asymptotique de la forme :
37% - s z Clh:’ + C2hE2 + . . ’ + CjhEJ + . . ‘, (1)
oti (h,) est une suite de nombres Gels convergente vers 0, 0 < o1 < cyz < . . . < cxi < . . . . Lorsque les puissances cyi, i 2 1, sont connues, on peut accClCrer (s,) par le E-algorithme (voir [ 11)
dans le cas oii (h,) v&Se certaines conditions. Dans cette Note, nous montrons qu’on peut accClCrer (s,) par le kkalgorithme, meme si les cxi ne
sont pas connues, dans le cas oti (h,) est telle que
h n+l --
hn h E d,h~‘+d,h$+-+djh$ +...;
oii 0 2 (hi 5 1, h # -1, 0 < PI < ,& < .+. < /Ji < . . . . Lorsque Yn, h, = A, ou Qn, h, = A”, on retrouve des rksultats obtenus dans [3].
Nous appliquons ici le &algorithme 2 1’acctlCration de la convergence des suites gCnCrCes par des pro&d& itkratifs de rksolution d’une Cquation non lint%ire, et 2 1’accClCration des suites obtenues par des mCthodes de dkrivation num&ique.
Note pr&entt!e par Roland GLOWINSKI.
0764-4442/98/0326010 1 I 0 AcadCmie des ScienceVElsevier, Paris 1011
A. Fdil
Le 6algorithme applique a une suite (sn), a pour regles :
@y) z.z s,, n 2 0,
@’ = @y) _ x~)A@~l A@;‘)
A (.$’ A6FI) , k>l,n>O.
(L’operateur de difference A agit sur l’incide superieur n : A?p) = TJ~“) - up’, AP+lup) =
AP(Aur))). Lorsque A(x~‘AG~~~) = 0, on pose : 6p’ = O~-~‘). La suite double (up’) est
dite suite auxiliaire du kalgorithme. En choisissant convenablement (XT?)), on retrouve certains
procedes d’acceleration de la convergence (voir [3]), en particulier : le AZ-it&e (CITY’ = I), le &-
it&t (
xp’ = &$ic”i” k--l 1
sgy > le O-algorithme (x?’ = +.
Ae:“_‘l”e~;‘l avec 6p’ = Ok’, oti @I”‘, i > 0, -
n 2 0, sont les quantites obtenues en appliquant le O-algorithme a (s,) (voir [2])), le T-algorithme
associe a l’extrapolation de Richardson de suite auxiliaire (a,) (x?) = s).
Notons par Ba (resp. BI) l’ensemble des suites (h,) telle que h,, + 0,
developpement asymptotique de la forme (2), avec 0 5 ]h( < 1 (resp. h ” 1). ( > * admette un
Soit (h,) E Be U B1. On designe par F(h,) l’ensemble des suites (sn) de la forme (1). Dans toute la suite, s designera la limite de (s,).
THBOR~ME 1. - Soient k > 1, (h,) E &, (sn) E FCh,). Si
1) 6pl - s M & aj,k-l h?-l, avec al,k-1 # 0, 0 < alXk-l < . . . < CE~,~-~ < . . .;
cn+l) 2) *- do,k = IF1 dj,k hi?“, UVeC 0 < pl,k < /!$k < . . ., do,k = 1 Si h # 0.
Alors, ou bien 3 N, V,n 2 N, 6r’ = s, ou bien 6c’ - s = jzl aj,k h:'.' avec a1.k # 0,
(1 + p) al,k-1 < Ql,k < . '. < aj,k < ..., oti p est tel que + i C # 0. n n
COROLLAIRE 1. - Soient k 2 1, (h,) E Bo, (sn) E FChn,. Si Vi E { 1,. . . : k}, F - do,i z
C d,,i h?“, avec 0 < pl,i < . . . < Sj9i < ~. ., d0.i = 1 lorsque h # 0, alors, ou bien 3 N, Vn > N, j=l
,t) = Gaul = s, 0~ &en Gp’ - s = o(~~-_‘,” - 5).
DEFINITION. - Soit 5’ une famille de suites convergentes. On dit que S est acce’le’rable par le 6-algorithme si pour toute suite (sn) E S, on a : pour tout k 2 1, ou bien 3 N, Vn >_ N, Gc’ = Gp), = s, 0~ bien Gp) - s = o(~~-:‘) - s).
THBOR~ME 2. - Soit (h,) E I&h,. L’ensemble Fchn, est acce’le’rable par le T-algorithme associe’
& l’extrapolation de Richardson avec (hlL) comme suite auxiliaire (
(n) _ xk L+n h ) n+k-hn ’ et par le
6-algorithme de suite auxiliaire x:’ = %.
Dkmonstration. - Decoule du corollaire 1. Le corollaire 1 montre que le A2-it&C (x?’ = 1) est le plus simple 6algorithme qui accelbre
u FW. (h,)e&
En utilisant le theoreme 1, avec un raisonnement par recurrence, on demontre le theoreme suivant :
THBORGME 3. - L’ensemble 5’ = U Fch,,j est acce’le’rable par le A’-it&r&, le @a-it&-k, le (hn)EBo
O-algorithme, le T-algorithme associe’ ti la transformation de Germain-Bonne CC;’ = ,,f+sknTi,, .
1012
AccGration de la convergence par le 6%algorithme
Remarque. - Lorsque h, = A”, 0 < 1x1 < 1, on retrouve des resultats obtenus dans [3].
THEOR-SME 4. - Soient k > 1, (hlL) E B1, (sn) E FCh ).
1) 6?J, - s = )gl aj,k-1 ht?‘, avec al kMl # 0 ‘kl SI, , , 1, k-l < “’ < aj,k-1 < . . .,
2) xp % do,kh,” + C dj., hf?, j=l
avec do,k # 0, -[j < p1.k < . . . < ,Ojj:k < . ‘, oli p est tel que
f$f + c # 0, alors, ou bien 3 N, Vn 2 N, ,p’ = s, 0~ &en .p’ - s N C aj,k h?.‘, avec n n
al,k # 0, (Yl,k-1 < al& < . ‘. < aj,k < . . . .
j=l
Une consCquence immediate du theoreme 4 est le corollaire suivant :
C~R~LLAIRE 2. - Soit k 2 1, (h,) E &, (sn) E F(h,). Si v’i E (1, . . . , k}, z$’ z do.; h,” + C d,,i h$‘,
j=l avec d0.i # 0, -0 < ,&,; < ‘.. < /3j,, < . .., oti P est tel que # -+ c # 0,
n R
alors, ou bien 3 N, Vn > N, Gp’ = s, ou bien Gp’ - s = ]Fl aj,khz”“, avec a1.k # 0,
al,&-1 < ffl,k < .’ ’ < “j,k < ‘...
TH~~OR~ZME 5. - Soit (h,) E B1. L’ensemble Fchn, est acce’lerable par les O-algorithmes associes aux
suites auxiliaires suivantes : x ~‘=h~~,k21,nL0,01i~esttelque~~~#O;~k -z, (n) _ h ” n n
k > 1, n 2 0; 5p) = *, k > 1, n > 0. -
Demonstration. - DCcoule du corollaire 2. Avec un raisonnement par recurrence et a l’aide du theoreme 4, on demontre aisement le theoreme
suivant :
THCOREME 6. - L’ensemble S = U Fc~,~J est accelerable par le O-algorithme, le C&-it&-e’ et (h,)EBI
par le T-algorithme associe a la transformation de Germain-Bonne.
Remarque. - Lorsque Vn, h, = $, on a 13 = -1, et on retrouve des resultats obtenus dans [3]. Considerons une suite (sn) generee par le pro&d6 iteratif suivant : so, s,+~ = G (s,). Supposons
que G est assez differentiable au voisinage de son point fixe, avec IG’ (s) 1 < 1. (G’ (s) designe la dCrivCe de G au point s.) D’apres des resultats dus a Walz 141, il existe un voisinage V de s tel que pout tout SO E V, s, - s = al h, + azh2, + . . . + akhk + o (hi), avec h, = (G’ (s))~ (resp. XP”, ou X depend de SO - s et 0 < 1x1 < 1) lorsque le pro&de iteratif est d’ordre 1 (resp. d’ordre p). La suite
(h,) appartient a Ba, par consequent (s,) est accelerable par les 6algorithmes du theoreme 3.
Exemple. - SO = 0, s,+l = e-+. s, + s g .5671432904097838.
Dans toute la suite, nous designons lfar dg)
(resp. d?), dp), (n)
le nombre de chiffres exacts de s,, et par dp)
d, ) le nombre de chiffres exact de la derniere quantite que l’on puisse calculer a partir de SO,...,~,, par le O-algorithme (resp. le 02-it&t, AZ-it&&, le T-algorithme associe a la transformation de Germain-Bonne).
Les resultats obtenus sont comme suit :
n (i( 71) 0
($“I 1
d(‘“) 2 d!“) .5
J’“) 1
8 3 5 6 7 4
12 3 10 11 16 9
14 3 12 14 17 12
16 4 15 15 17 17
1013
A. Fdil
Nous allons maintenant appliquer le 6algorithme au calcul de la derivee d’une fonction f(z) en un point za donne. Supposons qu’il existe un voisinage V de 20 tel que Qx E V, f(x)=f(xO)+ul (x-xO)nl+“‘+ub(x-x~)“~+o((x-xO)ai), avec ulfo, llal <.“<ak.
Soit (h,) E B. U Bt. La suite s, = ’ C-To+hn)-f (To1 hn est convergente vers f’ (x0). On a
(sn) E Fch,) ; par consequent, on peut accelerer (s,) par 1eS O-algorithmes present& precedemment.
Notons qu’on peut Cgalement utiliser le 6-algorithme pour calculer la derivee d’ordre k de f au point x0, en accelerant la convergence d’une suite (sn) d’approximations de f(‘) (~a), obtenue a l’aide d’une formule de derivation numerique.
Exemple. - f (z) = 2 (log2 + ~6l.~) cos (CC;) ; f’ (0) = log2. Pour h, = &, rz > 0, nous avons les resultats suivants :
n &“J 0
d(n) I
*!“I 2
($4 dj”) -I
8 4 9 9 7 7
12 5 8 8 13 9 14 7 13 15 13 15
16 7 16 16 13 14
RiSfkences bibliographiques
[l] Brezinski C., A general extrapolation algorithm, Numer. Math. 35 (1980) 175-187. [2] Brezinski C., Redivo Zaglia M., Extrapolation Methods, Theory_and Practice, North-Holland, Amsterdam, 1991.
[3] Fdil A., Some results of convergence acceleratrion for a general @-type algorithm, Appl. Numer. Math. 23 (1997) 219-240. [4] Walz G., Asymptotic expansions and acceleration of convergence for higher order iteration processes, Numer. Math. 59
(1991) 529-540.
1014
Recommended