LABORATOIRE D'ANALYSE NUMERIQUE ET D'OPflMISAïiON …

no d'ordre : 663

LABORATOIRE D'ANALYSE NUMERIQUE ET D'OPflMISAïiON

O O&P fC I1UniversitC des Scjtacts et ; echntquts (Ie Lille Randtes-Artois

pour obtenir le t i tre de

DOCTEUR en MATHEMATIQUES APPLIQUEES P r

Gu! Antoine SEDOGBO

ACCELERATION DE LA CONVERGENCE DE CERTAINS SOUS-ENSEMBLES DE SUITES LOGARITHMIQUES

Membrts du jury

UNIVERSITE DES SCIENCES ET TECHNOLOGIES DE LILLE

DOYENS HONORAIRES DE L'ANCIENNE FACULTE DES SCIENCES

M. H. LEFEBVRE, M. PARREAU

PROFESSEURS HONORAIRES DES ANCIENNES FACULTES DE DROIT 0

MM. ARNOULT, BONTE, BROCHARD. CHAPPELON, CHAUDRON, CORDONNIER, DECUYPER, DEHEUVELS, DEHORS. DION, FAL'VEL. FLEURY, GERMAIN, GLACET, GONTIER, KOURGANOFF, LAMOTTE, LASSERRE. LELONG. LHOMME, LIEBAERT, MARTINOT-LAGARDE, MAZET. MICHEL, PEREZ. ROIG, ROSEAC. ROCELLE. SCHILTZ, SAVARD, ZAMANSKI, Mes BEAUJEU, LELONG.

PROFESSEUR EMERITE

M. A. LEBRUN

ANCIENS PRESIDENTS DE L'UNIVERSITE DES SCIENCES ET TECHNIQUES DE LILLE

hlhl. M. PARREAU, J. LOMBARD, M. MIGEON. J . CORTOIS. A.DUBRULLE

PRESIDENT DE L'UNIVERSITE DES SCIENCES ET TECHNOLOGIES DE LILLE

M. P. LOUIS

M. CHAMLEY Hervé M. CONSTANT Eugène M. ESCAIG Bemand M. FOURET René M. GABLLARD Robert M. LABLACHE COMBIER Alain M. LOMBARD Jacques M. MACKE Bruno

Géotechnique Elecuoniclue Physique du solide Physique du solide Electroniclur Chimie Sociologie Physique moléculaire et rayonnements atmosphériques

M. MIGEON Michel M. MONTREUIL Jean M. PARREAU Michel M. TRIDOT Gabriel

EUDIL Biochimie Analyse Chiniie appliqiiée

M. BACCHUS Pierre M. BIAY S Pierre M. BILLARD Jean M. BOILLY Bénoni M. BONNELLE Jean Pierre M. BOSCQ Denis M. BOUGHON Pierre M. BOURIQUET Robert M. BRASSELET Jean Paul M. BREZINSKI Claude M. BRIDOUX Michel M. BRUYELLE Pierre M. CARREZ Christian M. CELET Paul M. COEURE Gérard M. CORDOh%ER Vincent M. CROSNIER Yves Mme DACHARRY Monique M. DAUCHET Max M. DEBOCRSE Jean Pierre M. DEBRABAhT Pierre M. DECLERCQ Roger M. DEGAUQLT Pierre M. DESCHEPPER Joseph Mme DESSAUX Odile hl. DHAINAUT André Mme DHAINAUT Nicole M. DJAFARI Rouhani M. DORMARD Serge M. DOUKHAN Jean Claude M. DUBRULLE Alain M. DUPOUY Jean Paul M. DYMENT Arthur M. FOCT Jacques Jacques M. FOUQUART Yves M. FOURNET Bernard M. FRONTER Serge M. GLORIEUX Pierre M. GOSSELIN Gabriel M. GOUDMAND Pierre M. GRANELLE Jean Jacques M. GRUSON Laurent M. GUILBAULT Pierre M. GUILLAUME Jean M. HECTOR Joseph M. HENRY Jean Pierre M. HERMAN Maurice M. LACOSTE Louis M. LANGRAND Claude

PROFESSELTRS - lère CLASSE

Astronomie Géographie Physique du Solide Biologie Chimie-Phy siclue Probabilités Algèbre Biologie Végétale Géoméme et topologie Anal y se numérique Chimie Physique Géogrrtphie Infomrttique Géologie générale Analyse lnfom-iatique Electronique Géographie In forniatique Gestion des entreprises Géologie appliquée Sciences de gestion Electronique Sciences de gestion Spectroscopie de la réactivité chimique Biologie animale Biologie iinimale Ph!!sique Sciences Economiques Physique du solide Spectroscopie hertzienne Biologie Mécanique Métallurgie Optique am~osphérique Biochimie structurale Ecologie numénque Physique moléculaire et rayonnements atmosphériques Sociologie Chimie-Physique Sciences Economiques Algèbre Physiologie animale h4icrobiologie Giométne Génie mécanique Physique spatiale Biologie Végétale Prob;ibilirés et statistiques

M. LAïTEUX Michel M. LAVEINE Jean Pierre Mme LECLERCQ Ginette M. LEHMANN Daniel Mme LENOBLE Jacqueline M. LEROY Jean Marie M. LHENAFF René M. LHOMME Jean M. LOUAGE Françis M. LOUCHEUX Claude M. LUCQUIN Michel M. MAILLET Pierre M. MAROUF Nadir M. MICHEAU Pierre M. PAQUET Jacques M. PASZKOWSKI Stéfan M. PETiT Francis M. PORCHE7 Maurice M. POUZET Pierre M. POVY Lucien M. PROUVOST Jean M. RACZY Ladislas M. RAMAN Jean Pierre M. SALMER Georges M. SCHAMPS Joël Mme SCHWARZBACH Yvette M. SEGUIER Guy M. SIMON Michel M. SLIWA Henri M. SOMME Jean Melle SPIK Geneviève M. STANKIEWICZ François M. THIEBAULT François M. THOAMAS Jean Claude M. THUMERELLE Pierre M. TILLEU Jacques M. TOULOTïE Jean Marc M. TREANTON Jean René M. TURRELL Georges M. VANEECLOO Nicolas M. VAST Pierre M. VERBERT André M. VERINET Philippe M. VlDAL Pierre M. WALLART Françis M. WEINSTEIN Olivier M. ZEYTOUNIAN Radyadour

Infoimatique Paléoiitologie Catalyse Géométrie Physique atomique et nioléculaire Spectrochimie Géographie Chiniie organique biologique Elecmnique Chimie-Physique Chimie physique Sciences Economiques Sociologie Mécanique des fluides Géologie générale Mathématiques Chinue organique Biologie animale Modélisation - calcul scientifique Autoi~larique Minéralogie Electronique Sciences de gestion Electronique Spectroscopie moléculaire Géométrie Electrotechnique Sociologie Chinlie organique Géographie Biochimie Sciences Econorniques Sciences de la Terre Gkoméme - Topologie Démographie - Géographie humaine Physique théorique Automatique Sociologie du uavail Spectrochimie infrarouge et raman Sciences Econorniques Chinie inorganique Biochimie Génétique Automatique Spectrochimie infrarouge et raman Analyse économique de la recherche et développement Mécanique

PROFESSEURS - 2ème CIaASSE

M. ABRAHAM Francis M. ALLAMANDO Etienne M. ANDRIES Jean Claude M. ANTOIh'E Philippe M. BALL Steven M. BART André M. BASSERY Louis Mme BAïTIAU Yvonne M. BAUSIERE Roben M. BEGUIN Paul M. BELLET Jean M. BERNAGE Pascal M. BERTHOUD Arnaud M. BERTRAND Hugues M. BERZIIi Roben M. BISKUPSKI Gérard M. BKOUCHE Rudolphe M. BODARD Marcel M. BOHIN Jean Pierre M. BOIS Pierre M. BOISSLER Daniel M. BOIVIN Jean Claude M. BOUCHER Daniel M. BOUQUELET Stéphane M. BOUQUIN Henri M. BROCARD Jacques Mme BROUSMICHE Claudine M. BUISINE Daniel M. CAPURON Alfred M. CARRE François M. CATTEAU Jean Pierre M. CAY A ï T E Jean Louis M. CHAPOTON Alain M. CI-IARET Pierre M. CHIVE Maurice M. COMYN Gérard Mme CONSTANT Monique M. COQUERY Jean Marie M. CORIAT Benjamin Mme CORSIN Paule M. CORTOIS Jean M. COUTURIER Daniel M. CRAMPON Norbert M. CURGY Jean Jacques M. DANGOISSE Didier M. DE PARIS Jean Claude M. DECOSTER Didier M. DEJAEGER Roger M. DELAHAYE Jean Paul M. DELORME Pierre M. DELORME Robert M. DEMUNTER Paul Mme DEMUYNCK Claire M. DENEL Jicques M. DEPREZ Gilbert

Composants électroniques Biologie des organisnles Analyse Génétique Biologie animale Génie des procédés et réactions chimiques Géographie Systèmes électroniques Mécanique Physique atomique et moléculaire Physique atomique, moléculaire et du rayonnement Sciences Economiques Sciences Economiques A na1 y se Physique de l'état condensé et cristallographie Algèbre Biologie végétale Biochimie métabolique et cellulaire Mécanique Génie civil Specnochimie Physique Biologie appliquée aux enzymes Gestion Chimie Paléontologie Mécanique Biologie animale Géographie humaine Chimie organique Sciences Economiques Electronique Biochimie structurale Composants électroniques optiques Informatique théorique Coinposants électroniques et optiques Psychophysiologie Sciences Economiques Paléontologie Physique nucléaire et corpusculaire Chimie organique Tectolique géodynamique Biologie Physique théorique Analyse Composants électroniques et optiques Electrochimie et Cinétique Infoniiütiqiie Physiologie animale Sciences Econonliques Sociologie Physique aromiclue, moléculaire et du rayonnement Informatique Physique du solide - christallographie

M. DERIEUX Jean Claude M. DERYCKE Alain M. DESCAMPS Marc M. DEVRAINNE Pierre M. DEWAILLY Jean Michel M. DHAMELINCOURT Paul M. DI PERS10 Jean M. DUBAR Claude M. DUBOIS Henri M. DUBOIS Jean Jacques M. DUBUS Jean Paul M. DUPONT Christophe M. DUTHOIT Bruno Mme D W A L Anne Mme EVRARD Micheline M. FAKIR Sabah M. FARVACQUE Jean Louis M. FAUQUEMBERGUE Renaud M. FELiX Yves M. FERRIERE Jacky M. FISCHER Jean Claude M. FONTAINE Hubert M. FORSE Michel M. GADREY Jean M. GAMBLIN André M. GOBLOT Rémi M. GOURIEROUX Christian M. GREGORY Pierre M. GREMY Jean Paul M. GREVET Patrice M. GRMBLOT Jean M. GUELTON Michel M. GUICHAOUA André M. HAIMAN Georges M. HOUDART René M. HüEBSCHMANN Johannes M. HUTTNER Marc M. ISAERT Noël M. JACOB Gérard M. JACOB Pierre M. JEAN Raymond M. JOFFRE Patrick M. JOURNEL Gérard M. KOENIG Gérard M. KOSTRUBIEC Benjamin M. KREMBEL Jean Mme KRlFA Hadjila M. LANGEVIN Michel M. LASSALLE Bernard M. LE MEHAUTE Alain M. LEBFEVRE Yannic M. LECLERCQ Lucien M. LEFEBVRE Jacques M. LEFEBVRE Marc M. LEFEVRE Christian Melie LEGRAND Denise M. LEGRAND Michel M. LEGRAND Pierre Mme LEGRAND Solange Mme LEHMANN Josiane M. LEMAIRE Jean

Microbiologie In foniiatique Physique de l'état condensé et cristallographie Chiniie minérale Géogaphie humaine Chimie physique Physique de l'état condensé et cxistallographie Sociologie démographique Specaoscopie hertzienne Géographie Spectrométrie des solides Vie de la firme Génie civil Algèbre Génie des procédés et réactions chimiques Algèbre Phvsiaue de l'état condensé et cristallographie . . Composants électroniques Mathématiques Tectonique - Géodynamique Chiniie organique, minérale et analytique Dynamique des cristaux Sociologie Sciences économiques Géographie urbaine, indusmelle et démographie Algèbre Probabilités et statistiques I.A.E. Sociologie Sciences Economiques Chimie organique Chimie physique Sociologie Modélisation,calcul scientifique, statistiques Physique atomique Mathématiques Algèbre Physique de l'état condensé et cristallographie In forniatique Probabilités et statistiques Biologie des populations végétales Vie de la M e Spectroscopie hertzienne Sciences de gestion Géographie Biochimie sciences Economiques Algèbre Embryologie et biologie de la différenciation Modélisation,calcul scientifique,statistiques Physique atomique,moléculaire et du rayonnement Chimie physique Physique Composants électroniques et optiques Pétrologie Algèbre Asrroiiomie - Météorologie Chiniie Algèbre Xiirilyse Spectroscopie hertzienne

M. LE MAROIS Henri M. LEMOINE Yves M. LESCURE François M. LESENNE Jacques M. LOCQUENEUX Robert Mme LOPES Maria M. LOSFELD Joseph M. LOUAGE Francis M. MAHIEU François M. MAHIEU Jean Marie M. MAIZIERES Christian M. MANSY Jean Louis M. MAUNSSON Pamck M. MERIAUX Michel M. MERLIN Jean Claude M. MESMACQUE Gérard M. MESSELYN Jean M. MOCHE Raymond M. MONTEL Marc M. MORCELLET Michel M. MORE Marcel M. MORTREUX André Mme MOUNiER Yvonne M. NIAY Pierre M. NICOLE Jacques M. NOTELET Francis M. PALAVIT Gérard M. PARSY Fernand M. PECQUE Marcel M. PERROT Pierre M. PERTLJZON Emile M. PETIT Daniel M. PLIHON Dominique M. PONSOLLE Louis M. POSTAIRE Jack M. RAMBObX Serge M. RENARD Jean Pierre M. RENARD Philippe M. RICHARD Alain M. RIETSCH François M. ROBINET Jean Claude M. ROGALSKI Marc M. ROLLAND Paul M. ROLLET Philippe Mme ROUSSEL Isabelle M. ROUSSIGNOL Michel M. ROY Jean Claude M. SALERNO Françis M. SANCHOLLE Michel Mme SANDIG Anna Margarette M. SAWERYSYN Jean Pierre M. STAROSWIECKI Marcel M. STEEN Jean Pierre Mme STELLMACI-IER Irène M. STERBOUL François M. TAILLIEZ Roger M. TANRE Daniel M. THERY Pierre Mme TJOTTA Jacqueline M. TOURSEL Bernard M. TREANTON Jean René

Vie de la firme Biologie et physiologie végétales Algèbre Systèmes électroniques Physique théorique Mathématiques ' Informatique Electronique Sciences économiques Optique - Physique atomique Autoniatique Géologie Sciences Econoniiques EUDIL Chimie Génie mécanique Physique atomique et moléculaire ModéIisation,calcul scientifique,statistiques Physique du solide Chimie organique Physique de I'étar condensé et cristallographie Chimie organique Physiologie des structures contractiles Physique atomique,moléculaire et du rayonnement Spectrochirnie Systèmes électroniques Génie chimique Mécanique Chimie organique Chinie appliquée Physiologie animale Biologie des populations et écosystèmes Sciences Economiques Chimie physique Informatique indusmelle Biologie Géographie humaine Sciences de gestion Biologie animale Physique des polymères EUDIL Analyse Composants électroniques et optiques Sciences Economiques Géographie physique Modélisation,calcul scientifique,statistiques Psychophysiologie Sciences de gestion Biologie et physiologie végétales

Chimie physique Informatique Informatique Astronomie - Météorologie Informaticlue Géiiie alimentaire Geoniéme - Topologie Systènies électroniques Mathématiques Informatique Sociologie du travail

M. TURREL Georges M. VANDIJK Hendnk Mme VAN ISEGHEM Jeanine M. VANDORPE Bernard M. VASSEUR Christian M. VASSEUR Jacques Mme VIANO Marie Claude M. WACREhTER Jean Marie M. WARTEL Michel M. WATERLOT Michel M. WEICHERT Dieter M. WERNER Georges M. WIGNACOURT Jean Pierre M. WOZNIAK Michel Mme ZINN JUSTIN NicoIe

Spectroçhiniie infrarouge et raman

Modélisation,calcul scientifique,statistiques Chiniie minérale Auroniariqlie Biologie

Electronique Chimie inorganique géologie générale Génie mécanique Inforniatique théorique

Specuochirnie Algèbre

Je remercie le Professeur C. BREZINSKI pour ses conseils et Monsieur B.

GERMAIN-BONNE, Maître de Conférences, pour son rôle de consultant.

J'ai eu l'honneur d'apprécier les qualités humaines et scientifiques du Pro-

fesseur P. SABLONNIERE. Je lui témoigne ma profonde gratitude pour son aide

précieuse.

TABLE DES MATIERES

INTRODUCTION

CHAPITRE 1 Rappels. Définitions. Notations.

O - Introduction 5

1 - Suites presque équivalentes 5

2 - Définition de A, et LOGF, 5

3 - Développements asymptotiques des Wtes de LOGF,. Définition des sous-

classes de Ap et LOGF' 6

4 - Rappel des algorithmes 8

5 - Accélération de la convergence 1 1

6 - Résultats de calcul formel 1 1

CHAPITRE 2 Algorithmes généraux pour les suites de LOGF,

O - Introduction

1 -&-algorithme modifié

2 - A2 modifié itéré

3 - 02-algorithme itéré

4 - 0-algorithme

5 - Conclusion

CHAPITRE 3 Etude des sous-classes de LOGF,. p = 1,2 par le A2 d7Aitken

modifié itéré, le Ba-algorithme itéré, l'&-algorithme modifié et le 6-algorithme

O f l - Introduction 2 9

1 - &-algorithme modifié 2 9

2 - A2 modifié itéré 3 4

3 -' Ba-algorithme itéré

4 - 6-algorithme

5 - Remarques

6 - Conclusion 3 8

CHAPITRE 4 Combinaison A2 modifié et theta;! pour les suites de LOGF', p = 1 '2

O - Introduction 3 9 '

1 - Combinaison 3 9

2 - Résultats numériques

3 - Conclusion

CHAPITRE 5 Applicaitons à divers problèmes d'Analyse Numérique

O - Introduction

1 - Etude des suites du type

x, = /l1n-l/p + P ~ ~ - ~ I P + P ~ ~ - ~ I P + .. . , p E IR+ - {O; 1)

2 - Etude des suites du type

x, = p2n-2 + /34n-4 + B6n-6 + . . . 3 - Etude des suites du type

s, = +/33n-3/2 +/15n-5/2 + . . . + P 4 n - 2 +B6n-3 + ... 4 - Calcul d'intégrales singulières


6 - Conclusion

CHAPITRE 6 Détermination de la classe d'une suite

O - Introduction

1 - Détermination de la classe


C O N a U S I O N

REFERENCES

INTRODUCTION

Soit LOG = ((Sn)/ limn,+, Sn = S et limn,+,(S,+l - S)/(Sn - S) = 1). Une

suite de LOG est appelée suite à convergence logarithmique ou plus brièvement suite lo-

garit hmique.

Des suites ou des séries à convergence logarithmique apparaissent dans de nom-

breux problèmes d'Analyse Numérique : sommations de séries, calcul intégral, intégration

d'équations différentielles, problèmes aux limites.

Parmi les premiers travaux sur les suites logarithmiques, citons : LUBKIN [23], WYNN

[35], BREZINSKI [5], LEVIN [20].

SMITH et FORD [33] en 1979 comparent numériquement l'efficacité de plusieurs

transformations sur diverses suites logarithmiques.

En 1980, DELAHAYE et GERMAIN-BONNE (131 démontrent qu'il ne peut exister

un algorithme universel capable d'accélérer la convergence de toutes les suites logarithmi-

ques. Par conséquent toute étude d'accélération de la convergence logarithmique n e peut

concerner que des sous-ensembles de LOG. On est donc amené à préciser différentes

familles de suites logarithmiques, avant de construire des algorithmes d'accélération

adaptés.

KOWALEWSKI [19] en 1981, définit et étudie quelques sous-ensembles de LOG.

On trouvera dans [4, 30, 29, 3, 28, 9, 21, 34, 10, 26, 151 d'autres travaux relatifs à la

convergence logarit hrnique .

~n '1989 , MASOS [25] étudie le choix de la suite auxiliaire du E-algorithme en fonction

du développement asymptotique de la suite dont on veut accélérer la convergence.

2

Cette thèse développe une idée de SABLONNIERE [28] consistant à modi f ier , com-

parer et combiner des algori thmes exis tants pour accélérer la convergence de quelques sous-

ensembles de LOG.

On donne également quelques applications à divers problèmes d'Analyse Numérique.

Nous considérons d'une part les suites (Sn) de la forme

où f est une fonction suffisamment différentiable et d'autre part les suites dont le dévelop-

pement asymptotique de l'erreur s'écrit :

a, > 0, B, constant ou polynôme en logn. Pour ces suites nous étudions le @-algorithme [4],

le d2-algorithme [5] itéré, des modifications du A2 d' Aitken [Il itéré et de l'~-algorithrne[3t,u. Nr,,,, ;k , j ,c ,n .~ , c-csz : ,~ A,, c ~ * n b , r > - , b ~ ~ i + du. LL2 . i 'A. tr iu* rncd.+.;' ut QI- c c \ < j ~ . . thma .

Ces différents algori thmes permet tent non seulement d'accélérer la convergence des

suites considérées mais aussi de donner une estimation asymptotique de l'erreur. Dans

certains cas, on obtient même un encadrement de la limite.

Toutes nos démonstrations sont ramenées à des développements de calcul formel.

Considérons par exemple la transformation définie par la première colonne paire de 1 '~ -

algorithme et notons-la E* .

Pour toute suite (x,), cette transformation peut s'écrire :

avec N = Arn+, et E = -AS,.

- Si (x,) est u n e sui te de point f i e , x,+l = f(xn), on pose x, = x . On a alors :

On définit ainsi une fonction e2(x) dont on peut étudier le développement en série

formelle de la variable x, par une technique que nous appelerons la technique du point fixe.

- Si (x,), de limite nulle, a un développement asymptotique tel que Zn = g($), on pose :

avec f (x) = x/(l + 2).

On définit aussi dans ce cas une fonction ez(x) différente de la précédente, dont on

peut étudier le développement par une technique qui sera appelée celle du développement

explicite.

La thèse est divisée en six chapitres.

Dans le Premier Chapitre, nous faisons des rappels et fixons les notations. Nous

définissons des sous-ensembles de LOG, notés LOGFp et contenant des suites du type :

Sn+1 = S n + a,+l(Sn - S)'+' + O ((Sn - S)P+2) ,

pour lequelles nous donnons des développements asymptotiques plus précis. Nous présen-

tons aussi le schéma général du A2 d'Aitken modifié et de l'e-algorithme modifié.

Dans le Deuxième Chapitre, nous nous proposons d'accélérer la convergence des

suites générales de LOGFp définies précédemment. Les algorithmes étudiés sont : 1 '~ -

algorithme modifié, le A2 modifié itéré, le O2 itéré et le &algorithme. Il est évident que

des renseignements plus précis sur une suite permettent une meilleure accélération de sa

convergence. Nous considérons donc aux troisième et quatrième chapitres, certains

sous-ensembles de LOGFI et LOGF2 pour lesquels nous présentons des algorithmes

appropriés.

Nous utilisons, pour les démonstrations de ces chapitres, la technique du point fixe

définie plus haut.

Dans divers problèmes d'Analyse Numérique, la solution s est approchée par les

termes d'une suite (s,). Quand le développement asymptotique de l'erreur en = s, - s est

semblable à celui d'une suite de LOGF,, il suffit d'appliquer les algorithmes des chapitres

précédents. Le but du cinquième chapitre est de considérer des développements autres

que ceux apparaissant dans LOGF'. Il s'agit essentiellement des suites (en) du type :

Tous les algorithmes proposés dans les chapitres précédents supposent connus les réels p

et 8 définis plus haut.

Nous étudions au sixième chapitre des estimations de ces réels en développant

des idées de BJORSTAD, DAHLQUIST, GROSSE [8]. Les démonstrations de ces deux

chapitres utilisent la technique du développement explici te.

Certains résultat,^ de cette thèse sont publiés dans [31, 321.

CHAPITRE 1

5

CHAPITRE 1

O - Introduction

Nous donnons ci-dessous des rappels, définitions et notations. A la fin du chapitre on

trouvera des résultats de calcul formel utilisés dans les démonstrations ultérieures.

1. Suites presque équivalentes

On dira que deux suites (un) et (un) de limite nulle, sont presque équivalentes ssi il

existe un entier no et un réel A non nul trb que U n - un, pour tout YI 2 no. On notera

alors un ~ - l . un.

2 - Définition de A, et LOGF,

Rappelons les définitions données par SABLONNIERE [28]. Soit A, l'ensemble des

fonctions f admettant le développement suivant au voisinage de O :

f ( X I = x + C aP+ixp+', p E N*, < O. i > l

Soit

L O G 4 = {(xn) /xn+~ = f(xn), f E A,, lim xn = 0). n++m

Rappelons maintenant quelques propriétés des sui tes de LOGF,

Théorème 1.1. : ( i ) V(xn) E LOGF,, x. n-"~ . (ii) LOGF, c LOGSF

" '-' = limn,+, w, = 1) . OÙ LOCSF = {(sn)/ limn,+, sz-s (tii) Toute suite d e LOGF, est monotone (strictement) à pa~tir d'un certain rang.

Démonstration.

(i) Cf. [12]

(ii), (iii) Cf. [19]

3 - Développements asymptotiques des suites de LOGF,.

Définition des sous-classes de A, et LOGF, pour p = 1,2 [28]

D'après DE BRUIJN [12, chap. 81 pour chaque fonction f de A,, il existe une unique

fonction

vérifiant l'équation fonctionnelle :

Définissons, pour toute fonction f , f n par :

et pour tout n 2 1, f n = f ~ f , - ~ . En posant xo = a: et xn = f ( ~ , - ~ ) = f,(x), la relation

(2) donne

1CI(xn) = $(fn(x)) = n + $(x).

Les coefficients de $ sont alors calculés explicitement, ce qui permet de déterminer

les développements asymptotiques des suites de LOGFp, pour tout p f N*. Nous donnons

ci-dessous les résultats précis pour p = 1,2 [28].

Théorème 1.2. : Soit f E A l , f (x) = x + xi>2 aiXi. O n a : -

avec

On définit :

I A: = {f E AI/CO # O) et LOGF; = {(x,)/ f E A;)

A:' = {f f Al/co = O) et LOGF," = {(x,)/ f E A:)

(i) Si (x , ) E LOGF;, alors le développement asymptotique d e (2,) est d e la forme .

(22) Si (x , ) E LOGF;', on a :

Remarque. Le coefficient co de $ est important puisque de sa présence dépend l'existence

de logarithmes dans le développement asymptotique de la suite.

Exemple l . f ( x ) = x - x2 , ( f E A i )

1 1 13 3 $ ( x ) = x-' + logx + -x + -x2 + -x + . . .

2 3 36

Exemple 2. f ( x ) = x - x2 + x 3 , ( f E A f )

Théorème 1.3. : Soit f E A2 , f ( 2 ) = x + C a i x i , on a a1013 : i23

où CO = 312 + aq/oi - a5/ai.

On définit les sous-ensembles :

A: = { f E A 2 / f impaire CO # O ) et LOGF: = { ( z , ) / f E A i )

A:' = { f E A 2 / f impaire et co = 0)etLOGFS" = { (x , ) / f E Ag')

8

(i) Si ( x , ) E LOGF;, on a le développement asymptotique :

(ii) Si ( 2 , ) E LOGFS', on a le d.a. :

(iii) Si (2,) E LOGF;", on a le d.a. :

- 1 12 sn = aln + a4n-3/2 + a9n-'I2 + . . .

Exemple 3 : f ( x ) = x - x3 + x 4 , (f E A;)

1 - 2 1 3 1 2 $ ( x ) = - x + z-' + 410gz - - x - -x + . . .

2 2 8 x , = (2,)-'1' + (2n)-' - (logn + 2 - 4$(xo) - 1 0 ~ 2 ) n - ~ / ~ / 8 & + . . .

Exemple 4 : f ( x ) = sin x , (f E Ag)

Exemple 5 : f ( x ) = x - x 3 + ? x 5 , ( f E Ag')

4 - Rappel des algorithmes

Au Au Pour toute suite ( u n ) nous notons R[un] = où A u , = - un et

A 2 u n = AU^+^ - Au,.

Le A2 d'Aitken transforme (un ) en

Il existe plusieurs autres formes de cet algorithme. En voici deux :

b ) La trans format ion O2 [5]

Le O2 transforme une suite (un ) en la suite (2,) définie par :

Afin d'éviter toute confusion avec les algorithmes 8 et O2 itéré définis plus loin, nous

noterons dorénavant

ê(un) = @2(un)-

c ) é-a lgor i thme 15'6, 41

Pour une suite ( u n ) donnée, on pose :

( n ) (n+l) (n+i) puis pour tout k > O : E ~ + ~ = 6k-1 + [ck - E t ) ] - 1 , vn E N.

On en déduit que

E Z L 2 = E2*+ l ) + 1/A

Pour une suite ( u n ) vérifiant :

( u = lim u n ) n-++oo

le E-algorithme s'écrit :

e ) p-algorithme [4]

Soit ( u n ) une suite.

(x , ) étant une suite auxiliaire.

Pour une suite ( u n ) , le 8-algorithme est défini de la façon suivante :

g ) Itération d'algorithmes.

Soit 7 une transformation et soit (un) une suite.

Posons u t ) = un,Vn E N et u n ) = 7(uf- '))vn E N,Vk E N*.

( k ) On dira que la suite (un ) est la k-ième itération de la transformation 7 appliquée à (un).

5. Accélération de la convergence

Soient (2,) une suite de limite nulle et T une transformation. Si (2,) a un

développement asymptotique du type xn = g(x) - a x a , on dit que T accélère la con-

vergence de (x,) ssi

6. Résultats de calcul formel [9, 271

Les démonstrations des théorèmes d'accélération de la convergence que nous ferons

utilisent deux principes : la récurrence et les développements de fonctions composées.

Voici les résultats dont nous nous servirons :

a ) Les po lynômes de Bell

Ce sont des polynômes à une ou plusieurs variables définis par :

n, k entiers tels que 1 5 k 5 n.

La sommation a lieu pour chaque groupe d'entiers naturels ci vérifiant

Exemples.

Les ( nX ) designent les coefficients binomiaux. Par convention ( ) = O s i k > n .

b) Développement de gof

