¿Por qué el método de Newton-Raphson no converge para algunas funciones?

Question

$f(x)=2x^2-x^3-2$. Este es un gráfico de tipo cúbico como se muestra. La raíz real de este gráfico es $(-0.839,0)$.

Entonces, la pregunta es usar el método de aproximación de Newton dos veces para aproximar una solución a esta $f(x)$.

Utilizo un valor inicial de $x_0=1$. Mi primera aproximación es $x_1=2$, y mi segunda es $x_2=1.5$. Parece que no me acerco más a la solución real a medida que sigo iterando a través del método.

¿Estoy entendiendo mal cómo utilizar esta aproximación? ¿Es el problema que mi primer intento estaba muy lejos de la solución real?

Answer 1

De hecho, te rendiste demasiado pronto; El método eventualmente converge:

1   2.000000000000000000000000000
2   1.500000000000000000000000000
3   0.3333333333333333333333333333
4   2.148148148148148148148148148
5   1.637079608343976160068114091
6   0.9483928480399477528436835979
7   1.910874140183680201544963299
8   1.405089904362402921055022221
9   -1.324018083676046424512855515
10  -0.9614381794507316717924414480
11  -0.8500221808505758631523579893
12  -0.8393807176849843501240483025
13  -0.8392867625049899194321196645
14  -0.8392867552141611764525252322
15  -0.8392867552141611325518525647
16  -0.8392867552141611325518525647
17  -0.8392867552141611325518525647
18  -0.8392867552141611325518525647
19  -0.8392867552141611325518525647
20  -0.8392867552141611325518525647
?

Answer 2

El método de Newton no siempre converge. Su teoría de convergencia es para convergencia "local", lo que significa que debes empezar cerca de la raíz, donde "cerca" es relativo a la función con la que estás trabajando. Lejos de la raíz puedes tener dinámicas altamente no triviales.

Una propiedad cualitativa es que, en el caso de 1D, no deberías tener un extremo entre la raíz que deseas y tu suposición inicial. Si tienes un número impar de extremos en el camino, entonces comenzarás a alejarte de la raíz deseada, como se ve aquí. Si tienes un número par de extremos en el camino, entonces comenzarás a ir en la dirección correcta, pero puede que luego te encuentres en un punto con un número impar de extremos en el camino, lo que conduce a problemas más adelante.

Por supuesto, eventualmente podrías encontrar una ocasión donde haya un número par de extremos en el camino, y luego logres saltar sobre todos ellos y llegar al lado correcto. En ese momento las cosas usualmente funcionarán (aunque no siempre). En este problema con tu suposición inicial, eso eventualmente sucede, porque el sistema eventualmente encuentra su camino justo un poco a la derecha del extremo en la derecha, lo que lo envía lejos hacia la izquierda.

Answer 3

Las otras respuestas son geniales. Me gustaría agregar un ejemplo concreto de comportamiento extraño del cual habla la respuesta de Ian.

Consideremos una función $f(x) = \operatorname{sgn} x \sqrt{|x|}$. Según el algoritmo, iteramos $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.$$ Ahora para la derivada (si no estamos haciendo la derivada en $x = 0$, el $\operatorname{sgn} x$ es simplemente una constante, y $|x| = x \operatorname{sgn} x$): $$f' = [\operatorname{sgn} x \sqrt{x \operatorname{sgn} x}]' = \operatorname{sgn} x \frac{1}{2\sqrt{x \operatorname{sgn} x}} \operatorname{sgn} x = \frac{1}{2\sqrt{|x|}}.$$ Sustituyendo: $$x_{n+1} = x_n - \frac{\operatorname{sgn} x \sqrt{|x|}}{1/(2\sqrt{|x|})} = x_n - 2 \operatorname{sgn} x \left(\sqrt{|x|}\right)^2 =\\ =x_n - 2\operatorname{sgn} x |x| = x_n - 2 x_n = - x_n.$$

Entonces, si comenzamos a iterar en $x = a$ (donde $a \neq 0$), obtenemos la secuencia $a, -a, a, -a, \ldots$ y el método se repite indefinidamente entre esos dos puntos, sin llegar nunca a la raíz $x = 0$!

¡Edit: Aquí tienes una imagen gnuplot: (En cada iteración, hacemos una tangente en el punto actual (la línea azul discontinua) y el $x$ para el cual la tangente cruza 0 se toma como la siguiente aproximación (así que seguimos a lo largo de la línea magenta para obtener el punto de partida para la siguiente iteración).

Por cierto, echa un vistazo a esta imagen de Wikipedia:

Muestra el plano complejo coloreado con 5 colores, cada color correspondiente a una raíz de la ecuación compleja $z^5 = 1$. Cada punto tiene entonces el color correspondiente a la raíz a la cual el método de Newton converge, si comenzamos desde ese punto. Las "flores" son hermosas de contemplar pero totalmente aborrecibles desde el punto de vista numérico.

Answer 4

El método de Newton no tiene garantía de convergencia global para funciones arbitrarias, como acabas de aprender.

Ahora, las personas han publicado ejemplos en los que el método de Newton no converge, pero todos son funciones bastante "inusuales" (algunas muy poco suaves), por lo que es natural asumir que son patológicas y que no ocurrirán en la práctica.

Tu ejemplo es uno en el que Newton solo necesita más iteraciones de las esperadas para converger, así que no es tan malo. Pero aquí hay un ejemplo de un polinomio cúbico para el cual el método de Newton no convergerá!

\begin{align*} f(x) &= -0.74 + 0.765 x + 1.1 x^2 - 3.55 x^3 \\ x_0 &= 5/9 \end{align*}

No solo eso, sino que de hecho es una oscilación estable—pequeñas perturbaciones no cambiarán el comportamiento.

¡Y para puntos adicionales, puedes generar tantos como desees! Solo deja que el paso de Newton sea $$g(x) = x - f'(x)^{-1} f(x)$$ y estás buscando una solución no trivial a la ecuación $$x_0 = g^3(x_0) = g(g(g(x_0)))$$ donde una solución $x_0$ sería trivial si $g(x_0) = x_0$ (también conocido como punto fijo).
Observa que la ecuación anterior es simplemente otra ecuación polinómica (aunque de un orden mucho mayor)—lo que significa que sus soluciones se pueden encontrar fácilmente de forma numérica.
La única advertencia es que estas soluciones no necesariamente serán estables. Sospecho que deberías poder colocar una condición de segunda derivada para asegurar soluciones estables, pero la ecuación exacta no es obvia para mí en este momento, así que lo dejo como un ejercicio para el lector. :-)

