Una raíz múltiple corresponde a un punto donde una función es tangente al eje x. Por ejemplo, una raíz doble resulta de
f(x) =
(x-3)(x-1)(x-1)
multiplicando
términos este polinomio luce como
f(x) = x3 -
5x2 + 7x – 3
En la siguiente figura podemos ver como la
función toca tangencialmente el eje de la x, en el punto donde existe la raíz
doble.
De la figura podemos ver algunos de los
problemas asociados con raíces múltiples, dichos problemas son:
Dado que la función no cambia de signo,
utilizar métodos basados en intervalos, como son el método de bisecciones,
regula Falsi, etc. Otro problema es que
cerca de la solución, la derivada tiende a cero, lo cual provoca que en el
algoritmo de Newton-Raphson tenga problemas de convergencia al tener una
división por cero.
Ralston y Rabinowitz (1978) proponen que se
haga un pequeño cambio en la formulación para que retorne la convergencia, así
la formulación para el método de Newton-Raphson es
en donde m, es la multiplicidad de la
raíz. Para este caso será necesario conocer a priori el número de raíces
multiples.
Otra alternativa propuesta por Ralston y
Rabinowitz (1978) es la de definir una nueva función u(x), que es el cociente
de la función y su derivada
Se puede mostrar esta función tiene las mismas
raíces que f(x) y que la multiplicidad de raíces no afectará. La
formulación del método de Newton-Raphson es:
La derivada de u(x) es:
Sustituyendo esta, tenemos la formulación final del Método de Newton-Raphson modificado.
Ejemplo.
Hacer una comparación entre el método de
Newton-Raphson y el método de Newton-Raphson modificado, para encontrar las raíces
del polinomio f(x) = x3 - 5x2 + 7x – 3.
Para nuestro calculo requerimos de:
f(x) = x3 - 5x2 + 7x – 3
f’(x) =3 x2 - 10x + 7
f’’(x) = 6x –10
Primeramente resolvemos con x0 =
0.
Newton-Raphson |
|
|
Newton-Raphson modificado |
|||
k |
xk |
f(xk) |
|
k |
xk |
f(xk) |
0 |
0 |
-3 |
|
0 |
0 |
-3 |
1 |
0.42857143 |
-0.83965015 |
|
1 |
1.10526316 |
-0.02099431 |
2 |
0.68571429 |
-0.22859475 |
|
2 |
1.00308166 |
-1.8964E-05 |
3 |
0.8328654 |
-0.06053668 |
|
3 |
1.00000238 |
-1.1343E-11 |
4 |
0.91332989 |
-0.01567446 |
|
|
|
|
5 |
0.95578329 |
-0.00399668 |
|
|
|
|
6 |
0.9776551 |
-0.00100975 |
|
|
|
|
7 |
0.98876617 |
-2.54E-04 |
|
|
|
|
8 |
0.99436744 |
-6.36E-05 |
|
|
|
|
9 |
0.99717977 |
-1.59E-05 |
|
|
|
|
10 |
0.99858889 |
-3.99E-06 |
|
|
|
|
11 |
0.9992942 |
-9.97E-07 |
|
|
|
|
12 |
0.99964704 |
-2.49E-07 |
|
|
|
|
13 |
0.9998235 |
-6.23E-08 |
|
|
|
|
14 |
0.99991175 |
-1.56E-08 |
|
|
|
|
15 |
0.99995587 |
-3.89E-09 |
|
|
|
|
16 |
0.99997794 |
-9.74E-10 |
|
|
|
|
17 |
0.99998897 |
-2.43E-10 |
|
|
|
|
18 |
0.99999448 |
-6.09E-11 |
|
|
|
|
La solución con x0 = 4
Newton-Raphson |
|
|
Newton-Raphson modificado |
|||
k |
xk |
f(xk) |
|
k |
xk |
f(xk) |
0 |
4 |
9 |
|
0 |
4 |
9 |
1 |
3.4 |
2.304 |
|
1 |
2.63636364 |
-0.97370398 |
2 |
3.1 |
0.441 |
|
2 |
2.82022472 |
-0.5956347 |
3 |
3.00869565 |
0.03508572 |
|
3 |
2.96172821 |
-0.1472843 |
4 |
3.00007464 |
2.99E-04 |
|
4 |
2.99847872 |
-6.08E-03 |
5 |
3.00000001 |
2.23E-08 |
|
5 |
2.99999768 |
-9.27E-06 |
6 |
3 |
-1.07E-14 |
|
6 |
3 |
-2.15E-11 |
Note que cuando existe una raíz múltiple (en el caso de x=1), el algoritmo de Newton Raphson modificado, tiene mejor comportamiento, que cuando no es el caso de raíz múltiple (x=3).
Implementación en Java.
/**
* <p>Title: Metodo de Newton Raphson Modificado</p>
* <p>Description: Compara los métodos de Newton</p>
* <p>Copyright:
Copyright (c) 2003</p>
*
<p>Company: UMSH</p>
* @author Dr. Felix Calderon Solorio.
* @version 1.0
*/
public class ej059 {
public static
void main(String[] args) {
Newton_Raphson(0,
1e-10);
Newton_Raphson_Modificado(0, 1e-10);
}
public static double
Newton_Raphson(double x0, double T)
{
int i =0;
double x =
x0;
while(Math.abs(f(x)) > T)
{
System.out.println("Iteracion " +
i++ + " " + x + " " + f(x));
x = x -
f(x)/df(x);
}
System.out.println("Iteracion " + i++ + " " + x +
" " + f(x));
return x;
}
public static
double Newton_Raphson_Modificado(double x0, double T)
{
int i =0;
double x =
x0;
while(Math.abs(f(x)) > T)
{
System.out.println("Iteracion " + i++ + " " + x +
" " + f(x));
x = x -
(f(x)*df(x))/(df(x)*df(x) - f(x)*ddf(x));
}
System.out.println("Iteracion " + i++ + " " + x +
" " + f(x));
return x;
}
public static
double f(double x)
{
return
(x*x*x - 5.0*x*x + 7.0*x - 3.0);
}
public static
double df(double x)
{
return
(3.0*x*x - 10.0*x + 7.0);
}
public static
double ddf(double x)
{
return
(6.0*x - 10.0);
}
}