Review Sheet for PHYS 305 at UA
Review Sheet for PHYS 305 at UA
Popular in Course
Popular in Department
This 11 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 25 views.
Reviews for Review Sheet for PHYS 305 at UA
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Chapter 4 Roots of Algebraic Equations In this chapter we will 0 learn how to solve algebraic equations using the 7 Bisection method 7 NewtonRaphson method 7 Secant method 0 introduce the concept of convergence of iterative methods One of the most obvious uses of computer algorithms in the physical and mathe matical sciences is in solving algebraic equations A computational method often provides the only way of obtaining the roots of an equation since analytic solutions exist only for a handful of cases In other situations a computational method may provide a faster route in obtaining the roots of an equation that has known analytic solutions In this chapter we will consider general equations of the form fI07 where is any function of the unknown variable 1 Every equations can be 41 trivially put in this form by subtracting its righthand side from its lefthand side The function may be an analytic expression in closed form such as re 71 l 42 Alternatively it may be a complicated computational procedure that returns a real number for each value of the argument 1 In this chapter we will consider only equations that involve real quantities and search for roots that are real numbers A root 10 of an equation 0 is said to have multiplicity k if there is a function 91 such that 101 I Iok91 A Alternatively a root 10 of an equation 0 is said to have a multiplicity k if 43 the k7th order derivative of the function evaluated at 10 is zero ie if dk r dzk OA To 44 41 Root Multiplicity Intermediate Value Theorem CHAPTER 4 ROOTS OF ALGEBRAIC EQUATIONS 2 2 1 1 g 0 0 1 1 2 IIII 2 IIII 2 1012 2 1012 x x Figure 412 An example of functions that have a root of multiplicity left one center two and right three Figure 41 shows a few illustrative examples of functions with roots of multiplicity one two and three In general a double root corresponds to a function that is tangent to the ziaxis whereas a root of multiplicity three or higher corresponds to a function that has an inflection point on the ziaxisi 41 The Bisection Method This is the simplest and most robust method for nding the root of an equation provided that we can guess an initial interval in which one and only one root exists The algorithm successively divides the interval in half bisects keeping the solution within its limits until it reaches a desired level of accuracy The main drawback of the method is its slow rate of convergence The bisection algorithm is based on the intermediate value theorem Consider afunction that is continuous in the interval a b with lt 0 Then there exists a value 10 in the interval ab such that f10 0 In other words this theorem states that if a continuous function changes sign in the interval a b then there is at least one root of the equation 0 within this interval It is worth paying close attention to the requirement that the function is continuous in the interval abi If it is not then the theorem does not guarantee the existence of a solution Consider for example the function f I 45 z 7 2 Clearly the function changes sign in the interval 0 4 However we cannot apply the intermediate value theorem for this function because it is discontinuous at z 2 Indeed there exists no value of z for which 0 When using the bisection algorithm to nd iteratively the solution of an equation of the form 0 we take the following steps 1 We start with an initial interval ab in which we know a priori that the solution exists 41 THE BISECTION METHOD 43 Roots of Polynomials A polynomial of degree n anzn an71zn 1 mm a0 0 with real coefficients has at most n real rootsl If the degree is an odd number then the polynomial is guaranteed to have at least one real root A polynomial of degree 2 is called a quadratic a polynomial of degree 3 is called a cubic a polynomial of degree 4 is called a quarticl General solutions for polynomials of degree up to four exist in closed forml It can be proved however that there exist no general solutions for polynomials of degree 5 or higher This theorem was proved in the early 19th century by the Norwegian mathematician Niels Hendrik Abel 180271829 and the Italian mathematician Paolo Ruflini 176571822 2 We calculate the midpoint of the interval In 01 b 4 6 3 At this point we need to decide whether the solution lies in the interval a zmid or in the interval 1mm 12 We will use the intermediate value theorem to make this decision If fa rm lt 0 47 then the function changes sign in the interval azmid and therefore this is where the solution liesl In this case we set I zmid so that at the end of this iteration the solution lies again in the interval a by If on the other hand f a f Imid gt 0 48 then we set a zmid for the same reason 4 If the width of the interval 12 7 a is still larger than the required accuracy we go back to step 2 to re ne the interval 5 When the width of the interval 12 7 a becomes smaller than the required accuracy then we have reached the solution to the equation In step 3 we need to pay special attention to what the algorithm does if the midpoint of the interval happens to be very close to the actual solution ie when fzmid 0 to within numerical accuracy In principle since the algorithm has reached the solution to the equation it can simply exit and return this value How ever this will require the introduction of an additional condition in the main body of the algorithm which will slow down its execution considerablyi Alternatively we can change the condition 47 in step 3 to u rm g 0 4 9 and proceed with the rest of the algorithm unalteredl It is important also to emphasize here the fact that the bisection method does not guarantee that the equation will be satis ed to any accuracyl Indeed the algorithm only guarantees that the root of an equation is bracketed to the required 44 CHAPTER 4 ROOTS OF ALGEBRAIC EQUATIONS double foodouble x prototype for function fx void bisectiondouble lower double upper Uses the bisection algorithm to find the solution to an algebraic equation of the form fx0 that is known to lie in the interval lowerupper The form of the equation is provided by the function foox and is supplied by the user The parameter ACCURACY determines the level to which the initial interval will be refined by successive bisections define ACCURACY 1096 double xmid the midpoint of the interval double alowerbupper its bounds do xmid05ab calculate midpoint if fooafooxmidlt00 if solution is in lower half bxmid set upper boundmidpoint else otherwise axmid set lower boundmidpoint while fabsbagtACCURACY until converged to ACCURACY lowera return the bounds upperb return accuracyi We can calculate what this implies for the value of the function by evaluating its Taylor expansion from I a to z b M fa mewm 4m x Neglecting the terms of higher order and rearranging the above expression we W 7 WM This last equality shows that at the end of the bisection algorithm the equation will obtain meat lD xa be satis ed to the required accuracy only if the function has a weak dependence on the variable 1 ie if ldfdzl S 1 If we need to circumvent this problem we can revise step 3 by requiring not only that the interval 12 7 a is smaller than the required accuracy but that the value of the function evaluated at the midpoint fzmid is smaller than the accuracy as well A C function that implements the bisection method as discussed here is shown above This function requires two arguments the lower and upper bounds of the initial guess for the interval in which a unique solution is guaranteed to exist Upon completion the arguments of the function contain the lower and upper bounds of an interval with a width that is determined by the parameter ACCURACY that contains the root of the equation This algorithm assumes that the function is provided by the user as a C function of the form double foodoub1e x 41 THE BISECTION METHOD 45 xex71 fx Figure 421 The function we 7 1 plotted against the variable x A quick glance reveals that the equation 0 has a unique solution in the interval 71 1 Finding the initial interval in which a unique solution to an equation lies is more of a guess than an algorithmi In most cases calculating the limiting values of the function at ioo or examining the graph of the function gives the best handle on bracketing its solutions These two techniques are illustrated with the following example Example Solving the equation 6 71 0 with the bisection method In order to study whether this equation has roots we will first check the limits of the function re 7 l as I 7gt iooi Calculating one of the limits is simple because lim 16 71 ooi 1700 4 12 Calculating the limiting value of the function as I 7gt 700 however requires the use of L7Hospital7s rule I 71 71 413 75 7 75 7 Aw 1gt grieve gt 1 tkw Because the two limits have opposite signs and the function is continuous the equation has at least one solution for some real value of the variable I If the function is monotonic and has two limits of opposing signs then it has at most one solution We study the monotonicity of the function by evaluating its derivative d i I 1 E i 414 This is positive when I gt 71 and negative when I lt 71 At 1 7l the function takes the value f7l 2 71368 which is negative As a result between I 700 and z 7l the function is negative and decreasing it has a minimum at z 7l and between I 7l and z 00 the function is increasing and changes signi Therefore the equation has only one solution in the interval 71 00 In order to obtain a nite upper bound on the interval in which the solution exists we recognize the fact that if z gt 1 fzzex7lgtlel7lgtli 4 15 Guessing the Initial lnterval Assessment of the Bisection Method 46 CHAPTER 4 ROOTS OF ALGEBRAIC EQUATIONS The function therefore changes sign in the interval 71 1 in which the single root of the equation liesi Alternatively we can guess an initial interval for the bisection algorithm by plotting the function and studying graphically its behavior A quick glance at the gure shows that the equation has only one solution which lies in the interval 71 l as we inferred earlier using analytical methods lnserting this interval as an initial guess in a bisection function allows us to nd the solution to the equation as 10 0567143 with an accuracy ofl X 1043 The bisection method is a very robust and simple to implement algorithm for nding the root of an equation lt guarantees nding the solution at the required accuracy within a nite number of steps The method however has a number of disadvantages It cannot nd the solutions to all equations For example a polynomial that has a root of multiplicity 2 does not change sign across the solution More speci cally the equation I 7 22 0 416 cannot be solved with the bisection method because the function I 7 22 is positive or zero for all real values of It The same is also true for many equations that are not polynomials of It For example the equation ex7z7l0 417 has an obvious root at z 0 even though the function ex 7 z 7 1 is never negativei It requires an a priori knowledge of an interval in which a unique solution exists This not necessarily a disadvantage of the method because it forces us to study thoroughly the equation before we solve it and hence protects us from making mistakes It is worth asking however which root does the bisection method nd when there are more than one roots in the initial interval The answer of course depends on the particular equation and the choice of initial intervali One can answer this question probabilistically however considering a large number of application of the method to various equations with various initial intervalsllli The result is fascinating Consider an equation 0 that has N simple roots in the interval ab which we will denote by 11 lt 12 lt lt zNi The bisection algorithm will nd the odd numbered roots 11 13 etc with equal probability and the even numbered roots 12 14 etc with zero probabilityi It is fair to say that these are not good chances to play with It converges slowly Although the uncertainty in the solution is reduced by a factor of two after each iteration the bisection method is the slowest among the root nding algorithms that we discuss in this chapter Before embarking into a more detailed study of this issue however we need to discuss in general the order of convergence of an iterative method 42 Order of Convergence of an Iterative Method When we employ an iterative method to solve a problem we start with an initial guess of the solution and improve it systematically with each cycle of the algorithmi 43 THE NEWTON RAPHSON METHOD 47 Our aims is to reach a given accuracy for the solution with the smallest number of cycles We often measure the ef ciency of an iterative method to achieve this by calculating its order of convergence For concreteness we will consider an iterative method that aims to nd the root of an algebraic equation 10 and denote by Ii the approximate solution after i iterationsi We will also use the symbol 6 to denote the fractional error between the approximate and the correct solution after i iterationsi If a constant number A exists such that l1i1 Iol W 7 A 418 then we say that our iterative method converged with an order N and an asymptotic error constant A If N l we call the convergence lineari If N 2 we call the convergence quadratic The higher the order of convergence of an iterative method the faster the so lution converges to a required accuracyi lndeed after the rst few iterations the de nition 4 18 implies that the error in the solution achieved by a method with order of convergence N is 541 2 AEZN i 419 We can use this de nition to calculate the order of convergence of the bisection method We will denote by A E b 7 a the size of the initial interval in which the single root exists This is also an estimate of the uncertainty 60 with which we know the solution a pn39on After one iteration the interval and hence the uncertainty is reduced to half ie 61 AQi After two iterations it is reduced by one more factor of two ie 62 A22 A22 and so on In general 1 6i1 Eei 4 20 and therefore the bisection method converges linearly with an asymptotic error constant of 05 We can use the linear order of converge of the bisection method to calculate how many iterations we will need to complete in order to reach an uncertainty 6 in the nal estimate of the solution It is easy to show by induction that after i iterations the uncertainty is 6i AZii Setting this to 6 and solving for i we obtain 239 w 4 21 10g10 2 We can therefore reduce the uncertainty with which we know the solution to an algebraic equation by six orders magnitude by using the bisection method for 20 iterations 43 The NewtonRaphson Method The NewtonRaphson method is an iterative algorithm for solving algebraic equa tions of the form 0 It overcomes two disadvantages of the bisection method It does not require knowledge of an interval in which a unique solution lies and it converges quadraticallyi However it does not guarantee convergence to a solution and requires an analytic knowledge of the rst derivative of the function In order to introduce this method we will consider a function that is continuous and such that the equation 0 has a root at z 10 We will also assume that we have made an initial guess for the value of the root which we will 4 8 CHAPTER 4 ROOTS OF ALGEBRAIO EQUATIONS The Development of the NewtonRaphson Methodp Sir Isaac Newton the famous English scientist of the 17th century used in his notes a method introduced by the French mathematician Francois Viete 154071603 in order to solve polynomial equations of order higher than four He then fol lowed a similar approach in his famous book Philosophme N at umlzs Principia Mathematica to solve the non linear equation x esinx M that connects the eccentric anomaly x to the mean anomaly M of a planet in an orbit of eccentricity e In 1690 the English mathematician Joseph Raphson approx imately 164871715 published a similar method to solve poly nomial equations of order up to ten with some references to Newton s work Neither Newton nor Raphson used the newly invented techniques of calculus to derive the method Instead they used algebraic and geometric arguments Half a century later Thomas Simpson 171071761 presented a sim ilar method for solving non linear equations based on argu ments of calculus The familiar Newton Raphson method was published in 1798 by the French mathematician Joseph Louis Lagrange 173671813 with reference to the work by Newton and Raphson but not to the work by Simpson Isaac Newton 164371727 denote by 1 which is different from the true solution by an amount 6 0 xi Using this information the Newton Raphson method allows us to improve our initial guess by calculating approximately the value of 6 In order to estimate 6 we Taylor expand the function f from x to the true solution 0 x 6 We obtain 500 fz 5 fz f 5 iii 50052 a 422 where primes denote derivatives of the function with respect to the variable By de nition f 0 0 and hence we can solve the above equation for 6 Neglecting terms of order 62 or higher we obtain f 6 xi 423 This is the amount we need to add to our guess in order to approach the true solution Because we have neglected terms of second and higher order in the Taylor expansion however we most probably did not reach the solution We therefore need to repeat these steps until we have converged to an acceptable solution We will consider the solution converged if two separate criteria are satis ed First the correction introduced to the solution by the last iteration should be smaller than a required accuracy Second the value of the function at the current value of the solution should be zero to within a required accuracy Figure 43 illustrates graphically the Newton Raphson algorithm In this exam ple 1 is our rst guess for the root of the equation f 0 When we approximate the function around 1 with the Taylor expansion 422 while keeping only terms up to rst order we are effectively replacing the function f with the straight line A1B1 that is tangent at f We then nd the abscissa 2 of the point at which the straight line A1B1 crosses the x axis by evaluating the correction 6 in 4 3 THE NEWTONVRAPHSON METHOD thuze 4 3 A gaphtoal teptesentatton ot the NewtonrRaphson algottthm tot ndtng the toot ot an algebrmc equatton equatton 4 23 We tepeat thts pxoceduze by apptoxtmattrg the funetton mound 22 wtth the tangent 1tne A232 nd the potnt 23 at whtoh thts tangent 1tne otosses the 278x15 and contmue unttl we have zeached the tzue solutton wtth the zequued aooutaoy It ts often sad that followtng the NewtonrRaphson method ts equtvalent to s1tdtng down the funotton along tangent 1tnes untt1 we nd the so1utton We can summattze the steps needed to nd the toot of an equatton wtth the NewtonrRaphson method as follows 1 We staxt wtth an tntttal guess to the toot 21 2 We update out guess setttng 21 5 a 21 whete the ootteotton 5 ts gtven by expzesslon 4 23 3 If 5 ts sma11et than the quuued aooutaoy and f239 o to wtthtn the quuued aooutaoy then we we have teaohed the so1utton Othetwtse we go back to step 2 Theze ts a patttoulat tssue that we need to be cazeful about when oa1ou1attng the eoueetton 5 ustng equatton 4 23 If the cuuent esttmate of the so1utton 21 ts at 01 neat an extzemum 01 an tn eetton potnt of the funetton f2 then the value of the deuvatwe f 2 becomes vezy small and thezefoxe the couectton 5 becomes vety 1atge Ctaphtoally the tangent to the funotton becomes neatly hottzontal and sends the next esttmate of the toot towatds oo O 700 Theze ts no goodgeneta1 way of teoovetttg fzom such an unfoztunate step The best ooutse of aotton ts to use a dt etent tntttal guess fo the so1utton A C functton that tmplements the NewtonrRaphson method as dtscussed heze ts shown above Thts funotton quuues one atguments the tnttta1 guess fo the so1utton Upon completton tt tetutns the toot to the equatton Thts algottthm assumes that the funetton f2 and tts dettvattve f 2 ate ptovtded by the met as C functtons of the fozm double foodouble x and double oopnmedoub1e x If the so1utton to an equatton has mu1ttp1totty one then the NewtonrRaphson otdet of Convexgence 410 CHAPTER 4 ROOTS OF ALGEBRAIC EQUATIONS double foodouble x prototypes for functions double fooprimedouble x double newtonraphsondouble root Uses the NewtonRaphson method to find the solution to an algebraic equation of the form fx0 The function fx and its derivative are provided by the functions foox and fooprimex and are supplied by the user The parameter ACCURACY is used in determining whether the method has converged to a solution Upon completion it returns the root of the equation define ACCURACY 1096 double delta NewtonRaphson correction double fxfprime fx and its derivative fxfooroot fx at xroot do fprimefooprimeroot f x at xroot if fabsfprimegtACCURACY if not extremuminflection deltafxfprime calculate correction else otherwise print error message and exit printfquotNewtonRaphson cannot convergenquot return 00 rootdelta update root fxfooroot fx at root until converged while fabs delta gtACCURACY I I fabsfx gtACCURACY return root method converges quadratically In order to show this7 we will consider two suc cessive approximations 11 and mill evaluated after the i th iteration and the one following it These two trials are related by equation 423 or 1 1 7 xi 7 i 424 1 If we denote by 61 E 11 7 IO and sill E mill 7 10 the deviations of the two approximations from the true solution 10 then 7 m Z1 7 61 7 i 425 We now Taylor expand the function around the true solution 10 to obtain 1 fI fIo f IoI 0 if 10f 10V l fIOWE 10 le1095 10V 7 426 where we have used the fact that fzo 0 We then take the derivative of the expanded function with respect to the variable I and evaluate it at 11 to obtain fIz fIo f 101i 10 4 27 43 THE NEWTON RAPHSON METHOD 411 Inserting equations 4 26 and 427 into equation 425 we obtain l 2 am 7 f W ZIEj fel 4 28 mun my Note that this last equation is value only if f zo 0 which is the reason why we required the multiplicity of the solution to be one We now expand the denominator in the fraction using the approximate relation lza 21azw 429 that is valid when I lt l rearrangement some terms keeping only those that are up to second order in the small parameter 6i and arrive at the nal result 5123 This last relation proves that the NewtonRaphson method converges quadratically 430 to a solution of multiplicity one of an algebraic equation This is of course true as long as the initial guess is not signi cantly different than the true solution If the multiplicity of the root is equal to m gt I then it can be shown that the NewtonRaphson method converges only linearly with an asymptotic error constant of 1 7 7 1 7 m i 431 In general the NewtonRaphson method is an algorithm that converges fast to the solution of an equation starting from a simple initial guess It also does not require an a priori knowledge of an interval in which the solution exists This method however also has a number of disadvantages It requires an analytic knowledge of the derivative In many situations this may not be possible if the function itself is the result of a numerical calculation In other cases calculating the derivative may be computationally so expensive that it counters the gain in speed achieved by the quadratic convergence of the method It does not converge globally Indeed our proof of quadratic convergence relies on two assumptionsi That the current guess to the solution is not very differ ence from the true value and that the derivative of the function at the guess is not zero If either of these conditions is not satis ed the method may not converge at all to the true solutioni In very symmetric situations it enters a cyclic behavior without converging to a solution Further Reading 1 Which root does the bisection algorithm nd Corliss Gi SIAM Review 19 2 325 1977 2 Historical Development of the NewtonRaphson Method Ypma T l SIAM Re view 37 4 531 1995 Assessment of the Newton Raphson method
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'