×

Aitken’s and Steffensen’s accelerations in several variables. (English) Zbl 0712.65037

Aitken’s acceleration of scalar sequences extends to sequences of vectors that behave asymptotically as iterations of a linear transformation. However, the minimal and characteristic polynomials of that transformation must coincide (but the initial sequence of vectors need not converge) for a numerically stable convergence of Aitken’s acceleration to occur. Similar results hold for Steffensen’s acceleration of the iterations of a function of several variables.
First, the iterated function need not be a contracting map in any neighbourhood of its fixed point. Instead, the second partial derivatives need only remain bounded in such a neighbourhood for Steffensen’s acceleration to converge quadratically, even if ordinary iterations diverge. Second, at the fixed point the minimal and characteristic polynomials of the Jacobian matrix must coincide to ensure a numerically stable convergence. By generalizing the work that Noda did on the subject between 1981 and 1986, the results presented here explain the numerical observations reported by Henrici in 1964 and 1982.
Reviewer: Y.Nievergelt

MSC:

65H10 Numerical computation of solutions to systems of equations
65B05 Extrapolation to the limit, deferred corrections
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] Fleming, W.: Functions of Several Variables, corrected 2nd printing. Berlin Heidelberg New York: Springer 1982
[2] Gantmacher, F.R.: Matrizentheorie. Berlin Heidelberg New York: Springer 1986
[3] Golub, G.H., Van Loan, C.F.: Matrix Computations 2nd ed. Baltimore London: The Johns Hopkins University Press 1989 · Zbl 0733.65016
[4] Henrici, P.: Elements of Numerical Analysis. New York: Wiley 1964 · Zbl 0149.10901
[5] Henrici, P.: Essentials of Numerical Analysis With Pocket Calculator Demonstrations. New York: Wiley 1982 · Zbl 0584.65001
[6] Henrici, P.: Solutions Manual Essentials of Numerical Analysis With Pocket Calculator Demonstrations. New York: Wiley 1982 · Zbl 0584.65001
[7] Kahan, W.M.: Numerical Linear Algebra. Can. Math. Bull.9, 757-801 (1966) · Zbl 0236.65025
[8] Noda, T.: The Aitken-Steffensen Formula for Systems of Non-linear Equations. S?gaku33, 369-372 (1981)
[9] Noda, T.: The Steffensen Iteration Method for Systems of Non-linear Equations. Proc. Japan Acad. Series A60, 18-21 (1984) · Zbl 0575.65041
[10] Noda, T.: The Aitken-Steffensen Formula for Systems of Non-linear Equations, II. S?gaku38, 83-85 (1986)
[11] Noda, T.: The Aitken-Steffensen Formula for Systems of Non-linear Equations, III. Proc. Japan. Acad. Series A62, 174-177 (1986) · Zbl 0595.65054
[12] Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis, corrected 2nd printing. Berlin Heidelberg New York: Springer 1983
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.