Ra´ıces de Polinomios

´ ´ Curso: Metodos Numericos en Ingenier´ıa ´ Profesor: Dr. Jose´ A. Otero Hernandez Correo: [email protected] web: http://metodosnumericoscem.weebly.com Universidad: ITESM CEM

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ TOPICOS

1

´ INTRODUCCION Ra´ıces de polinomios

2

´ METODO DE BAIRSTOW ´ del metodo ´ Presentacion ´ de un polinomio Factorizacion ´ Metodo de Bairstow Ejemplo

3

´ Metodo de Bairstow con MATLAB Programa MATLAB

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Topicos

1

´ INTRODUCCION Ra´ıces de polinomios

2

´ METODO DE BAIRSTOW ´ del metodo ´ Presentacion ´ de un polinomio Factorizacion ´ Metodo de Bairstow Ejemplo

3

´ Metodo de Bairstow con MATLAB Programa MATLAB

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ra´ıces de polinomios

Polinomio fn (x) = an xn + an−1 xn−1 + · · · + a2 x2 + a1 x1 + a0 donde n es el grado del polinomio, ai (i = 0, 1, · · · , n) son coeficientes constantes y pueden ser reales o complejos, Las ra´ıces pueden ser reales o complejas, Reglas de las ra´ıces de polinomios ´ de grado n, hay n ra´ıces reales o En una ecuacion complejas,

Si n es impar, hay al menos una ra´ız real, ´ Si existen ra´ıces complejas, estas se encuentran √
por pares beamer-tu-log conjugados (λ + iµ y λ − iµ, donde i = −1

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ra´ıces de polinomios

Polinomio fn (x) = an xn + an−1 xn−1 + · · · + a2 x2 + a1 x1 + a0 donde n es el grado del polinomio, ai (i = 0, 1, · · · , n) son coeficientes constantes y pueden ser reales o complejos, Las ra´ıces pueden ser reales o complejas, Reglas de las ra´ıces de polinomios ´ de grado n, hay n ra´ıces reales o En una ecuacion complejas,

Si n es impar, hay al menos una ra´ız real, ´ Si existen ra´ıces complejas, estas se encuentran √
por pares beamer-tu-log conjugados (λ + iµ y λ − iµ, donde i = −1

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ra´ıces de polinomios

Ejemplo de Polinomio f (x) = x3 − 19.12x2 + 101.5325x − 110.07095 Ra´ıces del Polinomio x1 = 1.45 x2 = 7.37 x3 = 10.3

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ra´ıces de polinomios

Ejemplo de Polinomio f (x) = x3 − 19.12x2 + 101.5325x − 110.07095 Ra´ıces del Polinomio x1 = 1.45 x2 = 7.37 x3 = 10.3

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Topicos

1

´ INTRODUCCION Ra´ıces de polinomios

2

´ METODO DE BAIRSTOW ´ del metodo ´ Presentacion ´ de un polinomio Factorizacion ´ Metodo de Bairstow Ejemplo

3

´ Metodo de Bairstow con MATLAB Programa MATLAB

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ del metodo ´ Presentacion

´ Metodos de Bairstow ´ ´ El metodo de Bairstow es un metodo iterativo para calcular aproximadamente las ra´ıces de polinomios

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ de un polinomio Factorizacion

´ de un polinomio Factorizacion Dado el polinomio: fn (x) = an xn + an−1 xn−1 + · · · + a2 x2 + a1 x1 + a0 Si dividimos el polinomio por el factor x − xr , entonces fn (x) = fn−1 (x) + R x − xr donde fn−1 (x) = bn xn−1 + bn−1 xn−2 + · · · + b3 x2 + b2 x1 + b1 ´ Aqu´ı, R = b0 es el Residuo, R = 0 si xr es una ra´ız. Ademas, bn = an bi = ai + bi+1 xr , para i = n − 1, · · · , 0

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Metodo de Bairstow

´ Metodo de Bairstow Dado el polinomio: fn (x) = an xn + an−1 xn−1 + · · · + a2 x2 + a1 x1 + a0 ´ Se divide el polinomio por un factor cuadratico: x2 − rx − s x2

fn (x) = fn−2 (x) + R − rx − s

donde fn−2 (x) = bn xn−2 + bn−1 xn−3 + · · · + b3 x + b2 R = b1 (x − r) + b0 bn = an bn−1 = an−1 + r bn bi = ai + r bi+1 + s bi+2 , para i = n − 2, · · · , 0

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Metodo de Bairstow

´ Metodo de Bairstow ´ El factor cuadratico se introduce para permitir la ´ de las ra´ıces complejas, determinacion Si x2 − rx − s es un divisor exacto del polinomio, las ra´ıces ´ ´ complejas pueden determinarse con la formula cuadratica, ´ El metodo se reduce a determinar los valores de r y s que hacen que el residuo sea igual o aproximadamente igual a cero. Para que el residuo (R = b1 (x − r) + b0 ) sea igual a cero, b0 y b1 deben ser igual a cero. Como es improbable que los valores iniciales para evaluar r y s conduzcan a b0 = 0 y b1 = 0, se necesita una forma ´ sistematica para modificar los valores iniciales.

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Metodo de Bairstow

´ Metodo de Bairstow ´ ´ Para buscar una forma sistematica el metodo de Bairstow, usa ´ una estrategia similar a la del metodo de Newton-Raphson. b0 y b1 son funciones de r y s: b1 = a1 + rb2 + sb3 = b1 (r, s) b0 = a0 + rb1 + sb2 = b0 (r, s) Desarrollo en serie de Taylor de b0 y b1 despreciando los ´ terminos de segundo orden y superiores: b1 (r + ∆r, s + ∆s) = b1 + b0 (r + ∆r, s + ∆s) = b0 +

∂b1 ∂r ∆r ∂b0 ∂r ∆r

+ +

∂b1 ∂s ∆s ∂b0 ∂s ∆s

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Metodo de Bairstow

´ Metodo de Bairstow Los incrementos ∆r y ∆s necesarios para mejorar nuestros valores iniciales se estiman, haciendo: b1 (r + ∆r, s + ∆s) ≈ 0 b0 (r + ∆r, s + ∆s) ≈ 0 Por tanto, 

∂b1 ∂r ∆r ∂b0 ∂r ∆r

+ +

∂b1 ∂s ∆s ∂b0 ∂s ∆s

= −b1 = −b0

Si las derivadas parciales de las b pueden determinarse, entonces hay un sistema de dos ecuaciones para ∆r y ∆s.

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Metodo de Bairstow

´ Metodo de Bairstow Bairstow demostro´ que las derivadas se pueden obtener de ´ de las b: manera similar a la obtencion cn = bn cn−1 = bn−1 + r cn ci = bi + r ci+1 + s ci+2 , para i = n − 2, · · · , 1 donde

Finalmente se llega a: 

∂b0 ∂r ∂b0 ∂s ∂b1 ∂s

= c1 , 1 = ∂b ∂r = c2 , = c3

c2 ∆r + c3 ∆s = −b1 c1 ∆r + c2 ∆s = −b0

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Metodo de Bairstow

´ Metodo de Bairstow Resolviendo ∆r y ∆s, se obtiene una mejora de los r y s, puesto que: ri+1 = ri + ∆r si+1 = si + ∆s En cada paso se estima un error aproximado para r y s, es decir: |εa,r | = ∆r r × 100% ∆s |εa,s | = s × 100% Cuando dichos errores caen por debajo de un error estimado “εs ”, los valores de las ra´ıces se determinan mediante: √ r ± r2 + 4s x= 2

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Metodo de Bairstow

´ Metodo de Bairstow Existen tres posibilidades: 1

El cociente es un polinomio de tercer grado o mayor. En tal ´ caso, el metodo de Bairstow se aplica al cociente para evaluar un nuevo valor de r y s. Los valores anteriores de r ´ y s pueden servir como valores iniciales en esta aplicacion,

2

´ El cociente es cuadratico. En este caso es posible√evaluar 2 directamente las dos ra´ıces restantes con: x = r± r2 +4s ,

3

El cociente es un polinomio de primer grado. En este caso, la ra´ız restante se evalua ´ simplemente como: x = − rs

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ejemplo

Ejemplo ´ Emplee el metodo de Bairstow para determinar las ra´ıces del polinomio: f5 (x) = x5 − 3.5x4 + 2.75x3 + 2.125x2 − 3.875x1 + 1.25 Utilice como valores iniciales r = s = −1 e itera hasta un error estimado εs = 1%

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ejemplo

´ Solucion bn = an bn−1 = an−1 + r bn bi = ai + r bi+1 + s bi+2 , para i = n − 2, · · · , 0 cn = bn cn−1 = bn−1 + r cn ci = bi + r ci+1 + s ci+2 , para i = n − 2, · · · , 1 ´ Solucion b5 = 1, b4 = −4.5, b3 = 6.25, b2 = 0.375, b1 = −10.5, b0 = 11.375,

beamer-tu-log c5 = 1, c4 = −5.5, c3 = 10.75, c2 = −4.875, c1 = −16.375,

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ejemplo

´ Solucion 



c2 ∆r + c3 ∆s = −b1 c1 ∆r + c2 ∆s = −b0

−4.875∆r + 10.75∆s = 10.5 −16.375∆r − 4.875∆s = −11.375

´ Solucion ∆r = 0.3558, ∆s = 1.1381, r = −1 + 0.3558 = −0.6442, s = −1 + 1.1381 = 0.1381, ∆r 100% = 55.23%, εa,r = r

εa,s

∆s 100% = 824.1% = beamer-tu-log s

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ejemplo

´ Solucion b5 = 1, b4 = −4.1442, b3 = 5.5578, b2 = −2.0276, b1 = −1.8013, b0 = 2.1304, c5 = 1, c4 = −4.7884, c3 = 8.7806, c2 = −8.3454, c1 = 4.7874,  −8.3454∆r + 8.7806∆s = 1.8013 4.7874∆r − 8.3454∆s = −2.1304 ´ Solucion ∆r = 0.1331, ∆s = 0.3316, r = −0.6442 + 0.1331 = −0.5111, s = 0.1381 + 0.3316 = 0.4697, εa,r = 26.0%,

εa,s = 70.6%

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ejemplo

´ Solucion ´ de cuatro iteraciones: Despues r = −0.5, εa,r = 0.063% s = 0.5, εa,s = 0.040%

x=

r±

√

−0.5 ± r2 + 4s = 2

p (−0.5)2 + 4(0.5) = 0.5, −1.0 2

Se queda el cociente: f3 (x) = −2.5 + 5.25x − 4x2 + x3

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Ejemplo

´ Solucion ´ de cinco iteraciones: Tomando r = −0.5 y s = 0.5 y despues r = 2, s = −1.249,

x=

2±

p (2)2 + 4(−1.249) = 1 ± 0.499i. 2

Finalmente, el cociente es un polinomio de primer grado y la ra´ız es: s x=− =2 r

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

´ Topicos

1

´ INTRODUCCION Ra´ıces de polinomios

2

´ METODO DE BAIRSTOW ´ del metodo ´ Presentacion ´ de un polinomio Factorizacion ´ Metodo de Bairstow Ejemplo

3

´ Metodo de Bairstow con MATLAB Programa MATLAB

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Programa MATLAB

function b a i r s t o w v 1 ( a , r0 , s0 , EE) % f n ( x ) = a {n}∗x ˆ{n}+a {n−1}∗x ˆ{n −1}+...+ a {2}∗xˆ{2}+ a {1}∗xˆ{1}+ a {0} % a = [ a {n} a {n−1} . . . a {2} a {1} a {0}] % r0−−− V a l o r i n i c i a l de r % s0−−− V a l o r i n i c i a l de s % EE−−−E r r o r estimado n=length ( a ) ; % Grado d e l p o l i n o m i o ( n−1) a=a ( n : −1:1) ; i f (mod( n−1,2) ˜ = 0 ) % mod : Modulo despues de l a d i v i s i o n : mod( X , Y) =X−Y∗ f l o o r (X / Y) m=( n−2) / 2 ; % Grado d e l p o l i n o m i o ( n−1) es impar else m=( n−3) / 2 ; % Grado d e l p o l i n o m i o ( n−1) es par end f o r j j =1:m r = r0 ; s = s0 ; Ear = 1000; Eas = 1000; while Ear>EE | | Eas>EE b(n) = a(n) ; % C a l c u l o de l o s b b ( n−1) = a ( n−1)+ r ∗b ( n ) ; f o r j = n−2:−1:1 b ( j ) = a ( j ) + r ∗b ( j +1)+s∗b ( j +2) ; end c(n) = b(n) ; % C a l c u l o de l o s c c ( n−1) = b ( n−1)+ r ∗c ( n ) ; f o r j = n−2:−1:2 c ( j ) = b ( j ) + r ∗c ( j +1)+s ( 1 ) ∗c ( j +2) ; end d r = −(−c ( 3 ) ∗b ( 2 ) +b ( 1 ) ∗c ( 4 ) ) / ( c ( 2 ) ∗c ( 4 )−c ( 3 ) ˆ 2 ) ; % S o l u c i o n d e l sistema ds = (−c ( 2 ) ∗b ( 2 ) +c ( 3 ) ∗b ( 1 ) ) / ( c ( 2 ) ∗c ( 4 )−c ( 3 ) ˆ 2 ) ; r = r + d r ; s = s+ds ; Ear = abs ( d r / r ) ∗100; Eas = abs ( ds / s ) ∗100; end

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Programa MATLAB

x (2∗ j j −1) = ( r + s q r t ( r ˆ2+4∗ s ) ) / 2 ; x (2∗ j j ) = ( r−s q r t ( r ˆ2+4∗ s ) ) / 2 ; a = b(3:n) ; n = length ( a ) ; r 0 = r ; s0 = s ; end r = − a ( 2 ) ; s = −a ( 1 ) ; i f n==2 x (2∗ j j +1) = −s / r ; e l s e i f n==3 x (2∗ j j +1) = ( r + s q r t ( r ˆ2+4∗ s ) ) / 2 ; x (2∗ j j +2) = ( r−s q r t ( r ˆ2+4∗ s ) ) / 2 ; else disp ( ’ e r r o r ’ ) end salida =[ x ’ ] ; disp ( s a l i d a )

beamer-tu-log

´ INTRODUCCION

´ METODO DE BAIRSTOW

´ Metodo de Bairstow con MATLAB

Programa MATLAB

>> a =[1 −3.5 a = 1.0000

2.75 2.125 −3.875 1 . 2 5 ]

−3.5000

2.7500

2.1250

−3.8750

1.2500

>> b a i r s t o w v 1 ( a,−1,−1,1) 0.5000 −1.0000 1.0000 − 0.4993 i 1.0000 + 0.4993 i 2.0071 >> b a i r s t o w v 1 ( a, −1 , −1 ,0.1) 0.5000 −1.0000 1.0000 − 0.4994 i 1.0000 + 0.4994 i 1.9996 >> b a i r s t o w v 1 ( a, −1 , −1 ,0.01) 0.5000 −1.0000 1.0000 − 0.5000 i 1.0000 + 0.5000 i 2.0000

beamer-tu-log