Root-finding by fitting rational functions

Author:
F. M. Larkin

Journal:
Math. Comp. **35** (1980), 803-816

MSC:
Primary 65H05

DOI:
https://doi.org/10.1090/S0025-5718-1980-0572858-2

MathSciNet review:
572858

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A tabular, recursive method is presented for the computation of a sequence of abscissae designed to converge to a simple zero of an analytic function. The key to the method is an efficient means for evaluating the zeros of a sequence of rational functions, having linear numerators, fitted to information previously computed.

Regional and asymptotic convergence properties of the method are described. Conditions sufficient to ensure convergence are derived, and it is shown that asymptotically quadratic convergence can be achieved, at the cost of only a moderate amount of "overhead" computation.

**[1]**A. C. AITKEN, "On interpolation by proportional parts, without the use of differences,"*Proc. Roy. Soc. Edinburgh*, v. 53, 1932, pp. 54-78.**[2]**P. Jarratt and D. Nudds,*The use of rational functions in the iterative solution of equations on a digital computer*, Comput. J.**8**(1965), 62–65. MR**0179936**, https://doi.org/10.1093/comjnl/8.1.62**[3]**P. Jarratt,*A note on the asymptotic error constant of a certain method for solving equations*, Comput. J.**9**(1967), 408–409. MR**0210312**, https://doi.org/10.1093/comjnl/9.4.408**[4]**P. Jarratt,*A review of methods for solving nonlinear algebraic equations in one variable*, Numerical methods for nonlinear algebraic equations (Proc. Conf., Univ. Essex, Colchester, 1969) Gordon and Breach, London, 1970, pp. 1–26. MR**0373271****[5]**F. M. Larkin,*Some techniques for rational interpolation*, Comput. J.**10**(1967), 178–187. MR**0215493**, https://doi.org/10.1093/comjnl/10.2.178**[6]**F. M. LARKIN,*The Newton Series in Analytic Function Theory*, Tech. Report 79-72, Dept. of Computing and Information Science, Queen's University, Kingston, Ontario, 1979.**[7]**F. M. LARKIN,*On a Generalization of Aitken's*-*Process*, Tech. Report 79-74, Dept. of Computing and Information Science, Queen's University, Kingston, Ontario, 1979.**[8]**F. M. LARKIN,*On the Acceleration of Certain Sequences by Rational Interpolation*, Tech. Report 79-75, Dept. of Computing and Information Science, Queen's University, Kingston, Ontario, 1979.**[9]**L. M. Milne-Thomson,*The Calculus of Finite Differences*, Macmillan and Co., Ltd., London, 1951. MR**0043339****[10]**E. H. NEVILLE, "Iterative interpolation,"*J. Indian Math. Soc.*, v. 20, 1936, pp. 87-120.**[11]**A. M. Ostrowski,*Solution of equations and systems of equations*, Second edition. Pure and Applied Mathematics, Vol. 9, Academic Press, New York-London, 1966. MR**0216746****[12]**Josef Stoer,*Über zwei Algorithmen zur Interpolation mit rationalen Funktionen.*, Numer. Math.**3**(1961), 285–304 (German). MR**0146950**, https://doi.org/10.1007/BF01386030**[13]**Leonard Tornheim,*Convergence of multipoint iterative methods*, J. Assoc. Comput. Mach.**11**(1964), 210–220. MR**0165653**, https://doi.org/10.1145/321217.321224**[14]**J. F. Traub,*Iterative methods for the solution of equations*, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR**0169356****[15]**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**0081979****[16]**Peter Wynn,*Über einen Interpolations-Algorithmus und gewisse andere Formeln, die in der Theorie der Interpolation durch rationale Funktionen bestehen*, Numer. Math.**2**(1960), 151–182 (German). MR**0128597**, https://doi.org/10.1007/BF01386220

Retrieve articles in *Mathematics of Computation*
with MSC:
65H05

Retrieve articles in all journals with MSC: 65H05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1980-0572858-2

Article copyright:
© Copyright 1980
American Mathematical Society