4.3: Aproximación numérica de raíces de funciones

Al encontrar puntos críticos de una función\(f\), se encuentra con el problema de resolver la ecuación\(f'(x)=0\). Los ejemplos y ejercicios hasta el momento se establecieron cuidadosamente para que las soluciones a esa ecuación se pudieran encontrar en una forma simple y cerrada. Pero en la práctica este no siempre será el caso, de hecho casi nunca lo es. Por ejemplo, encontrar los puntos críticos de\(f(x) = \sin\,x \;-\; \frac{x^2}{2}\) implica resolver la ecuación\(f'(x) = \cos\,x \;-\; x ~=~ 0\), para lo cual no hay solución en una expresión de forma cerrada.

¿Qué debes hacer en tal situación? ⁵ Una posibilidad es utilizar el método de bisección mencionado en la Sección 3.3. De hecho, en Ejemplo

Ejemplo\(\PageIndex{1}\): ivt

Agrega texto aquí.

Solución

se demostró que la solución a la ecuación\(\cos\,x = x\) (i.e.\(\cos\,x \;-\; x \;=\;0\)) existía en el intervalo\(\ival{0}{1}\), y luego se dio una demostración del método de la bisección para encontrar esa solución.

El método de la bisección es uno de los muchos métodos numéricos para encontrar las raíces de una función (es decir, donde la función es cero). Encontrar los puntos críticos de una función significa encontrar las raíces de su derivada. Aunque el método de la bisección podría usarse para ese propósito, no es eficiente, la convergencia a la raíz es lenta. Un método mucho más eficiente es el método ⁶ de Newton, cuya interpretación geométrica se muestra en la Figura [fig:newton] a continuación.

La idea detrás del método de Newton es simple: encontrar una raíz\(\bar{x}\) de una función\(f\), elegir una suposición inicial\(x_0\) y luego subir o bajar a la curva\(y=f(x)\) y dibujar la línea tangente a la curva en el punto\((x_0,f(x_0))\). \(x_1\)Sea donde esa línea tangente intersecta el\(x\) eje -eje, como se muestra arriba; repita este procedimiento\(x_1\) para obtener el siguiente número\(x_2\), repita on\(x_2\) para obtener\(x_3\), y así sucesivamente. La secuencia resultante de números\(x_0\),,\(x_1\),,\(x_2\),\(x_3\)\(\ldots\), se acercará a la raíz\(\bar{x}\). Se puede probar la convergencia bajo ciertas condiciones. ⁷ La fórmula general para el número\(x_n\) obtenido después de\(n \ge 1\) iteraciones en el método de Newton se puede determinar considerando la fórmula para\(x_1\). Primero, la línea tangente a\(y=f(x)\) en el punto\((x_0,f(x_0))\) tiene pendiente\(f'(x_0)\), por lo que la ecuación de la línea es

\[\label{eqn:newton} y ~-~ f(x_0) ~=~ f'(x_0)\,(x ~-~ x_0) ~.\]El punto\((x_1,0)\) está (por diseño) también en esa línea, de modo que

\[0 ~-~ f(x_0) ~=~ f'(x_0)\,(x_1 ~-~ x_0) \quad\Rightarrow\quad x_1 ~=~ x_0 ~-~ \frac{f(x_0)}{f'(x_0)}\]siempre que\(f'(x_0) \ne 0\). La fórmula general para\(x_n\) viene dada por el siguiente algoritmo:

Para implementar este algoritmo en un lenguaje de programación (para el cual el método de Newton es muy adecuado), se puede usar como guía el siguiente pseudocódigo independiente del lenguaje:

Ejemplo\(\PageIndex{1}\): newt1

Agrega texto aquí.

Solución

Utilice el método de Newton para encontrar la raíz de\(f(x) = \cos\,x - x\).

Solución: Como ya se sabe que la raíz está en el intervalo\(\ival{0}{1}\), elija\(x_0 = 1\) como suposición inicial. Los números\(x_n\) para se\(n \ge 1\) pueden calcular con una calculadora científica de mano, pero el proceso es tedioso y propenso a errores. El uso de una computadora es mucho más eficiente y permite más flexibilidad.

Por ejemplo, el algoritmo se implementa fácilmente en el lenguaje de programación Java. Guarde este código en un archivo de texto sin formato como newton.java:

public class newton {
   public static void main(String[] args) {
      int N = Integer.parseInt(args[0]); //Number of iterations
      double x = 1.0; //initial guess
      System.out.println("n=0: " + x);
      for (int i = 1; i <= N; i++) {
         x =  x - f(x)/derivf(x);
         System.out.println("n=" + i + ": " + x);
      }
   }
 
   //Define the function f(x)
   public static double f(double x) {
      return Math.cos(x) - x;
   }

   //Define the derivative f'(x)
   public static double derivf(double x) {
      return -Math.sin(x) - 1.0;
   }
}

Aunque el conocimiento de Java ayudaría, no debería ser tan difícil averiguar qué está haciendo el código anterior. El número de iteraciones\(N\) se pasa como parámetro de línea de comandos al programa, y\(x_n\) se calcula e imprime para\(n=0\),\(1\),\(2\),\(\ldots\),\(N\). Tenga en cuenta que la derivada de\(f(x)\) está “codificada” en el programa. ⁸ Tampoco hay error al verificar que el derivado sea cero en ningún caso\(x_n\). El programa simplemente se detendría en una división por error cero.

Compile el código, luego ejecute el programa con\(10\) iteraciones:

javac newton.java
java newton 10

La salida se muestra a continuación:

n=0: 1.0
n=1: 0.7503638678402439
n=2: 0.7391128909113617
n=3: 0.739085133385284
n=4: 0.7390851332151607
n=5: 0.7390851332151607
n=6: 0.7390851332151607
n=7: 0.7390851332151607
n=8: 0.7390851332151607
n=9: 0.7390851332151607
n=10: 0.7390851332151607

Tenga en cuenta que la solución\(\bar{x} = 0.7390851332151607\) se encontró después de solo 4 iteraciones; los números se\(x_n\) repiten para\(n \ge 5\). Esto es mucho más rápido que el método de la bisección.

Otro método numérico de búsqueda de raíces similar al método de Newton es el método secante, cuya interpretación geométrica se muestra en la Figura [fig:secante] a continuación:

La idea detrás del método secante es simple: encontrar una raíz\(\bar{x}\) de una función\(f\), elegir dos conjeturas iniciales\(x_0\) y\(x_1\), luego, subir o bajar a la curva\(y=f(x)\) y dibujar la línea secante a través de los puntos\((x_0,f(x_0))\) y\((x_1,f(x_1))\) sobre la curva. \(x_2\)Sea donde esa línea secante intersecta el\(x\) eje -eje, como se muestra arriba; repita este procedimiento\(x_1\) y\(x_2\) para obtener el siguiente número\(x_3\), y seguir repitiendo de esta manera. La secuencia resultante de números\(x_0\),,\(x_1\),\(x_2\),\(x_3\),\(\ldots\), se acercará a la raíz\(\bar{x}\), en las condiciones adecuadas. ⁹ Dado que la línea secante atraviesa\((x_0,f(x_0))\) y\((x_1,f(x_1))\) tiene pendiente\(\frac{f(x_1) - f(x_0)}{x_1 - x_0}\), la ecuación de esa línea secante es:

\[y ~-~ f(x_1) ~=~ \frac{f(x_1) - f(x_0)}{x_1 - x_0}\,(x ~-~ x_1)\]El punto\((x_2,0)\) está en esa línea, de modo que

\[0 ~-~ f(x_1) ~=~ \frac{f(x_1) - f(x_0)}{x_1 - x_0}\,(x_2 ~-~ x_1) \quad\Rightarrow\quad x_2 ~=~ x_1 ~-~ \frac{(x_1 ~-~ x_0) \cdot f(x_1)}{f(x_1) ~-~ f(x_0)}\]siempre que\(x_1 \ne x_0\). La fórmula general para\(x_n\) viene dada por el siguiente algoritmo:

Una diferencia que podrías haber notado entre el método secante y el método de Newton es que el método secante no usa derivados. El método secante reemplaza la derivada en el método de Newton con la pendiente de una línea secante que se aproxima a la derivada (recordar cómo la línea tangente es el límite de pendientes de las líneas secantes). Esto puede parecer un inconveniente, tal vez dando una pendiente “menos precisa” que la línea tangente, pero en la práctica no es realmente un problema. De hecho, en muchos casos es preferible el método secante, ya que los derivados de computación a menudo pueden ser bastante complicados.

Ejemplo\(\PageIndex{1}\): secant1

Agrega texto aquí.

Solución

Utilice el método secante para encontrar la raíz de\(f(x) = \cos\,x - x\).

Solución: Dado que ya se sabe que la raíz está en el intervalo\(\ival{0}{1}\), elija\(x_0 = 0\) y\(x_1 = 1\) como las dos conjeturas iniciales. El algoritmo se implementa fácilmente en el lenguaje de programación Java. Guarde este código en un archivo de texto sin formato como secant.java:

import java.math.*;
public class secant {
   public static void main(String[] args) {
      int N = Integer.parseInt(args[0]); //Number of iterations
      double x0 = 0.0; //first initial guess
      double x1 = 1.0; //second initial guess
      double f0 = f(x0);
      double f1;
      double x = 0.0;
      for (int i = 2; i <= N; i++) {
         f1 = f(x1);
         x = x1 - (x1 - x0)*f1/(f1 - f0);
         x0 = x1;
         f0 = f1; //Re-use f1 as f0 in the next iteration
         x1 = x;
         System.out.println("n=" + i + ": " + x);
      }
   }

   //Define the function f(x)
   public static double f(double x) {
      return Math.cos(x) - x;
   }
}

Compile el código, luego ejecute el programa:

javac secant.java
java secant 10

La salida se muestra a continuación:

n=2: 0.6850733573260451
n=3: 0.736298997613654
n=4: 0.7391193619116293
n=5: 0.7390851121274639
n=6: 0.7390851332150012
n=7: 0.7390851332151607
n=8: 0.7390851332151607
n=9: NaN
n=10: NaN

Observe que la raíz se encontró después de 6 iteraciones (\(n=7\)). El número indefinido NaN (que significa “Not a Number”) se devolvió comenzando con la octava iteración (\(n=9\)) porque\(x_7 ~=~ x_8\), de manera que\(f(x_8) ~-~ f(x_7) ~=~ 0\), provocando una división por error cero en el término

\[x_9 ~=~ x_8 ~-~ \frac{(x_8 ~-~ x_7) \cdot f(x_8)}{f(x_8) ~-~ f(x_7)} ~.\]

Para la función\(f(x) = \cos\,x \,-\, x\), la siguiente tabla resume los resultados de 10 iteraciones del método de la bisección, el método de Newton y el método secante:

Término	Bisección	Newton	Secante
\(x_0\)	0.5	1.0	0.0
\(x_1\)	0.75	0.7503638678402439	1.0
\(x_2\)	0.625	0.7391128909113617	0.6850733573260451
\(x_3\)	0.6875	0.739085133385284	0.736298997613654
\(x_4\)	0.71875	0.7390851332151607	0.7391193619116293
\(x_5\)	0.734375	0.7390851332151607	0.7390851121274639
\(x_6\)	0.7421875	0.7390851332151607	0.7390851332150012
\(x_7\)	0.73828125	0.7390851332151607	0.7390851332151607
\(x_8\)	0.740234375	0.7390851332151607	0.7390851332151607
\(x_9\)	0.7392578125	0.7390851332151607	undefined
\(x_{10}\)	0.73876953125	0.7390851332151607	undefined

El método de Newton encontró la raíz después de 4 iteraciones, mientras que el método secante necesitaba 6 iteraciones. Después de 10 iteraciones, el método de bisección aún no había encontrado la raíz con el mismo nivel de precisión que los otros métodos; se necesitarían 52 iteraciones (es decir,\(x_{52}\)) para lograr una precisión similar a 16 decimales.

En general el método de Newton requiere menos iteraciones para encontrar una raíz que el método secante, pero esto no significa necesariamente que siempre será más rápido. Dependiendo de la complejidad de la función y su derivada, el método de Newton podría implicar operaciones más “costosas” (es decir, calcular valores, en lugar de asignar valores) que el método secante, de modo que se componen las pocas iteraciones más posiblemente requeridas por el método secante para por menos cómputos totales.

Para ver esto, observe que el método de Newton siempre requiere que ambos\(f(x_{n-1})\) y\(f\,'(x_{n-1})\) se computen para el término n ^º\(x_n\) en la secuencia. El método secante necesita\(f(x_{n-1})\) y\(f(x_{n-2})\) para el ^n-ésimo término, pero un buen programador guardaría el valor de para que\(f(x_{n-1})\) pudiera ser reutilizado (y por lo tanto no recalculado) como\(f(x_{n-2})\) en la siguiente iteración, resultando en potencialmente menos total cálculos para el método secante.

Hay dificultades ocasionales en el uso del método de Newton. Por ejemplo, si\(f'(x_n) = 0\) para algunos\(n \ge 1\) entonces el método de Newton falla, debido a la división por 0 en el algoritmo. La razón geométrica es clara: la línea tangente a la curva en ese punto sería paralela al\(x\) eje -y por lo tanto no la cruzaría (asumiendo\(f(x_n) \ne 0\)). ¡No habría “siguiente número”\(x_{n+1}\) en la iteración! Consulte la Figura [fig:newtonpitfalls] (a) a continuación.

Otro posible problema es que el método de Newton podría alejarte de la raíz, es decir, no acercarte, típicamente por una mala elección de\(x_0\). Véase la Figura [fig:newtonpitfalls] (b) anterior. En algunos casos extremos, es posible que el método de Newton simplemente haga un bucle de ida y vuelta sin cesar entre los mismos dos números, como en la Figura [fig:newtonloop]:

En la mayoría de los casos una elección diferente para la suposición inicial\(x_0\) solucionará tales problemas. La mayoría de los libros de texto sobre el tema del análisis numérico discuten estos temas. ¹⁰ Hay condiciones bajo las cuales se garantiza que el método de Newton funcione, y la convergencia es rápida. El método de Newton tiene una tasa cuadrática de convergencia, lo que significa aproximadamente que los términos de error —las diferencias entre las raíces aproximadas y la raíz real— están siendo cuadrados a largo plazo. Más precisamente, si los números\(x_n\) para\(n \ge 0\) convergen a una raíz\(\bar{x}\), entonces los términos de error\(\epsilon_n = x_n - \bar{x}\) para\(n \ge 0\) satisfacer el límite

\[\lim_{n \to \infty} ~\dfrac{\abs{\epsilon_{n+1}}}{\abs{\epsilon_n}^2} ~=~ C\]para alguna constante\(C\). Los términos de error al cuadrado pueden sonar como algo malo, pero los\(x_n\) términos están convergiendo a la raíz, haciendo que los términos de error se acerquen a 0 para grandes\(n\). Al cuadrar un número\(\epsilon_n\) cuando\(\abs{\epsilon_n} < 1\) resulta en un número menor, no uno mayor.

Los métodos numéricos que hayas aprendido permitirán bosquejar las gráficas de muchas más funciones, ya que encontrar mínimos y máximos locales implica encontrar raíces de\(f'\), y encontrar puntos de inflexión implica encontrar raíces de\(f''\). Ya conoces algunos métodos para encontrar esas raíces.

Por último, a pesar de ser más lento, el método de la bisección tiene la buena ventaja de trabajar siempre. La velocidad de las computadoras modernas hace que la diferencia en la eficiencia algorítmica sea insignificante en muchos casos.

[sec4dot3]

Utilice el método de Newton para encontrar la raíz de\(f(x) = \cos\,x - 2x\).

Utilice el método de Newton para encontrar la raíz positiva de\(f(x) = \sin\,x - x/2\).

Usa el método de Newton para encontrar la solución de la ecuación\(e^{-x} = x\).

Usa el método de Newton para encontrar la solución de la ecuación\(e^{-x} = x^2\).

Utilice el método de Newton y\(f(x) = x^2 - 2\) para aproximar con\(\sqrt{2}\) precisión a seis decimales.

Utilice el método de Newton para aproximar con\(\sqrt{3}\) precisión a seis decimales.

2

Repita el Ejercicio 1 con el método secante.

Repita el Ejercicio 3 con el método secante.

2

Repita el Ejercicio 5 con el método secante.

Repita el Ejercicio 6 con el método secante.

La radiación cósmica de fondo de microondas se describe por una función similar a\(f(x) = \frac{x^3}{-1 + e^x}\) for\(x \ge 0\). Utilice el método de Newton para encontrar el máximo global de\(f\) precisión de cuatro decimales.

¿Una elección diferente para\(x_0\) en cualquiera de las gráficas de la Figura [fig:newtonloop] eliminaría el bucle infinito? Explique.

Dibuja una gráfica sin simetría alguna que tenga el problema de bucle infinito para el método de Newton.

El tiempo\(t(p)\) requerido para una fusión\(p\) -way de un archivo en una sola unidad de disco en la memoria es

\[t(p) ~=~ \frac{pa + m}{\ln\,p} ~,\]donde\(p>1\),\(a\) es el tiempo de acceso al disco, y\(m\) es el tiempo para leer en un segmento del tamaño de la memoria. Encuentra el entero más cercano al valor de\(p\) que minimiza\(t(p)\) cuando\(a = 24.3\) ms y\(m=3500.3\) ms.