Mtodo de Newton

Mtodo de Newton

En anlisis numrico, el mtodo de Newton (conocido tambin como el mtodo de Newton-Raphson o el mtodo de Newton-Fourier) es un algoritmo eficiente para encontrar aproximaciones de los ceros o races de una funcin real. Tambin puede ser usado para encontrar el mximo o mnimo de una funcin, encontrando los ceros de su primera derivada.

Descripcin del mtodo

La idea de este mtodo es la siguiente: se comienza con un valor razonablemente cercano al cero (denominado punto de arranque), entonces se reemplaza la funcin por la recta tangente en ese valor, se iguala a cero y se despeja (fcilmente, por ser una ecuacin lineal). Este cero ser, generalmente, una aproximacin mejor a la raz de la funcin. Luego, se aplican tantas iteraciones como se deseen.

Supngase f: [a, b] -> R funcin derivable definida en el intervalo real [a, b]. Empezamos con un valor inicial x0 y definimos para cada nmero natural n

Donde f' denota la derivada de f.

Obtencin del Algoritmo [editar]Tres son las formas principales por las que tradicionalmente se ha obtenido el algoritmo de Newton-Raphson.

La primera de ellas es una simple interpretacin geomtrica. En efecto, atendiendo al desarrollo geomtrico del mtodo de la secante, podra pensarse en que si los puntos de iteracin estn lo suficientemente cerca (a una distancia infinitesimal), entonces la secante se sustituye por la tangente a la curva en el punto. As pues, si por un punto de iteracin trazamos la tangente a la curva, por extensin con el mtodo de la secante, el nuevo punto de iteracin se tomar como la abcisa en el origen de la tangente (punto de corte de la tangente con el eje X). Esto es equivalente a linealizar la funcin, es decir, f se reemplaza por una recta tal que contiene al punto (x0, f (x0)) y cuya pendiente coincide con la derivada de la funcin en el punto, f'(x0). La nueva aproximacin a la raz, x1, se logra la interseccin de la funcin linear con el eje X de ordenadas. Matemticamente:

Ilustracin de una iteracin del mtodo de Newton (la funcin f se demuestra en azul y la lnea de la tangente est en rojo). Vemos que xn + 1 es una aproximacin mejor que xn para la raz x de la funcin f.

En la ilustracin adjunta del mtodo de Newton se puede ver que xn + 1 es una mejor aproximacin que xn para el cero (x) de la funcin f.

Una forma alternativa de obtener el algoritmo es desarrollando la funcin f(x) en serie de Taylor, para un entorno del punto xn:

Entonces, si se trunca el desarrollo a partir del trmino de grado 2, y evaluamos en xn + 1:

f(xn + 1) = f(xn) + f'(xn)(xn + 1 xn)

Si adems se acepta que xn + 1 tiende a la raz, se ha de cumplir que f(xn + 1) = 0, luego, sustituyendo en la expresin anterior, obtenemos el algoritmo.

Finalmente, hay que indicar que el mtodo de Newton-Raphson puede interpretarse como un mtodo de iteracin de punto fijo. As, dada la ecuacin f(x) = 0, se puede considerar el siguiente mtodo de iteracin de punto fijo:

g(x) = x + h(x)f(x)

Se escoge h(x) de manera que g'(r)=0 (r es la raz buscada). Dado que g'(r) es:

g'(r) = 1 + h'(r)f(r) + h(r)f'(r) = 1 + h(r)f'(r)

Entonces:

Como h8x) no tiene que ser nica, se escoge de la forma ms sencilla:

Por tanto, imponiendo subndices:

Expresin que coincide con la del algoritmo de Newton-Raphson

Convergencia del Mtodo [editar]El radio de convergencia de este mtodo es, por lo menos, cuadrtico. Sin embargo, si la raz buscada es de multiplicidad algebraica mayor a uno (i.e, una raz doble, triple,...), el mtodo de Newton-Raphson pierde su convergencia cuadrtica y pasa a ser lineal de constante asinttica de convergencia 1-1/m, con m la multiplicidad de la raz.

Existen numerosas formas de evitar este problema, como pudieran ser los mtodos de aceleracin de la convergencia tipo de Aitken o el mtodo de Steffensen. Derivados de Newton-Raphson destacan el mtodo de Ralsta-Ravinovitz, que restaura la convergencia cuadrtica sin ms que modificar el algoritmo a:

Evidentemente, este mtodo exige conocer de antemano la multiplicidad de la raz, lo cual no siempre es posible. Por ello tambin se puede modificar el algoritmo tomando una funcin auxiliar g(x)=f(x)/f'(x), resultando:

Su principal pega en este caso sera lo costoso que pudiera ser hallar g(x) y g'(x) si f(x) no es fcilmente derivable.

Por otro lado, la convergencia del mtodo se demuestra cuadrtica para el caso ms habitual en base a tratar el mtodo como uno de punto fijo: si g'(r)=0, y g(r) es distinto de 0, entonces la convergencia es cuadrtica. Sin embargo, est sujeto a las particularidades de stos mtodos.Ejemplo

Consideremos el problema de encontrar un nmero positivo x tal que cos(x) = x3. Podramos tratar de encontrar el cero de f(x) = cos(x) - x3.

Sabemos que f'(x) = -sin(x) - 3x2. Ya que cos(x) 1 para todo x y x3 > 1 para x>1, deducimos que nuestro cero est entre 0 y 1. Comenzaremos probando con el valor inicial x0 = 0.5

Los dgitos correctos estn subrayados. En particular, x6 es correcto para el nmero de decimales pedidos. Podemos ver que el nmero de dgitos correctos despus de la coma se incrementa desde 2 (para x3) a 5 y 10, ilustando la convergencia cuadrtica.

En pseudocdigo, esto es:

function newtonIterationFunction(x) {

return x - (cos(x) - x^3) / (-sin(x) - 3*x^2)

}

var x := 0.5

for i from 0 to 99 {

print "Iteraciones: " + i

print "Valor aproximado: " + x

xold := x

x := newtonIterationFunction(x)

if x = xold {

print "Solucin encontrada!"

break

}

Mtodo de Regula FalsiNos permite encontrar la raz de la ecuacin f(x)=0, donde f(x) es una funcin continua definida en el intervalo [a,b], con f(a) y f(b) de signos diferentes.Ejemplo

Encontrar las races de f(x)=x3-2x2-5=0, para ello necesitamos dos aproximaciones tomamos a=2 y b=3,ya que f(2)=-5 y f(3)=4, la tolerancia Tol=0.000001 y con N=10 iteraciones, obtenemos una raz en x = 2.690647. Cdigo en Visual Basic del ejemplo regula.zip (1.786 bytes)

Implementacin del algoritmo

Entrada a : extremo inferior

b : extremo superior

Tol : tolerencia

N : nmero mximo de iteraciones

Salida

Flag : me devuelve True si tuvo exito y False en caso de haber superado el numero de iteraciones, sin obtener la exactitud requerida.

Res : retorna la solucin de f(x) CdigoSub Regula_Falsi(ByVal a As Double, ByVal b As Double, ByVal Tol As Double, _

ByVal N As Integer, ByRef Flag As Boolean, ByRef r As Double)

Dim q, q0, q1, p As Double

Dim i As Integer

i = 2

q0 = f(a)

q1 = f(b)

Do While (i