iconEuler Examples

Interval Methods for Zeros

We demonstrate some interval methods for zeros of functions of one or several variables.

Let us start with a simple example. Solve x^2=2.

>function f(x) &= x^2-2
                                x  - 2

We need the derivative for the Newton algorithm.

>function df(x) &= diff(f(x),x)
                                 2 x

We start with the interval [1,2].


The Interval Newton Method is the following iteration.

Xn = X && ( m - f(m)/f(X))

It stops, if X=Xn. If X contains a zero, Xn does too. The inclusion is guaranteed, if (m-f(m)/X is a subset of X. The computation must be evaluated in interval terms, of course.

>repeat m=middle(X); Xn=X&&(~m,m~-f(~m,m~)/df(X)), until Xn==X; X=Xn; end;

Since the result is a proper subset of the interior of the start interval, we have a guaranteed inclusion.

Euler implements this in the function inewton2, which takes two functions of vectors f and df, or two expressions.


The function mxminewton computes the derivative with Maxima.


There is a simple function ibisect, which runs the bisection algorithm carefully to guarantee an inclusion of the solution.



Let us try another example.

>function f(x) &= tan(x)-x
                              tan(x) - x

We can use the bisection algorithm starting with a course interval.


How accurate is this result?

Indeed a plot shows that the cancellation in tan(x)-x destroys the accuracy of the function, and thus the accuracy of the zero.


Interval Methods for Zeros

The function ibisect stops early.


The Interval Newton Algorithm is not much better.


To get a better result, we need to approximate the function with its Taylor series, which can be evaluated very well.

>function f(x) &= taylor(tan(x),x,0,10)-x
                          9       7      5    3
                      62 x    17 x    2 x    x
                      ----- + ----- + ---- + --
                      2835     315     15    3


Strictly, we have not solved tan(x)=x here. We need to add an error term to be precise. The error of the Taylor series is

 f^(11)(xi)/11! x^11

with some xi between 0 and x.

>function dtan11(x) &= diff(tan(x),x,11);

We add the error term to f.

>function fi(x) := f(x) + dtan11(0||~x~)/11!*x^11

Now we get an exact and guaranteed solution.