Soient f ( x ) = Ci>] aixi et g ( ~ ) = p i X i . Posons g ~ f ( ~ ) = Ci>l y i ~ i - -

les Bn,k désignant les polynômes de Bell. Plus explicitement,

Y n = Pria; + P n - i ( n - 1 ) 0 ; - ~ ~ . 2

+(n - 2)Pn-2 [a;-3a3 + f(n - 3)a;-*a;]

+(n - 3)Pn-3 + (n - 4)a;-5a2a3 + f (n - 4 ) ( n - 5 ) c ~ ; - ~ a i ]

1 n-6 2 +(n, - 4)Pn-4 [a;-5a5 + (n - 5 ) ( ~ ; - ~ o z a 4 + ?al a 3 )

Si f 2 ( x ) = f o f ( x ) = En>, anxn , on obtient a , en remplaçant dans y,, Pi par a i

pour tout i. Donnons les expressions de y, et a , pour 1 5 n 5 7, dans le cas où al = 1 ;

c'est le cas qui sera le plus courant puisque pour les suites de point fixe considérées,

f ( ~ ) = X + + . . .

C ) D é v e l o p p e m e n t d e [l/ f ( x ) lm = [f ( x ) ] - ~

Soit f ( x ) = x + cr2x2 + a3x3 + . . . ( a 1 = 1).

2 avec u = u2x + 0132 + . = j ( x ) .

Mais ( 1 +u)-" = 1 + C . 3 21 ( - l ) j

On peut calculer g(f(x)) en appliquant la formule du paragraphe précédent, ce qui

donne

Donnons quelques expressions de y, pour m = 1.

d ) Développement d e [f (x)]

Un calcul analogue à celui du paragraphe précédent permet d'écrire

e) Développement d e g(x/l + x) et g(x/l+ 22)

g(x/1+ x) = C Y n x n et g(x/i + 2s) = C b,xn. i l 1 nll

On obtient y, et 6, en appliquant la formule de Faa Di Bruno respectivement à

Donnons les premières expressions de y, et 6, :

CHAPITRE II

ALGORITHMES GENERAUX POUR (x,) E LOGFp

16

C H A P I T R E II

ALGORITHMES GENERAUX POUR (x,) E LOGF,

O. Introduct ion

Notre principal objectif est maintenant de construire des algorithmes permettant

d'accélérer la convergence des suites de LOGFp et d'estimer les vitesses de convergence

des suites obtenues.

Il existe dans la littérature [25, 29, 2, 5, 20, 23, 21 divers algorithmes accélérant les

suites du type LOGFp. Nos algorithmes sont des modifications de 1'~-algorithme et du A2

d'Ait ken itéré, le aî2-algorithme et le @-algorit hrne.

Par définition, les suites de LOGFp sont de limite nulle. Mais les algorithmes

considérés s'adaptent à des suites de limite non nulle puisqu'ils ont la propriété de

translativité.

1. &-algorithme modifié

A partir de l'&-algorithme, nous définissons un nouvel algorithme de la façon suivante :

pour toute suite (2,) :

(n) NOUS noterons E ~ ( x , ) = tk .

La 'suite (AL) est une suite auxiliaire qui ne dépend que de la classe de la suite (x,).

On en déduit que :

ALGORITHME 1

( n ) (,+il A2k+1 '2k+2 = ' 2 k + - A '

V k E N,Vn E N ,

où A = M-' + N-' + Eel avec

Remarque

Les suites ( A k ) et (Af, sont liées par la relation

Nous adoptons le principe suivant pour toutes les démonstrations concernant l'&-algorithme

modifié :

appliqué au nième terme de toute suite ( x n ) de LOGF,, l'Algorithme 1 donne, en

posant

x = x,, xn+~ = f (x),

où A = M-' + N-' + E-l avec

et j 2 = fof .

Théorème 2.1 : L a convergence de tou te su i t e ( 2 , ) de LOGFp peut être accélérée

par l 'A lgor i thme 1 avec :

Plus préc isément , pour t ou t k E IV, ( E ~ ~ + ~ ( X , ) ) converge plus v i te que ( ~ 2 k ( x n ) ) e t

E 2 k ( x n ) ¢j x;+l n - ( k + l ) l p .

D e plus, 3i Ù l'étape k , & 2 k - 2 ( ~ n ) e t ~ ~ ~ ( 2 , ) a d m e t t e n t des d.a. d e t ype : & 2 k - 2 ( ~ n ) =

C4:x; e t E ~ x ( x ~ ) = C Bi307 avec B i # O , B ~ + I # 0 e t Bt+2 # 0, al or^ ~ 2 k + 2 ( ~ n )

i 2 k i 2 k + i

EX;+^ avec

Démonstration. D 'après le principe défini précédemment, il s'agit de montrer que

Démontrons-le par récurrence.

On vérifie facilement que ~ ~ ( 2 ) x 2 .

Supposons

et montrons que c 2 k + 2 ( x ) ~j x k + l .

Pour des raisons de commodité nous poserons :

Les résultats de calcul formel (chap. 1, paragraphe 6) nous permettent d'écrire :

On en déduit :

M-1 = - l r, +... A z k - ~ f l L z

N-1 - - 1 A 2 k f l k + i ( k + l ) @ p ~ k + ~ (l + CY=l + ' '

,y-1 - - - 1 A2kBk+l ( k + 1 ) o p z k + p (' + Ct=l T i x i ) + ' '

Les Di (resp. T i ) s'obtiennent en fonction des di (resp. t i ) par le calcul formel.

Par exemple,

Dl = -dl 7 D~ = -d2 + d:

T l = - t l , T2 = - t2 + t : .

Mais di = Ti Vi = 1,. . . , p - 2, C ~ X

On en déduit

On peut prendre par exemple A2k = -L k+l .

A2k+l = k + p

On a alors & 2 k + 2 ( ~ ) = exk+2 + . . . avec

Les calculs donnent :

En reprenant f (x) = 3 + Ci>l a p + i ~ ' + ~ (rappelons que la démonstration a été faite

pour f (x) = x + Ci>O O L ~ + ~ X P + ~ ), on a :

De plus,

Remarque

Pour que la démonstration précédente soit complète, il faut démontrer que E # O, pour

tout p > 1. Pour p = 1, dans [31], nous avons explicitement E en fonction de n et des a,,

ce qui montre bien que E # 0.

La relation de récurrence sur E , devrait pouvoir permettre dans les autres cas, un

calcul similaire. Même si E était nul, cela ne contredirait pas le fait qu'il y a accélération

de la convergence, au sens où nous l'avons défini (cf. chap . 1, paragraphe 5).

2. A2 modifié itéré

Soit (2,) une suite. On sait que le A2 d9Aitken appliqué à (x.) peut s'écrire

Si (x , ) est une suite de point fixe telle que z,+l = f (x ,) , alors :

(on rappelle que f i = f o f ) .

A chaque étape, on applique cet algorithme à une suite ( u n ) supposée de la forme

u n = g(x,). On a alors U,+I = g(xn+l) = go f ( xn ) et un+2 = gof i (xn) .

On pose alors x , = x pour simplifier.

Au départ g = Id.

('-') = g ( x ) = T ~ - ~ ( X ) et r k ( ~ ) = b k ~ g ( x ) + bkrk- l ( j ( x ) ) avec A l'étape k, x ,

On obtient ainsi l'algorithme du A2 modifié itéré qui s'écrit

ALGORITHME 2

La suite ( B k ) est une suite qui ne dépend que de la classe de la suite (x,) .

L'Algorithme 2 est dû à SABLONNIERE [28].

Théorème 2.2 : Soit (x,) E LOGFp ; l'Algorithme 2 avec

accélère la convergence d e (2,).

(k+l)) (k) Plus précisément, pour tout k E N, ( x n converge plus vite que ( x n ) et x i k ) t~ ,-&-(k+l)lp.

( k ) - De plus, si à l'étape k , x l ) admet un d.o. du type xn - BiX,, Où # 0, (k+l) alors x n 6 ~ i + ~ avec

Démonstrat ion : similaire à celle du théorème 2.1.

3. Op-algorithme i téré

SABLONNIERE (281 a défini l'algorithme suivant :

ALGORITHME 3.

Pour toute suite (x,),

&(xn) = x,,Vn E N, A h

et pour tout k > 1, O>t(xn) = O(Ot-i (2,)) où I(un) = un+1 + - V,)AU,+~ AU,+^ - Av,) pour toute suite (u,), avec

On applique l'Algorithme 3 à une suite (un) supposée de la forme un = g(x,). Et on

pose x, = x pour simplifier.

L'Algorithme 3 peut alors s'écrire :

au départ g = I d

à l'étape k,

g(x) = Bk-1(x) et h ( x ) = êg(x)

avec

On rappelle que 69 a été défini au paragraphe précédent.

Ce principe sera utilisé pour toutes les démonstrations concernant le 02-algorithme

itéré.

Theorème 2.3 : Pour toute suite ( x n ) E LOGFp, ( 6 k + l ( x n ) ) converge plus vite pue

( ê k ( x n ) ) e t

e k ( x , ) @ xi+' t) n-(k+l ) lp , v k E N.

De plus, si à l'étape k , e k ( x n ) admet un d.a. du type 9 k ( x n ) = xi>k+l / l ; x ; , avec

Bk+l # O, alors A k+2 e k + l ( x n ) 0 5 , ,

avec

Démonstration

D'après le principe défini précédemment, il s'agit de montrer que e k ( x ) a

x k + l , Vk EN.

Raisonnons par récurrence.

On vérifie facilement que el ( x ) a x 2 .

Supposons que êk( . r ) = g ( x ) = Ci,,+, - / l ix i et montrons que ê k + l ( x ) a x * + ~ .

Nous supposons que

La démonstration du théorème 2.1 nous permet d'écrire

avec

Les résultats de calcul formel donnent

avec r Q p + l k + 2 b k + 2 t ] = - +--

o p k + 1 b k + l et

Dl = OP+' k + 2 P k + 2

o p k + l B k + i

On a ainsi e k + ] ( x ) - & x k + ~ , avec

P k + 2 - b k + 2 8 = P k + 2 - P k + l + b k + ~

P ~ + I - b k + i P k + i - b k + i


8 = ~ 0 a 2 P k + l

( k + l ) ( k + 2 ) s ip = 2 .

En reprenant f ( x ) = x + Ci , ] Q ~ + ~ X P + ' , on a : -

4. @-algorit hme

En posant x = x,, le 8-algorithme ( P . l O ) peut s'écrire :

Ce principe sera utilisé dans toutes les démonstrations concernant le @-algorithme.

Théorème 2.4 : Pour toute suite (x,) E LOGFp, (e2kS2(xn)) converge plus vite

que (8zk(xn)), 'dk E N. De plus 82k(xn) # x;+' o n-(k+l)lp, 'dk E N.

Démonstration

D'après le principe défini précédemment, il s'agit de démontrer, par récurrence, que

eZk(x) xkS1, v k E N.

On vérifie aisément que 02(x) x2 et O3(2) 2-1-P. SUPPOSOnS

Les résultats de Calcul formel (chap. 1, paragraphe 6) donnent :

Posons

1 1 --- - C ~ , , X " - ~ - P (f (x)) k+p x k + ~ n2p-1

- b p - 1 - b p - 1 - b p - 1

bp = - P p bp = bP

b 2 p - 3 = b 2 p - 3 b 2 p - 2 = ~ : - l - ~ 2 p - 2 bbp -2 = ( b 2 p - 2 ) a - b ~ p - 2

La notation ( b 2 , - 2 ) . signifie que dans l'expression de b2p-2 , ai est remplacé par ai(P.19).

Mais comme bi = b: Vi = p - 1, . . . ,2p - 3,

Les calculs donnent

le calcul de N dans la démonstration du thérème 2.1 donne :

On en déduit que

Remarque : La complication des calculs ne nous a pas permis de donner la partie

principale pour le &algorithme.

5. Conclusion

