¿Cómo se determina qué representación de una función debe utilizarse para el método de Newton?

Question

Toma la ecuación:

$$x^2 + 2x = \frac{1}{1+x^2}$$

He restado el término correcto para formar $~f_1(x)~$ :

$$x^2 + 2x - \frac{1}{1+x^2} = 0$$

Quería tomar la derivada, así que reorganicé las cosas para hacerlo un poco más fácil, llámalo $~f_2(x)~$ :

$$x^4 + 2x^3 + x^2 + 2x - 1 = 0$$

Me di cuenta cuando grafiqué $~f_1(x)~$ y $~f_2(x)~$ que sus parcelas eran diferentes $($ aunque compartían la misma solución para $~x)~$ .

El método de Newton itera por la línea de la gráfica, así que me imagino que el método de Newton para estas dos ecuaciones no son equivalentes. Encontrarían la misma solución, pero llegarían a ella de formas distintas. En ese caso, ¿hay alguna forma de decidir qué ecuación utilizar para que el método de Newton obtenga el mejor resultado o el más rápido?

Answer 1

Para su curiosidad.

Al hacerme esta pregunta nada inocente, casi me está preguntando qué he estado haciendo durante los últimos sesenta años.

Mi respuesta es : ¿cuál es la transformación de $f(x)$ lo que la convierte en la más lineal en torno a ¿la solución? Si la encuentras, te ahorrarás muchas iteraciones.

Un caso que me gusta como demostración es $$f(x)=\sum_{i=1}^n a_i^x- b^x$$ donde $1<a_1<a_2< \cdots < a_n$ y $b > a_n$ ; en este sitio, podría encontrar muchos problemas de este tipo.

Tal y como está escrita, esta función es muy mala ya que varía muy rápido y es muy poco lineal. Además, pasa por un máximo (no fácil de identificar) y hay que empezar por la derecha del mismo para converger.

Consideremos ahora la transformación $$g(x)=\log\left(\sum_{i=1}^n a_i^x \right)- x\log(b)$$ Es casi una línea recta. Esto significa que puedes empezar desde casi cualquier lugar y converger rápidamente.

A título ilustrativo, pruebe con $n=6$ , $a_i=p_i$ y $b=p_{n+1}$ ( $p_i$ siendo el $i^{th}$ número primo). Siendo muy perezoso y utilizando $x_0=0$ los iterados serían $$\left( \begin{array}{cc} n & x_n \\ 0 & 0 \\ 1 & 1.607120621 \\ 2 & 2.430003204 \\ 3 & 2.545372693 \\ 4 & 2.546847896 \\ 5 & 2.546848123 \end{array} \right)$$ Utilizando $f(x)$ debe empezar a iterar con $x_0 > 2.14$ para tener convergencia (¡gran trabajo para saberlo!). Probemos con $x_0=2.2$ para obtener como iterados sucesivos

$$\left( \begin{array}{cc} n & x_n \\ 0 & 2.200000000 \\ 1 & 4.561765400 \\ 2 & 4.241750505 \\ 3 & 3.929819520 \\ 4 & 3.629031502 \\ 5 & 3.344096332 \\ 6 & 3.082467015 \\ 7 & 2.856023930 \\ 8 & 2.682559774 \\ 9 & 2.581375720 \\ 10 & 2.549595979 \\ 11 & 2.546866878 \\ 12 & 2.546848124 \\ 13 & 2.546848123 \end{array} \right)$$

El último punto que me gustaría mencionar : incluso si usted tiene una buena conjetura $x_0$ de la solución, buscar una transformación $g(x)$ tal que $g(x_0)\,g''(x_0) >0$ (es el teorema de Darboux) para evitar cualquier rebasamiento de la solución durante el camino hacia ella.

Answer 2

El método de Newton es muy robusto una vez que se cerca de una raíz: la función exacta que elijas para ejecutarlo no tiene mucha importancia; convergerá rápidamente sea como sea. Lo mejor es que utilices la que te resulte más fácil.

