raíces de polinomios - métodos numéricos · ra´ıces de polinomios polinomio f n (x) = a nxn +...

beamer-tu-logo

Raıces de Polinomios

Curso: Metodos Numericos en IngenierıaProfesor: Dr. Jose A. Otero HernandezCorreo: j.a.otero@tec.mxweb: http://metodosnumericoscem.weebly.comUniversidad: ITESM CEM

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

TOPICOS

1 INTRODUCCIONRaıces de polinomios

2 METODO DE BAIRSTOWPresentacion del metodoFactorizacion de un polinomioMetodo de BairstowEjemplo

3 Metodo de Bairstow con MATLABPrograma MATLAB

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Topicos

1 INTRODUCCIONRaıces de polinomios

2 METODO DE BAIRSTOWPresentacion del metodoFactorizacion de un polinomioMetodo de BairstowEjemplo

3 Metodo de Bairstow con MATLABPrograma MATLAB

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Raıces de polinomios

Polinomio

fn (x) = anxn + an−1x

n−1 + · · ·+ a2x2 + a1x

1 + a0

donden es el grado del polinomio,ai (i = 0, 1, · · · , n) son coeficientes constantes y puedenser reales o complejos,Las raıces pueden ser reales o complejas,

Reglas de las raıces de polinomiosEn una ecuacion de grado n, hay n raıces reales ocomplejas,Si n es impar, hay al menos una raız real,Si existen raıces complejas, estas se encuentran por paresconjugados (λ+ iµ y λ− iµ, donde i =

√−1)

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Raıces de polinomios

Polinomio

fn (x) = anxn + an−1x

n−1 + · · ·+ a2x2 + a1x

1 + a0

donden es el grado del polinomio,ai (i = 0, 1, · · · , n) son coeficientes constantes y puedenser reales o complejos,Las raıces pueden ser reales o complejas,

Reglas de las raıces de polinomiosEn una ecuacion de grado n, hay n raıces reales ocomplejas,Si n es impar, hay al menos una raız real,Si existen raıces complejas, estas se encuentran por paresconjugados (λ+ iµ y λ− iµ, donde i =

√−1)

beamer-tu-logo

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 Polinomiox1 = 1.45

x2 = 7.37

x3 = 10.3

MatLab> p = [1 − 19.12 101.5325 − 110.07095]

> x = roots(p)

x = 10.3000 7.3700 1.4500

beamer-tu-logo

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 Polinomiox1 = 1.45

x2 = 7.37

x3 = 10.3

MatLab> p = [1 − 19.12 101.5325 − 110.07095]

> x = roots(p)

x = 10.3000 7.3700 1.4500

beamer-tu-logo

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 Polinomiox1 = 1.45

x2 = 7.37

x3 = 10.3

MatLab> p = [1 − 19.12 101.5325 − 110.07095]

> x = roots(p)

x = 10.3000 7.3700 1.4500

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Topicos

1 INTRODUCCIONRaıces de polinomios

2 METODO DE BAIRSTOWPresentacion del metodoFactorizacion de un polinomioMetodo de BairstowEjemplo

3 Metodo de Bairstow con MATLABPrograma MATLAB

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Presentacion del metodo

Metodos de BairstowEl metodo de Bairstow es un metodo iterativo para calcularaproximadamente las raıces de polinomios

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Factorizacion de un polinomio

Factorizacion de un polinomioDado el polinomio:

fn (x) = anxn + an−1x

n−1 + · · ·+ a2x2 + a1x

1 + a0

Si dividimos el polinomio por el factor x− xr, entonces

fn (x)

x− xr= fn−1 (x) +R

donde

fn−1 (x) = bnxn−1 + bn−1x

n−2 + · · ·+ b3x2 + b2x

1 + b1

Aquı, R = b0 es el Residuo, R = 0 si xr es una raız. Ademas,

bn = an

bi = ai + bi+1xr, para i = n− 1, · · · , 0

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Metodo de Bairstow

Metodo de BairstowDado el polinomio:

fn (x) = anxn + an−1x

n−1 + · · ·+ a2x2 + a1x

1 + a0

Se divide el polinomio por un factor cuadratico: x2 − rx− s

fn (x)

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

donde

fn−2 (x) = bn xn−2 + bn−1 x

