Tasa de convergencia del método de Newton modificado para raíces múltiples

Question

Tengo un problema con el método de Newton modificado. Tenemos una función $f \in C^{(k+1)}$ y $r$ que es la raíz múltiple de la multiplicidad $k$ . También $f^{(k)}(r) \neq 0$ y $f'(x) \neq 0 $ en los alrededores de $r$ .

El método de Newton modificado es $$x_{n+1} = x_n - k\frac{f(x_n)}{f'(x_n)}$$ Cómo demostrar que $x_n$ converge a $r$ ¿aquella que es cuadrática?

He encontrado un método que utiliza una función $G(x) = (x-r) f'(x) - kf(x)$ pero luego se dice que $ G^{(k+1)}(r) \neq 0$ sino que proviene del hecho de que $f^{(k+1)}(r) \neq 0$ pero no tiene por qué ser necesariamente cierto, ¿tengo razón? Sabemos que $f^{(k)}(r) \neq 0$ pero no tenemos información sobre el $k+1$ primera derivada. Agradecería que alguien me explicara con precisión, por qué converge cuadráticamente.

Answer 1

Si $k=1$ , tienes una raíz simple, tu iteración se reduce al método de Newton y sabemos que en ese caso, el método de Newton converge cuadráticamente.

Si $k > 1$ , tiene una raíz múltiple y si $f$ tiene una raíz de multiplicidad $k$ en $r$ se puede escribir de la forma $f(x) = (x-r)^k h(x)$ donde $h(r) \neq 0$ .

Ahora su iteración es una iteración de punto fijo de la forma $x_{k+1} = g(x_k)$ donde $g(x) := x - k f(x)/f'(x)$ . Utilizando la expresión de $f$ arriba, puede comprobar que $g(r) = r$ por lo que $g$ se llama una función de punto fijo---no se mueve $r$ ---y $r$ se llama punto fijo de $g$ . Lo que ocurre con las iteraciones de punto fijo es que convergen (a un punto fijo de $g$ ) siempre y cuando $|g'(r)| < 1$ y las inicializas lo suficientemente cerca de $r$ . Si usted denota $e_n := (x_n -r)$ el error en el $n$ -ésima iteración, entonces, utilizando una expansión de Taylor, se obtiene $$ e_{n+1} = x_{n+1} - r = g(x_n) - r \approx g(r) + g'(r) (x_n - r) - r = g'(r) e_n $$ porque $g(r) = r$ . Así que, esencialmente, el error se reduce en un factor $|g'(r)|$ en cada iteración cuando esté lo suficientemente cerca de $r$ . Si $g'(r) \neq 0$ Esto se llama convergencia lineal. Pero, ¿qué pasa si $g'(r) = 0$ ? Simplemente se realiza una expansión de segundo orden en lugar de una expansión de primer orden y se obtiene $$ e_{n+1} \approx g(r) + g'(r) e_n + \tfrac{1}{2} g''(r) e_n^2 -r = \tfrac{1}{2} g''(r) e_n^2, $$ y ahora el error se eleva al cuadrado (aproximadamente) en cada iteración. Esto se llama convergencia cuadrática. (Si $g''(r)=0$ , se pasa al tercer orden, etc.)

¿Por qué estoy explicando todo esto? Si quieres demostrar que tu iteración Newton modificada converge cuadráticamente, puedes intentar demostrar que $g(r)=r$ y $g'(r) = 0$ .

Es exactamente el caso de tu iteración y es relativamente fácil si escribes $f(x) = (x-r)^k h(x)$ . Calcula $f'(x)$ , $f''(x)$ , $g'(x)$ simplificar, y a continuación, introducir $x=r$ . Verás que $g'(r)=0$ .