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