Prueba de que el método de Newton Raphson tiene convergencia cuadrática

Question

He buscado en Google esto y he visto diferentes tipos de pruebas, pero todas utilizan anotaciones que no entiendo.

Pero antes que nada, necesito entender lo que significa convergencia cuadrática, leo que tiene que ver con la velocidad de un algoritmo. ¿Es esto correcto?

Ok, así que sé que este es el método de Newton-Raphson:

ps

¿Cómo prueba que es convergencia?

Gracias.

Answer 1

El método converge en virtud de las hipótesis apropiadas. Suponga que usted ha determinado, por cualquier medio, de un intervalo de $[a,b]$ con $$f(a)<0<f(b);\qquad f'(x)>0, \quad f''(x)>0\quad(a<x<b)$$ (o similar, pero con diferentes signos de $f$, $f'$, y $f''$). A continuación, $f$ tiene exactamente un cero $\xi\in\ ]a,b[\ $. Además es obvio a partir de la observación de una figura, resp., la convexidad de las propiedades de $f$, que $$x_0:=b,\qquad x_{n+1}:=x_n-{f(x_n)\over f'(x_n)}\quad(n\geq0)\tag{1}$$ produce un monótonamente disminución de la secuencia de puntos de $x_n>\xi$. De ello se desprende que el $x_n$ convergen para algunos $\xi'\in[\xi,x_0]$. Dejando $n\to\infty$ $(1)$ implica $f(\xi')=0$, de donde $\xi'=\xi$.

Con el fin de analizar la velocidad de convergencia invocamos Taylor teorema: Para cada una de las $n\geq0$ hay un $x^*\in[\xi,x_n]$ con $$0=f(\xi)=f(x_n)+f'(x_n)(\xi-x_n)+{f''(x^*)\over 2!}(\xi-x_n)^2\ .$$ Esto implica, por definición, de $x_{n+1}$, que $$x_{n+1}-\xi={f''(x^*)\over 2 f'(x_n)}(x_n-\xi)^2\ .$$ Aquí para un gran $n$ el primer factor en el lado derecho es aproximadamente igual a $$C:={f''(\xi)\over 2 f'(\xi)}\ .$$ Esto significa que un gran $n$ tenemos aproximadamente $$x_{n+1}-\xi\doteq C(x_n-\xi)^2\qquad(n\gg1)\ .$$ Cualitativamente, esto significa que con cada uno de Newton paso el número de decimales correctos es acerca de duplicado. Que es lo que se entiende por "convergencia cuadrática".

Answer 2

Deje $f$ ser el doble continua, derivable en un intervalo $(a, b)$. Suponga que $f(x) = 0$ donde $a < c < b$ y $f'(c) \neq 0$. Entonces existe $0 < \epsilon < \min(c - a, b-c)$ con la siguiente propiedad: elija cualquiera de los $x_0 \in (c- \epsilon, c + \epsilon)$ y definir de forma iterativa $$x_{n+1} = x_n - {{f(x_n)}\over{f'(x_n)}},\text{ }n \ge 0.\tag*{$(1)$}$$ We have that $\{x_n\}_{n=0}^\infty$ converges to $c$ in the following fashion: $$\left|x_{n+1} - c\right| \le M\left|x_n - c\right|^2 \text{ for all }n \ge 0,\tag*{$(2)$}$$ where $M$ es una constante.

Podemos suponer $c = 0$, e $\epsilon$ suficientemente pequeño como para que $$\left|f'(x)\right| > {{\left|f'(0)\right|}\over2}$$ when $\izquierda|x\right| < \epsilon$ for some $B \in \mathbb{R}^+$. Then by Taylor's Theorem, $$f(x_n) - xf'(x_n) = {{x_n^2}\over2} f''(y_n)$$ for some $y_n$ between $)$ and $x_n$. Thus, for $\left|x_n\right| < \epsilon$, we have $$\left|x_{n+1}\right| = \left|-x_{n+1}\right|$$ $$=\left| {{f(x_n)}\over{f'(x_n)}} - x_n\right|$$ $$= {1\over{\left|f'(x_n)\right|}} \cdot \left| f(x_n) - x_n f'(x_n)\right|$$ $$= {1\más de{\left|f'(x_n)\right|}} \cdot \left| {{x_n^2}\over2} f"(y_n)\right|$$ $$\le {2\over{f'(0)}} \cdot {B\over2} x_n^2.$$ What we are doing is taking $x_{n+1}$ to be the point where the tangent line to the graph of $f$ at $x_n$ hits the $x$-axis. The inequality we proved shows that for $\left|x_n\right| < \epsilon$, we have $$\left| {{x_{n+1}}\over{x_n}}\right| < Mx_n,$$ so if $$\left| x_n\right| < \min\left( \epsilon, {1\over{2M}}\right),$$ we have $$\left|x_{n+1}\right| < {{\left|x_n\right|}\over2}.$$ Thus, $$\left|x_n\right| \to 0\text{ as } n \to \infty.$$

---

La tasa de convergencia en $(2)$ es cuadrática y por lo tanto más rápido que en la contracción principio. Allí, la convergencia es exponencial, aquí es super-exponencial. Esto juega un papel importante en las aplicaciones, también a problemas en la matemática pura (Nash incrustación de objetos). Si usted tiene experiencia en programación, se podría escribir un breve código que calcula esta secuencia de Newton para las funciones simples de su elección. Verás cómo rápidamente la secuencia estabiliza detrás de la coma.

Answer 3

Nos fijamos en el tamaño de la próxima valor de la función. Por simple raíces y cerca de la raíz, el valor de la función es una medida de la distancia a la raíz. $$f(x+h)=f(x)+f'(x)h+\frac12 f"(x+\theta h)h^2$$ Denotar $L=\max_{x\in I} |f''(x)|$ y establezca $f(x)+f'(x)h=0$, luego $$|f(x+h)|\le \frac L2 h^2=\frac L2\frac{f(x)^2}{f'(x)^2}$$ Ahora poner la primera derivados en la constante y volver a la iteración secuencia $(x_n)$ para obtener $$|f(x_{n+1})|\le C\,|f(x_n)|^2 \ffi |C\,f(x_{n+1}|\le|C\,f(x_n)|^2$$ donde $C=\frac{L}{2m^2}$ con $$0< m\le |f'(x)|\le M<\infty$$

---

Repite el cuadrado conduce a una diádica poder en el exponente, por lo que $$|C\,f(x_n)|\le|C\,f(x_0)|^{2^n}$$ Esto es lo que se quiere decir con la convergencia cuadrática, que el exponente es $2^n$ en lugar de $n$ como en el lineal de convergencia.

La condición para garantizar la convergencia es, a continuación,$|C\,f(x_0)|<1$.

---

Para la distancia a la raíz de $x_*$ uso $$f(x)=f(x)-f(x*)\le f'(x*+\theta(x-x*))\,(x-x_*)$$ así que $$m\,|x-x_*|\le |f(x)|\le M\,|x-x_*|\ffi \frac{|f(x)|}M\le |x-x_*|\le\frac{|f(x)|}m.$$