Para ser más precisos, dejemos que $f$ sea la función de la que queremos encontrar una raíz y definamos $g(x)=x-\frac{f(x)}{f'(x)}$ para ser la función que realiza un solo paso del método de Newton. Primero: debe quedar claro que las cosas van mal si $f'$ y $f$ comparten una raíz, así que vamos a suponer que no - y vamos a suponer que $f$ es suave cerca de la raíz, por conveniencia.

La idea es que $g$ arrastra todo lo que está cerca de una raíz hasta la raíz, y para cuantificar la rapidez, podemos echar un vistazo a su serie de Taylor en una raíz. Sea $x_0$ sea una raíz de $f$ . Si diferenciamos $g$ luego simplificar en $x_0$ señalando que $f(x_0)=0$ podemos ver lo siguiente: $$g(x_0)=x_0$$ $$g'(x_0)=0$$ $$g''(x_0)=\frac{f''(x_0)}{f'(x_0)}$$ En particular, esto nos dice que, una vez que estamos lo suficientemente cerca de $x_0$ si la cantidad actual de error es $e$ una aplicación más de $g$ hace que el error sea algo más parecido a $g''(x_0)e^2$ - esto es bastante fantástico independientemente de lo que $g''(x_0)$ es - si tomas un número pequeño y lo elevas al cuadrado una y otra vez, se hace realmente pequeño muy rápido - que es lo que queremos que le ocurra al error. Supongo que si usted fuera realmente ansioso, usted podría tratar de hacer $g''(x_0)$ pequeño eligiendo $f$ pero, siendo realistas, no importa, ya que suele ocurrir que la ejecución de un paso adicional del método empequeñece por completo cualquier ganancia derivada del ajuste fino. $f$ .

---

Dicho esto, el método de Newton puede comportarse bastante mal a escala global, incluso para polinomios puede hacer cosas realmente desagradables*. Elegir la función con cuidado tampoco es que ayude mucho en este caso, ya que cuando las funciones tienen derivadas muy pequeñas, el método es inestable, pero cuando tienen derivadas que crecen rápidamente (como cerca de una asíntota), el método converge muy lentamente. $f$ tampoco te ayudará en eso.

(*Ejemplo: Busca "cuencas de atracción del método de Newton" en Google - obtendrás estos increíbles gráficos de dónde converge el método si lo ejecutas en polinomios tan simples como $x^3-1$ a partir de varios puntos del plano complejo. Básicamente, cuando no cerca de una raíz, cualquier cosa puede ocurrir)

Answer 3

Depende de la derivada de tu función en los ceros de tu función.

La fórmula sugiere que $$x_{n+1} = x_n-\frac {f(x_n)}{f'(x_n)}$$

Así, obtendrá un resultado mejor (más rápido) si la derivada de su función es mayor en los ceros de $f(x)$ .

El proceso se vuelve muy punto inicial es cercana a cero.

Como caso muy interesante puede considerar $$y=\sin x$$ y tratar de encontrar $x=\pi$ comenzando en un punto cercano a $\pi/2$

Sin conocer los ceros de $f(x)$ Tomar una decisión no es tarea fácil.

Answer 4

No es difícil demostrar que sólo hay dos soluciones reales, ya que

• $x^2+2x$ disminuye de $+\infty$ a $-1$ en $(-\infty,-1]$ mientras que $\frac{1}{x^2+1}$ aumenta de $0$ a $\frac{1}{2}$ ;
• en $[-1,0]$ tenemos $x^2+2x\leq 0$ pero $\frac{1}{x^2+1}>0$ ;
• $x^2+2x$ aumenta de $0$ a $+\infty$ en $\mathbb{R}^+$ mientras que $\frac{1}{x^2+1}$ disminuye de $1$ a $0$ .

Digamos que estamos interesados en encontrar la raíz positiva, que se encuentra en $I=\left[0,\frac{1}{2}\right]$ .
En dicho intervalo $a(x)=x^2+2x$ es creciente y convexa, $b(x)=\frac{1}{x^2+1}$ es decreciente y cóncava.
Esto sugiere un ajuste de la iteración Newton-Raphson:

Nos interesa la intersección entre las curvas azul y naranja, que se sitúa a la izquierda de la intersección entre las líneas tangentes siena y púrpura. Resolviendo $$ 3x-\frac{1}{4} = \frac{28}{25}-\frac{16}{25}x $$ encontramos que $\frac{137}{364}$ ya es una buena aproximación de la solución en $[0,1]$ . Método de Newton (aplicado a $a(x)-b(x)$ ) con dicho punto de partida se garantiza que converge cuadráticamente (y de forma monótona) a la solución real $0.3708102352\ldots$