If we only have the function defined at discrete points
(say it's a vector of experimental readings, or the output of Matlab's
differential equation solver, for instance), that brings in the issue
of *interpolation*, an important numerical technique we'll ignore
for now.

You may have seen this root-finding method, also called the Newton-Raphson method, in calculus classes. It is a simple and obvious approach, and is an example of the common engineering trick of approximating an arbitrary function with a "first-order" function -- in two dimensions, a straight line. Later in life, you'll expand functions into an infinite series (e.g. the Taylor series), and pitch out all but a few larger, "leading" terms to approximate the function close to a given point.

As usual, Wikipedia has a very nice article (with a movie), on Newton's method. For the mathematically inclined there's a proof of the method's quadratic convergence time: roughly, the number of correct digits doubles at every step. (BTW, the proof uses a Taylor series.)

** The Idea:**

- Guess an
x close to the root of interest._{0} - Start Iteration: Approximate the function at that point by a straight line. The obvious choice is the line tangent to (in the direction of) the function's graph at that point.
- Notice that the slope of the required tangent is the derivative of the
function, so the line we want has that slope and goes through the
point
(x ._{0}, f(x_{0})) - This tangent line goes through the x-axis at a point
x , which is easy to calculate and which we bet is nearer to the root than_{1}x is._{0} - Compute
x and_{1}f(x ), and we're ready to go to Start Iteration and repeat the process until for some_{1}x , we find a_{i}f(x close enough to zero for our purposes._{i})

Considered as an algorithm, this method
is clearly a `while ` -loop; it runs
until a small-error condition is met.

** The Math:**

Say the tangent to the function at
_{0}_{1}_{0})_{0})_{0})/(x_{0} - x_{1})
=f'(x_{0})_{1} =
x_{0} - f(x_{0})/f'(x_{0})

Repeat until done: Generally,

(Eq. 1) _{i+1} =
x_{i} - f(x_{i})/f'(x_{i}).

**Example:** The function
^{4} -7.533333 x^{3} + 29.9
x^{2} -37.966667
x +5

We can see there is a root near 4.4, for instance.

3 iterations of the method starting at
_{0} = 3.8

CB's `function [my_root, err] = newton(x0, maxerr)`
is 11 statements long, including 2 to count and print iterations and 2
to assign a global array of polynomial coeffficients.
the functions ` function y = f(x)` and `der = f_der(x)`
are four statements, including `function, global, end`, and one
line
that actually does some work.

** Extensions and Issues:** There are lots of extensions, and various tweaks to the
method (use higher-order approximation functions, say). The
method extends to functions of several variables
(i.e. higher-dimensional problems). In that case it uses the
Jacobian matrix you may see in vector calculus, and also the
generalized matrix inverse you'll definitely see in the Data-Fitting
segment later in 160.

Clearly there are potential problems. The process may actually diverge, not converge. Starting too far from the desired root may diverge or find some other root. See a more in-depth treatment (like Wikipedia, say) for more consumer-protection warnings. To detect such problems and gracefully abort, One could watch that the error does not keep increasing for too long, or count iterations and bail out after too many, etc.

Here's Wikipedia: Secant method.

**The Idea:**

- Pick two initial values of
x , close to the desired root. Call themx . Evaluate_{0}, x_{1}y and_{0}= f(x_{0})y ._{1}= f(x_{1}) - As with the tangent line in Newton's method, produce the (secant)
line
through
(x and_{0}, y_{0})(x , and compute where it crosses the x-axis, and call that point_{1}, y_{1})x . Get_{2}y ._{2}=f(x_{2}) - Bootstrap along: replace
(x with_{0}, y_{0}), (x_{1}, y_{1})(x and repeat._{1}, y_{1}), (x_{2}, y_{2}) - Keep this process up: derive
(x from_{i}, y_{i})(x and_{i-1}, y_{i-1})(x until_{i-2}, y_{i-2})y meets the error criterion._{i}

**The Math: ** Easy to formulate given we've done
Newton's method. Starting with Newton (Eq. 1), use
the "finite-difference" approximation:

_{i}) ≈ Δy/Δx =
(f(x_{i}) - f(x_{i-1}))
/(x_{i} - x_{i-1})

Thus for the secant method we need two initial

Generally,

(Eq. 2) _{i+1} = x_{i} - f(x_{i})
[( x_{i} - x_{i-1}) /
( f(x_{i}) - f(x_{i-1}))]

** Example:**
For the same problem as above, a reasonable function prototype is

`function [my_root, err] = secant(lastx,x, maxerr)`.
Initializing at _{0} = 3.8_{1} = 3.9`newton`.

** Extensions and Issues:**
The most popular extension in one dimension is the *method of false position*,
*(q.v.)*
There is also an extension to higher-dimensional functions.

Same non-convergence issues and answers as Newton, only risk is greater with the approximation.

The convergence rate is, stunningly enough,
the Golden Ratio
, which turns up all sorts of delightfully unexpected places, not just Greek
sculpture, Renaissance art, Fibonacci series, *etc.* Thus it is
about
1.6, slower than Newton but still better than linear.
Indeed, it may run
faster since it doesn't need to evaluate the derivative at every step.