Numerical Analysis

Math 370 Fall 1998  MWF 11:30am - 12:25pm
\begin{matrix}c \\ ◯ \end{matrix}1998 Ron Buckmire  Fowler 127

Class 14: Monday October 05

SUMMARY Analyzing Root Finding Algorithms Continued: Newton-Raphson and Secant

READING Burden & Faires, 65–75

The Newton-Rapshon Algorithm

Bisection and False Position are both globally convergent algorithms, because, given a bracket which contains a solution, they both will find the solution, eventually.

Newton’s Method (and the Secant Method) is very different from these methods, in that instead of needing a bracket where the solution exists [i.e. two function values whose product is negative] one needs a single guess of the solution, which has to be “close” to the exact answer, in order for these locally convergent to get the solution.

A Derivation of Newton’s Method Write down the first 3 terms of a Taylor expansion of f(x) about the point (p_{0}, f(p_{0}))

Evaluate this function at the root, the point (p_{1}, 0) and solve for p_{1}

This is the iterative step for Newton’s Method Pseudocode for Newton’s Method

\underline{Example} Consider the function f(x) = x^{2} − A, where A > 0 Compute the Newton iterative step using the above function f(x)

Simplify it, so that it look like x_{n+1} = \frac{x_{n} + A/x_{n}}{2} . Recognize this iteration?

Secant Method

The secant method is very similar to Newton’s method, except that instead of actually computing the derivative, one approximates it using a difference quotient. This ends up in making the iterative step look algebraically identical to the one for the False Position method.

\underline{Exercise} We will write down the Secant Method iterative step below

If the iterative step is identical to False Position, how come the Secant Method is not just called the False Position method? Look at the picture... Secant Method, visually

False Position Method, visually Now, let’s recall what False Position look like, visually...

\underline{Example} Consider the following function f(x) = x^{3} − x + 2. On the left figure, draw on the graph the set of approximations to the zero, i.e. {p_{k}}, due to Newton’s Method, if you start at p_{0} = 1

On the right figure, draw on the graph the set of approximations produced by Bisection, Secant and False Position (use differently colored pens).