raices de funciones metodos numericos

Captulo 1

Raices de funciones de unavariable

1.1. Introduccion

Muchos problemas de ingeniera se reducen a encontrar las raices de unafuncion, vale decir, encontrar los valores de x para los cuales se cumple f(x) =0.

En ocasiones lo que se busca es para que valores de x una funcion toma uncierto valor (g(x) = C), o cuando dos funciones son iguales (p(x) = q(x)).Obviamente estos casos se reducen al primero, considerando f(x) = g(x)Cy f(x) = p(x) q(x) respectivamente.

Si la funcion es lineal, entonces la resolucion es sencilla, pues alcanza condespejar el valor de x. El problema se complica cuando la funcion no eslineal.

Veamos el siguiente ejemplo:

3

4 CAPITULO 1. RAICES DE FUNCIONES DE UNA VARIABLE

El calor especco molar de una mezcla de gases en un motor de combustioninterna viene dado por la siguiente expresion:

Cv = 7.563 1126.4T cal/Kmol.K

Los gases, al llegar al cilindro del motor, sufren una compresion isentropicadesde el volumen V1 a V2 . La relacion de compresion en este motor es:

r = V1V2 = 6

Si la temperatura inicial de los gases es T1=333K y la relacion entre tempe-ratura y volumen viene dada por: T2

T1CvT dT = 1.986 ln

V1V2

calcule la temperatura nal de los gases en el cilindro del motor.

Es evidente que si sustitiumos la expresion de Cv en la integral y resolvemosesta, nos quedan terminos que dependen de lnT y 1/T , por lo tanto llega-mos a una ecuacion no lineal que hay que resolver para poder encontrar latemperatura nal de los gases.

Otro ejemplo clasico es el calculo de una raiz cuadrada de un numero P :x =

P , que se puede plantear como el encontrar la raiz positiva de la

funcion f(x) = x2 P

En el presente captulo expondremos algunas tecnicas numericas muy sen-cillas que permiten encontrar aproximaciones a raices de funciones de unavariable. Todas estas tecnicas son iterativas, vale decir que requieren algunvalor inicial aproximado de la solucion, o un intervalo donde se sospeche queexiste una raiz de la funcion, y luego, mediante la aplicacion sistematica deuna regla o formula, ir mejorando esa aproximacion de manera iterativa, has-ta lograr un valor con la exactitud necesaria de acuerdo a la naturaleza delproblema que queramos resolver.

Para todas estas tecnicas es necesario tener en cuenta lo siguiente:

El metodo, si converge, lo hace a una, y solo una, de las raices de lafuncion. No necesariamente siempre converge, puede haber situacionesanomalas que hay que saber detectar.

Ningun de estas tecnicas numericas nos puede informar de antemano,cuantas raices tiene una funcion. Tampoco permiten encontrar varias

1.2. BISECCION 5

soluciones simultaneamente. Si una funcion tiene varias raices habra quedescubrirlas una a la vez.

Debe emplearse algun criterio para detener el proceso iterativo (criteriode convergencia).

No hay ninguna receta magica de como comenzar. Uno debe previa-mente analizar la funcion sobre la que va a trabajar y tratar de evaluardonde pueden existir soluciones y que valor o valores iniciales se puedenemplear para arrancar el metodo iterativo que uno haya elegido. Unaposibilidad elemental es evaluar la funcion para diferentes valores de xy ver donde ocurren cambios de signo, que puedan indicar la existenciade una raiz.

1.2. Biseccion

El metodo de biseccion es una tecnica que se basa en el teorema del valorintermedio:

Teorema del valor intermedio:Sea f(x) una funcion continua en un intervalo [a, b] . Entonces para cadavalor u tal que f(a) < u < f(b) , existe al menos un valor x = dentro de(a, b) tal que f() = u.

Basado en ese teorema, si encontramos un intervalo [a, b] en el cual la funcioncambia de signo (vale decir que se cumple que f(a)f(b) < 0), y f(x) escontnua, entonces dentro del intervalo [a, b] debe existir al menos un valorx = para el cual f() = 0. En realidad podemos decir que existe un numeroimpar de raices.

