Introduction to interval methods

Here are the demo programs for the introductory minicourse on interval methods. Download imni.zip.

The programs are written in Lua and run under the LÍVE framework, which you need to download and install. You also need to learn how to run a LÍVE program in your machine. See this tutorial.

Demo programs

The demo programs are interactive programs that illustrate interval solutions to some basic numerical problems. The programs typically solve a problem at different resolutions. Most of the code in these programs is for graphics, which you can skip. Read the code to understand and play with the numerical part, which is quite small. The numerical core is provided by the libraries. Programs for the same problem differ only in the numerical part. Compare them with a visual diff tool.

All programs react to the keys below. Some programs react to additional keys. See love.keypressed in the code and the brief description of individual programs below.

q or esc
quit the program
s
save a screenshot to your LÍVE directory.
On Mac OS X,this is ~/Library/Application Support/LOVE/imni/.
]
increase the resolution
[
decrease the resolution

To run a program, copy or link it to main.lua. On Mac OS X, just do make main P=foo.lua to select a program to run. This will create a symbolic link main.lua to foo.lua. Doing plain make always runs the program in main.lua. That's how LÍVE works.

Lecture 1

pi.lua
Archimedes and the approximation of π
toggle drawing outer polygons with o
sqrt2.lua
bisection method for computing sqrt(2)
graph.lua
graph plotting and sampling
toggle drawing colors, graph, points, uniform sampling, random sampling c g p u r
graph-ia.lua
graph plotting with interval arithmetic – uniform division
toggle drawing colors with c
graph-ia-adapt.lua
graph plotting with interval arithmetic – adaptive division finds ranges within tolerance
graph-ia-ad.lua
graph plotting with interval arithmetic and automatic differentiation – uniform division finds monotone pieces
graph-ia-ad-adapt.lua
graph plotting with interval arithmetic and automatic differentiation – adaptive division finds monotone pieces

Lecture 2

zero-ia.lua
solving equations with interval arithmetic – adaptive division
zero-ad.lua
solving equations with interval arithmetic and automatic differentiation – adaptive division finds monotone pieces and critical points
zero-ia-ad.lua
solving equations with interval arithmetic and automatic differentiation – adaptive division stops at monotone pieces
ineq-ia.lua
solving inequalities with interval arithmetic – adaptive division
go-ia.lua
global optimization with interval arithmetic – uniform division
go-ia-bb.lua
global optimization with interval arithmetic – adaptive division with branch and bound
go-ia-bb-2d.lua
global optimization with interval arithmetic – adaptive division with branch and bound 2d

Lecture 3

fp.lua
distribution of floating-point numbers
implicit-fp.lua
implicit curve plotting via uniform sampling
toggle drawing boxes, using corners with b c
implicit-ia.lua
implicit curve plotting with interval arithmetic – adaptive division
toggle drawing boxes, pruning tree with b p

Lecture 4

implicit-aa.lua
implicit curve plotting with affine arithmetic – adaptive division
toggle drawing boxes, pruning tree with b p
zero-aa.lua
solving equations with affine arithmetic
ineq-aa.lua
solving inequalities with affine arithmetic
go-aa.lua
global optimization with affine arithmetic – uniform division
zonotope-1d.lua
zonotope approximaton with affine arithmetic
toggle drawing boxes, graph, zonotopes with b g z
move left and right with
graph-aa.lua
graph plotting with affine arithmetic – uniform division shows zonotopes
toggle drawing boxes, colors, zonotopes with b c z
curve-ia.lua
curve plotting with interval arithmetic – uniform division
toggle drawing boxes, curve, points with b c p
curve-aa.lua
curve plotting with affine arithmetic – uniform division
toggle drawing boxes, curve, points, zonotopes with b c p z

Libraries

The demo programs use these libraries. The libraries for interval arithmetic and affine arithmetic export the same interface so that you can transparetly use affine arithmetic as a replacement for interval arithmetic. The libraries are very simple and are for demo only. They are not meant to be used in production.

ia.lua
interval arithmetic
ad.lua
automatic differentiation, one independent variable
aa1.lua
affine arithmetic, one independent variable
aa2.lua
affine arithmetic, two independent variables

Feedback

All feedback is welcome. Please send questions, comments, suggestions, requests, bug reports, and new demos to me by email.