ECE257ECE257 NumericalNumerical Methods Methods andandScientificScientific ComputingComputingRoots of EquationsRoots of EquationsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutTodayToday’’s class:s class:••Roots of EquationsRoots of Equations••PolynomialsPolynomialsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomialsPolynomials••A polynomial is of the form:A polynomial is of the form:••The roots of a polynomial follow these rules:The roots of a polynomial follow these rules:––There will be n roots to an n-th order polynomial.There will be n roots to an n-th order polynomial.The roots may be real or complex and need not beThe roots may be real or complex and need not bedistinctdistinct––If complex roots exist, they exist in conjugate pairsIf complex roots exist, they exist in conjugate pairs((λλ++µµi and i and λλ--µµi)i)––If n is odd, there is at least one real rootIf n is odd, there is at least one real root € fnx( )= a0+ a1x + a2x2+ L + anxnECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomialsPolynomials••Uses in electrical engineeringUses in electrical engineering––Solving for poles and zeros in transferSolving for poles and zeros in transferfunctionsfunctions––Solving characteristic equations in linearSolving characteristic equations in linearordinary differential equationsordinary differential equationsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomialsPolynomials € fnx( )= a0+ a1x + a2x2+ L + anxnF=A[0]FOR I=1 to N K = A[I] FOR J=1 to I K = K * X ENDFOR F = F + KENDFOR € n n + 1( )2 multiplications € n additionsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomialsPolynomials € fnx( )= a0+ x a1+ x a2+ L + xan( )( )F=A[N]FOR I=N-1 to 0 F = F*X + A[I]ENDFOR € n multiplications € n additionsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomial DeflationPolynomial Deflation••Given a polynomial and a single known root,Given a polynomial and a single known root,deflating the polynomial can reduce thedeflating the polynomial can reduce theorder of the polynomial and remove possibleorder of the polynomial and remove possibleredundant rootsredundant roots€ x4− 8x3− 20x2+ 288x − 576••Example:Example:––Root x=4 is knownRoot x=4 is knownECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomial DeflationPolynomial Deflation€ x4− 8x3− 20x2+ 288x − 576€ x − 4€ x3€ x4− 4 x3€ −4 x3€ −20x2€ −4 x2€ −4 x3+ 16x2€ −36x2€ +288x€ −36x€ −36x2+ 144 x€ 144 x€ −576€ +144€ 144 x€ −576€ 0ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomial DeflationPolynomial Deflation••Synthetic DivisionSynthetic Division1 -8 -20 288 -576€ x4− 8x3− 20x2+ 288x − 576414-4-16-36-1441445760ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomial DeflationPolynomial Deflation••Synthetic DivisionSynthetic Division1 -4 -36 +144€ x3− 4 x2− 36 x + 144414 0 0 -36-1440ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomial DeflationPolynomial Deflation••Synthetic DivisionSynthetic Divisionr=a[n]b[n]=0for i=n-1 to 0 b[i]=r r = r*t+a[i]endfor € a0+ a1x + a2x2+ L + anxn= b0+ b1x + b2x2+ L + bn−1xn−1( )x − t( )+ r € n multiplications € n additionsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutPolynomial DeflationPolynomial Deflation••If the known root is a calculated root, approximationIf the known root is a calculated root, approximationerror in that root may be compounded during theerror in that root may be compounded during thedeflation processdeflation process••With forward deflation, i.e. new polynomialWith forward deflation, i.e. new polynomialcoefficients are calculated in descending order, it iscoefficients are calculated in descending order, it isbetter to divide by roots of smallest absolute valuebetter to divide by roots of smallest absolute valuefirstfirst••Round-off errors can also be reduced by using rootRound-off errors can also be reduced by using rootpolishing.polishing.ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutRoots of polynomialsRoots of polynomials••Previous methods (Newton-Raphson, bracketing,Previous methods (Newton-Raphson, bracketing,etc.) have a few problems when applied toetc.) have a few problems when applied topolynomialspolynomials––Must determine an initial guess of the rootMust determine an initial guess of the root––Can not find complex rootsCan not find complex roots––May not convergeMay not converge••Polynomial-specific methodsPolynomial-specific methods––MMüüllerller’’s methods method––BairstowBairstow‘‘s methods methodECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 7John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutMMüüllerller’’s methods method••Similar idea to secant methodSimilar idea to secant method••Instead of projecting a straight line throughInstead of projecting a straight line throughtwo points to estimate the root, project atwo points to estimate the root, project aparabola through three points to estimateparabola through three points to estimatethe rootthe rootECE 257 Numerical Methods and