Para aplicar este metodo, entonces, es requisito previo encontrar al menos unintervalo [a, b] donde la funcion cambie de signo. Una vez que encontramosese intervalo, podemos aplicar el siguiente procedimiento iterativo:

1. calcular el punto medio del intervalo [a, b]: p = a+b2

2. evaluar en cual de los dos nuevos subintervalos creados [a, p] o [p, b]ocurre el cambio de signo de la funcion y quedarse con ese subintervalo:

si f(a)f(p) < 0 entonces asignar a b el valor de p


si f(p)f(b) < 0 entonces asignar a a el valor de p

3. evaluar la convergencia para el nuevo intervalo [a, b] obtenido:

si |a b| > entonces volver al punto (1) (continuar iterando)si |ab| entonces se llego a convergencia (se detiene el procesoiterativo)

Observese que el procedimiento es muy sencillo: en cada ciclo iterativo, re-duzco a la mitad el ancho del intervalo [a, b] con lo cual logro acotar, porizquierda y por derecha, el valor de la raiz.

Hasta cuando repito este procedimiento? Ahi es donde entra el criterio deconvergencia: el ancho del intervalo bisectado. Previo a comenzar el procesoiterativo debo elegir algun valor pequeno, llamemosle , de manera tal quecualquier valor x que diera en menos de del valor exacto de la raiz puedaser considerado una buena aproximacion al valor de la misma.

En este caso, si el ancho del ultimo intervalo [a, b] obtenido es menor que el que nos hayamos elegido, entonces tanto el valor de a como de b puede serconsiderado como una buena aproximacion al valor de la raiz que estamosbuscando y se detiene el proceso iterativo.

El valor de tambien determina cuantas cifras signicativas podemos emplearpara reportar el valor de la raiz obtenido.

El valor del ancho del ultimo intervalo obtenido [a, b] es tambien una cotasuperior al error absoluto que estamos cometiendo. Es evidente que tomamosel valor de a como aproximacion a la raiz, entonces lo peor que podra ocurrires que el valor verdadero de la raiz este cerca de b y viceversa.

La convergencia en realidad puede ser evaluada en terminos absolutos o enterminos relativos:

convergencia absoluta: |a b| Aconvergencia relativa: |ab|

R

Si empleamos criterio de convergencia relativo, obviamente que como no te-nemos el valor de , podemos emplear ya sea el valor de a o de b en su

1.2. BISECCION 7

lugar. Si multiplicamos por 100 entonces expresamos la convergencia relativacomo% del valor de la raiz.

Es indistinto cual de los dos criterios aplicar, pues es evidente que parala misma exactitud existe la relacion A R. Lo habitual es emplearconvergencia absoluta.

Ejemplo: Calcular2

Sabemos que el valor de2 se encuentra entre 1 y 2, por lo tanto podemos

tomar como intervalo inicial [1, 2]. La funcion que debemos evaluar pararesolver el problema es f(x) = x2 2. Elijamos un valor para epsilon de = 104. El aplicar el procedimiento anterior nos genera la siguiente tablade valores

iter a b |a b|0. 1. 2. 1.1. 1. 1.5 0.52. 1.25 1.5 0.253. 1.375 1.5 0.1254. 1.375 1.4375 0.06255. 1.40625 1.4375 0.031256. 1.40625 1.421875 0.0156257. 1.4140625 1.421875 0.00781258. 1.4140625 1.4179688 0.00390639. 1.4140625 1.4160156 0.001953110. 1.4140625 1.4150391 0.000976611. 1.4140625 1.4145508 0.000488312. 1.4140625 1.4143066 0.000244113. 1.4141846 1.4143066 0.000122114. 1.4141846 1.4142456 0.0000610

Como se desprende de la tabla, comenzamos con el el intervalo inicial [1, 2],que corresponde a la iteracion cero. Al cabo de la primer biseccion, ya hemosreducido el intervalo a [1, 1.5]. Luego a [1.25, 1.5] en la iteracion 2, etc. Encada iteracion evaluamos el ancho del intervalo |a b| y lo comparamos connuestro valor elegido de . Recien al llegar a la iteracion 14 encontramos unvalor de ancho del intervalo que cumple el criterio de convergencia |a b| < y ah detenemos el proceso iterativo.