n−3 + · · ·+ b3x+ 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-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Metodo de Bairstow

Metodo de BairstowEl factor cuadratico se introduce para permitir ladeterminacion de las raıces complejas,Si x2 − rx− s es un divisor exacto del polinomio, las raıcescomplejas pueden determinarse con la formula cuadratica,El metodo se reduce a determinar los valores de r y s quehacen que el residuo sea igual o aproximadamente igual acero.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 evaluarr y s conduzcan a b0 = 0 y b1 = 0, se necesita una formasistematica para modificar los valores iniciales.

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Metodo de Bairstow

Metodo de BairstowPara buscar una forma sistematica el metodo de Bairstow, usauna 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 losterminos de segundo orden y superiores:

b1 (r + ∆r, s+ ∆s) = b1 + ∂b1∂r ∆r + ∂b1

∂s ∆s

b0 (r + ∆r, s+ ∆s) = b0 + ∂b0∂r ∆r + ∂b0

∂s ∆s

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Metodo de Bairstow

Metodo de BairstowLos incrementos ∆r y ∆s necesarios para mejorar nuestrosvalores iniciales se estiman, haciendo:

b1 (r + ∆r, s+ ∆s) ≈ 0b0 (r + ∆r, s+ ∆s) ≈ 0

Por tanto, {∂b1∂r ∆r + ∂b1

∂s ∆s = −b1∂b0∂r ∆r + ∂b0

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

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Metodo de Bairstow

Metodo de BairstowBairstow demostro que las derivadas se pueden obtener demanera similar a la obtencion de las b:

cn = bn

cn−1 = bn−1 + r cn

ci = bi + r ci+1 + s ci+2, para i = n− 2, · · · , 1

donde∂b0∂r = c1,∂b0∂s = ∂b1

∂r = c2,∂b1∂s = c3

Finalmente se llega a:{c2∆r + c3∆s = −b1c1∆r + c2∆s = −b0

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Metodo de Bairstow

Metodo de BairstowResolviendo ∆r y ∆s, se obtiene una mejora de los r y s,puesto que:

ri+1 = ri + ∆rsi+1 = si + ∆s

En cada paso se estima un error aproximado para r y s, esdecir:

|εa,r| =∣∣∆r

r

∣∣× 100%

|εa,s| =∣∣∆s

s

∣∣× 100%

Cuando dichos errores caen por debajo de un error estimado“εs”, los valores de las raıces se determinan mediante:

x =r ±√r2 + 4s

2

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Metodo de Bairstow

Metodo de BairstowExisten tres posibilidades:

1 El cociente es un polinomio de tercer grado o mayor. En talcaso, el metodo de Bairstow se aplica al cociente paraevaluar un nuevo valor de r y s. Los valores anteriores de ry s pueden servir como valores iniciales en esta aplicacion,

2 El cociente es cuadratico. En este caso es posible evaluardirectamente las dos raıces restantes con: x = r±

√r2+4s2 ,

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

r

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Ejemplo

EjemploEmplee el metodo de Bairstow para determinar las raıces delpolinomio:

f5 (x) = x5 − 3.5x4 + 2.75x3 + 2.125x2 − 3.875x1 + 1.25

Utilice como valores iniciales r = s = −1 e itera hasta un errorestimado εs = 1%

beamer-tu-logo

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, · · · , 0cn = 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,

c5 = 1, c4 = −5.5, c3 = 10.75, c2 = −4.875, c1 = −16.375,

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Ejemplo

Solucion {c2∆r + c3∆s = −b1c1∆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,

εa,r =

∣∣∣∣∆rr∣∣∣∣ 100% = 55.23%, εa,s =

∣∣∣∣∆ss∣∣∣∣ 100% = 824.1%

beamer-tu-logo

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.80134.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-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Ejemplo

SolucionDespues de cuatro iteraciones:

r = −0.5, εa,r = 0.063%

s = 0.5, εa,s = 0.040%

x =r ±√r2 + 4s

2=−0.5±

√(−0.5)2 + 4(0.5)

2= 0.5,−1.0

Se queda el cociente:

f3 (x) = −2.5 + 5.25x− 4x2 + x3

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Ejemplo

SolucionTomando r = −0.5 y s = 0.5 y despues de cinco iteraciones:

r = 2,

s = −1.249,

x =2±

√(2)2 + 4(−1.249)

2= 1± 0.499i.

Finalmente, el cociente es un polinomio de primer grado y laraız es:

x = −sr

= 2

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Topicos

1 INTRODUCCIONRaıces de polinomios

2 METODO DE BAIRSTOWPresentacion del metodoFactorizacion de un polinomioMetodo de BairstowEjemplo

3 Metodo de Bairstow con MATLABPrograma MATLAB

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Programa MATLAB

function bai rs towv1 ( a , r0 , s0 ,EE)% fn ( 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−−− Valor i n i c i a l de r% s0−−− Valor i n i c i a l de s% EE−−−Er ro r estimadon= length ( a ) ; % Grado del po l inomio ( 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 del po l inomio ( n−1) es imparelse

m=(n−3) / 2 ; % Grado del po l inomio ( n−1) es parendfor j j =1:m

r = r0 ; s = s0 ;Ear = 1000; Eas = 1000;while Ear>EE | | Eas>EE

b ( n ) = a ( n ) ; % Calculo de los bb ( n−1) = a ( n−1)+ r∗b ( n ) ;for j = n−2:−1:1

b ( j ) = a ( j ) + r∗b ( j +1)+s∗b ( j +2) ;endc ( n ) = b ( n ) ; % Calculo de los cc ( n−1) = b ( n−1)+ r∗c ( n ) ;for j = n−2:−1:2

c ( j ) = b ( j ) + r∗c ( j +1)+s ( 1 )∗c ( j +2) ;enddr = −(−c ( 3 )∗b ( 2 ) +b ( 1 )∗c ( 4 ) ) / ( c ( 2 )∗c ( 4 )−c ( 3 ) ˆ 2 ) ; % Solucion de l sistemads = (−c ( 2 )∗b ( 2 ) +c ( 3 )∗b ( 1 ) ) / ( c ( 2 )∗c ( 4 )−c ( 3 ) ˆ 2 ) ;

r = r +dr ; s = s+ds ;Ear = abs ( dr / r ) ∗100; Eas = abs ( ds / s ) ∗100;

end

x(2∗ j j −1) = ( r +sqrt ( r ˆ2+4∗s ) ) / 2 ;x (2∗ j j ) = ( r−sqrt ( r ˆ2+4∗s ) ) / 2 ;a = b ( 3 : n ) ;n = length ( a ) ;r0 = r ;s0 = s ;

endr = − 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 +sqrt ( r ˆ2+4∗s ) ) / 2 ;x (2∗ j j +2) = ( r−sqrt ( r ˆ2+4∗s ) ) / 2 ;

elsedisp ( ’ e r r o r ’ )

ends a l i d a =[ x ’ ] ;disp ( s a l i d a )

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Programa MATLAB

x(2∗ j j −1) = ( r +sqrt ( r ˆ2+4∗s ) ) / 2 ;x (2∗ j j ) = ( r−sqrt ( r ˆ2+4∗s ) ) / 2 ;a = b ( 3 : n ) ;n = length ( a ) ;r0 = r ; s0 = s ;

endr = − 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 +sqrt ( r ˆ2+4∗s ) ) / 2 ;x (2∗ j j +2) = ( r−sqrt ( r ˆ2+4∗s ) ) / 2 ;

elsedisp ( ’ e r r o r ’ )

ends a l i d a =[ x ’ ] ;disp ( s a l i d a )

beamer-tu-logo

INTRODUCCION METODO DE BAIRSTOW Metodo de Bairstow con MATLAB

Programa MATLAB

>> a=[1 −3.5 2.75 2.125 −3.875 1 .25 ]a =

1.0000 −3.5000 2.7500 2.1250 −3.8750 1.2500

>> bai rs towv1 ( a,−1,−1,1)0.5000−1.0000

1.0000 − 0.4993 i1.0000 + 0.4993 i2.0071

>> bai rs towv1 ( a,−1 ,−1 ,0.1)0.5000−1.0000

1.0000 − 0.4994 i1.0000 + 0.4994 i1.9996

>> bai rs towv1 ( a,−1,−1,0.01)0.5000−1.0000

1.0000 − 0.5000 i1.0000 + 0.5000 i2.0000