Nous venons de généraliser les résultats de SABLONNIERE [ 28 1, puisque p n'est

plus limité à 1 ou 2.

Nous avons aussi considéré deux nouveau algorithmes, l'e-algorithme modifié que

nous avons défini et le 6-algorithme.

Il y a très peu de résultats théoriques sur le &algorithme, encore moins en ce qui

concerne les suites logarithmiques. Le théorème 2.4 mérite donc d'être souligné.

Les quatre algorithmes donnent les mêmes résultats (asymptotiquement). De plus, les

parties principales des suites transformées par 1'6-algorithme modifié et le A2 d'Aitken

modifié sont très semblables.

Nous verrons plus loin, que pour des valeurs particulières de p, il est possible d'encadrer

la limite.

CHAPITRE III

ETUDE DES SOUS-CLASSES DE LOGF,, = A i r , PAR LE n2 D'AITKEN MODIFIÉ ITÉRÉ,

LE Oz-ALGORITHME ITÉRÉ,

L'&-ALGORITHME MODIFIE ET LE 0-ALGORITHME.

29

CHAPITRE III

ETUDE DES SOUS-CLASSES DE LOGF,, p = ,,2,

PAR LE D~AITKEN MODIFIÉ ITÉRÉ,

LE 82-ALGORITHME ITÉRÉ,

L'&-ALGORITHME MODIFIE ET LE 8-ALGORITHME.

O. Introduction

Les quatre algori thmes généraux du chapitre précédent répondent à notre objectif.

Mais on peut obtenir des résultats plus précis sur la vitesse de convergence en considèrant

les sous-classes de LOGFp, p = 1,2.

1. €-algorithme modifié

Théorème 3.1 : Pour toute suite (2,) E LOGFp,p = 1,2, en appliquant

l'Algorithme 1, V k E N, ( ~ ~ ~ ~ ~ ( 2 , ) ) converge plw vite que ( E ~ ~ ( x ~ ) ) .

( i ) Pour (xn) E LOGG(p = 1,2),

De plu8 cZk(xn) e=) s;+' +=+ n - ( k + l ) I ~ , ~ k E N.

- ( ii) POUT (2,) E LOGF; ,

( iii) Pour ( x , ) E LOGFil,

A-1 = O, A2k = 1 / ( 2 k 4- l ) , A2kS1 = 2 k + 3 , V k E N.

De plus, E 2 k ( x n ) x i k S 1 (j n-(2k+1)12 , \dk E N.

( iv) Pour (x,) E LOGFS",

4 k+5 ~ 2 k + 2 ( x n ) & Z n

avec

Démonstration

(i) Théorème 2 . 1 , p = 1 pour LOGF; et p = 2 pour LOGF;.

(ii) On vérifie facilement que E ~ ( X ) x 3 .

Supposons

Les résultats de calcul formel donnent

' ?2k+1 = P 2 k + 1

?2k+2 = P 2 k + 2 + ( 2 k + 1 ) P Z k S 1 Q 2 ?2k+3 = &k+3 + ( 2 k + 2)a2P2k+2 + ( 2 k + l ) ( k + l )oiP2k+1 ?2k+4 = P 2 k + 4 + ( 2 k + 3)a2PZkS3 + ( 2 k + 3 ) ( k + 1 ) Q i P 2 k + 2

+ ( 2 k + 1 ) 4 2 k + 1 [ ~ 4 + 9 ( 2 k + 5)aq] ?2k+5 = P 2 k + 5 + ( 2 k + 4 ) ~ ~ p ~ ~ + ~ + ( 2 k + 3 ) ( k + 2 ) C Y i ~ 2 k + 3

( 2 k + l ( k + 3 3 + ( 2 k + 2 ) P 2 k + 2 [ a 4 + 3 )a2] + ( 2 k + 1 ) P 2 k + 1 [ ~ ~ + ~ ~ a ~ a ~ L +%(2k2 + 9k + l ) ]

On en déduit :

On a alors :

avec

on peut alors choisir :

Par ailleurs u = O, donc € 2 k + 2 ( x ) - ~ 3 ~ ~ ' ~ .

Les calculs donnent

(iii) 11 est facile de démontrer que : si f est impaire, alors & 2 k est impaire, pour tout k E N.

Supposons & 2 k ( x ) = Ci>2k+1 Piri.

Le calcul donne

et si on choisit

alors E ~ ~ + ~ ( X ) x2k+3, ce qui achève la démonstration.

(iv) On sait que E ~ ( x ) x5. Supposons

D'après la démonstration précédente &2k est impaire. Les résultats de calcul formel

donnent :

On en déduit :

On a alors :

avec

On peut alors choisir :

Par ailleurs, u = -* - (4k + l)a3, donc

c Z ~ + ~ ( X ) c t 4


2. A2 modifié itéré

Théorème 3.2 : POUT toute suite (x,) E LOGFp(p = 1,2), en appliquant ( k ) l'Algorithme 2, (1. ) converge plus vite que ( x f - l ) ) , POUT tout k E N * .

( i ) Pour (x , ) E LOGFP(p = 1,2), B k = ( k + p)/k,Vk E N.

Si (x , ) E LOGF;,

Si (x , ) E LOGF;,

(ii) Pour (x,) E LOGF;', B k = 2k/(2k - 1)Vk E N ; et x") n t, x2*+' n a n-2k-1.

(*+') - bx2+3, avec : De plus si x ik ) = ~ i > 2 k + l p,xk, 0 1 0 ~ 8 Z n -

(iii) Pour (x,) E LOGF;', B k = (2k+ 1 ) / ( 2 k - l ) ,Vk E N .

De plus xik) - z2k+1 n - n-(2k+1)/2.

(iv) Pour (s,) E LOGF;", B k = (4k-1)/(4k-3),Vk E N et x ik ) (j Z 4 k + l n - jj(4k+l)/2.

( k S 1 ) De plus si x i k ) = xi>4k+1 @ i x i i alor8 xn - - 6 ~ 4 , ~ + ~ , avec :

- De plus si x n ) = B i t ; , alors xik+') - 6 ~ ' , ~ + ~ , avec :

Remarque

Les résultats (i) et (iii) sont énoncés sans démonstration dans 1281 par SABLON-

NIERE.

Démonstrat ion

(i) Il suffit d'appliquer le théorème 2.2 avec p = 1 (resp. p = 2).

(ii), (iii), (iv) : Démonstrations similaires à celle du théorème 2.2.

3. 02-algorithme i téré

Théorème 3.3 Pour toute suite (xn) E LOGFp(p = 1,2), (Bk(zn)) converge plus

vite pue (8k-l(xn)), Vk $ 1.

( i ) Pour (x,) f LOGFi,

( i i ) Pour (x,) E LOGFS,

(iii) Pour (x,) E LOGF,",

De plus si êk(xn) = Ci>2k+l P~x;, alor3 B k + l ( ~ n ) -. B x ~ , * + ~ , avec :

( iv) Pour (x,) E LOGFS',

De plus si 8k(xn) = Ci24k+1 Bixnj alors 8k+l(xn) .- 8 ~ $ + ~ , avec :

Remarque

Les résultats (i), (ii) et (iv) sont énoncés sans démonstration dans [28] par SABLON-

NIERE.

Démonstration.

(i) Théorème 2.3, p = 1.

(ii) Théorème 2.3, p = 2.

(ii), (iv), (v) : démonstrations similaires à celle du théorème 2.3.

4. 8-algorit h m e

Théorème 3.4 Pour toute suite (x,) E LOGFp, p = 1,2,(82k+2(xn)) conveTge plus

vite que (g2k(xn)), Vk E N.

( i ) Pour (5,) E LOGF'(p = 1,2),

(ii) Pour (x,) E LOGF'(p = 1,2),

(iti) Pour (x,) f LOGF;",

Démonstration

(i) Théorème 2.4, p = l ,2 .

(ii), (iii) : Démonstrations similaires à celle du théorème 2.4.

5. Remarques

a ) On sait que la première étape (colonnes paires) de l'e-algorithme n'est rien d'autre que

le A2 d'Aitken. Cette propriété se conserve avec la modification de ces deux algorithmes.

b) Pour (x,) E LOGF;, lorsque co < O, les suites données par le A2 modifié itéré sont

alternées par étape. On a ainsi un encadrement de la limite d'une étape à l'autre. Quand

co > 0, c'est le e2 itéré qui vérifie cette propriété.

Ceci est un corollaire des théorèmes 3.2 et 3.3.

c ) En choisissant x, = n pour suite auxiliaire dans le p-algorithme, on a :

(i) pour (Sn) f LOGE',", coïncidence entre l'&-algorithme modifié et le p-algorithme ;

(ii) pour (Sn) f LOGFl,e2 = pz.

6. Conclusion

Les quatre algorithmes donnent aussi les mêmes résultats (asymptotiquement) pour

les sous-classes de LOGFp. A l'aide des parties principales on démontre que pour LOGF:,

les suites transformées par 1'~-algorithme modifié et le A2 d'Aitken modifié itéré ont le

même signe. Il en est sûrement de même pour LOGFp en général.

CHAPITRE N

COMBINAISON A2 MODIFIÉ ET e2 POUR LES SOUS-CLASSES D E LOGF,, p = 172

3 9

CHAPITRE IV

COMBINAISON A2 MODIFIÉ ET 82

POUR LES SOUS-CLASSES DE LOGF,, p = 132

O. Introduction

Pour chacune des sous-classes étudiées au chapitre 3, le A2 modifié itéré et le $2

i téré donnent des résultats semblables. D'où l'idée naturelle de les combiner pour accélérer

encore la convergence.

1. Combinaison A2 modifié et O2 pour ( x , ) E LOGF,, p = 1 ,2

SABLONNIERE [28] a d é h i l'algorithme suivant :

pour toute suite ( x , ) ,

ALGORITHME 4

x ( . O ) = s , v n ~ ~ e t p o u r k > ~ , n ~ ~ ,

Les suites ( c k ) , ( - y k ) et ( A k ) dépendent de k et p.

( k ) ( k ) ( k - 1 ) ) Pour chaque valeur de k, (y, ) et (2, ) sont les transformées respectives de ( x ,

par le A2 modifié et le ~ ~ - a l ~ o r i t L m e .

Il faut remarquer qu'il ne s'agit pas d'une simple combinaison. En effet, on n'a pas

utilisé séparément le A2 modifié itéré et le 82 itéré pour les combiner. Dans toute la suite

toute combinaison du A2 modifié et du 8 2 sera celle de l'Algorithme 4.

Théorème 4.1 : Soit ( x . ) E LOGF,,,p = 1'2. En appliquant l'Algorithme 4 , ( x n ) )

converge plus vite pue ( x L k - l ) ) , pour tout k 2 1.

( k ) ,, x2k+l n - ( 2 k + 1 ) / p Zn n

(ii) Pour ( x , ) E LOGFi',

z ( k ) - z4k+1 - n-(2k+l /2 ) n n

(iv) Pour ( x n ) E LOGF;",

Remarque

Les résultats (i) et (iii) sont énoncés sans démonstration dans [28] par SABLON-

N I E R , .

Démonstration

(ii) Soit (2,) une suite de point fixe telle que :

Le A2 d'Aitken appliqué à (x,) peut s'écrire :

avec A = N - l + E-l

où N = fi(.,) - f (xn ) et E = x , - f(xn).

Quant au A2 d'Aitken modifié, il peut s'écrire :

On définit ainsi une fonction 6' par :

avec A = N - l + E - l .

Où N = f2(x)- f (x )e t E = x - f(x).

Notons zk(xn) la suite issue de la combinaison à l'étape k.

26'(2)+e(z) On vérifie que zl(x) = 3 x4.

3 k + 4 Pour tout k 2 1, supposons z k ( x ) x3k+1 et montrons que zk+1(x) x .

- A2 modifié

Le A2 modifié appliqué à zk(x , ) peut s'écrire

avec A = N-' + E-'

0; hT = ~ k ( f 2 ( ~ ) ) - z k ( f (x)) et E = z k ( x ) - % k ( f (x)).

Posons

Les résultats de calcul formel donnent :

On obtient

avec

Les simplifications donnent

avec

On en déduit que

Déterminons le coefficient de x3k+3 dans 6 z k ( x ) . Soit E ce coefficient. On déterminera

plutôt le terne de e dépendant de ,û3.

E = 7 3 k + 3 - P ~ ( D ? - 03)

-D avec On sait que D j = (3k+27,2

On obtient

On a alors E = 2 ( 3 k + 1 ) ( 3 k + 2 ) p 3 '

- Thêta2 ( 8 2 )

Posons 8 ( x ) = B 2 ( z k ( x ) ) .

avec II4 = Gzk(f (x)) - 6 z k ( x ) .

1 3 k + 2 Posons 6 Z k ( x ) = y\x3k+1 + y 9 + y3x3k+3 + . . .. On sait que


45

3k+2 E t ê ( x ) = [ ~ 3 ~ + 2 - P l ( ~ - ~ ) ] ~ + [ ? ' 3 k + 3 - 8 1 ( v - q + p ~ - ~ u ) ] z ~ ~ + ~ + . . ,

avec

Les calculs donnent d(r) x3k+3.

Reste à déterminer le coefficient de s3k+3 dans ê(x). Soit O ce coefficient. on

déterminera le terme de O dépendant de B3.

On obtient après simplification,

On trouve alors que

D'où la combinaison

(iv) Les notations sont les mêmes que celles utilisées pour (ii).

Avec Bi = 3 on obtient z 1 ( 2 ) = 4"'(")+e(z) t) x 7 , 6' étant le A2 modifié avec le 5

coefficient B 1 .

Montrons que z k ( x ) xSkt2 , Vk 2 1 .

A2 modifié.

Posons z k ( x ) = P l x S k S 2 + ,92x5kS4 + P3x5k+6 + P 4 x S k S 8 + . . ..


A5k+2 = Pl

A 5 ~ + 4 = PZ + &(5k + 2 ) a 3 k k + 6 = P 3 + 2P2(5k + 4 ) a 3 + 2 P l a i ( 5 k + 2 ) ( 5 k + 4 ) A5k+8 = + 8 3 ( 5 k + 6 ) ~ 3 + 2 @ 3 ( ~ 3 ( 5 k + 4 ) ( 5 k + 6 )

+Pi [207(5k + 2) + ( 5 k + 2)a3[15 + t ( 5 k + 1 ) ( 5 k + g)]] . On obtient

- thêta 2 (O2)

Les calculs donnent e(x) a z5k+6

Et la combinaison est

En fait Z k + ] ( l ) x5k+8 car Zk+] est impaire.

(i), (iii) Démonstrations similaires à celle de (ii).

2. Résultats numériques

Tous les essais numériques ont été faits sur l'odinateur DPS8 - MULTICS (BULL) du

C.I.T.I. de l'université de Lille Flandres- Artois.

Les réels sont en double précision avec 16 chiffres décimaux.

Nous avons expérimenté des suites appartenant ou se ramenant à chaque sous-classe

de LOGFp, p = 1'2 , par les algorithmes suivants :

€-algori thme général (chap. 2)' E -algorit hme modifié pour la sous-classe, A2 d'Ait ken

modifié itéré, O2 itéré, @-algorithme (chap. 3) et combinaison AZ modifié et 6z.

Pour les suites de limite non nulle nous avons imprimé les suites d'erreur pour les

transformations. Le premier terme de chaque suite a été choisi pour une convergence lente.

D'autres valeurs donnent des résultats plus performants, mais très vite instables. Ceci est

illustré aux pages 5 3 et 5 8.

Les deux premiers algorithmes permettent de voir pour LOGFi', LOGF;' et LOGF;",

l'utilité d'un algorithme approprié.

m Vi "- 0 0 0 I I < 0 0 0 0 0 . 7 h W - n N O U . 7 N O m N O n N - O * * O mmYI % * D l O - N O Ih N N m O m m m Y O * m u . . . 0 0 0

m m m 0 0 0 I I I 0 0 0 N O 0 O h N. O h * O m o h N O O m N - n o 00.- m o m D n h n N O N t . - - h o m N h * * O n m N . . . 000

O * - O c 3 0 I I I 0 0 0 U N * o.-* N - n m g - - - 0 - h N O n m N O * h N h O * h Y) O * N w r n h - n m 0.0 U U U N F * . . . 0 0 0

I I I I I I 0 0 0 0 0 0 N O Q N * ~ m m o m e n i g ~ n m n - Q N O I h V i V i m m u o e u

ln-0nuh a u n ~ m m W Q O h n m , m n n m o 0 u m - s c O N h r n N O m Q n n N m L n O v I O J O

1 - r N r h U

h' Pi , r.- O C O I I I 00.2 orne h - N

" - V I < C, : c I I ' c n c C u 1

< r. r. P h n w 4 3 : N C C

O r - m m * N m m N L N m n m

C L *

h h h ?" C . . .. - Z r - n N - n n' C F C b u - "- ?" .? ,- .-- h .W. II" .Y

a . .

C C " I l l ~ c n c

I I I

N N N 0 0 0 I I I 0 0 0 O - * m m * u m o b m n O h N o m n m m N

* * u * * u m m m / O O O O O O O C O I I I I l I I I I i 0 0 0 0 0 0 0 0 0 D m m e h m U m Q Q O r O O O D U h n . 7 U h O V I h Q O O U N N N h h P O O n m N * m O N m W 0 0 u o h h b ~ m 0 w u O . r n m w n 0

' N N N N N ~ 0 0 0 0 0 I I I I I