Como el valor de es 104, solo podemos reportar 4 cifras luego del puntodecimal: 1.4142


Si queremos obtener una mejor aproximacion, debemos elegir un valor de mas pequeno.

Si bien el metodo de biseccion es un metodo muy robusto y conable, adolecedel defecto de que la convergencia es lenta. En cada iteracion el error cometidose reduce solo a la mitad, como se desprende facilmente de los valores de latabla.

Sin embargo es un metodo muy sencillo de implementar en computadora,por lo que el defecto de su lentitud de convergencia se disimula, si estamosresolviendo problemas sencillos.

En la practica se usan con mayor frecuencia metodos iterativos con mayo-res ratios de convergencia, como Newton-Raphson o Secante que veremosmas adelante pero nunca esta de mas recordar que este simple metodo sedemuestra muy robusto en situaciones donde Newton-Raphson o Secante noconvergen o muestran problemas de convergencia.

1.2.1. Convergencia del metodo

Como mencionabamos mas arriba, en cada iteracion el ancho del intervalode trabajo se reduce a la mitad, lo que determina que la convergencia de estemetodo sea lineal. Esto es, existe una relacio`n lineal entre el error cometidoen una iteracio`n y la siguiente: i+1 = i/2

Debido a la predecibilidad de la convergencia de este metodo, dado un in-tervalo inicial [a, b] y un criterio de convergencia , es perfectamente posiblepredecir cuantas iteraciones van a necesitarse para llegar a convergencia: concada iteracion el ancho del intervalo se reduce a la mitad, por lo tanto, luegode n iteraciones el ancho del intervalo sera |ab|

2n, donde a y b son los valores

correspondientes al intervalo inicial.

Dado es posible predecir cuantas iteraciones seran necesarias para llegar aconvergencia:

|ab|2n

< de donde n log2

|ab|

1.3. REGULA-FALSI 9

1.2.2. Casos problematicos

En la gura 1.1 se muestran algunas situaciones problematicas en la aplica-cion de este metodo u otros similares.

a aa

bb

b

1 2 3

Figura 1.1: Casos problematicos

Caso 1: podra ocurrir que la funcion tuviese una raiz doble en el intervaloque estemos considerando. Como la condicion para arrancar el metodo esdisponer de un intervalo donde la funcion cambie de signo, no seramos capa-ces de detectar esta situacion. Si sospechamos que la funcion tiene una raizdoble y la funcion y su derivada primera son contnuas en ese intervalo, unasolucion es buscar la raiz de la derivada primera de la funcion, ya que ambascomparten la misma raiz.

Caso 2: podra ocurrir que en el intervalo [a, b] elegido la funcion cambia designo, pero no una vez, sino un numero impar de veces. Es evidente que eneste caso lo que va a ocurri es que el metodo nos va a permitir encontrar unade esas raices, pero nos vamos a perder la existencia de las otras dos.

Caso 3: el que una funcion cambie de signo no siempre indica que existeuna raiz en ese intervalo. Podran haber discontinuidades o puntos y regionesde no existencia de la funcion. Para asegurarnos que lo que encontramos esefectivamente una raiz, debemos vericar que los valores funcionales tambientienden a cero al acercanos al valor de la raiz que buscamos. Ojo: no debemosemplear el criterio f(a) 0 o f(b) 0 como convergencia.

1.3. Regula-Falsi

Este metodo iterativo es similar al anterior en cuanto a que tambien se traba-ja desde un intervalo [a, b], donde la funcion cambia de signo, pero en lugar de


bisectar el intervalo, lo que hacemos es calcular la interseccion de la recta queune los valores funcionales en los extremos del intervalo, (a, f(a)) y (b, f(b)),con el eje de las abcisas y tomar ese punto como un extremo de un nuevosubintervalo. Luego, con el mismo analisis de signos que aplicamos en bisec-cion dedicimos con cual de los dos subintervalos generados nos quedamos yrepetimos el procedimiento.

