ECE257ECE257 NumericalNumerical Methods Methods andandScientificScientific ComputingComputingRoots of EquationsRoots of EquationsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutTodayToday’’s class:s class:••Roots of EquationsRoots of Equations••Bracketing MethodsBracketing MethodsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutRoots of EquationsRoots of Equations••Given a function f(x), the roots are thoseGiven a function f(x), the roots are thosevalues of x that satisfisfy the relation f(x)=0values of x that satisfisfy the relation f(x)=0€ f (x) = ax2+ bx + c = 0••ExampleExample€ x =−b ± b2− 4ac2a••The roots are:The roots are:ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutRoots of EquationsRoots of Equations••The need to solve for roots show up in manyThe need to solve for roots show up in manyengineering problemsengineering problems••Example: Finding the zeros and poles in aExample: Finding the zeros and poles in afrequency response transfer functionfrequency response transfer function••Also, can be used to find solutions to implicitAlso, can be used to find solutions to implicitvariablesvariablesECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutExampleExample+-i(t)Ct=0VFind a value of R such that the current is 5A at t=1sRECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutExampleExample••It is not possible to isolate R to the left side andIt is not possible to isolate R to the left side andthus solve for R.thus solve for R.••R is known as an implicit variableR is known as an implicit variable••Rewrite the function as a function of R set to 0Rewrite the function as a function of R set to 0€ i(t) =VRe−tRC5 =VRe−1RC€ f (R) =VRe−1RC− 5 = 0ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutRoots of equationsRoots of equations••Still need a method to solve for this rootStill need a method to solve for this root••Other examples of difficult to solve rootsOther examples of difficult to solve roots€ f (R) =VRe−1RC− 5 = 0€ f (x) = 3x6− 4 x5−12x4−15x3+ 19x2− 6x + 9 = 0€ = 3x5+ 5x4+ 3x3− 6x2+ x + 3( )x − 3( )= 0€ f (x) = ex− x = 0€ f (x) = ln x + x2+ 2 = 0ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutRoots of equationsRoots of equations••Non-computer methodsNon-computer methods––Graphical methodsGraphical methodsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutGraphical MethodsGraphical Methods••Not exactNot exact••Can give you a rough estimate of the rootCan give you a rough estimate of the root••Can give you insights on the number ofCan give you insights on the number ofroots and shape of the curveroots and shape of the curve••Can use the rough estimate in more preciseCan use the rough estimate in more precisenumerical methodsnumerical methodsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutGraphical MethodsGraphical Methods••Use to get an initial estimate of the root andUse to get an initial estimate of the root andalso to find out how many roots there arealso to find out how many roots there areECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutGraphical MethodsGraphical MethodsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutGraphical MethodsGraphical MethodsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutGraphical MethodsGraphical MethodsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutGraphical MethodsGraphical MethodsECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutGraphical MethodsGraphical MethodsGeneral CasesSpecial CasesECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutRoots of equationsRoots of equations••Non-computer methodNon-computer method––Exhaustive Search MethodExhaustive Search Method••To find the root in the interval [a,b], start at x=a, andTo find the root in the interval [a,b], start at x=a, andcheck if f(a) = 0, then try f(a+check if f(a) = 0, then try f(a+ΔΔ), f(a+2), f(a+2ΔΔ), and so on,), and so on,until we get f(x) sufficiently close to 0until we get f(x) sufficiently close to 0••If the step value If the step value ΔΔ is sufficiently small we can obtain an is sufficiently small we can obtain anaccurate result but this could take an extremely longaccurate result but this could take an extremely longtime. For example, if the interval is [0,10] and the steptime. For example, if the interval is [0,10] and the stepsize is size is ΔΔ = 0.001, it will take on average 10 000 = 0.001, it will take on average 10 000guesses.guesses.••In addition to theIn addition to the inefficiency of this approach, if inefficiency of this approach, if f(xf(x) is) isa steep function, this approach may not produce ana steep function, this approach may not produce anaccurate result.accurate result.ECE 257 Numerical Methods and Scientific ComputingFall 2004Lecture 6John A. ChandyDept. of Electrical and Computer EngineeringUniversity of ConnecticutExhaustive SearchExhaustive Search••ExampleExample––Find the root of the