Bisection

Type

Closed.

Requirements

A function f(x) and an interval [a, b] (in which f(x) is continuous) containing one and only one root.

Risks

If the function is discontinuous, the program can have an error when evaluating. Also, if the interval has more or less than one roots, unexpected behavior can happen.

Convergence rate

Linear

Advantages

If the criteria for the interval is satisfied, it always converges. Also, this is the easiest method to program and the easier to understand. The smaller the interval given, the faster it converges.

Disadvantages

This is the method with the lowest converge rate.

Fault tolerance

As long as the criteria are satisfied, this method doesn’t run.

Number of roots on each run

One.

Newton-Raphson

Type

Open.

Requirements

A function f(x), the derivative df(x) of f(x) and a starting point.

Risks

If the function presents small slopes in any iteration, the method diverges. On the other hand, if the function presents really big slopes in any iteration, the method converges really slow.

Convergence rate

Quadratic.

Advantages

This method has the quickest converging rate. Also, it just requires a starting point instead of two.

Disadvantages

This method requires the derivative, which can be hard to calculate and/or evaluate. Also, small slope functions (such as log(x)) diverge.

Fault tolerance

Some functions, such as periodic functions, can lead to unexpected behaviors with certain values. Also, small slopes fail.

Number of roots on each run

One.

Secant

Type

Open.

Requirements

A function f(x) and two starting points (different).

Risks

Similar as Newton Raphson. Also, this method can fail if both starting values are similar.

Convergence rate

Aureal number.

Advantages

It runs quicker than bisection and does not require a derivative.

Disadvantages

Can fall in the same errors as Newton-Raphson.

Fault tolerance

Fails less than Newton-Raphson, but still can have unexpected behaviours.

Number of roots on each run

One.

Bairstow

Type

Open.

Requirements

A polynomic function f(x) and two starting values.

Risks

The farther the starting values from the roots, the longer it takes to converge.

Convergence rate

Quadratic.

Advantages

This method allows us to find complex roots, and it may take a long time, but it doesn’t fail.

Disadvantages

Only works for polynomial functions. Really hard to implement and understand.

Fault tolerance

This method doesn’t fail.

Number of roots on each run

All.
Advertisements