• Author / Uploaded
• Eduardo Cano Ibarra

Citation preview

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´etodos Num´ericos en Ingenier´ıa Soluci´on num´erica de funciones no-lineales Prof. N´estor Garc´ıa Chan †Depto. de Ciencias B´ asicas ITESM

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

1 Un problema medioambiental

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Descarga puntual de aguas residuales en un r´ıo

(a) http://www.agua.org.mx

(b) http://notired.com.mx

Figura: Descarga de aguas residuales y consecuencias medioambientales

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Descarga puntual de aguas residuales en un r´ıo

En ingenier´ıa ambiental la siguiente ecuaci´ on es utilizada para calcular el nivel de ox´ıgeno disuelto c [mg/L] en un r´ıo aguas abajo de la descarga de un drenaje: c(x) = 10 − 20(e−0.15x − e−0.5x ) donde x es la distancia aguas abajo en kil´ ometros. ¿A qu´e distancia aguas abajo el nivel de ox´ıgeno cae hasta los 5 mg/L?.

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

2 Ra´ıces de funciones no-lineales y polinomios

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Ra´ıces de una funci´on no-lineal f (x) Definici´ on Asumiendo que f (x) dada es una funci´ on continua, cualquier num´ero (real o complejo) r tal que f (r) = 0 es una ra´ız o cero de f (x). Ejemplo Es bien conocido que las ra´ıces del polinomio cuadr´atico f (x) = ax2 + bx + c est´an dadas por la f´ ormula √ b ± b2 − 4ac r1,2 = − 2a Sin embargo no siempre es posible obtener f´ ormulas como en el caso anterior por lo que se recurre a los m´etodos num´ericos para encontrar una aproximaci´ on a la ra´ız de f (x). Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Funciones algebraicas y trascendentes Definici´ on Una funci´ on y = f (x) es algebraica si puede ser exprezada como fn (x)y n + fn−1 (x)y n−1 + · · · + f1 (x)y + f0 (x) = 0 siendo fi (x) un polinomio de i-esimo grado en x. Definici´ on Por otra parte los poliniomios son funciones algebraicas que se representan como fn (x) = an xn + an−1 xn−1 + · · · a1 x + a0 donde n es el grado del polinomio y las ai , i = 1, . . . , n son coeficientes constantes. Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Funciones algebraicas y trascendentes Definici´ on Las funciones trascendentes son aquellas que no son algebraicas, ejemplos de este tipo son las funciones trigonom´etricas, las funciones logaritmicas, la funci´ on exponencial entre otras. As´ı los m´etodos num´ericos buscan abordar los dos siguientes problemas: M´etodos num´ericos • Determinaci´ on de ra´ıces reales de ecuaciones algebraicas y trascendentes. • Determinaci´ on de todas las ra´ıces reales y complejas de los

polinomios.

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

3 M´etodos para encontrar una ra´ız

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo gr´afico

Un m´etodo simple para obtener una aproximaci´ on a una ra´ız r de una funci´ on f (x) = 0 es graficar la funci´ on y observar donde cruza el eje X. Este punto geom´etrico representa un valor aproximado de la ra´ız r. Al m´etodo anterior se le conoce como m´etodo gr´afico.

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo gr´afico Ejemplo La velocidad de ca´ıda de un paracaidista de masa m [Kg] y un coeficiente de resistencia c [kg/s] est´a dada por la f´ ormula  ct mg  1 − e− m . v(t) = c donde v(t) [mt/s] es la velocidad, t [s] el tiempo y g = 9.81 [mt/s2 ] la aceleraci´ on de la gravedad. Si m = 68.1 [kg], determine el coeficiente de resistencia c para que el paracaidista alcance una velocidad de v = 40 [m/s] despues de una ca´ıda libre de t = 10 [s]. Para responder el ejercicio definimos la funci´on f (c) de forma que dada la velocidad v = 40, buscamos un valor cr tal que f (cr ) = 0, esto es  ct mg  f (c) = 1 − e− m − 40. c Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo gr´afico Ejemplo Coeficiente de arrastre vs f(c) 60

50

40

f(c)

30

20

10

0

−10

0

5

Prof. N´ estor Garc´ıa Chan

10 c

15

20

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de bisecci´on

