Método de Newton-Raphson

feb. 25, 2020

El método de Newton-Raphson se basa en una aproximación de una función continua dos veces diferenciable por medio de su polinomio de Taylor de orden 2 $$ f(x) \approx f(x_0) + f’(x_0)(x-x_0) $$ si $x$ es una raíz de $f$, esto es $x \approx x_0 - \dfrac{f(x_0)}{f’(x_0)}$.

Este método es un ejemplo particular de método de punto fijo que convierte el problema de encontrar una raíz para $f(x)$ en un problema de encontrar el punto fijo de $g(x)=x_0 - \dfrac{f(x_0)}{f’(x_0)}$, sin embargo, para garantizar la convergencia del método se requiere tomar una aproximación inicial suficientemente cerca de la raíz de $f$. El siguiente teorema garantiza que siempre se puede encontrar una vecindad suficientemente pequeña de la raíz donde el método siempre converge:

Sea $f\in C^2[a,b]$. Si $p\in (a,b)$ es tal que $f(p)=0$ y $f’(p)\neq 0$, entonces existe una $\delta >0$ tal que el método de Newton genera una sucesión ${p_n}_{n=1}^{\infty}$ que converge a $p$ para cualquier aproximación inicial $p_0\in[p-\delta,p+\delta]$.

Diagrama de flujo

Código

El siguiente codigo implementa el método de Newton en C++:

///////////////////////////////////////////////////////////////////////////////////
// Programa para hallar la raíz de una función usando el método de Newton	 //
// El programa requiere subprogramas para las funciones f y f', 		 //
// el punto inicial p0, la tolerancia de error eps, y el máximo número 		 //
// de iteraciones permitidas, kmax. 						 //
// El programa muestra una tabla con los valores de x y su evaluación en f.	 //
///////////////////////////////////////////////////////////////////////////////////
# include <iostream>
# include <iomanip>
# include <math.h> // para log x
using namespace std; // Para usar cout

long double f(long double x); // Declara la función f
long double fprima(long double x); // Declara la derivada de f

int main(){
    int kmax;
    long double p0, p, eps;
    cout << "p0, eps, kmax\n";
    cin >> p0 >> eps >> kmax;
    // Verificamos que los valores ingresados permitan usar el algoritmo
    while(isnan(f(p0)) || isnan(fprima(p0))){
        if(isnan(f(p0)))
            cout << "La funcion no esta definida en " << p0;
        else if(isnan(fprima(p0)))
            cout << "La derivada de la funcion no esta definida en " << p0;
   		cout << "Ingrese nuevamente una aproximacion inicial p0\n";
   		cin >> p0;
    }
    cout << "Los valores ingresados son \n";
    cout <<  "p0= " << p0 << " eps = " << eps << "  kmax = " << kmax << endl;
    cout << "Los resultados son\n"; // Muestra el encabezado de la tabla
    cout << "k" << setw(15) << "x" << setw(22) << "f(x)\n"; 
    int k=0;
    p=p0;
    cout.setf(ios::fixed);
    while ((k<=kmax) && (fabs(f(p0))>eps)){
        // Muestra los valores de k, p y f(p)
        cout << k << setprecision(10) << setw(20) << p << setw(20) << f(p)
             << endl;
        k++; // incrementa el contador del ciclo
        p0=p; 
        p=p-f(p)/fprima(p);
    };
    if (fabs(f(p))<=eps) cout << "La raiz de f es " << p0; 
    else if (k>kmax) cout << "El metodo no converge en " << kmax << " pasos";
    return 0;
}
// El subprograma para ingresar la función f
long double f(long double x){
    return cos(x)-x;
}

// El subprograma para ingresar la derivada f'
long double fprima(long double x){
    return -sin(x)-1;
}

José Luis León Medina

Investigador Posdoctoral CONAHCYT

Mis intereses en investigación se centran en el campo de la topología algebraica, en particular propiedades homotópicas como la complejidad topológica.