Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Author: E. Gekeler
Journal: Math. Comp. 26 (1972), 427-436
MSC: Primary 65B99
DOI: https://doi.org/10.1090/S0025-5718-1972-0314226-X
MathSciNet review: 0314226
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] A. C. Aitken, ``On Bernoulli's numerical solution of algebraic equations,'' Proc. Roy. Soc. Edinburgh Sect. A, v. 46, 1926, pp. 289-305.
  • [2] C. Brezinski, ``Application de 1'$ \epsilon$-algorithme à la résolution des systèmes non linéaires,'' C. R. Acad. Sci. Paris Sér. A-B, v. 271, 1970, pp. A1174-A1177. MR 42 #7046. MR 0272165 (42:7046)
  • [3] J. Dieudonné, Foundations of Modern Analysis, Pure and Appl. Math., vol. 10, Academic Press, New York-London, 1960. MR 22 #11074. MR 0120319 (22:11074)
  • [4] E. Gekeler, ``Über den $ \epsilon$-Algorithmus von Wynn,'' Z. Angew. Math. Mech. (To appear.) MR 0285147 (44:2370)
  • [5] T. N. E. Greville, On Some Conjectures of P. Wynn Concerning the $ \epsilon$-Algorithm, University of Wisconsin Math. Res. Center Report #877, 1968.
  • [6] C. G. J. Jacobi, ``Über die Darstellung einer Reihe gegebener Werte durch eine gebrochene rationale Funktion,'' J. Reine Angew. Math., v. 30, 1846, pp. 127-156.
  • [7] J. B. McLeod, A Fundamental Result in the Theory of the $ \epsilon$-Algorithm, University of Wisconsin Math. Res. Center Report #685, 1966.
  • [8] E. H. Moore, ``On the reciprocal of the general algebraic matrix,'' Bull. Amer. Math. Soc., v. 26, 1920, pp. 394-395. (Abstract.)
  • [9] R. Penrose, ``A generalized inverse for matrices,'' Proc. Cambridge Philos. Soc., v. 51, 1955, pp. 406-413. MR 16, 1082. MR 0069793 (16:1082a)
  • [10] L. D. Pyle, ``A generalized inverse $ \epsilon$-algorithm for constructing intersection projection matrices, with applications,'' Numer. Math., v. 10, 1967, pp. 86-102. MR 36 #2296. MR 0219213 (36:2296)
  • [11] R. J. Schmidt, ``On the numerical solution of linear simultaneous equations by an iterative method,'' Philos. Mag., v. (7) 32, 1941, pp. 369-383. MR 3, 276. MR 0006231 (3:276d)
  • [12] D. Shanks, ``Non-linear transformations of divergent and slowly convergent sequences,'' J. Mathematical Phys., v. 34, 1955, pp. 1-42. MR 16, 961. MR 0068901 (16:961e)
  • [13] P. Wynn, ``On a device for computing the $ {e_m}({S_n})$ transformation,'' MTAC, v. 10, 1956, pp. 91-96. MR 18, 801. MR 0084056 (18:801e)
  • [14] P. Wynn, ``On a procrustean technique for the numerical transformation of slowly convergent sequences and series,'' Proc., Cambridge Philos. Soc., v. 52, 1956, pp. 663-671. MR 18, 478. MR 0081979 (18:478c)
  • [15] P. Wynn, ``The rational approximation of functions which are formally defined by a power series expansion,'' Math. Comp., v. 14, 1960, pp. 147-186. MR 22 #7244. MR 0116457 (22:7244)
  • [16] P. Wynn, ``On repeated application of the $ \epsilon$-algorithm,'' Chiffres, v. 4, 1961, pp. 19-22. MR 26 #6639. MR 0149145 (26:6639)
  • [17] P. Wynn, ``A comparison between the numerical performances of the Euler transformation and the epsilon algorithm,'' Chiffres, v. 4, 1961, pp. 23-29. MR 0162350 (28:5549)
  • [18] P. Wynn, ``Acceleration techniques for iterated vector and matrix problems,'' Math. Comp., v. 16, 1962, pp. 301-322. MR 26 #3176. MR 0145647 (26:3176)
  • [19] P. Wynn, Acceleration Techniques in Numerical Analysis, With Particular Reference to Problems in One Independent Variable, Proc. IFIP Congress 1962, North-Holland, Amsterdam, 1963, pp. 149-156. MR 0139256 (25:2691)
  • [20] P. Wynn, ``Singular rules for certain non-linear algorithms,'' Nordisk Tidskr. Informationsbehandling, v. 3, 1963, pp. 175-195. MR 29 #4219. MR 0166946 (29:4219)
  • [21] P. Wynn, ``Continued fractions whose coefficients obey a non-commutative law of multiplication,'' Arch. Rational Mech. Anal., v. 12, 1963, pp. 273-312. MR 26 #2766. MR 0145231 (26:2766)
  • [22] P. Wynn, ``General purpose vector epsilon algorithm ALGOL procedures,'' Numer. Math., v. 6, 1964, pp. 22-36. MR 29 #4220. MR 0166947 (29:4220)
  • [23] P. Wynn, Upon a Conjecture Concerning a Method for Solving Linear Equations, and Certain Other Matters, University of Wisconsin, Math. Res. Center Report #626, 1966.
  • [24] P. Wynn, ``Vector continued fractions,'' Linear Algebra Appl., v. 1, 1968, pp. 357-395. MR 38 #176. MR 0231848 (38:176)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65B99

Retrieve articles in all journals with MSC: 65B99


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1972-0314226-X
Keywords: $ \epsilon $-algorithm, acceleration of the convergence of sequences, quadratic convergent iterative method without differentiation, solution of equations
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society