Código de Mathematica para el gráfico:

Manipulate[
  With[{f = Evaluate[Rationalize[d + c # + b #^2 + a #^3]] &}, Plot[
    f[x], {x, -0.61, 1},
    PlotStyle -> {Thickness[Tiny]},
    Prolog -> {Thickness[Tiny],
      Line[Flatten[Map[
     {{#, 0}, {#, f[#]}} &,
     NestList[Compile[t, t - f[t]/f'[t]], x0, n]], 1]]}]],
  {{a, -3.55}, -4, 4},
  {{b, 1.1}, -2, 2},
  {{c, 0.765}, -1, 1},
  {{d, -0.74}, -1, 1},
  {{x0, 5/9}, 0, 1},
  {{n, 100}, 0, 1000, 1}]

---

Actualización:

He escrito un código para encontrar intencionalmente iteraciones estables e inestables:

Newton[f_] := t \[Function] t - f[t]/f'[t];
NewtonPlot[f_, xmin_, xmax_, x0_, n_, args___] :=
  Plot[f[x], {x, xmin, xmax}, args,
   Prolog -> {Thickness[Tiny],
     Line[Flatten[Map[
        {{#, 0}, {#, f[#]}} &,
        NestList[Compile[t, Newton[f][t]], x0, n]], 1]]}];
FindOscillatoryNewtonSolutions[f_, n_, h_](* {Stables,Unstables} *):=
  With[{step = Newton[f]},
   With[{nstep = t \[Function] Nest[step, t, n]},
    GroupBy[
     Map[#[[1]][[2]] &, 
      Solve[{nstep[t] == t, Abs[step[t] - t] >= h}, t, Reals]],
     t \[Function] 
      With[{step1hp = nstep[t + h], step1hm = nstep[t - h]}, True \[And]
        Abs[N[step1hp - t]] >= Abs[N[nstep[step1hp] - t]] \[And]
        Abs[N[step1hm - t]] >= Abs[N[nstep[step1hm] - t]]]]]];
With[{z = 400, xmin = -1.1, xmax = +0.65, h = 10^-3},
 Manipulate[
  With[{f = 
     t \[Function] Evaluate[Rationalize[d + c t + b t^2 + a t^3]], 
    n = 3, m = 8},
   With[{solcategories = FindOscillatoryNewtonSolutions[f, n, h]},
    If[Length[solcategories] >= 2,
     Map[{Transpose@{N@SortBy[NestList[Newton[f], #1, n - 1], N]},
        NewtonPlot[f, xmin, xmax, N[#1 + dx], n*m,
         PlotStyle -> {Thickness[Tiny]},
         ImageSize -> Scaled[0.2],
         PerformanceGoal -> "Quality"]} &, {First@Lookup[solcategories, True], 
       First@Lookup[solcategories, False]}],
     Throw["Did not manage to find both a stable and an unstable solution."]]]],
  {{dx, h}, -4 h, +4 h, h/4},
  {{a, -355}, -z, +z, 1}, {{b, 110}, -z, +z, 1},
  {{c, 77}, -z, +z, 1}, {{d, -74}, -z, +z, 1},
  SynchronousUpdating -> False]]

Observa, debajo, que el primer punto itera de forma estable, mientras que el segundo itera de forma inestable. (Las iteraciones se alejarían aún más, pero las corté en algún punto.)

Answer 5

La relación entre el punto de inicio y el punto de convergencia eventual para el método de Newton es complicada. Considere esta imagen (de MathWorld de Wolfram, Método de Newton):

mostrando las cuencas de atracción en el plano complejo para $x^3 - 1$, $x^4 - 1$, ... $x^{11} - 1$. Cada color corresponde a una raíz del polinomio. Cada punto está coloreado para que coincida con la raíz a la que el método de Newton eventualmente lleva ese punto.

Estas cuencas suelen ser bastante complicadas, pero si observa lo que está sucediendo en el plano complejo, puede ser un poco más claro lo que está sucediendo. La línea real se extiende horizontalmente, justo a la mitad de estas gráficas. Si todo lo que sabe es lo que está sucediendo en el eje real, que es lo que está viendo en su problema, puede resultar difícil predecir dónde va a terminar un punto dado.