Newton-Raphson

 

  • Introducción y antecedentes (para qué sirve y qué resuelve)

 

De los métodos que se usan para localizar raíces, la fórmula de Newton Raphson es la más usada. Este método se deduce a partir de la serie de Taylor. Cabe mencionar que este método tiene una adaptación para encontrar raíces múltiples, pero en este blog no se hablará de ello, sólo del que sirve para encontrar una raíz.

 

  • En qué consiste el método

 

Se da un valor inicial  para que podamos utilizar el método. A partir de este se puede trazar una tangente desde el punto [xi,f(xi)]. El punto en donde esta tangente cruza al eje x. Y de ahí se repite el proceso hasta que nos acerquemos a la raíz, es decir nuestra tangente sea 0.

 

Resultado de imagen para newton raphson formula

Fórmula del método

 

  • Requisitos previos del método

 

Se debe de dar un punto para a partir de este empezar a iterar, para que el proceso sea más óptimo en tiempo y disminuya el tiempo de iteraciones en necesario que el punto ingresado no esté tan alejado de la raíz.

 

  • Diagrama de flujo

 
diagrama

 

  • Criterio de detención del método (error):

 

Existen dos casos de detención para este método, declarados en nuestro código:

  1. Cuando las iteraciones han superado el número máximo de iteraciones (lo que nos dice que la función diverge).
  2. Cuando la diferencia entre x0 y x1 es menor que la tolerancia que permite el error.

 

 

 

 

 

  • Pruebas y resultados con casos de éxito, casos de falla y casos frontera

 

 

Función Punto introducido Error considerado Resultado de la raíz real Resultado obtenido con el método Problema
f(x)=ln(x)/x 2.75 0.00001 1 No se obtiene, el programa se cicla. El punto que se dio está muy alejado a la raíz y se tarda en encontrarla
f(x) = ln(x) 0 0.00001 1 Inf En la derivada se crea una división entre 0
f(x) = |x| 3 0.00001 0 No obtenemos resultado. La derivada de la raíz no existe y tiene dos diferenciales
f(x)=x+cos(x) 0 0.0001 -0.739085 -0.739085 NA

 

 

 

libro

En esta imagen se representan algunos casos en los que el método de Newton Raphson no funciona. Debido a que se cicla infinitamente o encuentra un punto en el cual la tangente es cero.

 

 

  • Conclusiones

 

 

Este método, comparado con el de bisección, ha logrado destacarse por encontrar los valores de la raíz en menos iteraciones, aunque, como el método antes mencionado existen casos donde el resultado de la raíz de la función no va ser encontrado. Por lo que es importante poner atención la tolerancia que le damos al programa para encontrar el resultado, el valor que le damos como inicial y el tipo de función que estamos intentando resolver.

Creemos que este tipo de actividades nos ayudan a ver la variedad de métodos que existen para resolver problemas, por lo que debemos saber identificar qué tipo de función estamos intentando resolver para poder elegir el método que sea más eficiente para encontrar el resultado que deseamos.

 

Sandra Alcaraz y Juan Abaroa


Método de Newton-Raphson

Introducción y antecedentes

El método de Newton-Raphson es un método numérico que encuentra las raíces de funciones. A diferencia del método de bisección, este es abierto. Esto se refiere a que es capaz de encontrar raíces en toda la función, no solo en un intervalo dado previamente.

Este método depende de varias aproximaciones lineales que se acercan mas al valor real con cada iteración.

En qué consiste el método

El método llega a su aproximación de la raíz realizando varias iteraciones de la misma ecuación.

Requisitos previos del método
Diagrama de flujo
Criterio de detención del método (error)
Código fuente
Pruebas y resultados con casos de éxito, casos de falla y casos frontera
Conclusiones


Newton-Raphson

Introduction

This method finds a root of a one-variable function. By root, we mean x | f(x) = 0.

Method

Newton-Raphson method works on a startup value given as input. Iteratively, it calculates the next point with the following formula. xn = xm – f(xm) / d(xm), where d(x) is the derivative of f(x). This formula runs on the following principle: getting the cut with the X axis of the straight line that is tangent to the curve in xm returns us xn, which is closer to the root than xm. Doing this iteratively, we can get a close value to the real root.

