Section3.3Newton's Method
We now investigate a calculus-based method (originally proposed by Newton and later
modified by Joseph Raphson) for solving the algebraic equation \(f(x) = 0\). In very basic
terms, this method involves iteratively finding tangent lines to a differentiable curve
and locating where those tangent lines intersect the horizontal axis.
The following is an Algorithm for the Newton-Raphson method:
The Newton-Raphson method for solving algebraic equations can be described as follows:
Check that \(f \in C^2\) on a given domain and find a way to guarantee that
\(f\) has a root on that domain.
Pick a starting point \(x_0\) in the domain
Draw a tangent line to \(f\) at \(x_0\) and find where it intersects with the
\(x\)-axis
Use the intersection of the tangent line with the \(x\)-axis as the next
approximation of the root (call it \(x_1\)).
repeat steps 3 and 4 until the intersection point gets close to the
root that you would like to approximate
Write the Newton-Raphson method algorithm mathematically. It may help to also draw a
picture of what the Newton-Raphson method is doing graphically.
Write a MATLAB function for the Newton-Raphson method. Be sure that it can take an
anonymous function handle as an input along with an initial guess and an error
tolerance.
When you are done writing code, test your Newton-Raphson function on an
algebraic equation for which you know the exact root (for example: \(x^2 - 2 = 0\)).
Newton's Method is known to have a quadratic convergnece rate. This means that \( \lim_{k \to \infty} \frac{|x_{k+1}-x_*|}{|x_k-x_*|^2}\) will be constant where \(x_*\) is the root that we're hunting for (see pages 85-87 of the textbook for a more thorough explanation). This implies that if we plot the error in the new iterate on the \(y\)-axis and the error in the old iterate on the \(x\)-axis of a log-log plot then we will see a constant slope of 2.
Ok. That might not be exceptionally clear so let's build an experiment to clarify things. Modify your
Newton-Raphson code so that it outputs all of the iterations instead of just the final root. Once you have the iterations compute the the error between the
approximations and the exact root. For simplicity let's solve the equation \(x^2-2=0\).
Plot the sequence of error approximations with the iterate \(e_k\) on the \(x\)-axis and
the iterate \(e_{k+1}\) on the \(y\)-axis of a log-log plot.
Your plot command will
look something like: loglog(error(1:end-1),error(2:end),'b*')
where
“error” is a vector containing all of the errors.
Quadratic convergence means that at every iteration the error should decrease by
roughly 2 orders of magnitude. How can you see this in your plot?
Now to finish this problem let's do the same thing for the bisection method. Modify your code to get the iterates and plot the errors on the same log-log plot as the Newton-Raphson errors. Explain the implication of this plot.
In the text read the projectile motion problem from page 71 up to the end of
page 72. Then consider Chapter 4 Exercise #17. Solve part (a) as instructed, but in
part (b) consider distances from 0 meters and up. Use \(v_0 = 126m/s\) and \(g=9.8m/s^2\)
as instructed in the text. Use your Newton-Raphson solver on equation (4.24) of the text to determine
the range of the weapon. Provide a plot to show the optimal firing angle
given the distance (distance on the \(x\)-axis and \(\theta\) on the \(y\)-axis). You should be able to validate your plot with a plot of the analytic solution found in part (a).
(Yes, I know that it is silly to do a numerical solver when you know the analytic solution, but think of this as another exercise to build your coding chops.)