On the solution of systems of equations by the epsilon algorithm of Wynn

Gekeler, E.

doi:10.1090/S0025-5718-1972-0314226-X

On the solution of systems of equations by the epsilon algorithm of Wynn
HTML articles powered by AMS MathViewer

by E. Gekeler PDF

Math. Comp. 26 (1972), 427-436 Request permission

Abstract:

The $\epsilon$-algorithm has been proposed by Wynn on a number of occasions as a convergence acceleration device for vector sequences; however, little is known concerning its effect upon systems of equations. In this paper, we prove that the algorithm applied to the Picard sequence ${{\text {x}}_{i + 1}} = F({{\text {x}}_i})$ of an analytic function $F:{{\text {R}}^n} \supset D \to {{\text {R}}^n}$ provides a quadratically convergent iterative method; furthermore, no differentiation of $F$ is needed. Some examples illustrate the numerical performance of this method and show that convergence can be obtained even when $F$ is not contractive near the fixed point. A modification of the method is discussed and illustrated.

References

Proc. Roy. Soc. Edinburgh Sect. A

Claude Brezinski, Application de l’$\varepsilon$-algorithme à la résolution des systèmes non linéaires, C. R. Acad. Sci. Paris Sér. A-B 271 (1970), A1174–A1177 (French). MR 272165
J. Dieudonné, Foundations of modern analysis, Pure and Applied Mathematics, Vol. X, Academic Press, New York-London, 1960. MR 0120319
E. Gekeler, Über den $\varepsilon$-Algorithmus von Wynn, Z. Angew. Math. Mech. 51 (1971), T53–T54 (German). MR 285147

On Some Conjectures of P. Wynn Concerning the $\epsilon$-Algorithm

J. Reine Angew. Math.

A Fundamental Result in the Theory of the $\epsilon$-Algorithm

Bull. Amer. Math. Soc.

R. Penrose, A generalized inverse for matrices, Proc. Cambridge Philos. Soc. 51 (1955), 406–413. MR 69793
L. Duane Pyle, A generalized inverse $\varepsilon$-algorithm for constructing intersection projection matrices, with applications, Numer. Math. 10 (1967), 86–102. MR 219213, DOI 10.1007/BF02165164
R. J. Schmidt, On the numerical solution of linear simultaneous equations by an iterative method, Philos. Mag. (7) 32 (1941), 369–383. MR 6231
Daniel Shanks, Non-linear transformations of divergent and slowly convergent sequences, J. Math. and Phys. 34 (1955), 1–42. MR 68901, DOI 10.1002/sapm19553411
P. Wynn, On a device for computing the $e_m(S_n)$ tranformation, Math. Tables Aids Comput. 10 (1956), 91–96. MR 84056, DOI 10.1090/S0025-5718-1956-0084056-6
P. Wynn, On a procrustean technique for the numerical transformation of slowly convergent sequences and series, Proc. Cambridge Philos. Soc. 52 (1956), 663–671. MR 81979
P. Wynn, The rational approximation of functions which are formally defined by a power series expansion, Math. Comput. 14 (1960), 147–186. MR 0116457, DOI 10.1090/S0025-5718-1960-0116457-2
P. Wynn, On repeated application of the $\varepsilon$-algorithm, Chiffres 4 (1961), 19–22. MR 149145
P. Wynn, The numerical transformation of slowly convergent series by methods of comparison. I, Chiffres 4 (1961), 177–210. MR 162350
P. Wynn, Acceleration techniques for iterated vector and matrix problems, Math. Comp. 16 (1962), 301–322. MR 145647, DOI 10.1090/S0025-5718-1962-0145647-X
P. Wynn, On a connection between two techniques for the numerical transformation of slowly convergent series, Nederl. Akad. Wetensch. Proc. Ser. A 65 = Indag. Math. 24 (1962), 149–154. MR 0139256
P. Wynn, Singular rules for certain non-linear algorithms, Nordisk Tidskr. Informationsbehandling (BIT) 3 (1963), 175–195. MR 166946, DOI 10.1007/bf01939985
P. Wynn, Continued fractions whose coefficients obey a noncommutative law of multiplication, Arch. Rational Mech. Anal. 12 (1963), 273–312. MR 145231, DOI 10.1007/BF00281229
P. Wynn, General purpose vector epsilon algorithm ALGOL procedures, Numer. Math. 6 (1964), 22–36. MR 166947, DOI 10.1007/BF01386050

Upon a Conjecture Concerning a Method for Solving Linear Equations, and Certain Other Matters

P. Wynn, Vector continued fractions, Linear Algebra Appl. 1 (1968), 357–395. MR 231848, DOI 10.1016/0024-3795(68)90015-3