¿Hay una ra´ız ah´ı?, ¿Com´ o la encuentro? Si f (x) es una funci´ on continua en el intervalo [xi , xd ] y ocurre que f (xi ) × f (xd ) < 0 entonces existe al menos una ra´ız xr dentro del intervalo [xi , xd ]. As´ı el m´etodo de bisecci´ on se inicializa determinando valores iniciales para xi y xd (p. ej. con el m´etodo gr´afico) y calcular la aproximaci´on xm de la ra´ız xr con la f´ ormula xm =

Prof. N´ estor Garc´ıa Chan

xi + xd 2

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de bisecci´on Posteriormente ha de ocurrir alguno de los tres casos siguientes: • Si f (xi )f (xm ) < 0 entonces la ra´ız se encuentra en [xi , xm ], por lo

que hacemos xd = xm y repetimos la f´ ormula de aproximaci´on. • Si f (xi )f (xm ) > 0 entonces la ra´ız se encuentra en [xm , xd ], por lo

que hacemos xi = xm y repetimos la f´ ormula de aproximaci´on. • Si f (xi )f (xm ) = 0 entonces xm = xr esto es xm es una ra´ız.

Los pasos anteriores se repiten hasta que a (o f (xr )) sea menor a una tolerancia predefinida s , siendo a dado por nuevo x − xanterior m × 100 % a = m nuevo xm

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de bisecci´on

Figura: Tomada de http://alvarortegas.blogspot.mx/2009/10/metodo-de-biseccion.html

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de bisecci´on Algo que es necesario destacar del m´etodo es que podemos conocer el num´ero de iteraciones n para obtener un tama˜ no del intervalo Ea = |xnuevo − xanterior | a trav´es de la f´ ormula m m  ∆x0  ln Ea n= ln(2) siendo n el numero de iteraciones, ∆x0 el tama˜ no del intervalo inicial y Ea el tama˜ no deseado del intervalo. Ejemplo En el problema del paracaidista, si deseamos obtener un intervalo Ea = 0.0625 a partir del intervalo inicial ∆x0 = 4, tenemos que n = 6.

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de bisecci´on

Ejemplo Utilice el m´etodo de bisecci´ on para encontrar una aproximaci´on de la ra´ız del problema del paracaidista con un tama˜ no de intervalo de Ea = 0.0625 e intervalo inicial [12, 16]. k 0 1 2 3 4 5 6

xi 12.0000 14.0000 14.0000 14.5000 14.7500 14.7500 14.7500

f (xi ) 6.1139 1.6111 1.6111 0.5937 0.0998 0.0998 0.0998

xd 16.0000 16.0000 15.0000 15.0000 15.0000 14.8750 14.8125

Prof. N´ estor Garc´ıa Chan

f (xd ) -2.2303 -2.2303 -0.3845 -0.3845 -0.3845 -0.1435 -0.0221

xm 14.0000 15.0000 14.5000 14.7500 14.8750 14.8125 14.7813

f (xm ) 1.6111 -0.3845 0.5937 0.0998 -0.1435 -0.0221 0.0388

M´ etodos Num´ ericos en Ingenier´ıa

Ea 1.0000 0.5000 0.2500 0.1250 0.0625 0.0313

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de bisecci´on Ejemplo Utilice el m´etodo de Bisecci´ on para calcular la ra´ız de la funci´on f (x) = e−x − x realice un gr´afico para observar posibles valores iniciales (la ra´ız verdadera es xr = 0.56714) y estime cuantas iteraciones ser´ıan necesarias para alcanzar un intervalo de tama˜ no Ea = 0.1. 1

0.5

f(x)=e−x − x

0

−0.5

−1

−1.5

−2

0

0.2

0.4

0.6

0.8

Prof. N´ estor Garc´ıa Chan

1 x

1.2

1.4

1.6

1.8

2

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de bisecci´on

Ejemplo Resumimos los c´alculos en la siguiente tabla: k 0 1 2 3 4

xi 0.0000 0.5000 0.5000 0.5000 0.5625

f (xi ) 1.0000 0.1065 0.1065 0.1065 0.0073

xd 1.0000 1.0000 0.7500 0.6250 0.6250

Prof. N´ estor Garc´ıa Chan

f (xd ) -0.6321 -0.6321 -0.2776 -0.0897 -0.0897

