1. Método de Newton-Raphson - ¿qué es?

Referencia: Burden 2.3 p49, Chapra 6.2 p148, Rodríguez 3.3 p52

Se deduce a partir de la interpretación gráfica o por medio del uso de la serie de Taylor de dos términos.

De la gráfica, se usa el triángulo formado por la recta tangente que pasa por f(x_i), con pendiente f'(x_i)  y el eje x.

El punto x_i+1 es la intersección de la recta tangente con el eje x, que es más cercano a la raíz de f(x), valor que es usado para la próxima iteración.

Reordenando la ecuación de determina la fórmula para el siguiente punto:

El error se determina como la diferencia entre los valores sucesivos encontrados |x_i+1 - x_i|

La gráfica animada muestra el proceso aplicado varias veces sobre f(x) para encontrar la raíz.

1.1 Recta Tangente para la gráfica

Si se quiere dibujar la recta tangente en el punto inicial, la ecuación de la recta se obtiene usando: el valor de la pendiente con la derivada f'(x) y cambiando la constante b por b0 para no confundirla con la b del intervalo [a,b]

Es necesario disponer de un punto conocido de la recta (x₀,f(x₀)) y la pendiente en ese punto f'(x₀), quedando solo el término de la constante como incógnita .

La función recta tangente se expresa para la gráfica como:

Tarea

Use la serie de Taylor hasta la primera derivada para encontrar el siguiente punto de aproximación x_i+1

2. Ejercicio

Referencia: Burden 2.1 ejemplo 1 p38

La ecuación mostrada tiene una raíz en [1,2], ya que f(1)=-5 y f(2)=14.

Muestre los resultados parciales del algoritmo de Newton-Raphson con una tolerancia de 0.0001

3. Desarrollo Analítico - ejemplo paso a paso

El método requiere  obtener la derivada f'(x) de la ecuación para el factor del denominador.

Para el desarrollo se inicia la búsqueda desde un punto en el intervalo [1,2], por ejemplo el extremo derecho, x₁=2.

iteración 1

iteración 2

iteración 3

La tabla resume los valores de las iteraciones

Observe que el error representado por el tramo se va reduciendo entre cada iteración. Se debe repetir las iteraciones hasta que el error sea menor al valor tolerado.

Las demás iteraciones se dejan como tarea

4. Algoritmo con Python para el método de Newton-Rapson

El método de Newton-Raphson se implementa con instrucciones básicas en el algoritmo en Python. Requiere la expresión f(x) y la derivada f'(x).

Se muestra el resultado del algoritmo luego de que el tramo alcance un valor menor que tolera.

Método de Newton-Raphson
itera  :  4
raíz en:  1.3652300139161466
errado :  3.200095847999407e-05

Se requiere añadir el control de iteraciones con iteramax en caso que el algoritmo NO sea convergente.

# Método de Newton-Raphson
import numpy as np

# INGRESO
fx  = lambda x: x**3 + 4*(x**2) - 10
dfx = lambda x: 3*(x**2) + 8*x

x0 = 2
tolera = 0.001
iteramax = 100

# PROCEDIMIENTO
itera = 0
tramo = abs(2*tolera)
xi = x0
while (tramo>=tolera and itera<iteramax):
    fi = fx(xi)
    dfi = dfx(xi)
    xnuevo = xi - fi/dfi
    tramo = abs(xnuevo-xi)
    xi = xnuevo
    itera = itera + 1

if itera>=iteramax:
    xi = np.nan

# SALIDA
print('Método de Newton-Raphson')
print('itera  : ', itera)
print('raíz en: ', xi)
print('errado : ', tramo)

5. Gráfica en Python

La gráfica se usa para revisar f(x), requiere indicar el intervalo [a,b] y el número de muestras en el intervalo:

# GRAFICA ---------------------
import matplotlib.pyplot as plt
a = 1
b = 2
muestras = 21
titulo = 'Newton-Raphson'

xj = np.linspace(a,b,muestras)
fj = fx(xj)
plt.plot(xj,fj, label='f(x)')
plt.plot(xi,0, 'o')
plt.axhline(0)
plt.xlabel('x')
plt.ylabel('f(x)')
plt.grid()
plt.legend()
plt.title(titulo)
plt.tight_layout()
plt.show()

6. Algoritmo en Python como Función para el método de Newton-Raphson

Se convierte el algoritmo a una función, con la opción para mostrar los resultados de las operaciones en cada iteración. Para el ejercicio se obtiene los siguientes resultados:

método de Newton-Raphson
i ['xi', 'fi', 'dfi', 'xnuevo', 'tramo']
0 [ 2.  14.  28.   1.5  0.5]
1 [ 1.5     2.375  18.75    1.3733  0.1267]
2 [1.3733e+00 1.3435e-01 1.6645e+01 1.3653e+00 8.0713e-03]
3 [1.3653e+00 5.2846e-04 1.6514e+01 1.3652e+00 3.2001e-05]
Método de Newton-Raphson
itera  :  4
raíz en:  1.3652300139161466
errado :  3.200095847999407e-05

