teorema de Kantorovich

Sobre la convergencia del método de Newton

El teorema de Kantorovich , o teorema de Newton-Kantorovich, es un enunciado matemático sobre la convergencia semilocal del método de Newton . Fue declarado 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 a una solución de una ecuación o una solución vectorial de un sistema de ecuaciones . El teorema de Kantorovich da condiciones sobre el punto inicial de esta secuencia. Si esas condiciones se cumplen, entonces existe una solución cerca del punto inicial y la secuencia converge a ese punto. ^{[1] [2]} ${\displaystyle x}$ ${\displaystyle f(x)=0}$ ${\displaystyle F(x)=0}$

Suposiciones

Sea un subconjunto abierto y una función diferenciable con un jacobiano que sea localmente continuo de Lipschitz (por ejemplo, si es dos veces diferenciable). Es decir, se supone que para cualquier existe un subconjunto abierto tal que y existe una constante tal que para cualquier ${\displaystyle X\subset \mathbb {R} ^{n}}$ ${\displaystyle F:X\subset \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ ${\displaystyle F^{\prime }(\mathbf {x} )}$ ${\displaystyle F}$ ${\displaystyle x\in X}$ ${\displaystyle U\subset X}$ ${\displaystyle x\in U}$ ${\displaystyle L>0}$ ${\displaystyle \mathbf {x} ,\mathbf {y} \in U}$

${\displaystyle \|F'(\mathbf {x} )-F'(\mathbf {y} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|}$

sostiene. La norma de la izquierda es la norma del operador. En otras palabras, para cualquier vector la desigualdad ${\displaystyle \mathbf {v} \in \mathbb {R} ^{n}}$

${\displaystyle \|F'(\mathbf {x} )(\mathbf {v} )-F'(\mathbf {y} )(\mathbf {v} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|\,\|\mathbf {v} \|}$

debe aguantar.

Ahora elige cualquier punto inicial . Suponga que es invertible y construya el paso de Newton. ${\displaystyle \mathbf {x} _{0}\in X}$ ${\displaystyle F'(\mathbf {x} _{0})}$ ${\displaystyle \mathbf {h} _{0}=-F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0}).}$

La siguiente suposición es que no sólo el siguiente punto sino toda la bola está contenida dentro del conjunto . Sea la constante de Lipschitz para el jacobiano sobre esta bola (suponiendo que exista). ${\displaystyle \mathbf {x} _{1}=\mathbf {x} _{0}+\mathbf {h} _{0}}$ ${\displaystyle B(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}$ ${\displaystyle X}$ ${\displaystyle M}$

Como última preparación, construya recursivamente, siempre que sea posible, las secuencias , , según ${\displaystyle (\mathbf {x} _{k})_{k}}$ ${\displaystyle (\mathbf {h} _{k})_{k}}$ ${\displaystyle (\alpha _{k})_{k}}$

${\displaystyle {\begin{alignedat}{2}\mathbf {h} _{k}&=-F'(\mathbf {x} _{k})^{-1}F(\mathbf {x} _{k})\\[0.4em]\alpha _{k}&=M\,\|F'(\mathbf {x} _{k})^{-1}\|\,\|\mathbf {h} _{k}\|\\[0.4em]\mathbf {x} _{k+1}&=\mathbf {x} _{k}+\mathbf {h} _{k}.\end{alignedat}}}$

Declaración

ahora si entonces ${\displaystyle \alpha _{0}\leq {\tfrac {1}{2}}}$

1. existe una solución dentro de la bola cerrada y ${\displaystyle \mathbf {x} ^{*}}$ ${\displaystyle F(\mathbf {x} ^{*})=0}$ ${\displaystyle {\bar {B}}(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}$
2. la iteración de Newton que comienza en converge con al menos un orden de convergencia lineal. ${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle \mathbf {x} ^{*}}$

Una afirmación que es más precisa pero un poco más difícil de demostrar utiliza las raíces del polinomio cuadrático. ${\displaystyle t^{\ast }\leq t^{**}}$

${\displaystyle p(t)=\left({\tfrac {1}{2}}L\|F'(\mathbf {x} _{0})^{-1}\|^{-1}\right)t^{2}-t+\|\mathbf {h} _{0}\|}$,

${\displaystyle t^{\ast /**}={\frac {2\|\mathbf {h} _{0}\|}{1\pm {\sqrt {1-2\alpha _{0}}}}}}$

y su proporción

${\displaystyle \theta ={\frac {t^{*}}{t^{**}}}={\frac {1-{\sqrt {1-2\alpha _{0}}}}{1+{\sqrt {1-2\alpha _{0}}}}}.}$

Entonces

1. Existe una solución dentro de la bola cerrada. ${\displaystyle \mathbf {x} ^{*}}$ ${\displaystyle {\bar {B}}(\mathbf {x} _{1},\theta \|\mathbf {h} _{0}\|)\subset {\bar {B}}(\mathbf {x} _{0},t^{*})}$
2. es único dentro de la bola más grande ${\displaystyle B(\mathbf {x} _{0},t^{*\ast })}$
3. y la convergencia a la solución de está dominada por la convergencia de la iteración de Newton del polinomio cuadrático hacia su raíz más pequeña , ^[4] si , entonces ${\displaystyle F}$ ${\displaystyle p(t)}$ ${\displaystyle t^{\ast }}$ ${\displaystyle t_{0}=0,\,t_{k+1}=t_{k}-{\tfrac {p(t_{k})}{p'(t_{k})}}}$

   ${\displaystyle \|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.}$

4. La convergencia cuadrática se obtiene a partir de la estimación del error ^[5]

   ${\displaystyle \|\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}\|.}$

Corolario

En 1986, Yamamoto demostró que las evaluaciones de error del método de Newton tales 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

Existe 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

1. Deuflhard, P. (2004). Métodos de Newton para problemas no lineales. Invariancia afín y algoritmos adaptativos . Serie Springer en Matemática Computacional. vol. 35. Berlín: Springer. ISBN 3-540-21099-7.
2. Zeidler, E. (1985). Análisis funcional no lineal y sus aplicaciones: Parte 1: Teoremas del punto fijo . Nueva York: Springer. ISBN 0-387-96499-1.
3. Dennis, John E .; Schnabel, Robert B. (1983). "Los teoremas de Kantorovich y la cartografía contractiva". Métodos numéricos para optimización sin restricciones y ecuaciones no lineales . Acantilados de Englewood: Prentice-Hall. págs. 92–94. ISBN 0-13-627216-9.
4. Ortega, JM (1968). "El teorema de Newton-Kantorovich". América. Matemáticas. Mensual . 75 (6): 658–660. doi :10.2307/2313800. JSTOR  2313800.
5. 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 Bib : 1974SJNA...11...10G. doi :10.1137/0711002. JSTOR  2156425.
6. Ostrowski, AM (1971). "El método de Newton en los espacios de Banach". CR Acad. Ciencia. París . 27 (A): 1251-1253.
7. Ostrowski, AM (1973). Solución de ecuaciones en espacios euclidianos y de Banach . Nueva York: Academic Press. ISBN 0-12-530260-6.
8. Potra, FA; Ptak, V. (1980). "Límites de error definidos para el proceso de Newton". Número. Matemáticas . 34 : 63–72. doi :10.1007/BF01463998.
9. Miel, GJ (1981). "Una versión actualizada del teorema de Kantorovich para el método de Newton". Informática . 27 (3): 237–244. doi :10.1007/BF02237981.
10. Potra, FA (1984). "Sobre las estimaciones de error a posteriori del método de Newton". Beiträge zur Numerische Mathematik . 12 : 125-138.
11. Yamamoto, T. (1986). "Un método para encontrar límites de error definidos para el método de Newton bajo los supuestos de Kantorovich". Matemática numérica . 49 (2–3): 203–220. doi :10.1007/BF01389624.
12. Rajkovic, primer ministro; Stankovic, MS; Marinkovic, SD (2003). "Sobre métodos q-iterativos para la resolución de ecuaciones y sistemas". Novi Sad J. Matemáticas . 33 (2): 127-137.
13. Rajković, primer ministro; Marinković, SD; Stanković, MS (2005). "Sobre el método q-Newton-Kantorovich para resolver sistemas de ecuaciones". Matemáticas Aplicadas y Computación . 168 (2): 1432-1448. doi :10.1016/j.amc.2004.10.035.
14. Ortega, JM; Rheinboldt, WC (1970). Solución iterativa de ecuaciones no lineales en varias variables . SIAM. OCLC  95021.
15. Oishi, S.; Tanabe, K. (2009). "Inclusión numérica del 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 , Matrix Editions, ISBN 978-0-9715766-3-6 (vista previa de la tercera edición y material de muestra que incluye Kant.-thm .) 
• Yamamoto, Tetsuro (2001). "Desarrollos históricos en el análisis de convergencia de 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 del Norte. págs. 241–263. ISBN 0-444-50617-9.