La formula iterativa que aplicamos en este caso es:

pi+1 = bi f(bi) bi aif(bi) f(ai) (1.1)

el valor de pi+1 en la ecuacion 1.1 divide al intervalo [ai, bi] en dos subinter-valos. Dependiendo de en que subintervalo ocurra el cambio de signo es queeleminos el nuevo subintervalo donde continuar iterando:

si f(ai)f(pi+1) < 0 entonces ai+1 = ai y bi+1 = pi+1

si f(pi+1)f(bi) < 0 entonces ai+1 = pi+1 y bi+1 = bi

En la gura 1.2 se muestra un ejemplo con 3 iteraciones del metodo. Vemoscomo los cortes de las secantes con el eje de las abcisas se van acercando alvalor de la raiz .

a0 a1 = p1

f(a0)

f(b0) = f(b1) = f(b2)

f(a1) f(a2)

a2 = p2p3 b0 = b1 = b2

Figura 1.2: Regula-Falsi

1.3. REGULA-FALSI 11

1.3.1. Regula-Falsi modicado (Algoritmo de Illinois)

La gura 1.2 tambien ilustra uno de los defectos que tiene este metodo: sila funcion no muestra cambios de concavidad cerca de la raiz, entonces unode los extremos del intervalo se repite en todas las iteraciones y solo el otroextremo es el que se acerca a la raiz. En principio este metodo tiene el mismocriterio de convergencia que biseccion, pero si uno de los extremos se repite,entonces podra ocurrir que no acotamos por izquierda y derecha el valor dela raiz y nunca llega a cumplirse que |ai bi| < . Ademas, la repeticion deun extremo hace que la convergencia sea lenta.

Hay una variante, conocida con el nombre de Regula-Falsi modicado o Al-goritmo de Illinois, que resuelve este problema y ayuda a acelerar la conver-gencia del metodo.

La gura 1.3 illustra esta variacion, que consiste en emplear la mitad delvalor funcional del extremo que se repite en la ecuacion 1.1:

Si se repite bi entonces pi+1 =

12f(bi)aif(ai)bi12f(bi)f(ai)

Si se repite ai entonces pi+1 =f(bi)ai 12f(ai)bif(bi) 12f(ai)

(1.2)

a0 a1 = p1

f(a0)

f(b0) = f(b1)

f(a1)

p2 p2

b0 = b1

12f(b1)

p3

Figura 1.3: Regula-Falsi modicado

El la gura 1.3 vemos el valor que tomara p2 en regula-falsi normal y el


que toma al aplicar regula-falsi modicado p2. Como el extremo bi se siguerepitiendo, volvemos a aplicar regula-falsi modicado y se obtiene p3, y as secontinua mientras el extremo b se sigue repitiendo. Eventualmente el valorpi+1 cae del otro lado de la raiz y el extremo que se vena repitiendo deja derepetirse y se vuelve a la formula normal de regula-falsi.

Ejemplo: apliquemos este metodo al ejemplo del calculo de2 con el mismo

criterio de convergencia = 104:

iter ai bi |ai bi|0 1. 2. 1.1 1.3333333 2. 0.66666672 1.3333333 1.4545455 0.12121213 1.3927126 1.4545455 0.06183294 1.3927126 1.424283 0.03157055 1.4089259 1.424283 0.01535716 1.4089259 1.4167718 0.00784587 1.412908 1.4167718 0.00386388 1.412908 1.4148584 0.00195049 1.4138888 1.4148584 0.000969510 1.4138888 1.4143753 0.000486411 1.4141325 1.4143753 0.000242712 1.4141325 1.414254 0.000121513 1.4141933 1.414254 0.0000607

Vemos en la tabla que la velocidad de convergencia es lineal, mostrando unaperformance similar a la del metodo de Biseccion

1.4. Newton-Raphson

El metodo de Newton-Raphson se basa en el desarrollo en serie de Taylor dela funcion f(x) alrededor de un punto x0:

f(x) = f(x0) + (x x0)f (x0) + 12(x x0)2f (x0) + ... (1.3)

Truncando la serie a primer orden e igualando a cero, tenemos

