The Secant Method - USM

1 Jim LambersMAT 772 Fall Semester 2010-11 lecture 4 NotesThese notes correspond to Sections and in the Secant MethodOne drawback of Newton s Method is that it is necessary to evaluate ( ) at various points, whichmay not be practical for some choices of . Thesecant methodavoids this issue by using a finitedifference to approximate the derivative. As a result, ( ) is approximated by asecant linethroughtwo points on the graph of , rather than a tangent line through one point on the a Secant line is defined using two points on the graph of ( ), as opposed to a tangentline that requires information at only one point on the graph, it is necessary to choose two initialiterates 0and 1. Then, as in Newton s Method , the next iterate 2is then obtained by computingthe -value at which the Secant line passing through the points ( 0, ( 0)) and ( 1, ( 1)) has a -coordinate of zero.

2 This yields the equation ( 1) ( 0) 1 0( 2 1) + ( 1) = 0which has the solution 2= 1 ( 1)( 1 0) ( 1) ( 0)which can be rewritten as follows: 2= 1 ( 1)( 1 0) ( 1) ( 0)= 1 ( 1) ( 0) ( 1) ( 0) ( 1)( 1 0) ( 1) ( 0)= 1( ( 1) ( 0)) ( 1)( 1 0) ( 1) ( 0)= 1 ( 1) 1 ( 0) 1 ( 1) + 0 ( 1) ( 1) ( 0)= 0 ( 1) 1 ( 0) ( 1) ( 0).This leads to the following ( Secant Method ) Let : be a continuous function. The following algorithmcomputes an approximate solution to the equation ( ) = two initial guesses 0and 1for = 1,2,3,..doif ( ) is sufficiently smallthen = return end +1= 1 ( ) ( 1) ( ) ( 1)if +1 is sufficiently smallthen = +1return endendLike Newton s Method , it is necessary to choose the starting iterate 0to be reasonably closeto the solution.

3 Convergence is not as rapid as that of Newton s Method , since the Secant -lineapproximation of is not as accurate as the tangent-line approximation employed by Newton will use the Secant Method to solve the equation ( ) = 0, where ( ) = 2 Method requires that we choose two initial iterates 0and 1, and then compute subsequentiterates using the formula +1= ( )( 1) ( ) ( 1), = 1,2,3,..We choose 0= 1 and 1= Applying the above formula, we obtain 2= 3= 4= we can see, the iterates produced by the Secant Method are converging to the exact solution = 2, but not as rapidly as those produced by Newton s Method . We now prove that the Secant Method converges if 0is chosen sufficiently close to a solution of ( ) = 0, if is continuously differentiable near and ( ) = = 0.

4 Without loss ofgenerality, we assume >0. Then, by the continuity of , there exists an interval = [ , + ]such that3 4 ( ) 5 4, .It follows from the Mean Value Theorem that +1 = ( ) 1 ( ) ( 1)2= ( )( ) ( )= 1 ( ) ( ) ( ),where lies between and , and lies between and 1. Therefore, if 1and arein , then so are and , and +1satisfies +1 max 1 5 /43 /4 , 1 3 /45 /4 23 .We conclude that if 0, 1 , then all subsequent iterates lie in , and the Secant Methodconverges at least linearly, with asymptotic rate constant 2 order of convergence of the Secant Method can be determined using a result, which we willnot prove here, stating that if{ } =0is the sequence of iterates produced by the Secant Methodfor solving ( ) = 0, and if this sequence converges to a solution , then for sufficiently large, +1 1 for some constant.

5 We assume that{ }converges to of order . Then, dividing both sides of the above relationby , we obtain +1 1 1 .Because is the rate of convergence, the left side must converge to a positive constant as .It follows that the right side must converge to a positive constant as well, as must its other words, there must exist positive constants 1and 2 1 1, 1 1 can only be the case if there exists a nonzero constant such that 1 = 1 1 ,which implies that1 = ( 1) and = .Eliminating , we obtain the equation 2 1 = 0,which has the solutions 1=1 + 52 , 2=1 52 we must have >1, the rate of convergence is Bisection MethodSuppose that ( ) is a continuous function that changes sign on the interval [ , ].

6 Then, by theIntermediate Value Theorem, ( ) = 0 for some [ , ]. How can we find the solution, knowingthat it lies in this interval?The Method ofbisectionattempts to reduce the size of the interval in which a solution is knownto exist. Suppose that we evaluate ( ), where = ( + )/2. If ( ) = 0, then we are , must change sign on the interval [ , ] or [ , ], since ( ) and ( ) have differentsigns. Therefore, we can cut the size of our search space in half, and continue this process until theinterval of interest is sufficiently small, in which case we must be close to a solution. The followingalgorithm implements this (Bisection) Let be a continuous function on the interval [ , ] that changes sign on( , ). The following algorithm computes an approximation to a number in ( , ) such that ( ) = = 1,2.

7 Do = ( + )/2if ( ) = 0or is sufficiently smallthen = return endif ( ) ( )<0then = else = endendAt the beginning, it is known that ( , ) contains a solution. During each iteration, this algo-rithm updates the interval ( , ) by checking whether changes sign in the first half ( , ), or inthe second half ( , ). Once the correct half is found, the interval ( , ) is set equal to that , at the beginning ofeachiteration, it is known that the current interval ( , ) contains test ( ) ( )<0 is used to determine whether changes sign in the interval ( , ) or( , ). This test is more efficient than checking whether ( ) is positive and ( ) is negative, orvice versa, since we do not care which value is positive and which is negative.

8 We only care whetherthey have different signs, and if they do, then their product must be comparison to other methods , including some that we will discuss, bisection tends to convergerather slowly, but it is also guaranteed to converge. These qualities can be seen in the followingresult concerning the accuracy of be continuous on[ , ], and assume that ( ) ( )<0. For each positive integer , let be the th iterate that is produced by the bisection algorithm. Then the sequence{ } =1converges to a number in( , )such that ( ) = 0, and each iterate satisfies 2 .It should be noted that because the th iterate can lie anywhere within the interval ( , ) that isused during the th iteration, it is possible that the error bound given by this theorem may bequite seek a solution of the equation ( ) = 0, where ( ) = 2 (1) = 1 and (2) = 1, and is continuous, we can use the Intermediate Value Theoremto conclude that ( ) = 0 has a solution in the interval (1,2), since ( ) must assume every valuebetween 1 and 1 in this use the Method ofbisectionto find a solution.

9 First, we compute the midpoint of theinterval, which is (1 + 2)/2 = Since ( ) = , we see that ( ) changes sign between = and = 2, so we can apply the Intermediate Value Theorem again to conclude that ( ) = 0 has a solution in the interval ( ,2).Continuing this process, we compute the midpoint of the interval ( ,2), which is ( + 2)/2 = Since ( ) = , we see that ( ) changes sign between = and = , so weconclude that there is a solution in the interval ( , ). The following table shows the outcomeof several more iterations of this procedure. Each row shows the current interval ( , ) in whichwe know that a solution exists, as well as the midpoint of the interval, given by ( + )/2, and thevalue of at the midpoint.

10 Note that from iteration to iteration, only one of or changes, andthe endpoint that changes is always set equal to the midpoint. = ( + )/2 ( ) correct solution, to ten decimal places, is , which is the number known as thegolden ratio. For this Method , it is easier to determine the order of convergence if we use a different measureof the error in each iterate . Since each iterate is contained within an interval [ , ] where = 2 ( ), with [ , ] being the original interval, it follows that we can bound the error by = . Using this measure, we can easily conclude that bisection convergeslinearly, with asymptotic error constant 1 MethodsIt is natural to ask whether it is possible to combine the rapid convergence of methods such asNewton s Method with safe methods such as bisection that are guaranteed to converge.