l a 0 0 0 0 ( m O . - w O j O N Q y l 0

f l n ~ c o n r - O r n O b - n

r(l * O . - Q O 0 I Q h D . O ~ r - o n n O Q N r n O

- O m r m m O r n 0 9 O

0 O * Q * Q * n N N . . . . . 0 0 0 0 0 I l I I I

. . . 0 0 0 I I I

*( 0 Q 0 0 Q 1 I I 0 0 0 n D h O *.. N - m N hi0 N O 0 CO O h O m m 0 D h Q U N O nh O hi.. r. c- N Q h N 0"- O -03 m . o n . . . 0 0 0

m m D e e O O O C O O O I 1 1 1 1 l 0 0 0 0 0 0 h o r y n h h 0 0 W . m - O - h Q O N O Or".*O- ~ e r i i l n - n m l c ~ n * * . . LOOCI O - n m n d n Q - N r * h h O I h f - O * O m n N O n 0 N - m . Y r h h o 4 - r v e . D h D O r C o r . m o r y r - Q * n N

O 0 0 0 0 0

0 0 0 O-.. O N O 0 w m O N O o w m O - * o n e O 0 m O h O O h N O - h 0 - 3 - O -n 0 0 - O m N n N N . . . 0 0 0

N N N N N N N N N N N 0 0 0 0 0 0 0 0 0 0 0 I l I I I I I I I I I 0 0 0 0 0 0 0 0 0 0 0 O Q m n Q N O h h O * - - n - - n 0 r N O Q

. . . . . . O O O D C O

N N N 0 0 0 I I I 0 0 0 O h h 0 r N N O 0 O Q h Q o m * O h O - - m m 0 0 0 0 0 0 - - D m 3 m r o m n D .7 m h.nn - c c . . . 0 0 0

*..***mm Q Q e O O e h h - I s > m m O O O O E O O 0 0 0 O t 0 0 0 t 0 0 0 I I I I I I I I I I I I I I I I ' I I I I a a n o a a a a o o a e o a o a 0 0 0 O D O V , ~ ~ N , / . . ~ V I D O ~ ~ - ~ O N N h ~ ~ n ~ e - N ~ - O * Q N ~ N m e * - - ~ D * N u m n o ~ * n m n o 0 0 0 n m w m m m * : U . . V O - O ~ W G , h00 f i h00000 * Q c ~ ~ * n 9 Q i h m ~ h b O h Q O ~ i : V , N - - 0 0 h O * h..N m ~ m m n . 7 - i m m ~ ~ m . 7 h ~ r ' e n * m r o ~ m w m Q N . . L O O O * ~ * m m n 0 W N 0 - O N : h W h Y , 0 Q O n * : N n b n f i r . 7 o c 0 l ~ - . n h ~ 0 ~ ~ e - n e Q O r i r l * ~ ~ . f r O r ? m m h ~ ~ ; n r ~ r ~ m n - n m l n e N h h w m m n , * * e m n n m

~ ~ N O N O C - ~ Q m m * h * m e * o n o h ~ . - m - ~ ~ o / w ~ m * C L ~ N O - ~ O O ~ ~ Q N O O * J N O ~ ~ r - r r W h ( r m c ) ~ - r b ~ m m m - . . . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 0 O O O C 1 O O O O O 1 i O O O

il

œ P C . 0 ' 0 0 0 0 0 r I l I l i ) 0 0 0 0 0 kDO1Vi h i n N - 0 0 m h m N , N O N O h NOO..., p D m - - e O h * - 0 h i - C O O O * Q W h o m o m m O O - n c * - - d e = - m m - E N h m hi - * m m O r h Y i I I l - . . . . oooop

- 00- - - , O I l I I 0 0 0 0 N O V I - n m * e * h h O .. m * P * c m m * O h 0 O * . - O n o * - - - * * * O V I N w o n - m w N 0 m n m m n n n o -&..O ON&. -

N N N N N N 0 0 0 0 0 0 I l I l I I 0 0 0 0 0 0 o e m n e ~ c r n r . 7 n o r n o n e - e 0 0 4 n - ndnh -9 N h n h w - - m Q n h 0 h N m Q O m

I ~ ~ . t m n m l m - h N 0 h

-None . - o n m r h l m ~ O O N N ~ . . * h D r n O O O O P * O Q . 7 n N h i N . . . . . . 0 0 0 0 C 0

N N N 0 0 0 I I I 0 0 0 O h h 0.-N N O 0 O Q h 90- *'O h O - - m m 0 0 0 0 m o n h e m o m - o m n D .. m h m n - F r . . . 0 0 0

* * -8 0 0 0 I I I O 0 0 * Y I - O .7 N O - n * O - e h i m 0 0 0 n e - ..*- O h m 0 h N <DO 0 nup. e o m n o - D Y l N m e n . . . 0 0 0

... 0 0 0 I l l 0 0 0 O m Q O n - k*.. N m V , 0 6 0 O h 9 0-iii o e m N O 9 r d 0 - n * o n - s m n m e * - N O C C - . . . 0 0 0

rnm Q e e O Q Q 0 0 0 0 0 0 0 0 I I I O I I I 0 0 o o e a 0 0 h N u h V I b O n e - - m . - D . 7 . O N * O n o h * - m.. ..*00-0 O * : * O - N N * o m m N - r D . 0 . 7 - / m m o o O f * U < D ' Q N . . ~ O O 0 N h Q h V I . C O r 0:- r VI h 0 0 Q Q j . > - O m m m n Y l r * d h ) h h < D m m ~ O N W N O 0 - O ~ S - * - hn o o n n o ~ w h œ m n w r c . . . . . . . . 0 0 O O O C i C C 1

h h - l t n m O O t 00 I I I I I a 0 0 0 0 D r * O N CymN m e m n o 0 0 m m 0 I.0 - 6 - h m

m P b D Q O o c ' o o o , - 1 1 1 1 1 1 0 0 0 0 0 ' 0 N ~ O ~ Y I h e m N c O O 9 m h - N - O h . O N O " c ~ N C O - J 0 N O = - N * O h . l h 0 nhi-00 Q e O 4 O N h ..0*0<0 N e * - n C w.. - -m O C r e m - m - mPNhOO N m - o n w 1 0 - . ? - m m - . . . . . . O O O O C 0 l

t n n n c c t t . I I I 1 C 0 O P w a c @ < e n b - n v n 1 C v i 0 3 - h h e < C r u - % C L ? C rriff N.- O \ ? . - & <r ,- * a y r c o 0 0 h.** @ O C Q r w r m N . - n * eam..

. S . .

C C C C I I I

r r r - I I I

r P d * c. .- C A <\ 6 C C h .- Q O r - .- P. "-

W h . ,

< C T D h .nr v ma' a n - O.& R. P fi. r -

h i V M U C O C O m e r )

D C D I I I 0 0 0 - - -

u e t 0 - m a u ah' = N u Q - h

. . . . . . O C C ' O C C

1 I I I I

C P.. n c CI c I I I

- C C C r ç

L h h h C C C C I I I 1 C C C C .- 1. c F '. h- .- - m..-C C P . C 0: <- n 6% a- * - C c % * h @ m C K.-c C .-er.h -Re.- h r n m e h e c Cr m m - N OCID.* C y r C h .*c^mn . . . . C C C C

N h h h h i h S h n m m C U C C C C C C V C C C ~ ~ C

O Li9 A A O. *TIC C1 P. 0:P.i- \ *O h cIn c h h C i h CO. -7 alcc O - 01.3 m F h ml* ln O h NIK h OC h OlVI PI - emO.eLP LeQ-?OO. s r - e L P m 0 n c I C ) m C ' m u e o

n*r. - olrn

s,;rp- r m l 0 - m m 9 ml-

& +

V \ * m C O C I l l 0 0 0 - 0 0 @.CD C U L o m w 9 . - C Nr.N m a - - - - C - m m e -a? P C C P7 Ln h - - N u o - N r? Q U m N . . . 0 0 0

mmmLn C C i O O I l I I 0 0 0 0 - C o r n C C C U CUr.9 o m m o b r C * N h N m D a - Q O T r C C r m O . N œ - w * e O w - I c . * l ch r r N h u o - O . N m Q 0 U m N N

. . a .

B O C O

Lnim 9 o n n c 1 I I I 1 O 6:- C? - mlc. m

N r'" N C P E * C œ L- V m e * " N m C N - O h œ, OL u O ff, h V I V -eh' w u - . Q U Q . S N - u h, O N h ' N . . . 0 3 C

- hm e c e c- c O. n hi h U F h c' 0 or. .. VI e N 02 h' h hi IO h m 0 - - . . CC,

r m 9 rn N

u u r w a 9 h e u (Ca* ch*- O N U m0.m N U * " cc M - mCiC.9 C N C h m - . . . m c n

O. Q'Q ti m Ln/- -i 0. -IN Q gl h l h m miN L-

Nim. 03 U oim l. h Y'O 9 r r / m r . ., . . Ci 010 O . . . . .

O C C C O

n m m m . , u . , U . J O C C C O C C 2 0

L P a o C C C

I I I P C O - 4 . 0

C C, C I I I o o n m Y W . - u *- e lcc n N r O U O C O b-. u . - m m * . i h ' O ^ c'lc 8,- h o N C O U m m - D m - - O N N'CIN P d r t

NNN 0 0 0 I I I 0 0 0 m O O

nnn 0 0 0 I I I 0 0 0 0 m . n O O Ih - 0 0 u o a n n ~ - m u 00- m o o N n - P u - a m - O O Q r N O u N u m O -

, m N N . . . . I O 0 0

00000 I l + I I 0 0 0 0 0 N - N O * P Q N Q * g D N O 0 O N O D N N O O h 0 m r O r ' > 0 N n o O O r h N D m i t m N 9 -

* u u m 0 000

1 1 1 1 0 0 0 0 rn Q N - u m.-,. o m o n U h - O ' O 0 0 - h(h m.- - (<O ". m m'O * N m * O C nIm,e O O".N O ".mm m n n o i 2122: h o e - e w + * ~ 0 m o h ( r c - 0 - c

" . J N N r r , 4 N r m m * > N * N r D d . . . . . . . . . . . . . . . . . . C O O O O O 0 0 0 0 0 0 C O O O O C

N n n n u u u u L - l n m 0 0 0 0 0 0 0 0 0 0 0 I I I I I I I I I I I 0 0 0 0 0 0 0 0 0 0 0 n o n m u - h h ~ m ~ m n r u m N * m m O N D O m n m h m ~ O O N m - o h * D O Q 0 0 0 m u h O u n u * N m - n u o n n n m o r - D n w m ~ m c h - ~ * m h U m D r n m - m m h L n N D O h O h h O U N m U N D O h m D 0 - O - 0 0 m n 0 m o o h ~ n - - o m m * e m e u o m O u m n n N u m * D - ~ m D - n o O O m u m m h ~ h h ~ n r n ~ o - Q N r Q m N r m m V . . . . . . . . . . . 0 0 0 0 0 0 ~ 0 0 0 0 1 1 1 l 1 1 . 1 1 1 1 '

h m - 0 0 0 I I I 0 0 0 N R O

O m L- N i n h m Q ID n e - ~ r . m N O Q h Ln YI N L- O - e n . . . O O C

- -

- ~ o m G ; o h N h * m ~ - ~ m h r O V I e O O * * * * m m - O ~ N O ~ O - m ~ n r r ~ 4 n n m n h h O P O h o O N - ~ O o e m ~ ~ r n - n O - O O N O O N N L n O r O h O h O U Q r D h - O m e ~ O 0 h O r n o h m

~ N Q - ~ Y I Q W O * * O O V I ~ - J N O ~ O N O ~ h ~ m h ~ n h ~ 0 m n r - W J e o m n m h ~ O N O ~ Q ~ ~ O m o n h u e h ~ ~ n ~ ~ n m - ~ m o r a n - n o o h ~ n ~ ~ o w Q O Q - U ~ - * - w * N - O - m r V I N D u . . . . . . d d g d é 9 8 8 9 o o o o o o

l h h h m i o o o o

I I I I 0 0 0 0 h n e N

I l I I 0 0 0 0 m - 0 0 - - - r O O N m e D m h O - O N . - -DU

O N L - r N L - m r h N D D O - h m . n O O N N O S 0 rl.r.0 O h N O U O r h L-Vl.-N . . . . 0 0 0 0 l

8 9 8 8 O h m 0 U h O Q O n N m r- N m r = % O N O W u N U D Q m m O u N c * N S > r Q N h N n m m u . - h u m L- N O <O O O n m O L n m m - h m * . . . . O 0 0 0 I I I I

-.-- O O O I I I 0 0 0 m P P

000 I I I 0 0 0 m e m h h u

. . . 0 0 0 0 O O O N O O O N 0 0 0 - 0 0 0 0 0 0 0 * 0 0 0 - O C O h O o n v, C 3 0 . r . h O O O O c o n = O O U O 0 0 - h o h e n o n 0 0 n ~ . - -

- h O u u u - n u O N D - < O N - U N

O . - % * D n O O N U h O h % O L n L - h e m O N O Q ~ m n m D L - M D D O Î D P - N e r i . . . . O O O O

N Q - N Ln D n e z n e m h h . . . 0 0 0

. . . . o o o c I I I I

NN- 0 0 0 I l l 0 0 0 - O h * e h - o n O n N O O h - 0 0 O * O e n 0 . - *N D O N e n n L n - h V I m N h O O n O ln r - h

a . . 0 0 0 I I I

n nno O 0 1 l I O 0 0 0 "00 O N * e n O n o - * - O - 0 0 m o n n o m o n o m n e N n O O N - * m m h m * * O h n ~ .

* O 00 t I

m m VI 000 I I I 0 0 0 O h * n *n - h Q - m m N O N Q o m - e n - n e -0 -4 m o n nnh - m . - J O O - - O e n m - - O . . . 000

l

0 0 O r . h 00000 I I I I I 0 0 0 0 0 00DDl.m ( IOOYIOh N m o m m O - O O O i O O O Q O - O N N O h e O O m V O h Q 0 O * h O h D G . D * N r e m o n - m n < O u h m n h ~ m n m - - N O O D U h N - U N . . . . . 0 0 0 0 0 O l l l

h m h 0 0 O I I I 0 0 0 O N N - n m N m N 0 O N - m - N O - * * O O n N n - m N O Q * * < O O ~ N h N n O N O N O * - - O . . . O 0 0 I I

N O - - * m n u - h o m - m m O O m r m * N D * G O O h h * m m - o r . - * m u - U O u D m U e m m D

I . . .

0 0 0 0 I I I 1

r - N 0 0 0 I I I 0 0 0 - D O Q m h O h m n n e . Y 0 0 - N O h C e m O D * O 0 b * N N W O r m w w - u 0 - 0 - - 0 n r h . . . 0 0 0 I I I

~ n n O 0 0 I I I 0 0 0 m m - N O - O N m h N N V I N N 0.i- - m m -0.- h g - * N O * O h - 0 0 0 -9 h.-h N O - - O *

m . . .

O 00

nnn 0 0 0 I I I 0 0 0 O O W m m 0 n - n G h O n e o * * a O * . - 0U.N h N N n - 4 1 Q Q h - - a h N J O N h * h ~ n N r r . . . 000

I I I 0 0 0 O N * * n ~ N N N O n N ~ n - O r h n m N 4 0 0 * * * N N O m m - - n e N O * n ~ o D - m V IN-

S . .

0 0 0 I I

,e?.-r--Prr+- C C C C C C

I I I C P C P * '.' h r h' F O I ; F- Q h <CD< -1 -7 ocIf

C C C

000 I I I 0 0 0 J 0 m O h h * no - 0 0 - * N

ô:: 0 - m nnN O N 0 m. - * -Y ~n h N Q - C C

Q h . 9 C C C

0 . . 0 0 0 I I I

- o u Q h h m N W * O h - ~ n * O 0 n m w m * n - c c

v u u r m i n m m O O O O C O O O 1 1 l 1 1 1 1 1 0 0 0 0 0 0 0 0 r O l o O l O m - O N 0 . t u h m f . u m n n m r n m h C 0 c m r i N n m m Q N w m m m N O N m m ( h m h N n D 0 0 . t r m N 0 m n D h h N D D ~ L ~ N N O ~ m m u r o h m e o - ~ h ~ m - n O m n - n o O O u - U O m O N Q * O U N Q Q W N Q u ~ o l ~ r n - u * n - w . , N r . . . . . . . . 0 0 C 0 C C C C

I l I I I

n n n 0 0 0 I I I 0 0 0 - n m h m * 0 m - *Na 0 m - N m h

n 4) n c o a r N m D h N N Iii U 0 . 0 0 0-n m 0 u - 0 0 0 m m . . . 0 0 0

I I I 1 0 0 0 0 -&NI. m o . 0 0 = - Q u n n o o O O D Q n 0 N O w n k o N00n O O U h ?-*Oh L n - O h c l m m

nnn 0 0 0 1 I I 0 0 0 0 0 0 - N D o m 0 Q . ? N 0 - O O h O - m . # * O 9 O O O

Y n m r m m c c - O * O 0.10 hhh . . . 0 0 0

nh n O - * C Q m - * O m e 0 .rN- nh N - o n - D O n -O m u - . . .

O17

* m m 000 I l l 0 0 0 N r m m m 0 œ r n h m * u o m O h - O * . - N D N m n n N O L Q h h h d 9 * n O - n e 9-h nnN ... 000

I I I I I 0 0 0 0 0 n P 9 m h O J ~ O O * O h * - O O O Q * r u a - O h N P - O * ~ ~ Q N N

- - - 000 I I * 0 - 0 - 9 0 n m Q O h m 0 O Q O * - - n u N m N 0 0 - h h 0 h n O 'r O 0 ND^ N O - D O * Q h O c c -

/;;.:

nnn O 0 0 I I I 0 O 0 uN9 O L n N h m a Q Q N Q o m N O 0 O N - O N 0 rime N * e n - O O - - *ml. n * ~ 4-n 0 O Q

é é 8

nnn 0 0 0 1 1 1 0 0 0 m a 0 O N 0 0 -0 Q * N 0 - O 9 - 0 - m . # u o e O O Q . r . v n * m m - m m C C C

0.19 0 4 0 hhh . . . . 0 0 0

J *:* m - m * 0 0 : 0 0 0 0 C I I I I 1 I I I 0 c . 0 0 0 0 0 NNIJ r *DQW' - -1- O e n 9

h 0 l Q 9 4 - V1 Q 0 : C h U N n r t N l - C h * * n h i ~ J e N + h O i n D O n ~ r 0!*mc. r - n -10 N h 0 % m J;- h e n -

, . l i . . . . . ' 0 0 ( 0 0 0 0 C

' I , I I l

N N N 0 0 0

Y nnnnnl O O O O D I I I I I 0 0 0 0 0 O * O - h hhY)*N 0 0 - m * - - * O n m O O m r i Q ~ O O N W h - O * ' r * N O h h O U * 0 1 N O W O ~ ~ m .Y n O - * - O ? m O * h h

m O Q 9 0 0 0 0 I I I I 0 0 0 0 m h r O n r œ ~ - N N * - N o n O O O - O h Q O n N m h O r n e n n o n D N O O h h * l n L n r m h o o m n h N D O r n h ~ - % e n

I I I 0 0 0 . - O N O m Ln N h h o m * N N - h h m 0 - * b r r r < O N -

m a - h m - ,n e D N m O 10 h r

122: m. - - n o n 0.79 m O r h - h D O N O D N * N N . . . ,O O O I I I

; n i L w N O * O i h O b m U O O D n ~ m u * O h %

O h Q h r e m * m o o e N non D m N D 1 N O N - N . - r b l .---

B . .

0 0 0 I l l

r r r - - - r - r r r r N N N N N N N N ~ n u u u u u ~ c r ~ n ~ ~ n c c a o o m o c ~ c c o o o c n o o c c

I I I 0 C C OCY. D rr

m o n r\. c e n m u h N r 9 - O O O N ., - Yi

n m - n - n O h * m u a n u - N - N .-en . . . 0 0 0 I I I

r r r r ~ N O O O O O C

m m m 0 0 0 I I I 0 0 0 n o - - m m o m m QU^ - 0 - O U Q O h 0 N Ln h N U W N N n 0 . O h N O 0 h N W 0.u-n m N h N N r . . . CI O O

. . . . . . C O O O C O

. . . . O O O C

m m ,. C C C I I I c n n ouoc

ri ri a W N C U O O n p c œ N u m e? h, 6 a5 O. - O 'OC , - k m Ln C O 0"- N U O r Cl in . - - Q . . . O 0 0 I I I

- . T u C O C I I I o n c C Y l C w> N Ln I C N m - * Y ) O h 0 2 m h e NLn u C r Q Ln- u ( r i m u D N n N O C m '-. h LnLnQ r, n ms hh*)

S . .

n c c I I I

UV*.* C C O C I I I 1 O O 0 h m Q N h O m r n c n u n *Ln -Q w u u u

h m - œ . o c - * 6 m u r . . . . C ' D O 0

I I I

Ln O O O C C I I 1 0 O 0 0.-N - O h e DC C vi m n m Ln Yi

m Y O I > Q O C C C C I I I I I

CI 0 O n - n u r n ~ 9 o. L n r w lh N it c e .@ u * C h n N Q u - no u r c n n M f. O * O Ln N N

r Q - ,,-,mu

m m - r u 0 O h O *Ln- O C7 h -Or. u Ln hi - Y i * * m m N O V I Ln-Ln

. . a

c n o 1

Ln r E u - u Ln ,.flic 0 0 0.n- C u- C) u m *Ln r N . - 9.Y m n m P) r h r - 3 . . . . . O 0 0 c CC)

1 1

. S .

C C D 1 I I

h h h h h * n i h h ~ ~ h i ~ u u e u i r u - ~ u r r ~ n t n ~ ~ i n C Yi

C C C C O O C C O O C O C O C O C C C O C O O O C C O c c 0 I I I I I I I I I I I I 1 1 1 1 1 1 1 1 1 I I I I I I I I 1 O ~ P C O ~ ~ P O C O O O O O C O ~ O ~ O n ~ h e n n o o n Q O - ~ ~ C ~ ~ U C O Y ~ h - h r - h h n c o ~ i r~~~~ u u - m p u - h N f l L n D e r C U m e c - - h D r u N V Q O + - a U Gr- U O r C m U N r r - C G * h h r - o - C m . - - r - r * O w h t n v h Q N - ~ U C L O O L ~ U O 4 - 0 0 r h N h O W L n m h U V - W . - ~ C h r - t - ~ ~ h e - w - - - e ~ m u r h ~ - 6 n O m - Q C Ln ~ n ~ m a h c o w - n m ~ i n I . - ~ C O ~ Q ~ O ~ ~ Q N O O o . h m m h - r C i n u L n O C r m n - m O - @ C O 6 O c - C - w O S < < - C r - - C r L n U Q m V C L n G C u n C C O m - N L n C D 03--. c m u h C h q O e m - - O ~ - m r r c ~ C O - m Q h - O 3.0'- ~ c C f l c r w h O C C - C C U C N L - L n C C U O - Q U P ~ +-Ln h % W R N U r O h O m r r m O h h u h O N h h W m D O u - Q ~ ~ C C - ~ W O ~ N W L ~ C Q ~ M ~ ~ Q W C m m - c u c ~ n 0 a' r . * m 0 6 h n n s m m ~ r c * - ~ n n m m o m c u u h - b u u O Q C m C Y i W N r 4 Y i G m r m C h 0 u Q O O u Y i œ - 0 2 Q r* U ~ r h m N C r - Y i n - 0 . - w m C ~ C m r - O i n r 0 . F - O YI ~i m h h O C O Y 1 L n Y i L n Y i - U IhVr .?NN( \NPUN d n - O L n - P r N

'L r- .n c O 0 I I I O P 0 ri h ai U h C 4 m u

m . .

C O C I l

h h' O O I I 0 O

w n m m n r N n Or. c Oj

rr C h 0 O N or. o u o. O r u Ln 0. h 6 N N . . C O

N -.- h

C C C I I I n a 0 - O - C 0 . N C N I O h m 0 hnn O - - W C 0 œ - O - 0 % u E n h N N NLnO Qmr - O O O h e m N N N . . . o n 0

u u o C C C

1 I I D O P L n c m N Y i u h O L n h - 3 O Q C O N n l n W h . - "2.-Q m o c - u w- O h N N L n u c O N 0 O r l n u u m cc- . . . n o 0

hhh O C l C I I I n o n 0 - u 0.D.m 0 0 - o m r - r u * Nr-r. m e n m a n N O C m m - Ln*- u u œ. a'he V I U N m e 0 m h h . . . 0 0 0

r.ceaU2 CIO c O C

r - h n W 2 . n PQr-Br.9 mLno.O)c m h - N m - n S C c m h 0 Q o c O o c n o - o.-nrcLn ~ ~ N N N N N N . . . . . O C O 0 0

h h h h h h h h O O O O O O O O I

h h h h h h 0 0 0 0 0 0

,.- *- n C C C I I I O C C ., P. h

C m - a * N O h r , V - r r .Q L. M.,* men

I l I l I l 0 0 d 0 O O O Q U C - m t U - 0 m K . C D m N m - N e u ? m h O C * a m U r o h U W 0 0 N c * E ermcf.m w u ? m a ~ , - I n U O r C O h U U W y r ~ C r i i ~ m m - u 6 r . N N OP. O G h n m ' L ? T>N(OPYi,> h h \ ? O m u u u u u u u . . . . . . C i O C I O O B I l l 1 1 1

a.-* h. .- ,.- e u *

N h W O yr O h h h * - 4

m . .

C ' C CI I I I

