Rootfinding by fitting rational functions
Author:
F. M. Larkin
Journal:
Math. Comp. 35 (1980), 803816
MSC:
Primary 65H05
MathSciNet review:
572858
Fulltext PDF Free Access
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. 5478.
 [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 (31 #4173)
 [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
(35 #1205)
 [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
(51 #9471)
 [5]
F.
M. Larkin, Some techniques for rational interpolation, Comput.
J. 10 (1967), 178–187. MR 0215493
(35 #6334)
 [6]
F. M. LARKIN, The Newton Series in Analytic Function Theory, Tech. Report 7972, 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 7974, 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 7975, Dept. of Computing and Information Science, Queen's University, Kingston, Ontario, 1979.
 [9]
L.
M. MilneThomson, The Calculus of Finite Differences,
Macmillan and Co., Ltd., London, 1951. MR 0043339
(13,245c)
 [10]
E. H. NEVILLE, "Iterative interpolation," J. Indian Math. Soc., v. 20, 1936, pp. 87120.
 [11]
A.
M. Ostrowski, Solution of equations and systems of equations,
Second edition. Pure and Applied Mathematics, Vol. 9, Academic Press, New
YorkLondon, 1966. MR 0216746
(35 #7575)
 [12]
Josef
Stoer, Über zwei Algorithmen zur Interpolation mit rationalen
Funktionen., Numer. Math. 3 (1961), 285–304
(German). MR
0146950 (26 #4469)
 [13]
Leonard
Tornheim, Convergence of multipoint iterative methods, J.
Assoc. Comput. Mach. 11 (1964), 210–220. MR 0165653
(29 #2933)
 [14]
J.
F. Traub, Iterative methods for the solution of equations,
PrenticeHall Series in Automatic Computation, PrenticeHall, Inc.,
Englewood Cliffs, N.J., 1964. MR 0169356
(29 #6607)
 [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
(18,478c)
 [16]
Peter
Wynn, Über einen InterpolationsAlgorithmus und gewisse andere
Formeln, die in der Theorie der Interpolation durch rationale Funktionen
bestehen, Numer. Math. 2 (1960), 151–182
(German). MR
0128597 (23 #B1636)
 [1]
 A. C. AITKEN, "On interpolation by proportional parts, without the use of differences," Proc. Roy. Soc. Edinburgh, v. 53, 1932, pp. 5478.
 [2]
 P. JARRATT & D. NUDDS, "The use of rational functions in the iterative, solution of equations on a digital computer," Comput. J., v. 8, 1965, pp. 6265. MR 0179936 (31:4173)
 [3]
 P. JARRATT, "A note on the asymptotic error constant of a certain method for solving equations," Comput. J., v. 9, 1967, pp. 408409. MR 0210312 (35:1205)
 [4]
 P. JARRATT, "A review of methods for solving nonlinear equations in one variable," in Numerical Methods for NonLinear Algebraic Equations (P. Rabinowitz, Ed.), Gordon and Breach, London, 1970. MR 0373271 (51:9471)
 [5]
 F. M. LARKIN, "Some techniques for rational interpolation," Comput. J., v. 10, 1967, pp. 178187. MR 0215493 (35:6334)
 [6]
 F. M. LARKIN, The Newton Series in Analytic Function Theory, Tech. Report 7972, 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 7974, 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 7975, Dept. of Computing and Information Science, Queen's University, Kingston, Ontario, 1979.
 [9]
 L. M. MILNETHOMSON, The Calculus of Finite Differences, Macmillan, London, 1965. MR 0043339 (13:245c)
 [10]
 E. H. NEVILLE, "Iterative interpolation," J. Indian Math. Soc., v. 20, 1936, pp. 87120.
 [11]
 AM. OSTROWSKI, Solution of Equations and Systems of Equations, Academic Press, New York, 1966. MR 0216746 (35:7575)
 [12]
 J. STOER, "Algorithmen zur Interpolation mit rationalen Funktionen," Numer. Math., v. 3, 1961, pp. 285304. MR 0146950 (26:4469)
 [13]
 L. TORNHEIM, "Convergence of multipoint iterative methods," J. ACM, v. 11, 1964, pp. 210220. MR 0165653 (29:2933)
 [14]
 J. F. TRAUB, Iterative Methods for the Solution of Equations, PrenticeHall, Englewood Cliffs, N. J., 1964. MR 0169356 (29:6607)
 [15]
 P. WYNN, "On a procrustean technique for the numerical transformation of slowly convergent sequences and series," Proc. Cambridge Philos. Soc., v. 52, 1958, pp. 663671. MR 0081979 (18:478c)
 [16]
 P. WYNN, "Über einen Interpolations Algorithmus and gewisse andere Formeln, die in der Theorie der Interpolation durch rationale Functionen bestehen," Numer. Math., v. 2, 1960, pp. 151182. MR 0128597 (23:B1636)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65H05
Retrieve articles in all journals
with MSC:
65H05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198005728582
PII:
S 00255718(1980)05728582
Article copyright:
© Copyright 1980
American Mathematical Society