xm 0.5000 0.7500 0.6250 0.5625 0.5938

f (xm ) 0.1065 -0.2776 -0.0897 0.0073 -0.0415

M´ etodos Num´ ericos en Ingenier´ıa

Ea 0.2500 0.1250 0.0625 0.0313

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de Newton-Raphson Un m´etodo con velocidad Si una aproximaci´ on inicial de la ra´ız de una funci´ on f (x) es xi , entonces es posible trazar una tangente desde el punto [xi , f (xi )] hasta que cruze el eje X en [xi+1 , 0]. Dicha tangente tiene pendiente f 0 (xi ) =

f (xi ) − 0 xi − xi+1

siendo xi+1 la siguiente aproximaci´ on a la ra´ız, as´ı despejandola de la f´ormula anterior tenemos xi+1 = xi −

f (xi ) f 0 (xi )

que es la conocida f´ ormula de Newton-Raphson para i = 0, 1, . . .. Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de Newton-Raphson

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de Newton Los errores del m´etodo son el de aproximaci´ on porcentual xi+1 − xi × 100 % a = xi+1 pero adem´as de el error de aproximaci´ on absoluto Ea,i+1 = |xi+1 − xi | Finalmente se puede demostrar que el error absoluto Ea,i+1 depende del error absoluto anterior, esto es, Ea,i+1 ≈

−f 00 (xi+1 ) 2 E . 2f 0 (xi+1 ) a,i

El proceso iterativo del m´etodo se detiene cuando el error de aproximaci´ on -porcentual o absoluto- es menor a una tolerancia predefinida s o Ea,s . Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de Newton

Ejemplo Utilice el m´etodo de Newton-Raphson para calcular la ra´ız de f (x) = e−x − x con valor inicial x0 = 0 y a = 0.5 % (la ra´ız verdadera es xr = 0.56714). i 0 1 2

xi 0.0000 0.5000 0.5663

xi+1 0.5000 0.5663 0.5671

a ( %) 100.0000 11.7093 0.1467

Prof. N´ estor Garc´ıa Chan

f (xi+1 ) 0.1065 0.0013 0.0000

|xi+1 − xi | 0.5000 0.0663 0.0008

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de la secante Un m´etodo libre de derivada Si consideramos la siguiente aproximaci´ on de la derivada evaluada en xi f 0 (xi ) ≈

f (xi−1 ) − f (xi ) xi−1 − xi

al sustituir en la f´ ormula de Newton-Raphson se obtiene xi+1 = xi −

f (xi )(xi−1 − xi ) f (xi−1 ) − f (xi )

que es la f´ ormula de la secante, note que dos valores iniciales de la ra´ız son requeridos y su convergencia es m´as lenta en comparaci´on con Newton ¿porqu´e?.

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de la secante

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de la secante Ejemplo Con el m´etodo de la secante encuentre una aproximaci´on de la ra´ız de la funci´ on f (x) = e−x − x comience con los valores iniciales x−1 = 0, x0 = 1 (use un corte de cinco cifras) y considere una tolerancia de error de a = 0.5 % (la ra´ız verdadera es xr = 0.56714) i 1 2 3 4

xi−1 0.0000 1.0000 0.6127 0.5638

xi 1.0000 0.6127 0.5638 0.5672

xi+1 0.6127 0.5638 0.5672 0.5671

Prof. N´ estor Garc´ıa Chan

a ( %) 63.2121 8.6659 0.5875 0.0048

|f (xi+1 )| 0.0708 0.0052 0.0000 0.0000

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de la falsa posici´on Falsa posici´ on: el m´etodo de bisecci´ on mejorado Este m´etodo consiste en encerrar la ra´ız xr de una funci´on f (x) dentro del intervalo [xi , xd ] (como en bisecci´ on), siendo la aproximaci´on de la ra´ız la intersecci´ on de la recta que pasa por los puntos (xd , f (xd )) y (xi , f (xi )) con el eje X, as´ı por la semejanza de tri´angulos (ver Figura) f (xi ) f (xd ) = xr − xi xr − xd donde al despejar xr obtenemos xr = xd −

f (xd )(xi − xd ) f (xi ) − f (xd )

que es la formula del m´etodo de la posici´ on falsa. Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de la falsa posici´on Funcionamiento del m´etodo y creterio de parada Gr´aficamente el m´etodo aplica la semejanza de tri´angulos

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de la falsa posici´on

Una vez calculado la aproximaci´ on xr aplicamos los mismos criterios de la bisecci´ on para definir el nuevo intervalo [xi , xd ] y repetimos el proceso. El criterio de parada el m´etodo es el usual, dada una tolerancia s buscamos que el error a < s .

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´ etodo M´ etodo M´ etodo M´ etodo M´ etodo

gr´ afico de bisecci´ on de Newton-Raphson de la secante de la falsa posici´ on

M´etodo de la falsa posici´on Ejemplo Con el m´etodo de la falsa posici´ on encuentre una aproximaci´on de la ra´ız de la funci´ on f (x) = e−x − x comience con los valores iniciales xi = 0, xd = 1 (use un corte de cinco cifras) y realice 4 iteraciones del m´etodo. Tome como ra´ız verdadera a xr = 0.5671. k 0 1 2 3

xi 0.0000 0.0000 0.0000 0.0000

f (xi ) 1.0000 1.0000 1.0000 1.0000

xd 1.0000 0.6127 0.5722 0.5677

f (xd ) -0.6321 -0.0708 -0.0079 -0.0009

Prof. N´ estor Garc´ıa Chan

xr 0.6127 0.5722 0.5677 0.5672

f (xr ) -0.0708 -0.0079 -0.0009 -0.0001

M´ etodos Num´ ericos en Ingenier´ıa

Ea 0.0405 0.0043 0.0005

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

4 Ra´ıces de sistemas de ecuaciones no lineales

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Raices de sistemas de ecuaciones no-lineales Sistema de ecuaciones no lineales Un sistema de ecuaciones no-lineales de n ecuaciones y n inc´ognitas tiene la forma general f1 (x1 , x2 , . . . , xn ) = 0 f2 (x1 , x2 , . . . , xn ) = 0 .. . fn (x1 , x2 , . . . , xn ) = 0 siendo fi funciones no lineales en las variables xi para , i = 1, 2, . . . , n, que son precisamente las inc´ ognitas del sistema. Un ejemplo de sistema es f1 (x, y, z) = x2 + xy − 10 = 0 f2 (x, y, z) = y + 3xy 2 + sen(xz) − 57 = 0 f3 (x, y, z) = ex+y+z + cos(yz) + ln(z) = 0

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´etodo de Newton para sistemas no-lineales de 2x2 El m´etodo de Newton para sistemas de ecuaciones no es otra cosa que la extensi´ on del m´etodo de Newton-Raphson ya visto, as´ı para mostrarlo consideremos el sistema no-lineal de 2 × 2 u(x, y) = 0 v(x, y) = 0 cuya soluci´ on es el par (xr , yr ). Entonces el objetivo es encontrar (xi+1 , yi+1 ) ≈ (xr , yr ). Para esto si ui+1 y vi+1 denotan las funciones u y v evaluadas en (xi+1 , yi+1 ), escribimos las series de Taylor para u y v con centro en (xi , yi ) como: ∂ui ∂ui + (yi+1 − yi ) + · · · + Ru ∂x ∂y ∂vi ∂vi = vi + (xi+1 − xi ) + (yi+1 − yi ) + · · · + Rv ∂x ∂y

ui+1 = ui + (xi+1 − xi ) vi+1

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´etodo de Newton para sistemas de ecuaciones no-lineales Se desea que ui+1 = vi+1 = 0 (¿porqu´e?) si esto ocurre podemos reescribir las ecuaciones anteriores en la forma ∂ui ∂ui ∂ui ∂ui + yi+1 = −ui + xi + yi ∂x ∂y ∂x ∂y ∂vi ∂vi ∂vi ∂vi xi+1 + yi+1 = −vi + xi + yi ∂x ∂y ∂x ∂y

xi+1

que es un sistema de dos ecuaciones lineales con inc´ ognitas xi+1 , yi+1 , resolvi´endolo con Cramer obtenemos las f´ ormulas ...

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´etodo de Newton para sistemas de ecuaciones no-lineales M´etodo de Newton para sistemas de 2 × 2 Dados la aproximaci´ on anterior (xi , yi ) encontramos la nueva aproximaci´ on (xi+1 , yi+1 ) con los esquemas num´ericos ui xi+1 = xi −

∂vi ∂ui − vi ∂y ∂y J(ui , vi )

vi yi+1 = yi −

∂ui ∂vi − ui ∂x ∂x J(ui , vi )

(1)

para cada i = 0, 1, . . . y siendo J(ui , vi ) el llamado Jacobiano (determinante) definido como J(ui , vi ) =

∂vi ∂ui ∂ui ∂vi − ∂x ∂y ∂x ∂y

Los esquemas finalizan cuando se satisfaga la tolerancia de error max{ax , ay } < s . Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

(2)

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

M´etodo de Newton para sistemas de ecuaciones no-lineales Ejemplo Realice tres iteraciones con el m´etodo de Newton para encontrar una aproximaci´ on de la soluci´ on del sistema de ecuaciones no-lineales u(x, y) = x2 + xy − 10 = 0 v(x, y) = y + 3xy 2 − 57 = 0 para esto considere los valores iniciales x0 = 1.5, y0 = 3.5. Soluci´ on: i 0 1 2 3

xi 1.5000 2.0360 1.9987 2.0000

yi 3.5000 2.8439 3.0023 2.9999

u(xi , yi ) -2.5000 -0.0644 -0.0045 -0.0000

Prof. N´ estor Garc´ıa Chan

v(xi , yi ) 1.6250 -4.7562 0.0496 -0.0000

a ( %) 26.3278 5.2764 0.0763

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

5 Ra´ıces de un polinomio y M´etodo de Bairstow

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

Divisi´on sint´etica

El proceso de divisi´ on de un polinomio Pn (x) de grado n por un factor (x − α) nos permite calcular las ra´ıces de del polinomio, as´ı consideremos un polinomio de grado n de la forma Pn (x) = (x − α)Pn−1 (x) + R(x) si dividimos el polinomio anterior entre el factor (x − α) obtendremos un cociente de grado n − 1 y un residuo. Si ocurre que el residuo R(x) = 0 entonces x = α es una ra´ız de Pn (x).

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

Divisi´on sintetica La divisi´ on de un polinomio de grado n, Pn (x) = an xn + an−1 xn + · · · + a1 x + a0 entre un factor (x − α) puede simplificarse si usamos la divisi´ on sint´etica la cual podemos resumir en la siguiente tabla:

+α

an +0 pn = an

pn−1

an−1 αpn = an−1 + αpn

··· ··· ···

a1 αp2 p1 = a1 + αp2

a0 αp1 p0 = a0 + αp1

Cuadro: Esquema divisi´ on sint´etica entre el factor lineal (z − α).

En el esquema anterior tenemos por una parte que el residuo es R(x) = p0 (constante) mientras que el cociente Q(x) es un polinomio de grado n − 1 dado por Q(x) = pn xn−1 + pn−1 xn−2 + · · · + p2 x + p1 . Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

Divisi´on sint´etica Ejemplo Con el esquema anterior compruebe que x = 8 es una ra´ız de la ecuaci´on polinomial P5 (x) = x5 − x4 − 60x3 − 20x2 + 464x − 384. Para esto x = 8 implica que (x − 8) es el factor (x − α) de P5 (x), as´ı al aplicar entonces el esquema de la divisi´ on sint´etica tenemos +8

1 0 p5 = 1

−1 8 p4 = 7

−60 56 p3 = −4

−20 −32 p2 = −52

464 −416 p1 = 48

−384 384 p0 = 0

Cuadro: Esquema divisi´ on sint´etica entre el factor lineal (z − 8).

y por tanto el residuo R = 0 mientras que el cociente es Q(x) = x4 + 7x3 − 4x2 − 52x + 48.

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

Divisi´on sint´etica Es posible considerar un factor cuadr´atico x2 + αx + β para la divisi´on sint´etica del polinomio Pn (x) = an xn + an−1 xn−1 + · · · + a1 x + a0 , al igual que el caso anterior la divis´ on es condensada en la siguiente tabla: -α

an

an−1 −αpn

pn = an

pn−1 = an−1 − αpn

-β

an−2 −αpn−1 −βpn pn−2 = an−2 − αpn−1 − βpn

··· ··· ··· ··· ···