In order to work, this method requires a function to solve, a starting point and either a number for iterations, a maximum absolute error value or a maximum iterative error value (the most common is the second one).

Examples

All of these testings were done with a maximal absolute error of 1e-12:

  • f(x) = x³ – 3x² – 4x + 2 (x0 = -2, x = -1.2924, 7 iterations, 4 ms)
  • f(x) = sin(x) + x – 2 (x0 = 2, x = 1.10606, 7 iterations, 7 ms)
  • f(x) = e^x + x² – 2 (x0 = 2, x = 0.537274, 8 iterations, 6 ms)

Singularities

This method can only find one root for each run, meaning that one must know how many roots the function has and where are they found.

It has trouble in the following cases:

  • The function has a tiny or huge slope in a point

Some examples of functions that fail are:

  • f(x) = x¹⁰-1 (In this function, the slope close to the root gets bigger, so the program cuts less on each iteration. In this case, the program found the root (x = 1) on 45 iterations, but if we gave the program a smaller error, it would take a lot of iterations)
  • f(x) =log(abs(x)) (If we pass x0 = 10, the program returns a bigger value (with alternating symbols) each time, since the slope gets smaller on every iteration)

Flowchart

newton-raphson

Code

Conclusions

Newton-Raphson is better against bisection method in terms of performance, since the answer converges a lot faster. Due to this, this is the method used on most advanced calculators.

On the other hand, by receiving only one value, the method can diverge (which in case of bisection doesn’t happen).


Método de Bisección

Introducción y antecedentes

Obtener las raíces de una función de manera analitica puede volverse una tarea complicada en especial con funciones no polinómicas. La situación es mucho más evidente cuando queremos usar una computadora para encontrar las raíces. Los metodos analiticos son muy dificiles de implementar, por lo que es necesario encontrar métodos diferentes.

Un método que numerico que es capaz de aproximar raíces de manera eficiente es el de bisección. El único requerimiento para comenzar el método es que el usuario debe escoger un intervalo cerrado y la bisección se encarga de encontrar una raíz que se encuentre dentro.

En qué consiste el método

El método utiliza el algoritmo llamado búsqueda binaria para encontrar la raíz. Para comenzar, el método debe de checar si los signos de los límites del intervalo son distintos, significando que si hay una raíz dentro. Una vez que confirmamos la presencia de una raíz en el intervalo, comenzamos la búsqueda binaria empezando desde la mitad del intervalo. Dependiendo del signo de la función evaluada en este punto decidirá si el algoritmo se mueve hacia el lado derecho o izquierdo.. La búsqueda continúa hasta que llegamos a un valor que cuando es evaluado en la función es cercano a cero. Este valor es la aproximación de la raíz de la función.

Requisitos previos del método

Para comenzar, es necesario escoger una función que no vaya a causar problemas con el algoritmo. En la mayoría de los casos basta con que la función sea continua en el intervalo escogido. Para el intervalo es necesario que exista una raíz dentro. Esto se decide checando los signos en ambos lados del intervalo. Si los signos difieren, si existe una raíz.

Diagrama de flujo

flow

Criterio de detención del método

El método termina cuando el valor actual de x evaluado en la función es menor a cierto número. Personalmente usé 0.000001.

Código fuente

#include<iostream>
#include<cmath>
#define EPSILON 0.000001

using namespace std;

double f(double x){
    // Function here
    return log(x);
}

double bisection(double x0, double x1){
    if(f(x0) * f(x1) > 0.0){
        cout << "Invalid range" << endl;
        return NAN;
    }
    double xm = (x0 + x1)/2.0;
    while(abs(f(xm)) >= EPSILON){
        //cout << x0 << ", " << xm << ", " << x1 << endl;
        if(f(x0) * f(xm) < 0.0){
            x1 = xm;
        }
        else{
            x0 = xm;
        }
        xm = (x0 + x1)/2.0;
    }
    return xm;
}

int main(){
    // Min, Max here
    cout << bisection(0.0, 10.0) << endl;
}

Pruebas y resultados con casos de éxito, casos de falla y casos frontera

Éxitos

Funciones polinomiales:

3*pow(x, 3) + pow(x, 2) - 7*x
bisection(-100.0, 100.0) --> -2.20915

Logaritmo:

