R: Demonstration of the Bisection Method for root-finding on an...

bisection.method {animation}

R Documentation

Demonstration of the Bisection Method for root-finding on an interval

Description

This is a visual demonstration of finding the root of an equation f(x) = 0 on an interval using the Bisection Method.

Usage

bisection.method(FUN = function(x) x^2 - 4, rg = c(-1, 10), tol = 0.001, interact = FALSE, 
    main, xlab, ylab, ...)

Arguments

`FUN`	the function in the equation to solve (univariate)
`rg`	a vector containing the end-points of the interval to be searched for the root; in a `c(a, b)` form
`tol`	the desired accuracy (convergence tolerance)
`interact`	logical; whether choose the end-points by cliking on the curve (for two times) directly?
`xlab,ylab,main`	axis and main titles to be used in the plot
`...`	other arguments passed to `curve`

Details

Suppose we want to solve the equation f(x) = 0. Given two points a and b such that f(a) and f(b) have opposite signs, we know by the intermediate value theorem that f must have at least one root in the interval [a, b] as long as f is continuous on this interval. The bisection method divides the interval in two by computing c = (a + b) / 2. There are now two possibilities: either f(a) and f(c) have opposite signs, or f(c) and f(b) have opposite signs. The bisection algorithm is then applied recursively to the sub-interval where the sign change occurs.

During the process of searching, the mid-point of subintervals are annotated in the graph by both texts and blue straight lines, and the end-points are denoted in dashed red lines. The root of each iteration is also plotted in the right margin of the graph.

Value

A list containing

`root`	the root found by the algorithm
`value`	the value of `FUN(root)`
`iter`	number of iterations; if it is equal to `ani.options('nmax')`, it's quite likely that the root is not reliable because the maximum number of iterations has been reached

Note

The maximum number of iterations is specified in ani.options('nmax').

Author(s)

Yihui Xie <http://yihui.name>

References

http://en.wikipedia.org/wiki/Bisection_method

http://animation.yihui.name/compstat:bisection_method

Examples

oopt = ani.options(nmax = ifelse(interactive(), 30, 2))

## default example
xx = bisection.method()
xx$root  # solution

## a cubic curve
f = function(x) x^3 - 7 * x - 10
xx = bisection.method(f, c(-3, 5))

## interaction: use your mouse to select the two end-points
if (interactive()) bisection.method(f, c(-3, 5), interact = TRUE)

## HTML animation pages
saveHTML({
    par(mar = c(4, 4, 1, 2))
    bisection.method(main = "")
}, img.name = "bisection.method", htmlfile = "bisection.method.html", ani.height = 400, 
    ani.width = 600, interval = 1, title = "The Bisection Method for Root-finding on an Interval", 
    description = c("The bisection method is a root-finding algorithm", "which works by repeatedly dividing an interval in half and then", 
        "selecting the subinterval in which a root exists."))

ani.options(oopt)

[Package animation version 2.2 Index]