a0 −αp1 −βp2 p0 = a0 − αp1 − βp2

Cuadro: Esquema divisi´ on sint´etica entre un factor cuadr´ atico, caso general.

En el esquema anterior tenemos por una parte que el residuo es R(x) = p1 x + p0 (lineal) mientras que el cociente Q(x) es un polinomio de grado n − 2 dado por Q(x) = pn xn−2 + pn−1 xn−3 + · · · + p3 x2 + p2 x. Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

Divisi´on sint´etica Ejemplo Determine el cociente del polinomio f (x) = x4 + 7x3 − 15x2 − 121x − 520 si se sabe que tiene un factor cuadr´atico de la forma Q(x) = x2 + 4x + 13 que contiene ra´ıces complejas conjugadas. -4

1

7 −4(1)

p4 = 1

p3 = 3

-13

−15 −4(3) −13(1) p2 = −40

−121 −4(−40) −13(3) p1 = 0

−520 −4(0) −13(−40) p0 = 0

Cuadro: Esquema divisi´ on sint´etica entre un factor cuadr´ atico, caso general.

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

M´etodo de Bairstow

Retomemos el polinomio Pn (x) de grado n escrito en la forma Pn (x) = an xn + an−1 xn−1 + . . . + a1 x + a0

(3)

entonces si dividimos Pn (x) entre el factor cuadr´atico x2 − ri x − si se obtiene el residuo R = b1 (x − ri ) + b0 . Observe que si b1 = b0 = 0 el factor cuadr´atico es un factor exacto y por tanto las ra´ıces de x2 − ri x − si = 0 ser´an ra´ıces de Pn (x) = 0.

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

M´etodo de Bairstow El m´etodo de Bairstow busca encontrar ri y si tales que b1 y b0 sean pr´ oximos a cero, para lograrlo, es necesario aplicar el esquema iterativo ri+1 = ∆r + ri , si+1 = ∆s + si siendo ∆r y ∆s soluci´ on del sistema de ecuaciones lineales ∂b1 ∂r ∆r

+

∂b1 ∂s ∆s

= −b1

∂b0 ∂r ∆r

+

∂b0 ∂s ∆s

= −b0

Bairstow demostr´ o que los coeficientes del sistema anterior se obtienen con divisiones sint´eticas sucesivas lo que da origen a siguiente m´etodo ...

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

M´etodo de Bairstow M´etodo de Bairstow Dadas las aproximaciones iniciales ri y si hacemos los pasos: P1 Identificamos el grado n del polinomio y sus coeficientes an , n = 0, 1, . . . , n. P2 Planteamos el sistema de ecuaciones lineales c2 ∆r + c3 ∆s = −b1 c1 ∆r + c2 ∆s = −b0

(4)

P3 Calculamos los coeficientes c1 , c2 , c3 , b1 y b0 a partir de los esquemas bn = a n bn−1 = an−1 + ri bn bj = aj + ri bj+1 + si bj+2

c n = bn cn−1 = bn−1 + rcn cj = bj + ri cj+1 + si cj+2

para j = n − 2, . . . , 1, 0. Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

(5)

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

M´etodo de Bairstow

M´etodo de Bairstow P4 Resolvemos el sistema obteniendo los incrementos ∆r y ∆s P5 Calculamos las nuevas aproximaciones ri+1 y si+1 con las formulas ri+1 = ri + ∆r,

si+1 = si + ∆s

(6)

calculamos errores ar , as y repetimos el proceso hasta satisfacer una tolerancia de error s

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa

Un problema medioambiental Ra´ıces de funciones no-lineales y polinomios M´ etodos para encontrar una ra´ız Ra´ıces de sistemas de ecuaciones no lineales Ra´ıces de un polinomio y M´ etodo de Bairstow

Divisi´ on sint´ etica M´ etodo de Bairstow

M´etodo de Bairstow

Ejemplo Utilizando el m´etodo de Bairstow para encontrar una primera aproximaci´ on de un factor cuadratico del polinomio f (x) = x4 + 2.75x3 + 2.125x2 − 3.785x + 1.25, utilice los valores iniciales r0 = −1, s0 = −1 y realice cinco iteraciones.

Prof. N´ estor Garc´ıa Chan

M´ etodos Num´ ericos en Ingenier´ıa