log(x)
bisection(0.0, 10.0) --> 0.999999

Fallas

Exponentes negativos:

1/x
bisection(-10.0, 10.0) --> El método no termina

Parábola sin parte negativa:

pow(x, 2)
bisection(-10.0, 10.0) --> Invalid Range

Fronteras

Cuando la raíz es uno de los límites del intervalo:

pow(x, 3)
bisection(0.0, 5.0) --> No termina

Se pueden añadir condicionales para corregir este caso.

Conclusiones

El método de bisección cumple con su función en la mayoría de los casos. Mientras la función sea continua y el intervalo válido no debería de haber problemas. Aún mejor es que el método es amigable con la manera que la computadora procesa los datos, pues llega a la respuesta de manera veloz y eficiente. El método no es muy confiable a menos de que se conozca bien a la función y al intervalo.


Bisección

Solución Numérica de Ecuaciones no Lineales y Polinomios

  • Introducción y antecedentes (para qué sirve y qué resuelve) 

El método de bisección es un método que nos ayuda a encontrar las raíces de una función con iteraciones. Los métodos de búsqueda incremental aprovechan que la raíz de una función se encuentra entre dos puntos que tienen signos opuestos. Por esto la localización del punto donde hay cambio de signo es la raíz. Para que este método sea más exacto se deben de dividir el intervalo en varios subintervalos, entre estos se busca el cambio de signo.

  • En qué consiste

También se conoce como corte binario, es un método de búsqueda incremental en el cual el intervalo siempre se divide a la mitad. Si la función cambia de signo sobre un intervalo, se evalúa el valor de la función en el punto medio. La posición de la raíz la determinamos a partir del punto medio del subintervalo, dentro del cual ocurre el cambio de signo. Esto se repite hasta tener una mejor aproximación.

  • Requisitos previos

Se necesitan tener dos puntos, los cuales deben de tener un resultado tal que  estos dos puntos evaluados en la función necesitan tener diferente signo entre ellos, para que el método sea efectivo.

Además los puntos de la función necesitan tener partes positivas

  • Diagrama de flujo

bicc

  • Criterio de detención

Existen 3 criterios de detención para este método:

  1. Cuando la evaluación de la función en el punto medio del intervalo de los valores dado es 0.
  2. Cuando la evaluación de la función con el primer valor del intervalo es 0.
  3. Cuando la evaluación de la función con el segundo valor del intervalo es 0.
  • Código fuente

biseccionh

  • Pruebas y resultados con casos de éxito, casos de falla y casos frontera
Función Raíces a y b intervalos introducidos Resultado con método
f(x)=x2+3x-4 -4 y 1 (-5 , -2)

(-1, 4)

-4 y 1

(éxito)

f(x)=x2+3x+4 no aplica
f(x)= -0.5

0.5

(-2,0)

(0,3)

-0.5

0.5 (éxito)

f(x)=x2 0 (-2,3) (fracaso)

loop infinito

  • Conclusiones

Para que el método sea efectivo se necesita que los puntos graficados de la función sean por lo menos unos negativos, ya que el método necesita que puntos evaluados tengan diferente signo.

El método no es muy efectivo, debido a que no es un método universal que sirva para todas las funciones. Además que las iteraciones que pueden ser demasiadas y el método no puede ser rápido.

Para la resolución de los problemas, es necesario aplicar métodos donde los resultados sean precisos y eficaces, por lo que consideramos este método puede presentar problemas en la obtención del resultado, dificultando así, ser considerado como una primera opción.

Equipo: Sandra Alcaraz y Juan Abaroa


Método de Bisección

Introducción

La función del método de bisección es encontrar la raíz de una ecuación y consiste en elegir un intervalo [a,b] para luego ir dividiendo ese intervalo en mitades hasta dar con la raíz. Para que este método sea posible debe ocurrir un cambio de signo, tal que, f(a)*f(b)<0.

Si f es continua en [a, b] y f(a) f(b) < 0, el método de bisección genera una sucesión  que aproxima un cero c de f con la propiedad que:  , n 1

Algoritmo

Paso 1: Elija valores iniciales inferior, x1, y superior, x2, que encierren la raíz, de forma tal que la función cambie de signo en el intervalo. Esto se verifica comprobando que f(x1) f(x2) < 0.