1.4. NEWTON-RAPHSON 13

f(x) f(x0) + (x x0)f (x0) = 0 (1.4)

Esa es la ecuacion de la recta tangente que pasa por el punto (x0, f(x0)). Dela ecuacion 1.4 podemos despejar el valor de x que corresponde al corte dela recta tangente con el eje de las abcisas:

x = x0 f(x0)f (x0)

(1.5)

Si el comportamiento de f(x) fuese lineal, entonces el valor de x que cumpledicha ecuacion sera la raiz de la funcion. Esto da pie a la formula iterativade Newton-Raphson:

xi+1 = xi f(xi)f (xi)

(1.6)

que genera una sucesion de valores {xi} que, de converger, lo hace a la raiz de la funcion. El criterio de convergencia sera entonces la distancia entraaproximaciones consecutivas a la raiz:

|xi+1 xi| < (1.7)

La manera de aplicar esta formula es muy sencilla:

1. Se elige un criterio de convergencia y un valor inicial x0 cualquiera. Sies cercano al valor de la raiz buscada, mejor. Esta es la iteracion cero,por lo que i = 0

2. Se aplica la formula y se obtiene un valor xi+1, que es una mejor apro-ximacion a la raiz

3. Se evalua el criterio de convergencia:

Si |xi+1 xi| se incrementa el valor de i y volvemos al punto2

Si |xi+1 xi| < entonces el proceso iterativo ha convergido y seconsidera que xi+1 es una buena aproximacion a la raiz buscada


x0

x1

x2x3

f(x)

x

f(x0)

f(x1)

f(x2)

Figura 1.4: Newton-Raphson

La gura 1.4 ilustra el proceso iterativo en Newton-Raphson. A diferencia deBiseccion o Regula-Falsi, que requieren un intervalo [a, b] donde la funcioncambia de signo, en Newton-Raphson se arranca con un punto x0, cualquiera,y las sucesivas aplicaciones de la formula 1.6 generan una sucesion de valoresx1, x2, x3, ... que converge a la raiz .

Ejemplo: volvamos al caso del calculo de2. Tomando como valor inicial

x0 = 1 obtenemos la siguiente tabla:

i xi f(xi) |xi+1 xi|0 1. - 1. 1 1.5 0.25 0.52 1.4166667 0.0069444 0.08333333 1.4142157 0.0000060 0.00245104 1.4142136 4.5111012 0.00000215 1.4142136 4.4411016 1.5951012

Vemos como en este caso el proceso iterativo converge mucho mas rapida-mente que en biseccion. Si consideramos el criterio de convergencia = 104

podemos comprobar en la tabla que en la cuarta iteracion el valor ya cum-ple con dicho criterio, y que con una iteracion mas ya se logran 12 cifrassignicativas exactas.

1.4. NEWTON-RAPHSON 15

Nota: este metodo tambien puede usarse para encontrar raices. El unicorequisito para encontrar una raz compleja, en caso que f(x) la tenga, esarrancar el metodo con un valor x0 complejo.

1.4.1. Convergencia en el metodo de Newton-Raphson

Sea f(x) una funcion contnua, con derivadas contnuas, para la cual quere-mos encontrar una raiz . Podemos escribir el polinomio de Taylor de primergrado alrededor de xi, para el valor x = como:

f() = f(xi) + ( xi)f (xi) + 12( xi)2f (i) = 0 (1.8)

donde i es un numero entre y xi. Si dividimos la ecuacion 1.8 por f(xi)

obtenemos:

f(xi)

f (xi)+ ( xi) + 1

2( xi)2f

(i)f (xi)

= 0 (1.9)

que puede rearreglarse de la siguiente manera:

xi f(xi)

f (xi)

= 1

2( xi)2f

(i)f (xi)

(1.10)

Pero segun la formula de Newton-Raphson, el termino entre parentesis rectoses el valor de xi+1 y teniendo en cuenta que i = xi y i+1 = xi+1 sonlos correspondientes errores cometidos en las iteraciones i e (i+1), entonces:

i+1 = 12

f (i)f (xi)

2i (1.11)

