September 26, 2006 --- Class 9 --- Root finding, Running adapt.c to find height,
			Oscillatory motion

Activities:

	Root finding

		We devoted most of the class to a discussion of root finding.

		In the program adapt.c, the secant method is used to solve
		the problem of what height must the object be dropped from.
		The secant method is easy to implement because only the
		function, not its derviative is needed.  Another advantage
		of this method is that it is not necessary to know that the
		root lies in a particular range.  However, the secant method 
		may be unstable.

		Some of the other methods require knowing that the root lies in
		a particular interval.  One knows there is a root because
		the function changes sign.  The bisection method evaluates
		the function at the middle of the interval.  From the sign
		of the function at the midpoint, it can be determined which
		half of the interval contains the root.  The function is
		then evaluated in the middle of that half interval, etc.
		This method doesn't have any stability problems, but it is
		slow to converge since the error only decreases by a factor
		of 2 each time the interval is cut in half.  After all, in
		this method we are only using the sign of the function at
		the endpoints of the current interval.

		In the method of false position, we approximate the
		function by a straight line between the endpoints of the
		interval and use the root of the straight line to guess
		where the root is.  We evaluate the function at the guessed
		root and replace the endpoint with the same sign of the
		function with the guess.  We then use the two current
		endpoints in the same procedure.  Convergence can be slow.
		The method of false position is a lot like the secant method
		except that in the secant method we always keep the two most
		recent points.  When we do that, we might no longer be in the
		original interval that brackets a root.  (In fact, we don't
		have to start off bracketing the root with the secant method.)
		This is what leads to the potential instability.

	Details of secant and false position methods

		In each method, we use two points on the curve
		of the function we want to find the root of.  We connect these
		points by a straight line, and find the root of the line.  That
		x value is used as our next guess of the root.  It is easy to
		show using simlar triangles that if the two points are (x1,y1)
		and (x2,y2). the value of x on the straight line for which y=0
		is given by

		x2 - y2* (x1-x2)/(y1-y2)

		In ~sg/chap3, you will find code in secant.c and 
		false_position.c for testing these methods.
		They implement the algorithms and print the
		results after each step.  You may vary the function f(x).
		These are set up as examples of the algorithm, not as general
		purpose root finding subroutines.

		We tried to find the root of f(x) = tan(x) - 6 using the 
		secant method.  It didn't work for one set of initial guesses, 
		but did for another.  Look at the difference between secant.c
		and secant2.c.  The code secant does not converge, but
		secant2, with different initial conditions does converge:

1.325900e+00 -1.998603e+00
1.374589e+00 -9.689273e-01
1.420405e+00 5.991223e-01
1.402900e+00 -1.000287e-01
1.405404e+00 -8.996072e-03
1.405652e+00 1.485253e-04
1.405648e+00 -2.169805e-07
1.405648e+00 -5.230483e-12
1.405648e+00 3.552714e-15
1.405648e+00 3.552714e-15

		Notice how quickly this converges near the end.  False position
		does not converge as quickly:

8.878937e-01 -4.770704e+00
1.207087e+00 -3.372870e+00
1.328629e+00 -1.951659e+00
1.375649e+00 -9.408807e-01
1.393945e+00 -4.046209e-01
1.401079e+00 -1.645238e-01
1.403864e+00 -6.530093e-02
1.404951e+00 -2.566518e-02
1.405376e+00 -1.004793e-02
1.405541e+00 -3.927745e-03
1.405606e+00 -1.534439e-03
1.405631e+00 -5.993137e-04
1.405641e+00 -2.340556e-04
1.405645e+00 -9.140465e-05
1.405647e+00 -3.569534e-05
1.405647e+00 -1.393967e-05
1.405648e+00 -5.443676e-06
1.405648e+00 -2.125846e-06
1.405648e+00 -8.301780e-07
1.405648e+00 -3.241982e-07
1.405648e+00 -1.266047e-07

		Note that in each set of output the variables are double 
		precision, but only a limited number of digits are printed out.

	Putting it all together: adapt.c

		In the program adapt.c, the secant method is used to solve
		the problem of what height must the object be dropped from.
		The secant method is easy to implement because only the
		function, not its derviative is needed.  Another advantage
		of this method is that it is not necessary to know that the
		root lies in a particular range.  However, the secant method 
		may be unstable as we saw above.

		We will talk more about root finding later in the course.
		There is a routine zbrent in Numerical Recipes that is
		quite sophisticated.
		The secant method is just fine for the problem solved in
		adapt.c because the function is very close to a straight
		line.

        Solving for the height
 
                To find the height at which the ball must be dropped, a
                root finding algorithm is added to the code.  It is based
                on the secant method.  The secant method can be unstable,
                so the loop is terminated upon a maximum number of
                iterations or when the desired accuracy is obtained.  This
                is done in the code adapt.c.  We finished the class by
		looking at the code and running it to solve the problem.

        Chapter 5---Oscillatory Motion

                We used the code ~sg/chap5/sho2.c and executable sho2 to 
		calculate the motion of a simple harmonic oscillator.  
		This code is based on the Euler method.  We found that energy 
		is not conserved.  In fact, we found that the energy grows
		exponentially with time, no matter how small the 
		integration step size.

		We will explore this in more detail in our next class.