nnnnn 0 0 0 0 0 I I I I I 0 0 0 0 0 m o ~ n n NODr0 .V ) r m o h n

nnnn 0 0 0 0 I l I I 0 0 0 0 O O h O h m ~ n h 0 m Q muI.0 - u ~ n h r m o l n o - - u h e a l * h N O * . - O 0 l o o n h I 0 h m O I 000.0 O U V I . 7 1 h hhh i

u u u u / . . a . /

0 0 0 0 I l I I I

0 0 0 0 0 0 + + + 0 0 0

m n u 0 0 0 0 n e m n / W r N h

n w n n

U V l h O h U h o 0 m r N hnh N N r h h U m u e m m - m w w

e h m n ~ o hhhhhh C C C ~ C C . . . . . . O O O O O C I I I

uuu "')P 9 h A h o 9 r r m N.$g 9-J N n.r O n n o N m u O W N O - N r 'O N Vl-4 m N F - n o * O U 0 W43W . . . 0 0 0 I I l

C E E m : 3H3if N O N m

O O N m u - w m w

uuu 000 I I I 0 0 0 V l - r O N W . - O 0 - 9 0

h r n n O n h m 0 0 - * N P r n r n m m 0 0 2 0

W N . - 8 W O O h 9 O

le, a

N ~ O D n u 0 0 m r m n r n mlm O N

m u u 8V-h

OUED-COD ::",z"^

O l h C7 YI

- 0 . 2 5 3 0 4 9 1 9 4 6 7 7 0 5 2 7 0 - 0 1 -0 .1 7 2 9 6 8 7 9 0 3 2 7 6 9 0 1 D-O 1 - 0 . 1 5 4 1 9 1 4 0 6 5 4 5 7 3 1 0 0 - 0 1 - 0 . 1 2 7 2 4 7 1 8 7 5 3 5 3 2 9 6 D - Q l - 0 . 1 0 7 5 3 9 6 5 9 7 7 5 9 5 7 6 0 - 0 1 -0 .925660907C28R5760-O2 - 0 . 8 0 8 4 9 8 4 7 5 2 9 5 7 7 3 2 0 - 0 2 - 0 . 7 1 4 6 4 0 C 9 4 9 5 8 4 1 4 1 D-02 - 0 . 6 3 7 9 8 7 6 7 0 6 6 4 0 2 8 3 D - 0 2 - 0 . 5 7 4 3 7 1 4 5 5 5 2 3 1 a 4 2 0 - O 2 - 0 . 5 2 0 8 4 8 4 3 0 1 9 4 4 9 7 8 0 - 0 2 - 0 . 4 1 5 2 9 5 3 0 6 7 5 7 6 1 4 5 0 - 0 2

N N O 0 0 0 1 I I 0 0 0 n c o o O D . 7 N O m N Q N r . 7 - YImm -0.- Q O Q Q N h h h O O h m h.7.- Q N D n e h N N Q

I I I c a r

.- r-. T. - u O.

ICI m c. x. h <O b C 0% r? M O - h h u o m h C m &. IV G h r O m u * & r. N

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ! 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 + + * + + + + + + + * * * + + 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Q n m Q 0 Q m V h n m O N o o r ~ h u ~ ~ ~ u r n n ~ r 0 0 m Q h t m u M u O m N D O O O O N u Y I h m E D Q * O Q o 0 0 D Q U Q N Q U O Q Q V D ~ O O Y I O U Q u N r m m h h m m 0 0 m h N Q Y I r 0 m Q n m n Q 0 0 u O n D h h N N O h O m u 0 0 0 0 - Y I Q r Q - - D O O N 0 0 C - O D U O O Q r C m - m 0 0 m u u N h ~ 0 m 0 0 0 u 0 ~ u ~ ~ m ~ ~ r n m ~ m o ~ h n ~ O n O - 0 m m u D Q Q Q - m 0 O - O Q O O O ~ ~ U O P ~ ~ N o m - m ~ r n n ~ - o ~ ~ m r . r . U n n N N N N N N N - r r - r . . . . . . . . . . . . . . . O O O O O O O O O O O O O O C

O r - -.-- I I I 0 0 0 0. m D Q Q Q 0 0 0 , O h O l m m * ' u 0. n m m N . eh*?

Q h C .

h u r u m r I.-N O m N - m .- . . . 0 0 0 1 I l

U m m ' O C 0

I I I 0 0 0 n h u

O N 0 h 0 0 Q r YI O h h t n r w O h N O VIN O N * r . - D Q u m . 7 N N u o - - o n N h D Fr.* . . . 0 c C :

'00.0 - C r I I I 0 0 0 D N r n V i c o h C 0 O r * r - Q ho?* . , r o m - r n * n a - 0 O - a D O h h N P 7 N N O 7.0.- N o - O u r u . . . C' O 0

I I

r r r N N N N N N N . 7 O O C D O O C O O C O I l l l l l l l l l l a n n ~ n n ~ o ~ ~ a o C ~ ~ - u m - m m v Q h O h D m m o h n * P N V h Q N h U U N N m ~ m u m c m - ~ m o Q Q u N m Q D Q m Q o Q m Q Q O Q m m * Y I O . - r u n - m h u h O O Y I O u m - m * m r Q r n m h U m Q m N m n u 0 h o u ~ m h e ~ n h ~ I o D Q N Q h r V N - m D r m m N . - O m m C N n O e h h N c + m r o m * m N u N Q - m N n m m ~ ~ O Q . T N ~ O U - U m r r O U m N - r r E . . . . . . . . . . . O C O O C O O O O O C 1 1 1 1 1 1 1 1 1 1 1

..rmAhi<CuN . .PCSOOO OC: I I hF Ig * . * *

m n n C O 0 I l l 0 0 0 o o m N Pl U Vl - 0. Q r r O N - - Q N N O & * h m m N N Q m m N D - Q + - * * O - 0 Q Q N O N N r . . . C O C I I I

rcZf.- O u D r - o n u m h Q D N h.-QQ D O u m n m ~ u N - Q E . h N N C Q Q N Q .-.no.& m c - t c o N m Q m m m o - m o n - m - e . 7 . . . . 0 0 0 0

I I I

Inac C C ' C I I I n c n h h O C r * c e u (5 *> P h 0 7 C- lnhl-

NNN 0 0 0 1 I I 0 0 0 -Nu r O h ' oon ; m a . - h O *' N - 0 - u h m m 0 n o - O Q N Q 0 91 O N Q . VInVI O N h 4i 0 9' h*", . . I 0 0 0

l

N N t 4 0 0 0 I I I 0 0 0 O u - 0 o m n Lna", D O 0 h o u 0 m O r Q n q r c n n-.. u u h Ur... h Y r V m u e VI r VI O-.. N - -a . . . 0 0 0

nnnn C) O O O

N N N 0 0 0 ) I I O 0 0 h * O m n w D N O - N D Q O VI m * m U O N n o N - m V I 0 0 o m m * N O ",O OJ n 4 VI m n m N N - . . . 0 0 0 I I l

N N 0 0 1 l 0 0 O O - n VIN - * h u 0 - N VI

VIO O 0 * o Q J h - h m VI - 0 * C C

1

O O I I

N W l 0 0 I I 0 0

O - rl.

m", n 4) O 0 N n O Q n e o r 0 N O - N n u .. N Q N V I C -

8 . .

O 0 I

h h h 0 0 0 I I I 0 0 0 h Q O ha ln O - - o n - *.-& -lm0 m m * 9 n Q N a 0 O O O O r h N n - n e - Q r ? - O N O h ,n N -

a . . 0 0 0 1 l I

m m 0 0 l l 0 a n VI * Q

O P r n -7 ", O h VI m n rrr O h 4 Q n m e n Q n 0 4) V I N 0 -

b.,.*.?

' P C C I I I t D C n h u "3"- n m .a h - N - * c i C C * -. rf LA C"," , P.-& P h u h - 0

P VIh - r y - *'. O - - Y \ a . .

C c' O I l

....

. C r - c: ' I l

' n o 0 r2 m c *",a N U * C a n " 3 .? 0 h L' N * m h x r r y, < % O h ~ i n C O - rn * U

0 - LA -L.- - ". r., . . . r t 3 I I I

Q h * C c ) n m e ~ . n ? . m C r O " , " h m a œ - r m c . Q " - V O CU",-.- h O h h n<rr \ .u O * h O

hO l \ r " - O N * - r -h " , . . . . C O C O I I I

. . . . . . C O C O I I I 1

; I I I &dl0

NNNN O 0 0 0 N N N N

0000 I I I I 0 0 0 0 O h * O N m n Q N O N O r n N O D I ) * - U Q * Q Q U D N anne* * N r Q m a 0 9 * o m m - * N O o r n o m 0 n 4 - d o n o

o o o o O * O * * n o * Q O N N - - N O

. . . . . . . . . ,<;q-. O O O O O O O O O C

n N N - . . . . . i o o o o

I I I I

3. Conclusion

L'algorithme de combinaison (Algorithme 4) est tout à fait efficace numériquement,

mais plus vite instable.

Les résultats donnés par l'€-algorithme modifié et le A2 d'Aitken modifié itéré sont

pratiquement identiques ; cela n'a rien d'étonnant puisqu'on a démontré au chapitre 2 que

les parties principales des suites transformées par ces deux algorithmes sont très semblables.

De plus, ces résultats sont meilleurs que ceux du û2 itéré, lesquels sont meilleurs que

ceux du 9-algorithme.

La propriété d'encadrement énoncée pour LOGFi, à la page 38, se vérifie numérique-

ment.

CHAPITRE V

APPLICATION A DIVERS PROBLÉMES D'ANALYSE NUMÉRIQUE.

65

CHAPITRE V

O. Introduction

Dans divers problèmes d'Analyse Numérique, la solution S est approchée par les

termes d'une suite (S,).

Dans certains cas, on peut déterminer le développement asymptotique de l'erreur

en = Sn - S.

Pour les suites (Sn) dont l'erreur a un développement asymptotique du type LOGF,

(chap. 1. paragraphe 2)' il suffit d'appliquer les algorithmes appropriés des chapitres 3 et

4.

Par exemple, pour la série Sn = Cy=l l / i 2 , le développement asymptotique de (en)

est du type LOGFY.

D'autres exemples sont développés dans ce chapitre. Nous proposons aussi des al-

gorithmes pour des suites dont le développement asymptotique de l'erreur n'est pas du

type LOGF,. Ces suites apparaissent dans de sommations, intégrations approchées ou

résolutions d'équations différentielles [24, 171.

1. Etude des suites du type :

Théorème 5.1 : O n peut accélérer la convergence des suites (Sn) telles que

P 1 S n - S = - P 2 P 3 +- . ~ I P + = + . - , p E R+ - {O, 11, Vi , Bi E R.

par l'Algorithme 1 avec :

A2k = l / ( k + 1 ) A2k+i = k + p + 1 vk E

= O

Plus précisément, V k E N , (cZk+2(Sn)) converge p l u vite que ( c Z k ( S n ) ) et

Démonstration

Posons x n = $ + & + + ... 1 Si x = nïTp, alors xn = g ( x ) avec

P - 1 1 ~ = C a i x i f ( x ) = x ( 1 + )

Montrons, par récurrence sur k , que

Les résultats de calcul formel (chap. 1, paragraphe 6) nous permettent d'écrire :

Posons


Comme di = t , Vz = 1,. . . , p - 1, on a :

On en déduit donc que

Supposons maintenant

et montrons que E ? ~ + ~ ( x ) * x k + 2 .

Ici g ( 2 ) = C i > k + l - /3ixi.

En posant

les résultats de calcul formel donnent :

mais t' = di pour i = 1,. . . , p - 1,

ce qui donne

Et après calcul,

On en déduit que

et E ~ ~ + ~ ( x ) +j xk+*.

Théorème 5.2 : Soit ( S n ) une suite telle que :

Pl S n - S = - P 2 B 3 +-+- n , l / P n , 2 / ~ n , 3 / p

+ . . . , p E R+ - { O ; 1)

L'Algorithme 2, avec Bk = ( k + p ) / k , V k > 1, accélère la convergence d e ( Sn ) .

( k ) Plus précisément, pour tout k E N, ( x ! , ~ + ~ ) ) converge plus vite que ( x , ) et

Démonstration

Similaire à celle du théorème 5.1.

Applications aux séries :

Pour les séries dont le terme général est une fonction de n suffisamment différentiable,

la formule de sommation d'Euler-Maclaurin donne un développement asymptotique :

considérons la suite ( S n ) définie par :

Si f admet dans [m; n] une dérivée (2r + 1) ième continue par morceaux, on a :

n r B ( n ) - f ( 2h - ' ) (m) ) + Rr

h= 1

où Rr est le reste dont une majoration est :

et B, les nombres de Bernouilli. Cf DIEUDONNE [14]

La convergence d'une telle série est donc accélérée par les algorithmes des théorèmes

5.1 et 5.2 avec p = 1 /(a - 1). On peut encore améliorer les résultats de ces deux théorèmes

en étudiant les suit,es de type :

cr réel, a > 1.

Nous supposerons que pl = O, pour avoir une régularité. On a alors le théorème

suivant :

Théorème 5.3 : Soit ( S n ) une suite telle que

8 > O, p; E W, Vi ; Po # 0.

I/ 'Algorithme 1 avec :

accélère la convergence d e ( S n ) . Plus précisément, Vk E N , ( E ~ ~ + ~ ( S ~ ) ) converge plus vite

Démonstration

B Posons tn = $(Po + 4 + n: + . . .). s i x = $, dors tn = g(x) avec

i l i f ( x ) = x ( - 1 ) - x et f 2 = f o f . i21

I

Posons 90 f ( 3 ) = C7iXi et g0f2(x) = Aixi- i2e


ce qui conduit à :

avec

On a alors

On en déduit que Al = y et

Supposons maintenant

et montrons que ~ 2 k + 2 ( x ) * 5 2k+0+2



On en déduit que

et E ~ ~ + ~ ( x ) x2k+e+2 ce qui achève la démonstration.

Remarque

Nous verrons au chapitre suivant des algorithmes permettant d'estimer 8.

2. Etude des suites du type

b

I = f (x)dx

où f est une fonction suffisamment dérivable sur [a, b] et la suite ( S n ) définie par les

formules des trapèzes :

hn Sn = - [ f ( a ) + 2 f ( x 1 ) + . . . +2f ( xn - i ) + f ( b ) ] , pour n 1 2 ; 2

avec hn = -" n et r , = a + ih,Vi 2 1.

On démontre, voir [ I l ] , que ( S n ) converge vers I . Et une généralisation de la formule

d'Euler-Maclaurin donne [24] :

On peut alors appliquer à ( S n ) les algorithmes des théorèmes 5.1 et 5.2 avec p = 112.

Rappelons ces résultats que nous complét,ons.

Théorème 5.4 : L'Algorithme 1 avec :

accélère la convergence de ( S n ) définie par la formule des trapèzes.

Plus précisément, pour tout k E W, (€2k+Z(Sn)) converge plus vite que ( cZk (Sn ) ) et

€Zk(Sn) - I n-2k-2. De ~ 1 ~ 3 , POUT tout k E W, S i - I " cik(Sn - I ) ~ ~ et

€2*(Sn) - I = ci(Sn - 1);) alors i22kS.2

Démonstration

Il suffit d'appliquer le théorème 5.1 avec p = 112. Une démonstration complète s'avère

nécessaire pour le résultat complémentaire.

Posons X n = Sn - I = Ei2i @ 2 i n - 2 i .

Si x = ', dors x n = g ( x ) avec

On obtient dors E ~ ( X ) ¢j x 4 .

Supposons = CilZk cix i et E ~ I ( X ) = Ci22k+2 c i x i .

Nous reprenons les notations du premier paragraphe du deuxième chapitre.

Les résultats de calcul formel nous permettent d'écrire :

On obtient,

avec m = ( D 2 - T 2 ) / ( D l - T l ) et

n = D3 - T3 - (2k + 2)~2A2kc2k+2 Di - Ti A z L - I c ~ ~ ( D I - T i ) '

On a immédiatement Dl - Tl = 2k + 3, ce qui donne

A2k = 1 / ( k + 1 ) {-42i+1 = (2k + 3)/2.

C Z k 3 De plus, m = 2(k + 1 ) - -. On en déduit que

avec E = Y2k+4 - c2k+2(m2 - n) .

Le calcul donne alors

Théorème 5.5 : L'Algor i thme 2 avec Bk = ( 2 k + 1 ) / 2 k , Vk 2 1 , accélère la

convergence de ( Sn ) .

( k ) P lus préc isément , pour t ou t k E N , converge plus v i te que ( x , ) e t

- I - n-2k-2* n

D e p h s , pour t ou t k E IV, s i x?) - I = c i ( S n - I ) ' , alors

avec

Démonstration


Théorème 5.6 P o u r tou t k E N , ( g k + l ( s n ) ) converge plus vite pue ( e k ( s n ) ) e t

D e plus, pour t ou t en t ier k , s i

alors ê k + l ( ~ n ) - I - B ( s , - I)2k+4 avec

Démonstration

Reprenons les notations utilisées lors des démonstrations des théorèmes 5.4 et 2.3.

Démontrons par récurrence que :

On vérifie facilement que el ( x ) w x 4 .

Supposons que ê k ( x ) = ~ i > 2 k + 2 c ix i = g ( ~ ) .

La démonstration du théorème 5.4 nous permet d'écrire :

avec :

2 k + 2 q =- ( 1 + rn'x + n'x2) + . . . 2k + 3

1

avec

{

' b 2 k + 2 = ~ k + 3 C 2 k + 2

2kS2 1 b 2 k + 3 = - 2 k + 3 C 2 k + 2 + 2 k + 3 C 2 k + 3

2 k 5 b2k+4 = & ~ 2 k + 4 - c z k + 3 + f ( k + l ) ( l O k + 1 7 ) ~ ~ ~ + ~

2 - 1 Cz1+3

\ 2 ( k + 1 ) ( 2 k + 3 ) c z t + 2 '


1 1 1 1 m = -- 2k + 2 (t'l +Dl) 7-t = -

2 k + 2 (ta + D2 + t i D i )

Les calculs donnent alors

Bg(z) ̂- 4z2k+2 avec :

Théorème 5.7 : Pour tout k f N, (02k+2(Sn) ) converge plu8 vite que (02k(Sn) ) et

Démonstration


Les résultats des théorèmes 5.4 à 5.7 peuvent être améliorés par :

Théorème 5.8 : L'Algorithme 4 avec

accélère la convergence de ( S n ) .

Déinonstration.

A chaque étape k , nous allons appliquer à ( x , ) telle que x , = 9 + 9 + 9 + . . ., le

A2 d'Aitken modifié et le $2-algorithme, afin de les combiner.

1 Posons x = ;.

A chaque étape k , on dispose de z k ( x ) . Le A2 modifié appliqué à zk peut s'écrire

Bk 6 ' r k ( x ) = ~ ( f ( x ) ) + a

où f ( r ) = et A = N-' + E-' avec

Le &-algorithme appliqué à 2 k s'écrit :

où 6 a k désigne le A2 d'Aitken normal appliqué à z k et M = 6 z k ( f ( x ) ) - 6 t k ( x ) . A

. Z k + ] ( x ) est alors la combinaison de 6 ' z k ( z ) et $ ( x ) .

3k+5 Supposons z k ( x ) x 3 k S 2 et montrons que f k + ] ( x ) e x .

Posons

Les résutlats de calcul formel'donnent

avec

On obtient alors :

alors S t z k ( x ) a x 3 k + 4 . Si Bk = 3 k + 2 >

Il reste à déterminer le coefficient E de x3k+4 dans b t z k ( x ) .

Le calcul donne

Posons maintenant

Les résultats de calcul formel nous permet tent d'écrire :

Les calculs donnent alors

Et si on désigne par O le coefficient de x3k+4 dans &x), on a :

La combinaison est donc

ce qui termine la démonstration.

- Etude d u E-algorithme pour les suites d u type :

Posons gi(n) = -&. On constate, avec les premiers calculs, que (E:")) ne converge pas plus vite que (E:"))

Le E-algorithme n'est donc pas efficient pour cette suite. Nous allons plutôt étudier

l'itération de la première étape du E-algorithme.

( k ) Désignons par (Tn ) (chap. 1, paragraphe 4g) les suites ainsi obtenues. Rappelons

