Re: Reliable ComputingÙ absxÙ for intervals?
Michel,
No, the problem appears with any floating-point algorithm that would not get the correct answer if it were executed in infinite precision. Gaussian elimination in interval arithmetic DOES enclose the true solution (assuming conditioning is good enough to avoid division by an interval containing zero). Gauss-Seidel iteration does not.
What an approximate ODE solver (or PDE solver) is SUPPOSED to compute is NOT the correct answer, but an approximation to the correct answer. What the solver computes often can be expressed as a truncated Taylor series.
As a very simple example, consider y' = -y, y(0) = 1. True solution is y(t) = e^{-t). Let h be a (constant) step size.
The simplest numerical method one might apply (please don't) is Euler's method. y(h) is approximated by 1 - h, which differs from the true e^{-h} by terms of order h^2 and higher, the truncation error or the method.
Similarly, rootfinding by Newton's method does not yield containment when executed in intervals, although a very good interval version of Newton's method works by evaluating the derivative on a relatively wide interval containing the root.
Dr. George F. Corliss
Electrical & Computer Engineering
Haggerty Engineering #296
Marquette University
P.O. Box 1881
1515 W. Wisconsin Ave.
Milwaukee WI 53201-1881
George.Corliss@xxxxxxxxxxxxx
414-288-6599; -288-4400 (GasDay); -288-5579 (Fax)
Www.eng.mu.edu/corlissg
On 4/15/09 4:01 PM, "Michel Hack" <hack@xxxxxxxxxxxxxx> wrote:
George Corliss wrote:
> Consider an ODE solver, say Runge-Kutta. If we change double to interval,
> we should get an interval that encloses what the RK code computes, but it
> is quite likely that we will get an interval that does NOT enclose the
> correct answer. If that happens, the user is likely to conclude that
> the interval community has lied; he did NOT get an enclosure of the true
> solution. He missed class the day the prof covered truncation errors?
I'm not sure I follow. Truncation errors should occur in both directions,
possibly eventually widening intervals to the point of uselessness, but
why would containment be violated? I have to admit that I have never
used RK (though I have heard of it, and browsed, but never seriously
studied, some numerical analysis textbooks), so perhaps I'm overlooking
something.
Are you perhaps assuming incorrect scalar->interval conversions,
i.e. replacement of 0.1 with
[+1.00000000000000006E-001, +1.00000000000000006E-001]
instead of
[+9.99999999999999917E-002, +1.00000000000000006E-001]
when converting the program (assuming Binary64-based arithmetic)?
Whatever IA extensions are added to the language, they must provide
means to avoid that kind of mistake.
Michel.
---Sent: 2009-04-15 21:13:13 UTC