Kantorovich theorem

The Kantorovich theorem (Newton-Kantorovich theorem) is a mathematical statement on the semi-local convergence of Newton's method. It was first stated by Leonid Kantorovich in 1948^[1]^[2].

Newton's method constructs a sequence of points that under certain conditions will converge to a solution $x$ of an equation $f(x)=0$ or a vector solution of a system of equation $F(x)=0$ . The Kantorovich theorem gives conditions on the initial point of this sequence. If those conditions are satisfied then a solution exists close to the initial point and the sequence converges to that point^[1]Cite error: A <ref> tag is missing the closing </ref> (see the help page). if $t_{0}=0,\,t_{k+1}=t_{k}-{\tfrac {p(t_{k})}{p'(t_{k})}}$ , then

$\|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.$
The quadratic convergence is obtained from the error estimate^[3]
$\|\mathbf {x} _{n+1}-\mathbf {x} ^{*}\|\leq \theta ^{2^{n}}\|\mathbf {x} _{n+1}-\mathbf {x} _{n}\|\leq {\frac {\theta ^{2^{n}}}{2^{n}}}\|\mathbf {h} _{0}\|.$

Corollary

In 1986, Yamamoto proved that the error evaluations of the Newton method such as Doring(1969)、Ostrowski(1971, 1973)^[4]^[5]、Gragg-Tapia(1974)、Potra-Ptak(1980)^[6]、Miel(1981)^[7]、Potra(1984)^[8]can be derived from the Kantorovich theorem^[9].

Generalizations

There is a q-analog for the Kantorovich theorem^[10]^[11]. For other generalizations/variations, see Ortega-Rheinboldt(1970)^[12].

Notes

^ ^a ^b P. Deuflhard: Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms., Springer, Berlin 2004, ISBN 3-540-21099-7 (Springer Series in Computational Mathematics, Vol. 35)
^ Zeidler, E. (1985). Nonlinear Functional Analysis and its Applications: Part 1: Fixed-Point Theorems. Springer.
^ Gragg, W. B.; Tapia, R. A. (1974). "Optimal Error Bounds for the Newton-Kantorovich Theorem". SIAM Journal on Numerical Analysis. 11 (1): 10–13. doi:10.1137/0711002. JSTOR 2156425.
^ A. M. Ostrowski, “La method de Newton dans les espaces de Banach,” C. R. Acad. Sei. Paris, 27 (A) (1971), 1251–1253.
^ A. M. Ostrowski, Solution of Equations in Euclidean and Banach Spaces, Academic Press, New York, 1973.
^ F. A. Potra and V. Ptak, “Sharp error bounds for Newton’s process,” Numer. Math., 34 (1980), 63–72.
^ G. J. Miel, “An updated version of the Kantorovich theorem for Newton’s method,” Computing, 27 (1981), 237–244.
^ F. A. Potra, “On the a posteriori error estimates for Newton’s method,” Beiträge zur Numerische Mathematik, 12 (1984), 125–138.
^ Yamamoto, T. (1986). A method for finding sharp error bounds for Newton's method under the Kantorovich assumptions. Numerische Mathematik, 49(2-3), 203-220.
^ Rajkovic, P. M., Stankovic, M. S., & Marinkovic, S. D. (2003). On q-iterative methods for solving equations and systems. Novi Sad J. Math, 33(2), 127-137.
^ Rajković, P. M., Marinković, S. D., & Stanković, M. S. (2005). On q-Newton–Kantorovich method for solving systems of equations. Applied Mathematics and Computation, 168(2), 1432-1448.
^ Ortega, J. M., & Rheinboldt, W. C. (1970). Iterative solution of nonlinear equations in several variables. SIAM.

References

John H. Hubbard and Barbara Burke Hubbard: Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, Matrix Editions, ISBN 978-0-9715766-3-6 (preview of 3. edition and sample material including Kant.-thm.)

Literature

Kantorovich, L. (1948): Functional analysis and applied mathematics (russ.). UMN3, 6 (28), 89–185.
Kantorovich, L. W.; Akilov, G. P. (1964): Functional analysis in normed spaces.

[Deuflhard-1] P. Deuflhard: Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms., Springer, Berlin 2004, ISBN 3-540-21099-7 (Springer Series in Computational Mathematics, Vol. 35)

[Zeidler-2] Zeidler, E. (1985). Nonlinear Functional Analysis and its Applications: Part 1: Fixed-Point Theorems. Springer.

[3] Gragg, W. B.; Tapia, R. A. (1974). "Optimal Error Bounds for the Newton-Kantorovich Theorem". SIAM Journal on Numerical Analysis. 11 (1): 10–13. doi:10.1137/0711002. JSTOR 2156425.

[4] A. M. Ostrowski, “La method de Newton dans les espaces de Banach,” C. R. Acad. Sei. Paris, 27 (A) (1971), 1251–1253.

[5] A. M. Ostrowski, Solution of Equations in Euclidean and Banach Spaces, Academic Press, New York, 1973.

[6] F. A. Potra and V. Ptak, “Sharp error bounds for Newton’s process,” Numer. Math., 34 (1980), 63–72.

[7] G. J. Miel, “An updated version of the Kantorovich theorem for Newton’s method,” Computing, 27 (1981), 237–244.

[8] F. A. Potra, “On the a posteriori error estimates for Newton’s method,” Beiträge zur Numerische Mathematik, 12 (1984), 125–138.

[9] Yamamoto, T. (1986). A method for finding sharp error bounds for Newton's method under the Kantorovich assumptions. Numerische Mathematik, 49(2-3), 203-220.

[10] Rajkovic, P. M., Stankovic, M. S., & Marinkovic, S. D. (2003). On q-iterative methods for solving equations and systems. Novi Sad J. Math, 33(2), 127-137.

[11] Rajković, P. M., Marinković, S. D., & Stanković, M. S. (2005). On q-Newton–Kantorovich method for solving systems of equations. Applied Mathematics and Computation, 168(2), 1432-1448.

[12] Ortega, J. M., & Rheinboldt, W. C. (1970). Iterative solution of nonlinear equations in several variables. SIAM.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]