El teorema de Kantorovich , o teorema de Newton-Kantorovich, es un enunciado matemático sobre la convergencia semilocal del método de Newton . Fue establecido por primera vez por Leonid Kantorovich en 1948. [1] [2] Es similar a la forma del teorema del punto fijo de Banach , aunque establece la existencia y unicidad de un cero en lugar de un punto fijo . [3]
El método de Newton construye una secuencia de puntos que bajo ciertas condiciones convergerán en una solución. de una ecuación o una solución vectorial de un sistema de ecuaciones . El teorema de Kantorovich da condiciones en el punto inicial de esta secuencia. Si se satisfacen esas condiciones, existe una solución cerca del punto inicial y la secuencia converge hacia ese punto. [1] [2]
Supuestos
Dejar ser un subconjunto abierto y una función diferenciable con un jacobiano que es localmente Lipschitz continuo (por ejemplo, sies dos veces diferenciable). Es decir, se supone que para cualquier subconjunto abierto existe una constante tal que para cualquier
sostiene. La norma de la izquierda es una norma de operador que es compatible con la norma vectorial de la derecha. Esta desigualdad se puede reescribir para usar solo la norma vectorial. Entonces para cualquier vector la desigualdad
debe aguantar.
Ahora elige cualquier punto inicial . Asumir que es invertible y construye el paso de Newton
La siguiente suposición es que no solo el siguiente punto pero toda la pelota está contenido dentro del conjunto . Dejar sea la constante de Lipschitz para el jacobiano sobre esta bola.
Como última preparación, construya de forma recursiva, siempre que sea posible, las secuencias , , de acuerdo a
Declaración
Ahora si luego
- una solución de existe dentro de la bola cerrada y
- la iteración de Newton que comienza en converge a con al menos orden lineal de convergencia.
Una declaración que es más precisa pero un poco más difícil de probar utiliza las raíces del polinomio cuadrático
- ,
y su proporción
Luego
- una solución existe dentro de la bola cerrada
- es único dentro de la bola más grande
- y la convergencia a la solución de está dominado por la convergencia de la iteración de Newton del polinomio cuadrático hacia su raíz más pequeña , [4] si, luego
- La convergencia cuadrática se obtiene de la estimación del error [5]
Corolario
En 1986, Yamamoto demostró que las evaluaciones de errores del método de Newton como Doring (1969), Ostrowski (1971, 1973), [6] [7] Gragg-Tapia (1974), Potra-Ptak (1980), [8] Miel (1981), [9] Potra (1984), [10] puede derivarse del teorema de Kantorovich. [11]
Generalizaciones
Hay un q -análogo para el teorema de Kantorovich. [12] [13] Para otras generalizaciones / variaciones, ver Ortega y Rheinboldt (1970). [14]
Aplicaciones
Oishi y Tanabe afirmaron que el teorema de Kantorovich se puede aplicar para obtener soluciones confiables de programación lineal . [15]
Referencias
- ↑ a b Deuflhard, P. (2004). Métodos de Newton para problemas no lineales. Invarianza afín y algoritmos adaptativos . Serie Springer en Matemática Computacional. Vol. 35. Berlín: Springer. ISBN 3-540-21099-7.
|volume=
tiene texto extra ( ayuda ) - ^ a b Zeidler, E. (1985). Análisis funcional no lineal y sus aplicaciones: Parte 1: Teoremas de punto fijo . Nueva York: Springer. ISBN 0-387-96499-1.
- ^ Dennis, John E .; Schnabel, Robert B. (1983). "Los teoremas de Kantorovich y el mapeo contractual". Métodos numéricos para optimización no restringida y ecuaciones no lineales . Acantilados de Englewood: Prentice-Hall. págs. 92–94. ISBN 0-13-627216-9.
- ^ Ortega, JM (1968). "El teorema de Newton-Kantorovich". Amer. Matemáticas. Mensual . 75 (6): 658–660. doi : 10.2307 / 2313800 . JSTOR 2313800 .
- ^ Gragg, WB; Tapia, RA (1974). "Límites de error óptimos para el teorema de Newton-Kantorovich". Revista SIAM de Análisis Numérico . 11 (1): 10–13. Código bibliográfico : 1974SJNA ... 11 ... 10G . doi : 10.1137 / 0711002 . JSTOR 2156425 .
- ^ Ostrowski, AM (1971). "La method de Newton dans les espaces de Banach". CR Acad. Sci. París . 27 (A): 1251-1253.
- ^ Ostrowski, AM (1973). Solución de ecuaciones en espacios euclidianos y de Banach . Nueva York: Academic Press. ISBN 0-12-530260-6.
- ^ Potra, FA; Ptak, V. (1980). "Límites de error agudos para el proceso de Newton". Numer. Matemáticas . 34 : 63–72. doi : 10.1007 / BF01463998 .
- ^ Miel, GJ (1981). "Una versión actualizada del teorema de Kantorovich para el método de Newton". Computación . 27 (3): 237–244. doi : 10.1007 / BF02237981 .
- ^ Potra, FA (1984). "Sobre las estimaciones de error a posteriori para el método de Newton". Beiträge zur Numerische Mathematik . 12 : 125-138.
- ^ Yamamoto, T. (1986). "Un método para encontrar límites de error agudos para el método de Newton bajo los supuestos de Kantorovich". Numerische Mathematik . 49 (2-3): 203-220. doi : 10.1007 / BF01389624 .
- ^ Rajkovic, PM; Stankovic, MS; Marinkovic, SD (2003). "Sobre métodos q-iterativos para la resolución de ecuaciones y sistemas". Novi Sad J. Math . 33 (2): 127-137.
- ^ Rajković, PM; Marinković, SD; Stanković, MS (2005). "Sobre el método q-Newton-Kantorovich para resolver sistemas de ecuaciones". Matemática Aplicada y Computación . 168 (2): 1432–1448. doi : 10.1016 / j.amc.2004.10.035 .
- ^ Ortega, JM; Rheinboldt, WC (1970). Solución iterativa de ecuaciones no lineales en varias variables . SIAM. OCLC 95021 .
- ^ Oishi, S .; Tanabe, K. (2009). "Inclusión numérica de punto óptimo para programación lineal" . Cartas JSIAM . 1 : 5–8. doi : 10.14495 / jsiaml.1.5 .
Otras lecturas
- John H. Hubbard y Barbara Burke Hubbard: cálculo vectorial, álgebra lineal y formas diferenciales: un enfoque unificado , ediciones de matriz, ISBN 978-0-9715766-3-6 ( vista previa de 3. edición y material de muestra que incluye Kant.-thm. )
- Yamamoto, Tetsuro (2001). "Desarrollos históricos en el análisis de convergencia para los métodos de Newton y similares a Newton". En Brezinski, C .; Wuytack, L. (eds.). Análisis numérico: desarrollos históricos en el siglo XX . Holanda Septentrional. págs. 241-263. ISBN 0-444-50617-9.