September 20, 2007 --- Class 8 --- 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.