September 30, 2004 --- Class 10 --- Graphing velocity ratio,
			Root Finding (continued)

Activities:

	Graphing the velocity ratio as function of the height via shell script

		It is relatively easy to make a graph of the velocity ratio
		as a function of the initial height.  We can use a foreach
		loop to set the initial height.  Then, we need to manipulate 
		the output of adapt_step to get the velocity ratio.  This
		last step is done with an awk script.  The
		awk file ~sg/vel_ratio.a  contains two lines:

/^V/{vel=-$4;  rec=NR}
NR==rec+1 && NR >1  { ratio =vel/$1; print ratio}

		Below is a shell script to run adapt_step and pipe the output
		through awk.  If you run this at the screen, you will
		find all the prompts from adapt_step, which are written
		to the standard error, mixed up with the output from the
		awk script, which are written to the standard output.
		If you redirect the standard output to a file with the ">"
		symbol, only the output you want will wind up in the file.

#!/bin/csh

	foreach height ( 20000 40000 60000 80000 100000 120000 140000 160000)
		echo -n $height "  "
		adapt_step <<EOF |awk -f ~sg/vel_ratio.a
		$height
		.001
		.1
EOF
	end

	Secant Method

		In the last class we talked about the secant method and the
		method of false position for root finding, but we did not give
		any formulae.  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.

		Two codes in ~sg/chap3 can be used to monitor the convergence 
		of these two methods.  The codes are false_position.c and
		secant.c .  
		They implement the algorithms and print the
		results after each step.  You may vary the function f(x).
		These are set up a examples of the algorithm, not as general
		purpose root finding subroutines.

		We will talk more about root finding later in the course.
		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 will look at this code in
		the next class.