Instrucciones en Python

# Método de Newton-Raphson
# Requiere fx y dfx
# x0 es el valor inicial para la búsqueda de raíz
import numpy as np

def newton_raphson(fx,dfx,x0, tolera, iteramax=100,
                   vertabla=False, precision=4):
    '''fx y dfx en forma numérica lambda
    xi es el punto inicial de búsqueda
    si no converge hasta iteramax iteraciones
    la respuesta es NaN (Not a Number)
    '''
    itera=0
    xi = x0
    tramo = abs(2*tolera)
    tabla=[]
    if vertabla==True:
        print('Método de Newton-Raphson')
        print('i', ['xi','fi','dfi', 'xnuevo', 'tramo'])
        np.set_printoptions(precision)
    while (tramo>=tolera):
        fi = fx(xi)
        dfi = dfx(xi)
        xnuevo = xi - fi/dfi
        tramo = abs(xnuevo-xi)

        unafila = np.array([xi,fi,dfi,xnuevo,tramo])
        tabla.append(unafila)
        if vertabla==True:
            print(itera,np.array([xi,fi,dfi,xnuevo,tramo]))
        xi = xnuevo
        itera = itera + 1

    if itera>=iteramax:
        xi = np.nan
        print('itera: ',itera,
              'No converge,se alcanzó el máximo de iteraciones')
    tabla = np.array(tabla,dtype=float)
    return(xi,tabla)

# PROGRAMA -------------------------
# INGRESO
fx  = lambda x: x**3 + 4*(x**2) - 10
dfx = lambda x: 3*(x**2) + 8*x

x0 = 2
tolera = 0.001
iteramax = 15
verdigitos = 4 # ver digitos en tabla

# PROCEDIMIENTO
xi,tabla = newton_raphson(fx,dfx,x0,tolera,iteramax,
                          vertabla=True,
                          precision=verdigitos)
n = len(tabla)
errado = tabla[n-1,4]

# SALIDA
print('Método de Newton-Raphson')
print('itera  : ', n)
print('raíz en: ', xi)
print('errado : ', errado)

7. Gráfica en Python para la función del método de Newton-Raphson

Requiere el intervalo [a,b] del eje x, la cantidad de muestras.

Para el caso de realizar la gráfica de una iteración particular, usar la variable itera_graf. Por ejemplo para las gráficas presentadas en cada iteración en la sección de desarrollo analítico.

Las instrucciones que se añaden al algoritmo como función son:

# GRAFICA ---------------------
import matplotlib.pyplot as plt

a = 1
b = 2
muestras = 21
itera_graf = 2 #n-1 # iteración en gráfica
titulo = 'Newton-Raphson'

xk = np.linspace(a,b,muestras)
fk = fx(xk)

xa = tabla[:,0]
ya = tabla[:,1]
xb = tabla[:,3]
dfi = tabla[:,2]
# Aproximacion con tangente
b0 = ya[itera_graf] - dfi[itera_graf]*xa[itera_graf]
tangentek = dfi[itera_graf]*xk + b0
ci = -b0/dfi[itera_graf]

plt.plot(xk,fk, label='f(x)')
if itera_graf==(n-1): # iteración final
    plt.plot(xi,0, 'o')
if itera_graf<(n-1): # una iteración en gráfica
    titulo = titulo+', itera='+str(itera_graf)
    plt.ylim([np.min(fk),np.max(fk)])
    plt.plot([xa[itera_graf],xa[itera_graf]],[0,ya[itera_graf]],'--',color='red')
    plt.plot(xa[itera_graf],ya[itera_graf],'o',color='red',label='xi')
    plt.plot(xk,tangentek,color='orange',label='tangente')
    plt.plot(ci,0,'o',color='green',label='x[i+1]')
    
plt.axhline(0)
plt.xlabel('x')
plt.ylabel('f(x)')
plt.grid()
plt.legend()
plt.title(titulo)
plt.tight_layout()
plt.show()

8. Función en librería scipy.optimize.newton

El método de Newton-Raphson se encuentra disponible también en la librería  Scipy, como uno de los métodos de optimización numérica. Usando el ejemplo y lo definido para el ejercicio se puede usar como:

>>> import scipy as sp
>>> sp.optimize.newton(fx,x0, fprime=dfx, tol = tolera)
1.3652300139161466
>>>

https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.newton.html

Tarea

Calcule la raíz de f(x) = e^-x - x, empleando como valor inicial x₀ = 0

• Revisar Resumen Sympy para obtener la derivada.