\documentstyle[fleqn,epsf,calc]{article}
\markright{Chapter 3: Worksheet 10}
\begin{document}

\Bf{Chapter 3: Worksheet 10  \hfill Jack K. Cohen \hfill Colorado School of Mines}

\vspace{1.5ex}
\Cb{Newton's Method, Equation Solving with \Mma}
\vspace{1.5ex}

\noindent \Bf{Suggested Problems}
Section 3.9: Read section 3.9.

\vspace{1.5ex}

\begin{enumerate}
\item Illustrative Example 2 (the ``cork ball problem'') gives the formula for the volume of a segment of height $x$ and radius $r$ of a sphere whose radius is $a$ as $V = $ {\Large $\frac{\pi x}{6}$} $(3r^2 + x^2)$ (see Figure 1).  The same volume was cited on the last worksheet as $V = $ {\Large $\frac{\pi x^2}{3}$} $(3a - x)$.
	\begin{figure}[htb]
	\epsfysize 110pt
	\centerline{\epsffile{ws10p1.eps}}
	\caption{Sketch for Problem 1} 
	\end{figure}
	
	\begin{enumerate}
	\item Show that these formulas are equivalent. (\Sc{note:} The quantity here denoted by $x$ is also denoted by $y$ and $h$ in other problems and examples in the text.)
	\item Suppose that the density of water is 1 and the density of the ball is $\rho$. Appeal to Archimede's law to obtain the equation $\rho V_{\rm sphere} = V_{\rm segment}$.   Using the \Em{second} form above for the volume of the segment, obtain the cubic equation $4 \rho a^2 = 3 a x^2 - x^3$.   Show that when, as in the illustrative example, $\rho = 1/4$ and $a = 1$, we obtain the equation $3x^2 - x^3 = 1$ in agreement with the text.
	\item Use the Intermediate Value Theorem to prove that the explicit cubic equation, $x^3 - 3x^2 + 1 = 0$, just derived has at least one root in the interval $[0, 1]$.
	\end{enumerate}

\item One way to solve equations with \Mma\ is to code in your own Newton's method:
\begin{verbatim}
f[x_] := x^3 - 3x^2 + 1
x = 0.5

x = x - f[x]/f'[x]
\end{verbatim}
Here we have defined the ``cork ball''  function in accordance with \Mma\ syntax and defined a starting  value at the midpoint of an interval that we have proved contains a root.  The third line computes the ``new''  value of $x$ ($x_{n+1}$) on the left from the ``old'' value ($x_n$) used on the right (the ``old'' value is 0.5 the first time we do this).  We can then ``Enter'' the third line over and over again to generate a sequence of approximations.  On this example, you should get successively:
\begin{verbatim}
0.666667
0.652778
0.652704
0.652704
0.652704
\end{verbatim}
This agrees with the value found in the text.  Apply this approach to the following problems:
	\begin{enumerate}
	\item (3.9.1) $x^2 - 5 = 0; \quad  x_0 = 2.5$ (i.e. find the positive square root of 5)
	\item (3.9.2) $x^3 - 2 = 0; \quad  x_0 = 1.5$ (i.e. find the cube root of 2)
	\end{enumerate}

\item One problem with the above method is that we erase each approximation in the process of producing the next one.   One simple way to avoid this is to use a ``loop'':
\begin{verbatim}
f[x_] := x^3 - 3x^2 + 1
x = 0.5;
Do[
    x = x - f[x]/f'[x];
    Print[x],
{8}]
\end{verbatim}
which gives the ``cork ball'' output:
\begin{verbatim}
0.666667
0.652778
0.652704
0.652704
0.652704
0.652704
0.652704
0.652704
\end{verbatim}
The ``8'' that appears in curly brackets at the end of ``Do Loop'' tells how many times to iterate.

 \Bf{Important and subtle point:}  By default, \Mma\ tries to compute with exact arithmetic.  This can take a long time, so it is usually best to include a decimal point (e.g., 0.5  instead of  1/2) in the starting value to signal to \Mma\ that infinite precision is not required.
 
 Since Newton's method often converges quickly, let's print the results to greater precision by altering the \Tt{Print} statement:
\begin{verbatim}
f[x_] := x^3 - 3x^2 + 1
x = 0.5;
Do[
	x = x - f[x]/f'[x];
	Print[ N[x, 16] ],
{8}]
\end{verbatim}
\begin{verbatim}
0.6666666666666666
0.6527777777777778
0.6527036468361321
0.6527036446661393
0.6527036446661393
0.6527036446661393
0.6527036446661393
0.6527036446661393
\end{verbatim}

Apply this approach to the following problems:
	\begin{enumerate}
	\item (3.9.3) $x^5 - 100 = 0; \quad  x_0 = 5.0$ (i.e. find the fifth root of 100)
	\item (3.9.4) $x^{3/2} - 10 = 0; \quad  x_0 = 2.0$ (i.e. compute $10^{2/3}$)
	\item $x^{1/3} - 1; \quad x_0 = 2.0$ (i.e. compute $1^3$ the hard way)
	\item $x^{1/3} - 1; \quad x_0 = 5.0$
	\item Explain why the output in the last two examples differ.
	\end{enumerate}

\item There are several equation solvers directly built in to \Mma---be aware that Newton's method is a key element in their construction!  However, other considerations are also needed in such professional packages to deal with potential ``divergent'' behavior as occured in the last example.   Polynomial equations are markedly simpler than the general case and \Tt{Solve} and \Tt{NSolve} deal with these and with some equations that can be reduced to polynomials by algebraic manipulations (e.g. by squaring).   \Tt{Solve} attempts to give exact solutions, while \Tt{NSolve} gives only numerical solutions.  As implied, \Tt{Solve} cannot exactly solve all polynomial equations (there is no mathematical method to do this for equations of degree 5 and higher).   However, \Tt{Solve} can sometimes handle equations with parameters.

First a cubic with a parameter---\Tt{Solve} is our only chance:
\begin{verbatim}
equation = x^3 - 2a x^2 - 4 x + 8a == 0;
solutions = Solve[equation, x]
    {{x -> 2 a}, {x -> 2}, {x -> -2}} (* the solutions written as rules *)

equation /. solutions     (* check solutions by substituting back *)
   {True, True, True}    (* all 3 check exactly *)
\end{verbatim}
\Tt{Solve} works ok here, because the equation was special (an answer that is 17 pages long isn't of much use and that can easily happen with an arbitrary cubic).   Here is a quadratic for which we get exact solutions with \Tt{Solve}:
\begin{verbatim}
equation = x^2 - 3x + 4 == 0;
Solve[equation, x]
           3 + I Sqrt[7]         3 - I Sqrt[7]
    {{x -> -------------}, {x -> -------------}}
               2                     2
\end{verbatim}
If we only want numerical approximations, it is more efficient to use \Tt{NSolve}:
\begin{verbatim}
equation = x^2 - 3x + 4 == 0;
NSolve[equation, x]
    {{x -> 1.5 - 1.3228756555323 I}, 
      {x -> 1.5 + 1.3228756555323 I}}
\end{verbatim}

Use \Tt{NSolve} to get all three roots of the ``cork ball'' equation.

\begin{figure}[htb]
\epsfysize 100pt
\centerline{\epsffile{ws10p5.eps}}
\caption{Diagram for Problem 5.} 
\end{figure}

\item A 100-ft tree stands 20 feet from a 10-ft fence.  Then the tree is ``broken'' at a height of x feet, so that it just grazes the top of the fence and touches the ground on the other side of the fence with its tip (see Figure 5). 
	\begin{enumerate}
	\item Derive the equation $x^3 - 68x^2 + 1100x - 5000 = 0$ for $x$.
	\item Solve this equation using \Tt{NSolve} and decide which roots make physical sense.
	\end{enumerate}

\item \Tt{NSolve} won't work  on most non-polynomial equations, for example, it fails on our old friend the ``asteroid'' equation:
\begin{verbatim}
equation = Cos[1000/r] == r/(r + 10);
NSolve[equation, r]
    Solve::ifun: 
       Warning: Inverse functions are being used by Solve, so
         some solutions may not be found.
     Solve::tdep: 
       The equations appear to involve transcendental
         functions of the variables in an essentially
         non-algebraic way.
              1000       r
    NSolve[Cos[----] == ------, r]
                r       10 + r
\end{verbatim}
All those messages are \Tt{NSolve}'s way of saying it can't solve the equation.   In this case, you must use \Tt{FindRoot}.  \Tt{FindRoot} requires additional information---at the minimum a starting guess (as does Newton's method).   By previous trial and error, we know there's a root near 50,000, so:
\begin{verbatim}
lhs = Cos[1000/r] - r/(r + 10);
FindRoot[lhs == 0, {r, 50000}]
    {r -> 50008.3}

solution = N[ FindRoot[lhs, {r, 50000}], 16]
    {r -> 50008.32913584035}
    
lhs /. solution
               -11
    -1.10986 10
\end{verbatim}
Notice the techniques for printing more decimal places and for checking the accuracy of the solution.  Also observe that it is still an open question of how to get that starting value without trial and error---the next Chapter will give us a technique for doing that.
% FindRoot -- asteroid problem, tan problem

\begin{enumerate}
\item \Tt{Plot} $\tan x - x$ on $[0, 4 \pi]$ to get crude values for the positive roots near the origin.
\item Use \Tt{FindRoot} to get accurate values for the first 4 positive roots of the equation $\tan x + x = 0$ and check the accuracy of your solutions.
\end{enumerate}

% Logistic growth
\end{enumerate}
\end{document}