Paso 2: Una aproximación de la raíz xr se determina mediante: xr=(x1+x2)/2

Paso 3: Realice las siguientes evaluaciones para determinar en qué subintervalo está la raíz:

  1. a) Si f(x1 )f(xr ) < 0, entonces la raíz se encuentra dentro del subintervalo inferior o izquierdo. Por lo tanto, haga x2 = xr y vuelva al paso 2.
  2. b) Si f(x1 )f(xr ) > 0, entonces la raíz se encuentra dentro del subintervalo superior o derecho. Por lo tanto, haga x1 = xr y vuelva al paso 2.
  3. c) Si f(x1 )f(xr ) = 0, la raíz es igual a xr, o cuando el valor es menor que el error mínimo, es decir f(xr) <= abs(Errormínimo). termina el cálculo.

Requísitos previos

Para poder utilizar el método se debe de conocer un intervalo [a,b] en donde la función contenga una raíz y sea continua.

Diagrama de flujo

 

Criterio de detención

 

Para detener el método de bisección y dar una aproximación del cero de una función se examina si |f(cn)| < , donde es una tolerancia previamente establecida (por ejemplo = 10-12).
También se puede usar como criterio de parada el error relativo entre dos aproximaciones del cero de f ,
En el ejemplo anterior si =0.005, el procedimiento se pararía en la octava iteración con el criterio |f(cn)|< , ya que:
|f(c8)| = |f(1.1171875)| = 0.004208 < = 0.005,
pero si se usa el criterio , el procedimiento se detendría en la novena iteración porque:

Código C++

https://github.com/Estefycp/M-todosNumericos/blob/master/Biseccion/BiseccionTerminado.cpp

Pruebas

pruebas

Conclusiones

El método de bisección tiene la desventaja que es lento en cuanto a convergencia (es decir que se necesita un n grande para que sea pequeño). Otros métodos requieren menos iteraciones para alcanzar la misma exactitud, pero entonces no siempre se conoce una cota para la precisión. Cuando hay raíces múltiples, el método de bisección quizá no sea válido, ya que la función podría no cambiar de signo en puntos situados a cualquier lado de sus raíces. Una gráfica es fundamental para aclarar la situación. En este caso sería posible hallar los ceros o raíces trabajando con la derivada f’(x), que es cero en una raíz múltiple.

 


Bisection

Introduction

This method finds a root of a one-variable function. By root, we mean x | f(x) = 0.

Method

Bisection method works on an interval given as input. Iteratively, it divides the interval into two equal intervals, and chooses one based on the following principle: the root will be found where the first value of the interval is negative/positive and the second value is the opposite, since this implies the function goes through the X axis and the root is in that interval.

In order to work, this method requires a function to solve, an interval (two real numbers, the first one smaller than the second one) and either a number for iterations, a maximum absolute error value or a maximum iterative error value (the most common is the second one).

Examples

All of these testings were done with a maximal absolute error of 1e-12:

  • f(x) = x³ – 3x² – 4x + 2 ([-2, 0], x = -1.2924, 42 iterations, 7 ms)
  • f(x) = sin(x) + x – 2 ([1, 2], x = 1.10606, 39 iterations, 5 ms)
  • f(x) = e^x + x² – 2 ([0, 1], x = 537274, 41 iterations, 5 ms)

Singularities

This method can only find one root in each interval, meaning that one must know how many roots the function has and where are they found.

It has trouble in the following cases:

  • The function is non continuous in the interval given
  • The function contains multiple roots in the interval given

Some examples of functions that fail are:

  • f(x) = 1 / x – 1 (if we pass [-2, 2], the method has trouble since f(x) is discontinuous on x = 0)
  • f(x) = x⁴ – 14x³ + 71x² – 154x + 120 (if we pass [3, 4], the method can’t find anything, since the roots are on the first interval)

* In the code, there is a condition to detect roots on the beginning.

Flowchart

bisection

Code

Conclusions

In general, bisection method is not that good for solving problems. It works when one knows where the roots are and one only needs to get a good approximation of it. And, one must be careful to give an interval containing one and only one root, and the function must be continuous on that interval.


Método de Bisección

Introducción y antecedentes