que (TA')) = (E!")) = première étape du E-algorithme. " ..

On a le théorème suivant :

Théorème 5.9 : L 'algorithme

( TA0) = Sn (suite definie par la formule des trapezes)

( k ) accélère la convergence de ( S , ) . Plus précisément, pour tout k > 1 , (Tn ) converge plus ( ' - 1 ) ) et TL*) - 1 ¢=, n - k - 3 . vite que (Tn

Démonstration :

L'algorithme va être appliqué à ( x , ) telle que xn = $j + 5 + 9 + . . . 1 En posant x n = g ( ; ) et x = i, on a :

Et l'application de la première étape du E-algorithme à T ( ~ - ' ) peut s'écirre, avec 1 . gk(n) =

Démontrons, par récurrence sur k, que

Il est facile de vérifier que T ( ' ) ( x ) x 4 .

Supposons T("-')(x) = C ,!?;xi. i>k+2

Posons

D'après les résultats de calcul formel,

et le calcul donne T ( ~ ) ( x ) xk+3.

Conclusion.

Nous disposons donc de plusieurs algorithmes pour le calcul d'intégrales de fonctions

suffisamment différentiables.

Les quatre premiers donnent les mêmes résultats (asymptotiquement). Quant à

l'algorithme de combinaison (théorème 5.8)' c'est le plus efficace.

Nous ferons plus loin des comparaisons avec d'autres méthodes.

3. Etude des suites du type :

Considérons l'intégrale singulière du type

1 = 1' avec g(0) s 0-

En posant j(x) = 9, on peut définir la suite (Sn) (cf. paragraphe 2).

On a [24] :

On peut alors calculer I en accélèrant la convergence de (S,). D'où le théorème

suivant :

Theorème 5.10 : L'Algorithme 1 avec :

accélère la convergence d e ( S n ) .

Plus précisément, pour tout k E N , ( E ~ ~ + ~ ( S ~ ) ) converge plus vite que ( & 2 k ( S n ) ) et

c Z k ( S n ) - I o n - f ( 2 k + 1 ) .

Démonstrat ion :

Nous allons appliquer l'&-algorithme modifié à la suite ( 3 , ) telle que 2, = + P3n-3/2 + @5n-5/2 + . . . + /34n-2 + P6n-3 + . . .

Reprenons le formalisme adopté lors de la démonstration de théorème 5.1, avec

Démontrons, par récurrence sur k, que

Comme A-1 = O et A. = 1, A = N-' + E-l

Posons gof ( x ) = Ci>1 Y ~ X ' et g o f 2 ( x ) = A i x i . - Les résultats de calcul formel donnent :

On obtient alors = -9 [1+ (F - 4) 5 2 1 + . . .. On en déduit que Al = 3 et ~ ~ ( 5 ) e x 2 .

Supposons maintenant que

Posons


X 2 k - 1 = a X z k = b

A2k+l = C - a ( 2 k - 1 ) X Z k S 2 = d - 2kb X Z k + 3 = e - ( 2 k + 1 ) c + ( 2 k - 1 ) [$ + ( k - l ) ] a .

Le calcul donne

ce qui termine la démonstration.

4. Calcul d'intégrales singulières du type

0; f (x ) = .*>f(O) = f ( l ) = 0.

Soit (Sn) la suitse définie au paragraphe 2. On a [24] :

C'est à dire que (Sn - 1) f LOGF;" et les algorithmes étudiés pour cette classe (chap.

3 et 4) permettent le calcul de telles intégrales.

5. Résultats numériques.

a) Séries

Nous avons d'abord considéré les séries suivantes :

Le développement asymptotique de l'erreur de (1) et (2)' via la formule d'Euler

Maclaurin, est du type LOGF':. Celui de (3) est du type LOGF;". Quant au dévelop-

pement asymptotique de l'erreur de (4)' il est semblable à celui des suites étudiées au

chap. 5, paragraphe 2.

Pour ces quatres séries, nous avons appliqué 1'~-algorithme modifié (ou le A2 modifié

itéré) et l'algorithme de combinaison.

Ensuite, pour diverses séries, dont plusieurs de Riemann, nous avons expérimenté

l'algorithme du thérème 5.3. ,

A.C. MATOS [25] a étudié l'application du E-algorithme à diverses familles de suite

dont le développement asymptotique de l'erreur (ou quelques termes de ce développement)

est connu. On verra, à la page 101, une comparaison avec un de nos algorithmes. Nous

n'avons imprimé que les suites d'erreur pour les transformations.

T h < c . ~ r n r 3. A

~ . Q 2 1 6 ç 1 7 8 ? 1 4 7 ~ 2 3 2 D - ~ 2 ! l . 3 5 ! 3 5 4 3 6 1 ~ 1 5 2 9 9 8 0 0 - 3 3 0.1 9 2 3 5 3 5 9 4 0 9 7 5 9 9 3 0 - 0 2 0 . 1 1 6 7 c 3 9 3 0 8 0 C 4 8 9 ? D - 0 2 1

C . 7 7 C 4 4 4 3 1 2 3 6 1 1 5 2 5 D - 0 3 ~ , S 3 9 2 7 ~ 6 5 4 5 1 0 ~ 0 0 4 D - ~ 3 ,

+?=A 1 2 . 3 9 4 6 5 3 5 7 4 9 5 L 8 Q 3 5 0 - Q 3 0 . 2 3 8 9 9 4 6 4 5 4 2 3 3 8 9 1 D-03 1

' 0 . 2 3 2 3 9 7 5 4 1 7 1 1 ~ 1 5 4 D - 0 3 i 0.1 5 5 5 h 4 6 9 4 7 6 3 9 1 5 ? 0 - Q 3 i 9 . 1 5 9 6 7 9 2 5 8 C i 5 4 F n G D - 9 3

/ C. 1 2 4 3 2 6 5 2 2 5 9 3 0 2 0 2 D - 0 3 2.1 rJ43rJZl 5 S 6 7 7 0 3 6 2 D - 0 3

- 0 . 4 5 1 5 5 3 1 9 5 5 9 5 0 4 9 2 3 - 0 4 1 - C o l 5 2 5 Q 2 7 6 7 2 9 9 5 7 3 2 0 - 0 4

- ? . 6 2 6 2 2 5 3 5 7 7 3 1 1 5 3 7 D - 0 5 \ - 0 . 2 9 7 S ? R 7 3 L L 7 9 2 2 2 1 D - C 5 -2 .1 5 6 9 2 3 2 0 5 3 4 1 8 6 1 1 D-n5 1 -C. 896ZLZPJSI)2719?,3r)9-(36 k = 2 - 0 . 5 4 4 4 Ç 4 4 3 6 3 0 1 2 5 5 1 3 - 0 6

1 - 9 . 3 4 7 4 2 3 2 1 1 5 3 8 5 5 3 3 D - 0 6 - 3 . ~ 3 1 1 C ~ 1 1 1 5 6 6 5 5 ~ 2 9 - O 6 - C o 1 5 8 9 4 7 3 1 8 5 7 C 2 5 9 7 3 - 0 6 -0 .11 2 5 2 2 1 5 5 5 1 3 2 6 1 9 9 - 0 6

f i CI. 2 5 2 7 7 7 3 3 9 3 9 3 2 2 0 8 D - 3 6 Q , 7 0 7 0 2 3 5 1 6 1 5 6 5 5 5 3 0 - 0 7 U . 2 4 3 1 2 1 2 5 8 9 4 9 5 2 7 4 D - 0 7 2 . 9 7 0 5 1 5321 5 2 7 2 9 5 8 D - 0 8

k =3 9 . 4 3 3 6 9 6 5 8 6 3 0 2 6 4 2 3 0 - 0 8 9 . 2 1 1 5 ~ 1 5 5 5 3 1 3 8 ~ ? 4 0 - 0 9 9 ,11091 L76L8292C36D-OR 3 ,016031 7 8 6 3 4 6 2 8 2 8 0 - 0 9

w 0 . 3 5 9 1 6 1 7 3 3 2 1 3 6 8 5 1 D - O 9 A -0 .11 2 5 5 5 2 9 1 6 9 2 5 6 4 6 0 - 0 8

'-ri. 2 8 7 9 2 7 3 3 7 7 8 S ~ 1 3 Z D - 3 9 - 9 . 5 8 2 4 3 2 2 6 5 0 8 1 6 1 7 9 ~ - 1 0

4 I z 4 - 5 . 3 1 C 3 5 2 2 5 1 2 3 5 1 ~ 3 5 0 - 1 9 - 2 . 1 2 2 4 6 7 3 7 7 2 0 6 3 3 3 6 0 - 1 Q -0.51 M 3 Q 6 3 4 4 5 2 1 7 4 2 D - 1 1 - 0 . 2 6 1 9 7 0 7 4 0 2 3 9 5 9 2 1 0 - 1 1

w -

t n M M C r: C. I I 1 a P O 7- - r. ,.Ph N N VI - I C ) r .

- C r - - r. C' f. r ni r - s u Pi ., C' u u n. CI r. (ri

- r .u O n! Pi -.-a D r. n' LP u 7- . . . O c- C

m n v u u O C, C1 c n I I I I I P c , O C C

LP tn b- C' C C. I I I o c e NF., O: P N r' In O n n r n- -a - * O e- O. n V I . O ., <n r. f . 0 - P - Y I V I 9 0 F- m o m Y\ E: VI - r.4 Ci U n, r

S . .

r: C C' I l l

.nQCCr . Ci C' C C C I l I I I c n o o o C > L P L P C V I ncni r w - r . r .u r n t @ o O a C N V . b r C'nc r. r I C Q N ~ ., F f f c3 h LP c W N r . - ce.- r.- I I 0 C - Y \ n .CI- n n ~ i n h - r . N C Y i i c t ,

,-> 0 r *- cr ': : : lc . : C , C <.,Ci <- 1 l I I

r. C 1 C O C IC) - O VI O r- ne IC)

LP C M n : n

C

h o 0- C C C I I I c m n r C. P IC) a e> 4 r. u: e u * n. ni n s e c n a - c r m U n P .au VI -anc P C h' C Ci r7 U C'N *1 n, - .-*ri

a . .

C E L-

Q O . D - o . o . ~ C O C C - P r I I 1 1 1 1 O P P ~ O ~ 0 - u P - V I L P V Q Q C - ~ . ~ Cr. Mm.-*

- C Y . ' 4 * ~ n I i ' v . v . * 3 ~ . , . C C .Pr. hr. . C< < . C' C <' C I ' c C r C C , P C C i C> C ' C ( 1 I I I 1 1 1 1 1 1 1 I I I I 1 m a ~ r r n n ~ f i o e c C- o o o c br\< V I w r C + C \ 9 l nu O O ~ C ' C ~ : U Q % L : F ~ I ~ C un,

w i 0 M L P v I u I Q ~ N ~ ( O . i C C CU- ' VIC. s <' O- 6.n. n . 0 . 4 h .r; - P

Q N - - M r < r i r @ o r ~ 7 r . C v , , . s N . ~ c., ! + C C & . - Du ni r .Fr i r m c ' r

. c P w + ~ < ~ c u - - c - ai.- c , ~ - < L . , ~ ) ~ L P ~ ' Y . ~ . C Y , e . - .-,- vin P ~ L T . ~ ~ C \ ~ ) L P M U L ~ - : + i n - - v r r l m e n , * - O tne-w>.- c - c ir. ., CI O O. . C . ' P ' C ' U I . P c . - u < o * ? O Ir\ P. .LT P. -7 h u . m r n jp - .. .- -.. ,- o ,On,',' h W P P .C . r i r , . r . * ' l l. n. .,,A

e i w , 'CI C 7- h l P O. N VI - C r> P', n, O n. y < ,y < U O c -1 u * .. n - ,- ni .- 1.3 r .. r- I- U I - Y -7 (r' r n -7 W . n , r. O .- . . . . . . . . . . . . . . . . . , , ,. < ' 1 ' C' '- I i < r: < . < ' ç i C ;,- , , C' c -

1 1 1 1 1 1 1 1 1 1 1 .

I I I I I I I I I I I I / l I I I l C n ~ ~ n e c ~ , - n c ~ c , o n c m o e ~ n n w O n u m n C a - V I - * Q n - t C h r . a O + u C ' * v > N u o . V I O . p , r m ~ r . ~ ~ - u ( r n i b n -peu\?@ - O L . - U C + h u e w m i n L P C ' C ~ C rr. VI- .Y - ~ c ‘ u r ) r n o u u r < h ~ M C , F > C - n o - u n ~ o - m w u - r ~ , c P - u ~ - - c o ~ M + ~ r . - n a-w, - P c ~ P - - - r r w * i ~ r u L 0 % r - ~ . a r c n L A O - r r -- 7)- 0 L-r re- ,OP C ~ r i . - - ~ h . - . - P " - C C 0 - '',n7)<-,. U.V.-< <.-i-n.,- P h 0 * o

< - . - L P I c ~ < ~ L - . J r n r r a n n in e C O r. c * .ri c ' n h n ri'u'n na r. L , u ~ - n e W ~ h , i . C n C i P n r v r Q .,,,.-w C U h,., - - L n , . ,- < - C ' f i .-t-

c'.-.-.-C.-Fru-n.- - - * r . ( r

, - - - , - . - - - r - - - - - - -

r - c c r ' r " : r ' C ' C C ~ t < - C C + . + + * + + + + * * , + + + CC'- C I L L n P P O ~ ~ n r l r . c c ~ C P C ~..--1.n.-<&.-~. c n .- r- F P <- ,n t~ 1.7 r y, c*. r. <r 'ln n <r .. w - P O c <. fi,+ r t h

< . W . Y L- _: O . O CC ., P n ' - , r- h C ' E O ' < " < - C C ' b ? . n o < r Cr. C . ' C .c < ' < x Y. C C- *- -̂. 0 b ' ~ v .c r P.. W. < - C ' r h i> C .- C I l ' l l i I. F P .na . - m c - r r * . n i \ c . . - o < ( . P ' L - c r - P C < * C - C C r . ? < , G . . * C I P < . C r \ , < . . P C < < < .- C ~ . C ~ , - . . C P C ~ < h,. + r r O ! A + - r - t e .- P , ? , P .P - ,> c u 6 , - c 4 W . , .: P r'c i c c r r. i r r' . i r r rr r r , r ' i : ,: c F l r . - . r i h r . . , - r U C L > ' < . P 4 r C C - - C , - C r - r - C r - . . . . . . . . . . . . . . . i

Pi. C

C r i I I (3 0 O C n. P m m P- Ln r P.'

, Y i C ?

i n "? I C ., <> <' ,P -1 - h i? . . r- 1 '

1

I.. Pi F-. C ' Ç . C I I 1 O <. c m m - ., P C D n C' ,- P. F

1- C C

Ln 0 P' .- P II c\ .- in q1 .n r) .ri "' W. n -r (7 .O n O -1 .' r " i- n Cl u C 4: Cf . . . C C' "

r L I . C - 0,-P < P - ,* .- r. " ' w O h r C ' n, r Y C C C

.n .C .r' <- r. r i I l 1 a r c c - C. 1 O' -1 C "' u P P ' L n C P U X C m c h a P C. h b' nu- c r LP m L- w. ., ., - m m C O P I r i 7 . ?-' - m n. . . . C < - r - I I I

h,.r,h P- '2

C C . C C C . 1 I l I I

r ) L P C P. r- C c.,. " u W h i L n C ' . y . u- - -1 .= c h - n 0. 0- I*I T' C, fi,;. P mr. h i r d - r ? ~ n i o r - n o 0 , - C ' r n c 2:s r; ", I P i r r. P ,: 1- 1,. L N-1 P - i L n c r. -1 DL 1 ,,\ c. w3 ..- V , n , h fi. O

- 1 . . < . 'O!,- < l ' C

1 i

I.

C 1 C'

0- O ,. - .T r. r rC C - - r m . . C' 1 ' I I

~ , - C C . - C ~ C C T - - - - C C

C F C C C C C L . C > C ' C ~ C r n c . + + + * + + + + * + + + + + + C o m n c n C . ~ n 6 C C n C L C C 3 I ~ W P r r - - 1 r V * h h O ~ C V - 0 0 . - V r . h b - Q V t ? r C Z C . . C P - O I P I ~ , ~ ~ . D r . c 3 r C rr. C U c ~ ~ - P T . - c r. r n i w i - C . n N C h P . h u Y D f 7 P L ' h . ~ C IOGC - C C = C O : P C . ? C . F C r C r , - d C C C P rY.?CC r < c ' - - m r C C r .oh .,r-.r,r.n c - . - u L P ~ ~ P - O r , ~ < r c . r r r c h e V, 0 ; n 7 C i r O. < - ,ri e 8"

I C K C . ' - P - a . ~ , ~ c - n y l r r n O I C ? P r..--L7h C r . I > r . ~ - , P U - * - , C-.rn~v'r. h n e F r c -1lnr.n C r i - c " u n , r < m f i u h ~ , ~ r r i - - c P ~ r r r - n i n , n i - - - c - - n s n i N ni ri n. n, r.3 9 . . . . . . . . . . . . . . . n r c r: r. c- r: r, P C l L- c.- P r > a

r > O r. t LC r\ , C, P., < C' '> V r .?O <~'r. Y c o r r. "- ,.y

C'". - ( 3 u 0' C C - P-". C h u - c- r ni C' N u

Y Pî ,- C C. C I I I c n Cd h n - a @ u Y1 P f. T\ Ti* e h L' VI cf, - C C * 6 LC u v h N C < C CI c . n f. Cl Y " u - n 0- * h C O I - d n ~

. m .

C l> C

F 1.- u O O C ' 1 I I 0 0 0 r. .- - .- h' P. C. u- - n a u C

V l - O .- C n- . . . C C? ri

L C VI .KI .i C C C C I I 1 I C O C O O U h U " - C m 4 tan 4 4 * - @ Y i r V>civrC C l . - C O n - < n N c n r, r.-< V I h 13 P- O f. rn*l,-- r " 0 0 - c ni .* w * ? - Y r r- r' Y n - * r -

a . . ,

CI LI 1 ) ' 7

I I I I

I I I I f P P P f. LC P ' h ' r o u u r h V I u ntr.olih

C C - n U F C P I <.rN.- V 0, en r-. - P N C V r.7 L' r- - C C h f . i n d C t r - \ t u - - ,> Cr. ., n, ir-r.n . . . . <. c r, 1-

C'n r. r . v n C P ' C u - u r . v . e P f. C! C J V- *' P - 1- C O LC Y in in C 1 f . h r. - F ~ ~ " . D r . w ~ n c > r ' ~ u c ? n - ~ i n r \ , ~ r , r n i n ~ CI .-niv.? C ~ i ~ i n 6 < r h r . r . h f . w u o ' o

8 Pi n ' W . c r, r- I I I

C C 0 a in c n P r - < ,-%,

C 0 . u ' 0. <C u n i PL C. Y i r V> ,,- C r .r, 'C n- "?u 1 - L, r. C r l ., C r. 0' " F. <r O C. -3 n n, 9 . . . 1 , r i c

LI rv n w rr, h 13 h P i 0 . u o *,pl - 0 Y - . o r P l r 1 I P P . ? O O .. In*- " - 0

v r C c - . - . - ,>h . . . . r . < ! r-! C

.. tn Cc'

1 I 0 c?

t-? W. Cl n n s u'

.Q C - ,- C .- .KI "- - C O -t c- e-

u '7. n .... ,C u ,. - ,- - "- . . , % l > I I

c : c 3 t.CC'C.CIO 1 1 1 1 1 1 I I O P r n r r o n - 0 C1 I .c - r . -n< c>c,,,tn...o r. Y

U O I P C N C U I I h Y i i < i n ; r N O . a . .. ni n t , .n n, -9 n. Cini r p e C N N : n' 0 . .- u *- ,- u VI O 0 w, -PU ' inC 0 u ,-. n ir ir - ' - P n ' l m 'fi P. r -7 .- r F. "- <' nI

.. r nYi IC C I I

Cl c? u D . C C CJ CI^ c n- I I I I I I P D C O C C c,.rr.mu'@ > . v u O W C Q W 6 C ' C - m.- .C o ' n , ~ ,% C In 6-l C C. ni P; F N n t N

. . . . . . c - r <., r y L-' ~

I I I

c . . - L-P. C F . r \-I. n. N. ? .. r> ,., r P 4 r C " - Y h r l p ' . r n 0 C > C r . < t , % C * C r F .- IC P. "' L- C r . i . P - C - 1 h . " P . - t < .

mm N N n, n, iq

C I C) C C Y-' c-. C' 1 1 1 1 1 1 1 L > O I., P, r r c r - C , r c t " - C , . - W L - P . . - C " I h a , , - C O O a - Y l l r c t .. .op r - c ? n * R r d u u m " . Y i o r * C'P 0 O & C - O

m n r. r- r a m - O .-mm., n. 0 W . N CI C O '

L P m - . , w O C C: O .n rl .- - P ' D z l r - n r i r i y r . n n n . c - F u M * l p i r . I O C R , . O - - ? - - - a . . . . . . . r> r - r - r> ? r- t-,

...... 8 CI P. N ., YI C ' i . r C ~ C ' C ' C i C I l I I I I l l n î l o o a c - r . c * r c , * u fi C m <. -er rhc <:-p. *>h .Cr. lc r r. 5i ' O - .n .~>- - n LP ,.-*a< .,CI C O r" - 1 Y I y : a " o - c Y',*. .'. , O'.r. "- r r. 1, P l ,- C ' ," - LP .O n. VI P. Ir, C r - C> L' r, V CS P ' n C1 LP r C . 0 C O. l m - IC Y M P . , L P C r. .O c t (L ~z113 A a - F. n l t P h vr h m .? Ou s r - m 0' d rn c t r' v r - o-

. r u r u - <' C C C' r m C " c - - V I r. F. P r W F O #ri+ y l n . y i C n * - r h C . F \ c - . - C L w 1, r. 6 C.' C N U W T \ I Y i in in r~ o v, u n i - e u . . . . . r > c3 C ' C C I I I I 1

U U D - C C O I I 1

CI C 12 O a. 6 - C u .- r w * - a 9 2 . m * U N >O,. P n - c - n, c t - N D n h c t n r-c- *FI.

n c n - Yio - n - -

a . .

c- C> C'

- c7 <- - 7 - 1 1 1 O P a Y\ - r- C C - e n C u - O. Q - O Q N .- 4 u ... r. Yi .- c t v r nr. r v- *> <r

œ P: 5i C m N n z l n c t r .T a - - . . . C > C C

O l

u .. h u v c-

i , , r. h h o. C C - LI n3 u 6 - r n n.. r. P' h h C C h n. - m \7 <C c r. .. r' r * 0-

8 . .

C' C C I I

- n n ~ r v ~ r n r n m m r m r 4 4 m ~ m m a a a a 7 i u > ~ c h h c r ~ ) z c ~ O : O O C C ' - - - - n , - - ~ C ~ C - C C ~ : C ~ C > C ~ C . C ~ C : C ~ n r i c ~ ~ ' ~ > o n o c > n r i c c n c o c c o c r - 7 - 7 - c c - - I I I I I I I I I I I I I I I I I I I I I I I l I 1 1 1 1 l 1 l I I I I I I I I 1 1 1 1 1 n ~ n n o n c ~ o n c ~ c n ~ n o n n n o o n n o n o n ~ n n n c , c n o o r c n o r @ n o n U ~ - D ~ ~ W L P L ~ I ~ Y . ~ U O O C C - 1 - 0 . o ~ - m w c r . w c ~ r r n n r m - ( ~ O o r \ . ~ a c - a c h ~ ~ c ~ m T r r i ~ * u h ~ . ~ v v o n ~ h m u w w m a h ' h u m e h n m m n o a 0 o . - v m - - - o u h - ' C n i r . 3 ~ 4 P- . n u - - - - o : r n r ' ~ c c . m ~ u - o ~ l - - h - - r - c n ~ r C o ‘-cc c , h r - u r r ~ . ~ C * - ~ ~ ~ > Z I ~ U N ~ G Ç ? ~ o N N - ~ C C ) N ~ ~ N ~ > m h r \ ' e ~ . m ~ h / n i ~ ~ , U U O , C . Y - a i r * U < : Y ~ ~ U - C C ~ . C I ~ D ~ O - - C C + O . Q C O ‘ C > W - r ~ ~ ~ ~ h h ' m ~ ~ ~ ~ e ~ ~ ~ ~ - ~ ~ - h ~ ~ r ~ , . f - h - 0 9 h < r . , h ~ a t r i . 0 r r ~ m * ~ c ~ ~ r > r. - ~ ~ N N ~ W G U G X V ~ - W . c . L ~ ~ L . % O. i c c ~ h m e . y r r n c o h i w - h h o , ~ m c . n . m c m u n e r . u o C h m , - r i h u m - C - m o o . r n ~ t ~ u ~ ~ . u r ~ - r ~ - m i h n i ~ c - h m p r w . h ~ . - C ~ . ~ U O L O ' C C ~ O . m m h r x C h - u l h u ~ 4 r ~ ~ p l w h ~ n i ~ - o . r - y . r j n n s r ~ r r ~ ~ i n L u n o . r . , r r a r m - m m m r v , r - ? ^ o - r r m w - c c * U F L U h r ~ a h n w ~ ~ r , ~ > - ~ n i u ? o ~ u a - ~ n ~ u r c t i , o n w m r \ . e h m n - c . n h h-hnf" . n u i r n h o r r d o - r . r c c ~ c . . - . ~ c - , ~ - r ~ ~ u r c m v \ m ~ o n n ~ o m r ~ ~ u v ~ r , . h i r m n ~ r r - 1 :

! r n i ~ ~ n - n r : ~ w o . u n - v u n d r r r - n a F r . r , r m w m r i n ~ r r œ m o : c 4 . n e c r \ . s - c u C . r i ~ r . r v ~ m m ~ . - t ~ ~ d u ~ - . 1 m h ~ m ~ e u n ~ o , n i m r m ~ r r o ~ m r \ . a - ? d e C . < - t - ncu-hic

C ~ P O ~ I : ~ T ~ ~ ~ P C ~ C C - . ~ P C D L ~ ~ : L ~ O C ~ P C ~ C ~ C - ~ C C ~ C C C C P ~ r i r c ~ c ~ r o c > c c . e r / I I I I I I I I 1 . 1 I / I I I I I I I I

C >--

T $ @ in II II

II 11 Y r Y & s

.. - -

" ' 0 : C Y ; P L P C V . ,.-.-PU .'>< h u C. ,O+C'<.C4 ni r .C h v' h .- .O c r u - P I t o - - V?m fl 0.- ni -7 o' h o - W C u V P i Q r < . I - - C in FI. ., ..T .. r. r. 0.Y. r . r m a o r .

n i+ c < ? c . c - rl -.,O N - r - C - P

c C C' O c. C + + + r n r r C Cr. ,- O Y O CV. L P r r r n r ~ ., C i r C' ,- LT C U P r- C Y, , -TL a r .O r C- N r u * C C 0 - o r hhl.

m . .

r c r r >

i * o v o C r . C Q r r Q , h m ~ ~ O t c Q h w M I d - r Y , h u l n O . . 2 m C \ ' , L m r n ' v ~ u P I u I I . - ~ C ~ . n w . w a i. r i o in,n'.~r.. u o n c n C U - C h hOnjnn,.,m3F.?P,.7*CO

m a - r b - r ~ . - r k ~ r % r ~ r c c : o c P O C v ' . r i C I C I . C V I N h O ' r <,L'13ULPrd'P O - G - C C C ~ u r n i n t - r u u l a . t h w : ~ e c i h .- nt - . P * O-r. ,y a - h ec'r-r r i>- n r c - ,'l-"=,C?.-o m n n , - - . - *n - - " ' . . 2ee . . . . . . . . . . . . . . . . . . . .

c ' i: c c: C' P c.. r- C'

Y i u u P O O I I 1 .-Oc- n ~ m m ri> -3 n e o : w w a Cr. r .-a ct r r n IX u I?

-7 O Y\ L n CI nt C' D C O P CI' < 3 0 0 Y' - C .- 1- r .-O+

. . a c x c i r -

\r.,*

C c c I I I C P C IP Chl r < N h -no r I P r h C ' h k h h O h <% .- u u- c O "- nl .,** p r -. 1, D C P L- * - . n N n -.- . . . r r c r,

r d . 7 1 P b - m m * - 0 6 ~ n c r . c c r ~ c ~ c c c I I I l 1 I I I I I I D m o n l ~ ~ r n o n o ~ C r u c - . n c ~ n - u C \ h C,.flC"-.-rvu.J.7 I L O - ~ C ~ O m c r - n p u O 4 b- u <" ri r C l LP e 0:. c r e m ~ m r c - r n ~ n ' h * CI,. tc., r 3 m c ' P C l n u 3

n w ~ . n n ~ . - ~ D ç < - r w e - f i , W . 2 + r P.., r.r. .r @ r h O ' . v ' C , e n , a * o r O - C I ' e o In -) 0 r. < < C. r. CI' C? V l , r u - C - . P ~ h cric r r n .n RI r r. n ir 8 - n v' r .-N,, . -"2mYiwv'nmC ,- n, ni h C> *- nm O c. h 0 . -m. -v 'F- - . -x*w. .

r N N -1 PJ n, n! n, *? u . ~ - n c : r o r ~ r = C r ,

I I I I I I I I I I m ~ c c ~ n a n n r N - C U m C C - P i - c s . n c n c ir o.-- u n i c r . ~ c - u , ~ ~ u r o r, O'> V3 D- ci C\' l W. w, C - m r h M O Y I I C < > y l -PCI"- lFCICIC<.-N s n j < - r m u h i h r m v r , n m r \ h m C . C V C r 6- N h r. C. C)C- b' L- m ni O. r x mi-- O . , f i+*--< O ' C Q m - n r . n , m i r n i e - m Y I L r i . n - r . F , * r C > P . r \ - h - f i r . % - ~ c0.n I - D c - P - r f . - C h * - u C - . - * O . . . . . . . . . . L' ' 7 O <' O 1 ' Cl II' 1 ' P

-3 u I- C I I O C r U Ic u D- b î

a Q a- u- m c n, F t" r,

m d - 1 ni r w C M . - . * . C I r c

a <, * O 0 IC I I I P O (' c m r. .- c C .C K ni in O h n e ? NP C ml . .n o r . 4 r r Pi m o I- - r, c t- C IO

Ir r h m a * r n - ., A, N

a . . c- r . 1 ,

1

P-*n .rr1:., e M U n O e r v C C U - & r i 0 n e c ? w m ~ -

c n, y w c r. hhi.Tr-l.5rF.'1 U r 0 A..UO D- h MW C o - n Cl. C'f. * a 0 h*lr - D C P 4 .- .- nn. ti .- cr P. LI +Ir. - * r 10 F C ) Q D e < O h coh N Y I C . ~ * * .E n a - G n o f -

b - m n c - M h c - n ' = * Y I 0 0' n i h "l r. .- .-.C *L"., hi P C C W i n + v P n c o w r - + n r P ., w c . * -Fr.. a hl. C

C c o C C ' C C C O C . C . C ~ C ('C' C C c7r. C C C , C, C j C . C C>C r. C . + + * * + + + * + + + + * 4 + O O O C < > O ~ C O ~ ~ C Y ~ D h h C > t " R u r \ . y > i c - . , C C r h . c .z CJ P- a - C. L1 r. n, .. C C C., O. * Y - O r ' l . P . h . I r . r . - h C r r . 0 - . n c c ~ r ~ . - y l h m n ' n o c*v.m Y 1 C i D m c - I . r v m % - O ' L ' r . r P C C C - ~ ' i c n m r v r n ~ , ~ o ., rire ~ ~ w c r c ~ n m ~ - v 0 CW., * O r ? r . - - C \ Y.PiK,.. CC""-* . n C C ? r - h h f i . m r . - * r - , , , , , .

"7 C C .-mr., C. C I , N O r *,p- , Q . P C ' ~ . C . O ' P J L C P C - ~ O P . ~ - ~ y r ~ * ~ P n ~ ~ ~ > r n r ~ n ~ m c ' . - ~ r r . - o c C . ' m - 0 h i n h - n o - ~ . ~ - * r I h I n * m . r i n n + O 0 - p , .. ~ m r . ~ ? ~ c r ~ ~ i n h n Q F - C . ,- .-f i 'Fu.-mL- %nL?L-".C,-,.p* . . . . . . . . . . . . . . . n P c CJ ri P n C> 7 O c c i P r - ,

- - - - . - - - - - - - - - - - - - - - - - _ _ _ _ - - -- ---.. . .

. . ~ - . ..

1 " ~ ' .Y 4 ~ L P L P \c> .P 4-0 in .O ~ r - IL r- U, pi a' (> » P- O O CL c ? ~ > c I , - CJ O Y ~ I ~ ~ ~ I M N ~ ' M ~ rn C C CI C.\ L:. Cl C' C ? Ci C. C C' Ci C> C' C' C ' C ) C C O C C . C ' O C? v r r c r T c r c r r r c r c r r l l l l l l l l l l l l l l I I I I I I I I I I l 1 I I 1 I I I l l I I I I I f l I I I I O O O C - ~ ~ A O C . C ~ C I ~ C ~ ~ ~ ~ C O C \ ~ C ' ~ C ~ L ~ ~ L ' P ~ I I ~ O L ) ~ A D O C > L > ~ ~ C . ~ P ~ O ~ ~ 1x7 Cl? M M b R cx'j C C t b r t t o if fl .C 0 t- <?- ir. W C ' V b. rC 7 u ' r O. Q p C i r O P.'<> VImc) p. o > M p.1 V'-Y I>b nt a, or o. 4 C\ J -1 7 Ci \E? CI-. iP c i ,I .T r r u 7 ,- .C O <> -3 r" r-. n~ a r c r . 1 ci C v r- O. u> ni a M 0 r q t- M r- 0 n . I\ @ in n~ d a n' \I, -1 .J in r- J C. P- i r t n O ' r ta' r (\, u3 ~7 O' VI tn .C Ln 0 c .41 r- r.'~ m n -O .C - b W m r \ i O f r v i C : ~ P - r 4 ~ 0 ' . ~ ) C l v r i i . ~ f ' - n ~ C ~ r P - t / r U C7\< fi \L o : P " O u 7 C 9 & b - 3 d O N r \ r i 0 * C N V I \ O ~ C P ~ ~ N N ~ & ~ O .U n . c ' r r n i < . ? n ~ r * i f - l ~ i ~ > . ~ - ? u ~ - ~ & n - m . j ~ " r . r ~ u \ ~ b m o . d r " i r \ < r - U' w LT a 4 m c c - n4 'r? u) O 1 p: LI\ CI 1'- -3 ~.'l C- b .C h Y c.-I O? ~1 ,- \O IL tn 4 I\ ci! O. C-? u 0'- N O. OC ul) VI b LI\ \<> n . ri C' P3 ni ni -r C r- r . < ir c m u- < 1 Cr. o . r ' r . r? W. r- \f CJ .E g d O cc ri r L' <> -3 L* SC F .I a' C. r \ l fP (7 r ~ - ~ n ~ m ~ n ~ n ~ n ~ ( - c . ~ i ~ i r ~ r - l ~ ~ ~ , ~ ~ ~ '7 o\r.-o.ir.r< v p , r n . o. .-, , c , c ~ . o ,sir- r, .-O cc n- i r p, - C . ni W I ~ \ q i o ar- ~ > r \ ~ c ~ j I ~ o. c - n r - ch M O-. . n o ) o .r> p. .- (1. r. ,- 0 ~7 P .t O: I" .O (-1 *F r cr 0: c a in C: nit u\ 4 c (r- r r 1, P- .CI -7 C* r- r" c i O. c .l U. C O C I u .T .t ~ ( I ' L ~ I ~n - rk P rlu\ LÎ> .-- + in -0 n! fi 0, 4 c-n r.- w b 1.- V> I,. c c.- nt -1 u> 4 <? a, 01 L'Y <J r- i d - u\ I \ , b g .r n : O - Y' b. q O C- v <> P? n: 7 Cr s' ( 5 4 0. IL- P- C. V ri P. P- P a <* C-. r e ir, .<' -1 -? u- r in r . u- O ' in rc r" C.1 F O c - 'L? P. \II Ir C Fn - M O. <: - \j ir 4 '0 b ~3 C C' u r -3 (-.' - -0 nt .t 1 ) . P . f i fi- .O II\ 9 m Y ,- (13 PT ni ~7 CI- c ri: O ' P ni G ip rd* m II- O ,- c') rc P? r\l .j u\ .t (I (C .t ( 1 r- < .O r q <‘ ( > u a m b 10 c i , S- lr ln ti .4 n~ g n~ CF PC) U' r CI\. ni (3. .O CL. b -0 CS O: r,' in (y .r L< C- -1 1:' b cl' ni I'> in ,- o ifr r: c > in t n LA .t , 17 ID r- 4 g r ' j C' C; \c: 41 O' C. C? O" ne pc P" (N r .n r -T -0 P. r Y d P ' r rr 4 u T \ ' 4: C\: tT\ ni r PC 4 I'J -9 CF ni cr IC: t- 117 O r M 0 n. c W. I,> LA c N W . . . . . . . * . . * . . . * . . . . . . . . . . . . . . . * . . . * e . * * * m * * * * r > r r r C - c 3 C- 5 c r c-8 ( i 1: + C ' c - c c <-1 ( 1 c - c 1 r.: c . (-. c ) C. : C' (.-. r=-a c., < ' - c:.- c > L-I r.- C-' C' <: r.1 < . r.1 C-- CI I" r.' 11, c \

1 1 1 1 1 l 1 l 1 1 1 1 l 1 1 1 1 1

b ) Calcul intégral

(i) Calcul d'intégrales de fonction suffisamment différentiables

Les algorithmes des théorèmes 5.4 et 5.8 ont été appliqués pour le calcul de

l'intégrale

On trouvera, dans [4, 291, des algorithmes plus performants. Mais ceux que

nous avons proposés au chapitre 5 ont un double intérêt : ils donnent des suites

aternativement croissantes et décroissantes d'une étape à la suivante, ce qui permet

un encadrmeent de la valeur de l'intégrale ; de plus ces algorithmes nécessitent

beaucoup moins d'évaluations de fonctions.

(ii) Calcul d'intégrales singulières.

Pour certains types d'intégrales singulières, KAHANER [18] propose l'appli-

cation de I'E-algorihtme à la suite (Sn) définie au chap. 5, paragraphe 2, avec h , - - F. b - a Considérons l'intégrale

avec f(0) = f(1) = O.

Nous avons vu au chapitre 5, paragraphe 4 que l'on pouvait appliquer, pour

le calcul de 1, les algorithmes de LOGF;". Nous avons donc expérimenté les

algorihtmes des théorèmes 3.2 et 4.1.

La méthode de KAHANER est légèrement meilleure que le A2 modifié itéré

avec les mêmes remarques que précédemment sur les évaluations de fonctions et

l'encadrement de la valeur de l'intégrale. Nous avons aussi essayé l'algorithme du

thérème 5.10 pour l'intégrale

Dans tous les exemples, seules sont présentées les suites d'erreur pour les

transformations.

Nous avons démontré dans la première partie de cette thèse que l'&-algorithme

modifié, le A2 d'Aitken modifié itéré, le 82-algorithme itéré et le 8-algorithme

donnent les mêmes résultats (asymptotiquement) pour les suites de point fixe.

Le deuxième paragraphe de ce chapitre nous permet d'afffirmer que cette 1 propriété reste vraie pour les suites dont l'erreur est une fonction en ;.

CHAPITRE VI

DETERMINATION DE LA CLASSE D'UNE SUITE.

107

CHAPITRE VI

DETERMINATION DE LA CLASSE D'UNE SUITE.

O. Introduction

Les suites que nous avons étudiées jusqu'ici sont de deux types :

Mais nous avons montré, chapitre 1 théorème 1, qu'une suite de type (1)

vérifie (2). Dans la suite de ce chapitre, on considère seulement les suites de type

(2).

Le réel p est important à double titre : il détermine la classe de la suite et

intervient dans les algorihtmes d'accélération que nous avons proposés.

- Il est donc nécessaire de déterminer un procédé pour estimer p.

1. Détermination de la classe d'une suite

BJORSTAD, DAHLQUIST, GROSSE [8], ont démontré les théorèmes suiv-

ants :

108

Théorème 6.1 : Soit (Sn) une suite convergeant vers S et telle que

Alors la suite (Tn) telle que Tn = A S n s

O & V S n = Sn - Sn-', 1 converge vers --.

l+*

P

D e plus, T, = -1 + n-2(co + cln-l + c2n-2 + . . .). P

Théorème 6.2 : Soit (Sn) une suite réelle telle que :

Alors l'algorithme :

accélère la convergence de (x, (*-')) vers -'. Plus précisément, pour tout k E N , P

Remarques : Le théorème 6.1 donne la limite de la suite (Tn) tandis que le

théorème 6.2 accélère la convergence de cette suite.

En pratique le théorème 6.2 permet donc d'estimer p. Mais les résultats,

comme nous le verrons au chapitre suivant, ne sont pas toujours très bons.

Le théorème suivant propose un algorithme plus efficace.

Théorème 6.3 : Soit (Sn) une suite réelle telle que :

L 'algorit hrne :

I et pour k > 1 et n E N,

(k) 2 y ~ ) + ( 3 k - l ) r ~ ) 1 Z n = 3k+l 9

1 (k-i)) vers -- accélère la convergence de (x, P '

D e plus, pour t ou t k E N ,

Démonstration.

Similaire à celle du thérème 5.8.

Signalons maintenant un résultat intéressant : A.M. LITOVSKY, dans sa thèse, [22,

chapitre 21, a démontré le théorème suivant :

Théorème 6.4 : So i t (Sn) u n e suite convergente d o n t les erreurs en = Sn - S

vér i f ien t :

k en+l = en - anen, avec lim an # 0.

n++m

S o i t (Th) la sui te déf inie , pour t o u t n, par :

[ml désigne la partie entaèr'e de m.

Alors lim TL = 2-h où h = ( k - 1)-'. n-rw

En appliquant ce théorème à une suite

Conclusion

Nous disposons donc de quatre algorithmes pour l'estimation de p ; le plus

efficace est celui de théorème 6.3.

2. Résultats numériques

Nous avons appliqué les algorihtmes des théorèmes 6.2 et 6.3 à diverses séries.

En réalité nous n'avons testé que l'efficacité théorique de ces algorithmes. Les

suites imprimées sont les suites d'erreur.

m m * 0 0 0 I I I 0 0 0 m - Q U O N O O Q C - r n o m m N m N O N - h E? h C ' m r O N U m m - m m r N m O n 9 N 0 0 0 N r - e

a . . 0 3 0

u v m o c 0 I I I 0 0 0 O u m N U m NNI . e u - - m m N o m n v 4 ) m m c NVIPI u P'i O h r - O N m Q ?.NO UNI. h C P I - . -O . . . O C 0

9 9 * 0 0 0 I l l 0 0 . 3 m r N a m - I.NQ r.Nm u u m -Ln- u 0 0 N m Q O m o o a m N O * m U Q a 9 r 0 - m O N U m N r . . . O 0 0

- e h * m m c c m h n r O e n i P ycW,piQ

N N N O C 0 I I I n 0 o h O C m P" m- n w c - 0 . m N b - O N IO r ni .- m N m o Ne4 N W C N P c N N m C ) N O C r h m m U Q Y > P I N N . . . O D C i I I I

4 - - . - - r

. . . . O O C C

c c -

0 0 0 I I I 0 0 0 - m m + N O N m r N m u M Ln *- c m 0 o . m u N m VI

-.-.- O O O I l 1 0 0 0 Ç? D C Q r u W U D -60 a - m 0 0 0 m a n W O U I .um Q U U r m N U r N QI. <O

0 0 0 0 D O M * 0 0 - Q C C N Q 0 O I . h O O N I . 0 O I . Q O O N C, C 0 I . U O D N U o c - a O e N m

- N Q m V I N M U U O *--O DY>.- m m - m c c Nlnr. N PI r PI-b- O VI u o m m N r m . - m u a m .- . - C C

n * * 0 0 0 I I I O O O L n 0 0 0 - N N m o. n w n r m n m h N - N * u n m - r . r u n - - 0 0 r. m h

m . 0 9 9 O O O D

I I I 1 O O O C n o O h

n o n O N - Orna' m m * n O h

m * . - m e n - n * N N O N . . . 0 0 0

- m . o 0 n o u o n D O m

* ~ G U k A l A m m Q O h h C W 0 . o . Q O O O O O O O O O O O C O O O C O

0 o . o . P 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

O O C C

O O O O O O O O D D O n o O O O n I I I 1

. - u ~ o . ~ o r . ~ m m O ~ N C ~ ~ N O O O C

0 m m u * * * o o . 0 0 h . r C o I . m O U C O

L m O O o . o . n e m e - - r + . r L m m m ~ r N

o u - u h n m o ~ m h r , c n h c ,.c'*YI

Q o . m O u m m ~ n 0 0 . Q*b,.hN.- O * h m

m e ~ n - m n e m m ~ U M - - C C Q OOCiY\YI N * m O

m m e e t v i v m n m u D O E C - N ~ n U N O

m U N P . O V I r M U O N h O P m h C * D u m h

m m h N l n - m m O h O m r N m D r . N o n -

u m h h c s - n O r h w ~ ~ n r ~ m o . ~ O.OKC\* O h m h D G h E O r C m m u * N -

m O e N r.mvl*

o h m m o - m 0.mf.t 0 N N O

O r r - . - r r , N N N N N N (4.-0r.-nuuu- n u ',.Qmo U r U r m u N r e O m N Q N O m N

C C C C O 0 O C c O C 0 0 . . . . . . . . . . . . . . . . . m U M C

+ 1 1 1 1 1 1 1 1 1 1 1 1 . m . .

O n a O O O o O o O O C P 0 0 0 0 0 0 0 0 C > O C ) O O O O O C i , C O 0 0

n u - r - a m x O - u C m m 1 1 1 1 1 1 1 I I I m m + r O h C u O N r u O

u u u O O C I I 1 O O O m h r . t n m h i - O U h O PI Ci r e n m * O N nt & h *mu3 o. nt m o. m O m - a, O hl o NNÇ) t h 0 O' rf hi

m . .

0 . 2 0

P TB-

n + 5 s N J

n n Y u u ~ L n l n L n m L n C O O O O O O O O O O

UULn 0 0 0

' 1 1 I O 0 0 LhhN in O O

1:: z h O O m n n . -mm o e m 10 h O Io. m OCi iQ Q N .-un iN r. m l O h h im m YI O - O . . . .O O O

m u u 000 I I I 0 CI O unln r Q L n m e u Ln O YI * O r .--YI e n o c - r i * ? h h O*? - N N (CI

l u O 1C C n u lQ u 0. n m r- N m n . . . 0 0 0

YILnO 0 0 0 I I I 0 0 0 m 0 0 n m m U W O F U N N O * O r n o iffi- N h O O - r N Ln Ln Q t Q O O *? 0 - 6 m o n h n m N F O . . . 0 0 0

u u m oc0 l I I 0 0 0 n ( E 1 C * i O Q - h m h f. h CI Ci O u e n = O r Ln m O - D m - N - C IO% *.-Ln m o - O N N - 0 0 - r - n

B . .

0 0 0

O O O 0 0 0 I I I 0 0 0 - 0 . m m . - - m &, h r m r - N O - % O * v o n Fr.+ L n O N u * O? 00.- QO-O . - O N m o u m m * n N r . . . O 0 0

Ln Ln YI 0 0 0 I I I 0 0 0 a r c LnhN - a m Q N - *?a- 0 0 % - c c Ne"-

N e - r b m u m l n O L n r h m O & \ t h n N - . . . O O D

. -CC

O C C I I I 0 0 0 c o n a s c c m u * m.-.- * O - - C N *Cr . LnLn ln O O h N ln a> . -O- * Y \ - œ (O n un- O o. v\ h m * . . . O 0 0 1 1 1

rrh' O C 0 I I I 0 0 0 m e m - u O w o - r- m O m N O m m - 6 p i U "-a-- u C - r.0.I- O O l n u m u N Q L n U r - C O hNh - r Q . . . O C 0 I I I

N IV N 0 O 0 I l l 0 0 0 C - D Q u * Q N n % Q IO n n e f. NLn u r h * O @ r- O h, u C - C N * - a l 0 3 0 3 0 N YI h r. N F r - * L n . . . 0 0 O I I I

1

N N N 0 0 0 I I I 0 0 0 j r. m u * * ln c o u C M - m m 0 ' VI..-

œ m œ - 0 m u - D j n h r U m m I

D a r 0 0 0 + + 1 0 0 0 r N m O h ". r o m .- m O I n m m Q m O In N r O O N m o u o n * In N C Q C O 0 0 - C l m O D N -3 N r O

C C - - . -

O O O C O 1 1 1 1 1 0 0 0 0 0 - r m o u m m Q N O m m c y i o O h N h m mNmmI. m o . u m m m u N m O Q Q h O Q O N O h O N r - a m O h Q D r O O N Q O M U N W U - M h Y i N O

O N h m d m N r r

.-NNNN O O C O O

I I t l 1 n n n a n I c - N Q t r ~ n ~ h ~ ~

. . . 0 0 0 I I I

u u m m m O O O O O O O O O O O O O C O 1 1 1 1 1 1 1 1 1 1 a 0 0 0 0 0 0 0 0 0 U O U C N D O 0 D . O

0 l c m O D m m m C 0 0 0 0 0 C

Q Q Q Q 0 0 0 0

I I I I I I I 0 0 0 0 0 0 0

1 1 1 1

m U 0 . r r L - N 0 0 0 0 r u m n

O h Q h 0 0 m O u N r D O r

0 r D . m

. -QU0- -nPrO r r r Q

W D r % N Q m u -i C c

N O r 6 - r M O N h Q

m O * Q N Q O m < O o m u u m

m r o m

N N I n N Q N - n @ I c Q Q r U m ( D h h u

m r u -

m m m D m m m N r r m

Q r n D u V N m m Q N r

h U o O U O D h r N Q Q O

D m Q N r C I c m m 0 N h

U N m Q O Q m O Q Q N

r N I c N r Q r N N . - ~ r h h r . . . . . . . . . . .

~ 0 0 0 0 0 0 0 I l I I I l

O O C C I I

O O o - r r r r r r - r N O O C O O O c o O O O O o + + + 1 1 1 1 1 I I I I I 0 0 0 0 0 P 0 0 0 0 0 0 0 n . - I ) ~ o m m c ~ a ~ - m N m N N h h Q m m C h O O U U r h N D D N C Q m M Q m r D r r u N m I n O Q u h a h N r Q Q m D P l N m m r r n ~ ~ u m m ~ ~ m m m ~ m h

ipr.r.hIc n o O O O C C 00

I I I 1 1 I I 0 0 0 0 0 0 0 O m C Q - ,,,mu ' s ;Z Q r n Q C h Ic- * ? o . - * O C F r U N I - O O O * aCOVImm P-N N N U O C Q 0-U Q u h m r in i r Q 0 . 6 W r ICCU M J m h T ) 1 6 C I c m Q D m i D D u m m m m Q C u m * c P C C e mr.*mr E'h hULnrnC.l P m - h m - - .-N

u u m m V i . Q * O O O O O C O I l I I I I I 0 0 0 0 0 0 0 OVIN-^

a a a C O D I I I 0 0 0 0.00 nj u h u m h m n' U h * m c - a uuc-

I I I I I I a m 0 a n o N h a U r - I - O a C h a m P ? N * f i l c - h ( C h * - i O U c - c - m a - P N N V I N O P - m r . 9 m e c P c - u r c m a I D 0 o n u m c - u O - N h W P I I C O L n C e N c - h m ~ N r r m U G C ~ e O N r M m b r r C N N m NmOc.."-. . . . . . . P O O O C ' C I I I I

r m a 00-0 . u m c - u - h O W D m m - r b - O; - C O Q N h a ' . 3 N - . . . 000

. . . . . . . C I C O C C F C I I I I I I

u u m m m a a e e a h h r = m - D L c O c O O O O O O C O C O C O L C O C C r r c r I l I I I I I I I I I I I I I I I I I I 1

0 C 0 0 O O O O 0 C b C O n m 0 0 O n a n m u v a - ~ U O - U - - h r m * D r . m < n m m o m m - - f f - m m . - c w m

,ql E N O O m m h r m Q O O N O m U C rr. N r m O ~ m r m ~ h œ W c - m - f . . m h W D U C Q ~ N Q ~ ~ ~ C O u N a Q m N m m m m m D m O h m h C e Q O O m N m - " - m . - P " O

V L ' D N . -w .c . - c m - m

F e m m m a Q r U N O a h o c m c m m O I 0 . N q b P ? D ~ ~ ~ ~ . - N O C - f f m P - U P - m D O C C I ~ R

r m m e u h m ~ g m C c m h D & N .-m.,% ~ - o N c N ~ ~ ~ . M m m h c * O - o n a w u n n r

J w ~ ~ m m O C * O o m N u N N O h W r - ? N C C ' ~ N b . - - . . . . . . . m . .

0 0 0 0 0 0 0 0 0 0 ~ c o o ~ ~ o occ-c). I l I I I I I 1 4

m m 0. C C C I l l o n o m c 0- u n - ,.ch. h-"-

I I I 1 n e a n ~ c n m m a - u rT m m u *,.- ,(PD o . m m 0 m r l . 9 - = c e

h N m m M N

","c; P- r 0-

h * C 0. u r. U C C - N n , n u o - m e c " m F - . . . C O O

1

u u m m m ~ O a Q I O O O O O O O O O O C

> m o O O . U N - r r t o - . - & U N . . . . n t 0 0 I I I

C - - - - r . - N N N N N N O o n O C O O O O C O n c + 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 a a 0 0 n 0 cl f . -O-.-mNNOUo.Q f . h n m C N N W h m N r W U L - C W N U r h N - Q W W U M W h . . Q m N N Q N O U - e o m e U r U m Q n m m O N U n h m m O N u r o . 0 % h C P C m N u m N n O Q N o - O U o . o m m C n - U h N n f . - Q Q e u U C n m C W + O . N F l C U U P ) Q W m M 0 m Q O h Q m N b Q W 09 o o . u n 0 U o > r h n O m N O O U ~ N O W W - ~ O W N N P U Q D r n r m W N Q

/ 0 m 0 P r m N O W c l U Q D i - m u n ~ - c e c e m ~ n . . . . . . . . . . . . .

0 0 C 0 C 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1

P in-

+

U m m 0 0 0 I I I O 0 0 r. u U -4 N D e m œ U N D . W C * n m N

m Q 0 0 0 l I l 0 0 0 m u r . C D N e n n O m o n, h nhn O m N O m r i 0 - m U r r U h ". f . n m 0 9 O b u - m O N r - 9

, . . . C O 0 I I I

r k P 1 . . I O C 0

I I I

U m m N n U m e C P C C i n o 0 0 I I I I l I I I P D O o n e n o o . r N V . f . Q Q l f WO'O m r c c n u r - O m Ni.-OU . -UN T i @ . - N C n r M n C Q n N - 0 0 m n m Q M 0 n e .-f.r.mu

I I I a n 0 W h O - e ,.,

I I I 0 0 0

Q h )CI - V. C e h n m n

ü. 64 i. * O C Qf-Q c o r n N O N h D Q

r - N r W W Q h r r . n r O N U F E 9 m m - Q Q O C h N r N F "Y m -

Qr.N r C n . 2 - - 9 - u r . n m p " 5 O ' Q C E O P C h O m w w . n O h O C .-a-m N r m I O D MO.' - , - - N b

o n u a;cucn- Nuu r n h . r N U r f . m h - r m e

-6.1 O N U "-.OIT P - f h

u u u W . W . m a C C O C C C O

NW.LTLn rIcr.r- --O". D3.aMO ODD-a3 m m - & , N W U U OOVio - O U U P - W O h m V I N N P W D r P N

N N O C Y I @ - 6 ru.-,-- . . . .

0 c 0 c c - + + + 0 . 3 0

cmr. r. Vi l.') P i m a -r.C Ou3F N b 0 n m m .7 m u a u m . . . L' O 0 I I I

N Q Ü b O - O O 0QLP.O m m N O r Q O r O - 0 0 O U O O N m m œ r n m m

-nor.u . - o o ~ b O 0 Q Mr., -N M U N m r . r m 0 m 0 t . m N N C C . . . . 0 0 0 0

. . . . . O O O C O

. . . . . . . . . . . . . . . . . . . . . . . . . . . F 0 0 0 O O O O C 0 0 O O O D C i C C O * P O C O c 3 C " O I l 1 1 1 1 1 I I I

C C C N Y , m m u . - . , r - m m . , m m C C O O O C C C O O m O C C O o r

r m m a G C C O I l I I n o P o N O U Y , N9YIN h C h d

o r u . , o c - c ; h m U D h - v V\rnU.-c-C.- . - N m a . 7 - r . . . . . . . O C S O C O C O

I I I

. . . . . . . . . . . . . . . . O ~ O ~ ~ O P C ~ V C O O O C \ V ~

I l l l I I l l I I I

. 7 u . , u m m m ' O O O O C C C I I I I I I I

' 0 0 0 0 0 C O l . C ' h - u * u r

- . . . . . . . . . . . . . C 0 0 0 ~ 0 0 D n U 0 0 , g I I I 1 1 I l I I I I I 1

- - - r f . m., . . . . . . . C O C ' C P P L '

Nous disposons donc de quatre algorithmes pour l'estimation de p ; le plus

efficace est celui du théorème 6.3

Les méthodes de contrôle d'erreur proposées par BREZINSKI [4] permettent

en pratique de déterminer p.

REFERENCES

CONCLUSION

Pour une suit,e (2,) de point. fixe ou non, vérifiant

nous avons divers algorithmes capables d'en accélérer la convergence.

L'algorihtme le plus efficace est 1'Algorihtme 4. Mais pour les suites de point

fixe, cet algorithme exige plus que la connaissance de p. Il faudrait donc un moyen

complémentaire à l'estimation de p pour le rendre opérationnel dans ces cas.

Une constante de nos travaux est le fait que les Algorithmes 1, 2 et 3 et le

8-algorithme donnent les mêmes résultats pour toutes les familles de LOG que

nous avons considérées.

L'&-algorithme modifié et le O-algorithme n'ont pas été combinés car une telle

combinaison ne peut être que linéaire, donc moins efficace que l'Algorithme 4 (p.

39).

REFERENCES

[Il A.C. AITKEN, On Bernouilli's Numerical Solution of Algebraic Equations,

Proc., Roy., Soc., Edinburgh, 46 (1926), 289-305.

[2] M. BELLALI J , A Simultaneous Process for Convergence Acceleration and

Error Control,

[3] M.D. BENCHIBOUN, Etude de Certaines Généralisations du Procédés

d'Accélération de la Convergence, Thèse de 3ème cycle, Université des Sci-

ences et Techniques de Lille (1987).

[4] C. BREZINSKI, Accélération de la Convergence en Analyse Numérique,

Lecture Notes Math. 584, Springer-Verlag, Berlin (1977).

[5] C. BREZINSKI, Accélération de Suites à Convergence Logarithmique, C .R.

Acad. Sc. Paris, 273 A (1971) 727-730.

[6] C. BREZINSKI, Error Control in Convergence Acceleration Processes, IMA

J . Numer. Anal. 3 (1983) 65-80.

[7] C. BREZINSKI, A. General Extrapolation Algorithm, Numer. Math., 35

(1980),

[8] P. BJORSTAD, G. DAHLQUIST, E. GROSSE, Extrapolation of Asymptotic

Expansions by a Modified AITKEN 6'-Formula, BIT, 21 (1981), 56-65.

[9] L. COMTET, Analyse Combinatoire, Tome 1, Collection SVP, P.U.F. (1970).

[IO] F. CORDELLIER, Caractérisation des Suites que la Première Etape du 8-

Algorithme Transforme en Suites Constantes, C.R. Acad. Sci. Paris, 284 A

(1977) 389-392.

[il] P.J. DAVIS, P ; RABINOWITZ, Numerical Integration, Blaisdell, Wattharn

(1967).

[12] N.G. DE BRUIJN, Asymptotic Methods in Analysis, Dover, New-York (1981).

1131 J.P. DELAHAYE, B. GEFtMAIN-BONNE, The Set of Logarithmically Con-

vergent Sequences Cannot Be Accelerated, SIAM J. Numer. Anal. 19 (4)

(1982) 840-844.

[14] J . DIEUDONNE, Calcul Infinitésimal, Herman, Paris (1968).

[15] J.E. DRUMMOND, Sumrning a Comrnon Type of Slowly Convergent Series

of Positive Terms, J. Austral. Math. Soc. Ser. B., 19 (1976)) 416-421.

[16] T. HAVIE, Generalized Neville Type Extrapolation Schemes, BIT, 19 (1979)

204-213.

1171 D.C. JOYCE, Survey of Extrapolation Processes in Nuemrical Analysis, SIAM

Rev., 13 (4) (1971), 435-488.

[18] D.K. KAHANER, Numerical Quadrature by the &-algorithIn, Math. Comp.,

26 (119) (1972) 689-693.

[19] C. KOWALEWSKI, Possibilités d'Accélération de la Convergence logarit h-

mique, Thèse Université des Sciences et Techniques de Lille (1981).

[20] D. LEVIN, Development of Non-Linear Transformationss for Improving Con-

vergence of Sequences, Intern. J . Computer Math., B3 (1973) 371-388.

[21] D. LEVIN, A. SIDI, Two New Classes of Nonlinear Transformations for

Accelerating the Convergence of Infinite Integrals and Series, Appl. Math.

Comput. 9 (1981) 175-215.

[22] A.M. LITOVSKY, Accélération de la Convergence des Ensembles Synchro-

nisables, Thèse, Université des Sciences et Techniques de Lille (1989).

[23] S. LUBKIN, A Method for Sumrning Infinite Series, J . Res. Nat. Bur.

Standards, 48 (1952), 228-254.

[24] J.N. LYNESS, B.14'. NINHAM, Numerical Quadrature and Asymptotic Ex-

pansions, Math. Comput ., 21 (98) (1967) 162-178.

[25] A.C. MATOS, Construction de Méthodes d'Extrapolations à Partir de

Développements Asymptotiques, Thèse, Université des Sciences et Techniques

de Lille (1989).

[26] N. OSADA, A Convergence Acceleration Method for some Logarithmically

Convergent Sequences, SIAM J. Numer. Anal., 27 (1) (1990) 178-189.

[27] J. RIORDAN, An Introduction to Combinatorial Analysis, John Wiley, New

York (1958).

[28] P. SABLONNIERE, Convergence Accélération of Logarithmic Fixed Point

Sequence, J . of Comp. and Applied Math., 19 (1987) 55-60.

[29] H. SADOK, Accélération de la Convergence de Suites par Utilisation des

Transformations Composites, Thèse de 3ème cycle, Université des Sciences et

Techniques de Lille (1986).

[30] K. SATO, On Acceleration Procedures of some Slowly Convergent Infinite

Summations, J . of Information Processing, 4 (3) (1981), 152-154.

[31] G .A. SEDOGBO , Convergent Acceleration of some Logarithmic Sequences,

J. of Comp. and Applied Math., (1990) 32 (1990) 253-260.

[32] G .A. SEDOGBO, Convergent Accelerat ion of some Logari thmic Sequences,

J. of Comp. and Applied Math., AN0 221, Université de Lille 1, (1990).

[331 D.A. SMITH, W.F. FORD, Acceleration of Linear and Logarithmic Conver-

gence, SIAM J. Numer. Anal., 16 (2) (1979) 223-240.

[34] J. WIMP, Sequence Transformation and Their Applications, Academic Press,

New York (1981).

[35] P. WYNR, On a Procusteam Technique for the Numerical Tkansformation

of Slowly Convergent Sequences and Series, Proc. Cambridge Phil. Soc. 52

(1956) 663-671.

[36] P. MiYNN, On a Device for Computing the e,(S,) Transformation, MTAC,

10 (1956), 91-96.

ACCELERATION DE LA CONVERGENCE DE CERTAINS SOUS-ENSEMBLE DE SUITES LOGARITHMIQUES.

Soit LOG l'ensemble des suites à convergence logarithmique. Il ne peut exister

un algorithme capable d'accélérer la convergence de toutes les suites de LOG. Nous

définissons des sous-ensembles de LOG et proposons divers algorithmes qui, non

seulement accélèrent la convergence des suites considérées, mais surtout estiment

l'erreur.

Nous présentons aussi des algorithmes permettant de déterminer la classe

d'une suite appartenant à l'un de ces sous-ensembles, afin de lui appliquer des

algori t hmes adaptés.

Une étude numérique détaillée illustre nos algorithmes qui s'appliquent aussi

à divers problèmes d'Analyse Numérique : sommations de séries, calcul intégral,

intégrations d'équations différentielles, problèmes aux limites.

MOTS-CLES

Documents

LABORATOIRE D'ANALYSE NUMERIQUE ET D'OPflMISAïiON …