que nos muestra que el error cometido en la iteracion (i+ 1) es propocionalal cuadrado del error cometido en la iteracion i, por lo que la convergenciadel metodo es cuadratica.


2 1.5 1 0.5 0.5 1 1.51

1

2

3

x

p(x)

Figura 1.5: problema de oscilacion en Newton-Raphson: p(x) = x3 2x+ 2

1.4.2. Casos problematicos

Si bien el metodo de Newton-Raphson funciona muy bien en la mayora de lassituaciones, y no requiere necesariamente arrancar con un valor x0 cercano auna raiz, hay ocasiones en que dependiendo del valor inical elegido, puedenhaber problemas de convergencia. Hay situaciones en las que el calculo puedeoscilar o incluso llegar a diverger.

En la gura 1.5 se muestra el caso de un polinomio para se puede dar unaoscilacion de la cual no es posible escapar. En este caso si tenemos la malafortuna de elegir x0 = 0 o x0 = 1, caemos en una oscilacion ya que para x = 0la tangente del polinomio corta el eje de las abcisas en x = 1 y cuando x = 1la tangente corta en x = 0 y el proceso iterativo queda atrapado entre estosdos valores. La manera de detectar este tipo de oscilaciones es vigilar losvalores de xi y vericar que |xi+1 xi| 0 a medida que avanza el procesoiterativo.

En la gura 1.6 se ilustra otra situacion problematica. No necesariamentepor arrancar en el punto b, cercano a la raiz a, se llega a ella. En este caso,debido al comportamiento de la derivada de f(x) el proceso iterativo terminadivergiendo a x . En cambio, arrancando en el punto c, se llega enpocas iteraciones al valor de la raiz. Incluso este ejemplo ilustra el por que nodebe usarse |f(x)| < como criterio de convergencia, porque como en estecaso f(x) 0 a medida que x , llegaremos a un valor de xi para elcual se cumpla |f(xi)| < y sin embargo el valor de xi no es la raiz. Siempredebe recordarse que la convergencia se mide sobre lo que se esta calculando,

1.5. METODO DE LA SECANTE 17

Figura 1.6: problema de divergencia en Newton-Raphson

en este caso la sucesion de valores xi.

1.5. Metodo de la Secante

Uno de los inconvenientes del metodo de Newton-Raphson es la necesidad deevaluar no solo la funcion f(x) sino tambien su derivada en cada iteracion.Una variante que elimina la necesidad de evaluar la derivada es aproximar elvalor de la derivada por la secante:

f (xi) f(xi) f(xi1)xi xi1 (1.12)

con lo que la formula de Newton-Raphson se convierte en la formula deSecante:

xi+1 = xi f(xi) xi xi1f(xi) f(xi1) (1.13)

Tal como se muestra en la gura 1.13, el metodo requiere dos valores de xpara arrancar: x0 , x1. La primer aplicacion de la formula da el valor x2,luego se vuelve a aplicar la formula pero ahora con los puntos x1 y x2 lo cualnos da el valor x3. El proceso iterativo eventualmente converge a la raiz buscada.


x0x1

x2

x3

f(x)

x

f(x0)

f(x1)

f(x2)

Figura 1.7: Secante

Ejemplo: nuevamente mostramos el calculo de2 para comparar con los

metodos anteriores. Necesitamos arrancar el metodo con dos valores, x0 = 1y x1 = 2. Aunque en este caso la funcion cambia de signo entre estos dospuntos, esto no es requisito para elegir esos primeros dos puntos del metodo.Se pueden elegir dos puntos cualesquiera. El proceso iterativo, para un valorde = 104 se muestra en la tabla siguiente:

i xi xi+1 |xi+1 xi|0 1. 2. 1.1 2. 1.3333333 0.66666672 1.3333333 1.4 0.06666673 1.4 1.4146341 0.01463414 1.4146341 1.4142114 0.00042275 1.4142114 1.4142136 0.0000021

En este caso se puede apreciar que la velocidad de convergencia del metodoes similar a la de Newton-Raphson, costando apenas una iteracion mas.

raices de funciones metodos numericos

Documents