El método de bisección se utiliza para encontrar una raíz aproximada de una función, que se buscará dentro de un intervalo inicial [a, b], en el cual ocurre un cambio de signo en la función evaluada, es decir, f(a)f(b) < 0, por lo que el intervalo [a, b] debe contener un valor c, donde f(c) = 0. El teorema del valor intermedio para funciones continuas, que establece que si f es continua en [a, b] y si k es un número entre f(a) y f(b), entonces existe por lo menos un c ∈ (a, b) tal que f(c) = k.

Algoritmo

  • Se eligen valores iniciales para a y b de tal forma que la función cambie de signo: f(a)f(b) < 0.
  • Se bisecta el intervalo [a, b], calculando el punto intermedio con x = (a + b) / 2, este será la primera aproximación a la raíz.
  • Se selecciona el sub-intervalo en el que la raíz se debe de encontrar:
    • Si f(a)f(b) < 0, entonces la raíz se encuentra en (a, x), ahora b = x.
    • Si f(a)f(b) > 0, entonces la raíz se encuentra en (x, b), ahora a = x.
  • Este proceso se repite hasta encontrar el valor de la raíz o uno muy cercano a ella, es decir, cuando f(x) ≤ |ε|.

Requisitos previos

Para poder utilizar el método de bisección se debe saber de antemano un intervalo en donde la función contiene una raíz, además, la función debe ser continua en [a, b].

Diagrama de Flujo

bisectionMethod.png

Criterio de detención

El método de bisección se detienen cuando se encuentra un valor c ∈ (a, b) tal que f(c) ≤ |ε|, donde ε es un valor próximo a cero. También se puede definir un número máximo de iteraciones para que el método se vea forzado a finalizar si no encuentra un valor que cumpla con los requisitos de terminación.

Código en c++


#include <cmath>
 
#define ITER 1000
#define MINERR 1E-15
 
typedef double (* vFunctionCall)(double x);
 
bool sameSign(double x, double y) {
  return x * y >= 0;
}
 
double biseccion(vFunctionCall fun, double x0, double x1) {
  double y0 = fun(x0);
  double y1 = fun(x1);
 
  if (y0 == 0) {
    return x0;
  } else if (y1 == 0) {
    return x1;
  }
 
  int i = 0;
  double x, y;
  while (i < ITER) {
    x = (x0 + x1) / 2;
    y = fun(x);
 
    if (abs(y) <= MINERR) {
      return x;
    }
 
    if (sameSign(y, y0)) {
      x0 = x;
      y0 = y;
    } else {
      x1 = x;
      y1 = y;
    }
    i++;
  }
 
  return x;
}

Pruebas:

Función Raices [a, b] Resultado
sin (x) + 2x – 1 0.335418 [-10, 10] 0.335418
x^3 – 6 x^2 + 3 x + 10 -1, 2, 5 [-200, 600] -1
x ^ 4 – 2 x ^ 3 – 3 x ^ 2 + 4 * x + 4 -1, 2 [-2, 3] f(a)f(b) < 0 (excepción)
x ^ 4 – 2 x ^ 3 – 3 x ^ 2 + 4 * x + 4 -1, 2 [-1, 2] -1
1 / x^3 y ≠ 0 [-1, 1] -1.86653e-301
1 / x^3 No hay [-999999999999999999, 999999999999999999] -5e+17

Conclusiones

El método de bisección es el método más antiguo y elemental para determinar las raíces de una ecuación. Tiene limitantes, pues se necesita saber de antemano en que rango se encuentra la raíz. En las pruebas podemos observar que el algoritmo continua aún cuando f tiende a infinito en [a, b] hasta alcanzar el limite de iteraciones. El código pueden encontrarlo en github: https://github.com/hermesespinola/metodos_numericos/tree/master/bisection


So the semester’s over…

Yes! It's all over now. And it’s the start of something else, too.

This is the time and place where I would want to talk about my experience on this course, #TC1019. Having Ken as our teacher taught me a lot of things about myself, and made me see things I considered normal and standard in a whole different scope. For all right and wrong, here’s my attempt at expressing all of it in video format:



Ken, thanks for everything. May our paths meet again someday.

I wish I knew as many song lyrics as you do so I could somehow make a pun out of this, but I just don’t. But as my last post this semester, I’ll just leave here a song I like very much that may fit this all… “The Last Song”: