El método de Newton-Raphson (NR) es una técnica numérica que consiste en hallar la solución para sistemas de ecuaciones no lineales a partir de aproximaciones sucesivas. Cada paso o iteración da una aproximación a la solución. Una condición conocida como Convergencia se cumple cuando las aproximaciones calculadas en las iteraciones toman un valor muy cercano a la solución (Lee and Wang 2003).
Suponga que se requiere resolver una ecuacuación para \(x\). Sea \(f(x)=0\) la ecuación antes mencionada igualada a cero, con \(f(x)\) una función de valor real. El cálculo aproximado a partir del método de NR se realiza mediante un algoritmo que utliza una fórmua de recurrencia. A continuación, se presentan con mayor detalle estos dos elementos.
Al igual que cualquier método iterativo, se requiere una fórmula de recurrencia para realizar cáculos en cada iteración. En el caso del método de NR, se parte de la ecuación de la recta tangente en un punto \(\hat{x}_k\) de la función \(f(x)\):
\[\begin{equation} g(x) = f'(x)[x-\hat{x}_k] + f(\hat{x}_k) \tag{2.1} \end{equation}\]
donde \(f'(\cdot)\) es la derivada de la función \(f(\cdot)\).
Considere el punto \(x=\hat{x}_k\) como la aproximación de la iteración número \(k\). El método de NR utiliza como valor para la siguiente aproximaxión, \(\hat{x}_{k+1}\), el intercepto en \(x\) de la recta tangente a la función en \(\hat{x}_k\), como lo ilustra la Figura 1.
Figure 2.1: Ilustración de una iteración del método NR.
En otras palabras, el punto \(x=\hat{x}_{k+1}\) es tal que \(g(\hat{x}_{k+1})=0\). De esta forma, la expresión (2.1) adquiere la siguiente forma:
\[\begin{equation} 0 = f'(x)[x-\hat{x}_k] + f(\hat{x}_k) \tag{2.2} \end{equation}\]
Si se toma \(x=\hat{x}_{k+1}\) en (2.2) y se despeja, se obtiene la fórmula de recurrencia del método de NR:
\[\begin{equation} \hat{x}_{k+1} = \hat{x}_k - \frac{f(\hat{x}_k)}{f'(\hat{x}_k)} \tag{2.3} \end{equation}\]
El procedimiento para el cálculo aproximado comienza suponiendo un valor estimado de \(x\), denotado como \(\hat{x}_0\). Este valor incial es tal que \(f(\hat{x}_0) \approx 0\), y por lo tanto, la forma que toma la ecuación (2.3) para la primera iteración es la siguiente:
\[\begin{equation} \hat{x_1} = \hat{x}_0 - \frac{f(\hat{x}_0)}{f'(\hat{x}_0)} \tag{2.4} \end{equation}\]
El proceso iterativo termina en la \(k\)-ésima iteración si se cummple cualquiera de las siguientes condiciones:
En la práctica, el usuario define aquellos valores que se consideran aproximados a cero, lo cual hace que el criterio de finalización sea subjetivo. Cada uno de estos valores recibe el nombre de Tolerancia, y sSe recomienda que tengan un orden de magnitud entre \(10^6\) y \(10^7\).
La impementación computacional se resume de la siguiente forma (Burden and Faires 2011):
Valor inicial \(x_p = \hat{x}_0\), Tolerancia (\(TOL\)), número de iteraciones máximo \(N_0\).
SalidasSolución aproximada \(x\) o mensaje de falla.
Paso 1 Hacer \(k=1\), definir \(x_p\)
Paso 2 Mientras \(k<=N_0\) Hacer los pasos 3 - 6
Paso 3 Hacer \(x = x_p - f(x_p)/f'(x_p)\)
Paso 4 Si \(|x - x_p|<TOL\) entonces imprima \(x\)
Parar
Paso 5 Hacer \(k=k+1\)
Paso 6 Hacer \(x_p = x\)
Paso 7 Imprimir mensaje “Procedimiento fallido”
Finalizar
El raquetbol es un deporte de raqueta mixto que se juega en una pista totalmente cerrada, similar al squash.
Figure 2.2: ¿Cómo jugar raquetbol?
Fuente: WikiHow
Como cualquier deporte de competición, el raquetbol tiene que ver con la disciplina, habilidad y tenacidad de quienes lo practican. Sin embargo, en cada juego también existen factores no controlables: nervios, molestias físicas inesperadas, entre otros, los cuales adicionan un componente aleatorio. Por ello, es razonable tratar el resultado de un juego de raquetbol en términos probabilísticos.
Aunque varios autores han abordado el problema de determinar la probabilidad de ganar un juego de raquetbol, Keller (1984) es pionero. En su trabajo, el encontró que la probabilidad de que un jugador \(A\) gane por un puntaje 21-0 al jugador \(B\) se calcula con la siguiente expresión:
\[\begin{equation} P_w = \frac{1+p}{2}\left( \frac{p}{1-p+p^2} \right)^{21} \tag{2.5} \end{equation}\]
donde \(p\) es la probabilidad de que el jugador \(A\) gane cualquier encuentro encuentro (independiente de quien haga el servicio). Burden and Faires (2011), en uno de los ejercicios de su texto, propone el cálculo de la probabilidad \(p\) tal que el jugador \(A\) gane por un puntaje 21-0 en al menos la mitad de los partidos que juegue, con una tolerancia de \(10^{-3}\).
De acuerdo con la información suministrada, \(P_w=0.5\). Además, la variable que se desea hallar se denota como \(p\).
De acuerdo con la formulación del método de NR, la ecuación que se debe solucionar es la expresión (2.5) igualada a cero. En otras palabras, se va a solucionar la siguiente ecuación:
\[f(p)=0\]
donde \(f(p)\) es una función objetivo tal que:
\[f(p) = \frac{1+p}{2}\left( \frac{p}{1-p+p^2} \right)^{21} - 0.5\] A continuación, se presentan unas líneas de código en las cuales se grafica \(f(p)\):
f.p <- function(p) {
( (1 + p)/2 )*( p/(1 - p + p^2) )^21 - 0.5
}
curve(f.p, col = 'blue', lwd = 2, from = 0, n = 100, xlim=c(0, 1), ylab='f(p)', xname="p")
abline(a=0, b=0, lty = 5)
Figure 2.3: Gráfica de la función objetivo.
En la figura anterior se puede apreciar que \(p>0.8\). Para hallar una solución aproximada, se va a implementar el méteodo de NR.
a. Opción 1
El método puede ser implementado programando la rutina que se definió más arriba. A continuación, se presentan unas líneas de código correspondientes al método de NR:
NR <- function(f, x0, tol = 1e-6, N0 = 500) {
require(numDeriv) # Paquete que hace derivadas numéricas
# x0.....Valor inicial
# N0.....Número de iteraciones
# Verificar que el punto inicial no sea una raiz
fx0 <- f(x0)
if (fx0 == 0.0) {
return(x0)
}
k <- 1 # Inicializar contador
A <- NA # Inicializar vector de iteraciones
while (k <= N0) {
dx <- genD(func = f, x = x0)$D[1] # primera derivada, f'(x0)
x1 <- x0 - (f(x0) / dx) # Cálculo de la aproximación siguiente
A[k] <- x1 # Almacenar iteraciones
# Imprimir el resultado cuando |x1 - x0| < tol
if (abs(x1 - x0) < tol) {
aprox <- tail(A, n=1)
res <- list('Raíz aproximada' = aprox, 'iteraciones' = A, 'Número de iteraciones' = k)
return(res)
}
# Si NR no ha alcanzado la convergencia, debe continuar
x0 <- x1
k <- k + 1
}
print('El método falló. El número de iteraciones no es suficiente.')
}
Para calcular la solución, basta con tomar la función f.p
previamente escrita e ingresarla como el argumento f
en la función NR
, como se muestra a continuación:
NR(f = f.p, x0 = 0.75, tol = 1e-3)
## $`Raíz aproximada`
## [1] 0.8423048
##
## $iteraciones
## [1] 0.8822045 0.8412975 0.8423056 0.8423048
##
## $`Número de iteraciones`
## [1] 4
b. Opción 2:
El paquete pracma provee la función newtonRaphson
para aplicar el método. Para utilizarla, basta con tomar la función f.p
previamente escrita e ingresarla como argumento. Además, se debe ingresar el valor inicial, que en este caso es \(0.75\)
require(pracma)
newtonRaphson(fun = f.p, x0 = 0.75, tol = 1e-3)
## $root
## [1] 0.8423048
##
## $f.root
## [1] -1.969369e-08
##
## $niter
## [1] 4
##
## $estim.prec
## [1] 2.714979e-06
La solución puede visualizarse en la salida $root
, el valor \(f(p)\) en la salida $f.root
y el número de iteraciones en $niter
. Para obtener más información, consulte la documentación oficial.
Sin importar la opción que se utilice, se llega a que \(p \approx 0.8423\) para que el jugador \(A\) gane al menos la mitad de los partidos que juegue.
NR es un método poderoso y simple para encontrar la solución de ecuaciones no lineales. A pesar de esto, no carece de inconvenientes:
Figure 3.1: El punto inicial es un punto de derivada nula.
Burden, Richard L.; and J. Douglas Faires. 2011. “Solutions of Equations in One Variable.” In Numerical Analysis, 9th ed., 78. Boston.
Keller, Joseph B. 1984. “Probability of a Shutout in Racquetball.” SIAM Review 26 (2): 267–68. https://doi.org/10.1137/1026037.
Lee, Elisa T., and John Wenyu Wang. 2003. “Appendix A.” In Statistical Methods for Survival Data Analysis, 428. Wiley Series in Probability and Statistics. Hoboken, NJ, USA: John Wiley & Sons, Inc. https://doi.org/10.1002/0471458546.
WikiHow. 2018. “How to Play Racquetball - with pictures.” https://www.wikihow.com/Play-Racquetball.
Wikipedia. 2018. “Racquetball.” https://en.wikipedia.org/wiki/Racquetball.