Thread Subject:

Guaranteed precision at numerical integration?

Hello,

in order to prove a mathematical statement, I need check the value of an integral which is evaluated numerically in Matlab.

Now, which guarantee do I have that the value is correct up to say the 5th significant digit? Since, if it is only correct some 99.9% of the time, I apparantly can not use this value to rigorously prove the mathematical statement..

Infos/Links on this topic are highly appreciated! Thank you very much in advance,
Best regards.

On 11/2/2011 2:05 PM, Triantafyllos wrote:
> Hello,
>
> in order to prove a mathematical statement, I need check the value of an
>integral which is evaluated numerically in Matlab.
>
> Now, which guarantee do I have that the value is correct up to say the 5th
>significant digit? Since, if it is only correct some 99.9% of the time, I apparantly
>can not use this value to rigorously prove the mathematical statement..
>
> Infos/Links on this topic are highly appreciated! Thank you very much in advance,
> Best regards.

Do you know what the exact value is supposed to be?

If you do not the correct value, then I do not see how can you
guarantee anything.

One common method to use, is to make the intervals smaller and
smaller (the numerical integration intervals, or interval lengths)
until relative error has reached some preset value, which
the user decides on.

--Nasser
ps. I am not an expert in numerical analysis, but play one on TV.

Hi Nasser,
thanks for your message. So regarding the relative error which can be predefined: Is this maximal error guaranteed or just an approximation? That is my problem.

Also, I have a range where I want the value to be. However I don't think that this knowledge changes something on whether it is possible to guarantee something regarding the correctness..because there is no reason why it should

"Nasser M. Abbasi" <nma@12000.org> wrote in message <j8s591$nuu$1@speranza.aioe.org>...
> On 11/2/2011 2:05 PM, Triantafyllos wrote:
> > Hello,
> >
> > in order to prove a mathematical statement, I need check the value of an
> >integral which is evaluated numerically in Matlab.
> >
> > Now, which guarantee do I have that the value is correct up to say the 5th
> >significant digit? Since, if it is only correct some 99.9% of the time, I apparantly
> >can not use this value to rigorously prove the mathematical statement..
> >
> > Infos/Links on this topic are highly appreciated! Thank you very much in advance,
> > Best regards.
>
> Do you know what the exact value is supposed to be?
>
> If you do not the correct value, then I do not see how can you
> guarantee anything.
>
> One common method to use, is to make the intervals smaller and
> smaller (the numerical integration intervals, or interval lengths)
> until relative error has reached some preset value, which
> the user decides on.
>
> --Nasser
> ps. I am not an expert in numerical analysis, but play one on TV.
>
>
>
>

On 11/2/2011 4:00 PM, Triantafyllos wrote:

> "Nasser M. Abbasi"<nma@12000.org> wrote in message<j8s591$nuu$1@speranza.aioe.org>...
>> On 11/2/2011 2:05 PM, Triantafyllos wrote:
>>> Hello,
>>>
>>> in order to prove a mathematical statement, I need check the value of an
>>> integral which is evaluated numerically in Matlab.
>>>
>>> Now, which guarantee do I have that the value is correct up to say the 5th
>>> significant digit? Since, if it is only correct some 99.9% of the time, I apparantly
>>> can not use this value to rigorously prove the mathematical statement..
>>>
>>> Infos/Links on this topic are highly appreciated! Thank you very much in advance,
>>> Best regards.
>>
>> Do you know what the exact value is supposed to be?
>>
>> If you do not the correct value, then I do not see how can you
>> guarantee anything.
>>
>> One common method to use, is to make the intervals smaller and
>> smaller (the numerical integration intervals, or interval lengths)
>> until relative error has reached some preset value, which
>> the user decides on.
>>
>> --Nasser
>> ps. I am not an expert in numerical analysis, but play one on TV.
>>
>>
>>
>>

Please do not top post. Makes it hard to follow. adjusted below:

> Hi Nasser,
> thanks for your message. So regarding the relative error which
> can be predefined: Is this maximal error guaranteed or just an
>approximation? That is my problem.
>

Relative error is something you specific, a number, which
you set. It is common thing to do in numerical
methods.

Let say I(n) is the numerical integral, when using N intervals.
Then relative_error at step n = |I(n)-I(n-1)|/|I(n)|

You can then say when relative_error < 0.001, then stop. And
use I(n) as your final answer. The value 0.001 is something you
decide on. The smaller, the more 'accurate' your final answer
is supposed to be.

Again, if you do not know the exact (analytical correct value),
I do not know what else to use. If you know the exact value,
then you can use that in the above formula, like this

relative_error = |exact_value-I(n)|/|exact_value|
(assuming the exact value is not zero).

> Also, I have a range where I want the value to be. However
>I don't think that this knowledge changes something on whether it
>is possible to guarantee something regarding the correctness..because
>there is no reason why it should
>

If the algorithm you are using is guaranteed to converge on the problem,
and the problem you are solving is well posed (i.e. it does have a
solution), then you can use the above method to decide how 'good' your
final numerical answer is.

Other than that, you need to specify what exactly is the problem you
are solving and more details.

good luck,
--Nasser

"Triantafyllos" wrote in message <j8s49o$4hf$1@newscl01ah.mathworks.com>...
> Hello,
>
> in order to prove a mathematical statement, I need check the value of an integral which is evaluated numerically in Matlab.
>
> Now, which guarantee do I have that the value is correct up to say the 5th significant digit? Since, if it is only correct some 99.9% of the time, I apparantly can not use this value to rigorously prove the mathematical statement..
>
> Infos/Links on this topic are highly appreciated! Thank you very much in advance,
> Best regards.

You CANNOT guarantee any fixed tolerance on a numerical
integration. Period.

One can always provide a function that will cause any adaptive
integration tool such as quad to fail any tolerance you choose.

Period.

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <j8shit$ib4$1@newscl01ah.mathworks.com>...
> "Triantafyllos" wrote in message <j8s49o$4hf$1@newscl01ah.mathworks.com>...
> > Hello,
> >
> > in order to prove a mathematical statement, I need check the value of an integral which is evaluated numerically in Matlab.
> >
> > Now, which guarantee do I have that the value is correct up to say the 5th significant digit? Since, if it is only correct some 99.9% of the time, I apparantly can not use this value to rigorously prove the mathematical statement..
> >
> > Infos/Links on this topic are highly appreciated! Thank you very much in advance,
> > Best regards.
>
> You CANNOT guarantee any fixed tolerance on a numerical
> integration. Period.
>
> One can always provide a function that will cause any adaptive
> integration tool such as quad to fail any tolerance you choose.
>
> Period.
>
> John

I thought about if there was an algorithm which only stopped after checking via the standard error terms (using derivatives) that the desired precision has been reached? However, I understand that evaluating these error terms usually involves evaluating derivatives in certain ranges, something which may in most cases cause at least similar problems as the original problem.

And according to your statement John, there is no such algorithm for general functions, which sounds reasonable.

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <j8shit$ib4$1@newscl01ah.mathworks.com>...
> You CANNOT guarantee any fixed tolerance on a numerical
> integration. Period.
>
> One can always provide a function that will cause any adaptive
> integration tool such as quad to fail any tolerance you choose.
>
> Period.
>
> John
- - - - - - - - - -
  I support what John has stated. Using any of the numerical integration procedures always necessarily depends on the values of the given integrand at a finite, discrete set of points, simply because a computer has time for carrying out only a finite number of arithmetic operations. Who is say what may happen between such points if nothing further is known about the integrand? For all you know, it could suddenly shoot up to some enormous value and come back down without the quadrature routine ever being aware of it.

  To be rigorously certain about placing bounds on an integral's value, you must know something about its integrand at all points within the continuum range of integration. If it is a real sine function for example, you would know rigorously that it never exceeds the value one in absolute value. If you know that its second derivative value is bounded between su and sl over an interval between (closely-spaced?) points x1 < x2, then the integral between x1 and x2 differs from that of the enclosed trapezoid by -s*(x2-x1)^3/12 for some s between su and sl. (I hope I remembered that formula correctly.) This should illustrate the kinds of things you would need to know about an integrand for a fully rigorous proof of an integral value's bounds.

  Of course if you can find an analytic expression for the integral using the methods of calculus, that is the very best kind of rigor to have because it depends only on the endpoint values of the indefinite integral.

Roger Stafford

"Triantafyllos" wrote in message <j8sk7m$pum$1@newscl01ah.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <j8shit$ib4$1@newscl01ah.mathworks.com>...
> > "Triantafyllos" wrote in message <j8s49o$4hf$1@newscl01ah.mathworks.com>...
> > > Hello,
> > >
> > > in order to prove a mathematical statement, I need check the value of an integral which is evaluated numerically in Matlab.
> > >
> > > Now, which guarantee do I have that the value is correct up to say the 5th significant digit? Since, if it is only correct some 99.9% of the time, I apparantly can not use this value to rigorously prove the mathematical statement..
> > >
> > > Infos/Links on this topic are highly appreciated! Thank you very much in advance,
> > > Best regards.
> >
> > You CANNOT guarantee any fixed tolerance on a numerical
> > integration. Period.
> >
> > One can always provide a function that will cause any adaptive
> > integration tool such as quad to fail any tolerance you choose.
> >
> > Period.
> >
> > John
>
> I thought about if there was an algorithm which only stopped after checking via the standard error terms (using derivatives) that the desired precision has been reached? However, I understand that evaluating these error terms usually involves evaluating derivatives in certain ranges, something which may in most cases cause at least similar problems as the original problem.
>
> And according to your statement John, there is no such algorithm for general functions, which sounds reasonable.

An adaptive numerical integration uses the function
values at a selected set of points. It then computes
an estimate of the integral, along with an estimate of
the error, based on what are typically implicit local
polynomial approximations to the function.

If those polynomial approximations are inaccurate,
then one cannot expect the estimate of the integral to
be of limited quality. For example, can you compute
the integral of a step function using a tool like quad?
Since the function is discontinuous, it will be poorly
approximated near the discontinuity, so the integral
in that subregion will be poor.

Another problem case is a function that is identically
zero, except for what is effectively a delta function
at some location- a very narrow but very high spike,
making the true integral some non-zero but large value.
Since quad will almost certainly miss this narrow spike,
seeing only a function that is zero at every point
chosen, the adaptive rule will fail.

For yet one more example where you will see problems
using an adaptive tool like quad, pass quad a function
that is everywhere constant, and exactly zero. Now,
save those locations it chooses to evaluate the function
at. Next create a new function which is identically zero
at every such location that quad chose on that first pass
through, but very different from zero at other points.
One can do this using a Lagrange interpolating
polynomial for example. The true integral will be
any arbitrary number, yet at every point that quad
chooses, the function is identically zero. Therefore,
quad will perforce predict an integral of zero, yet
the function may have any integral you choose to
specify.

My point is that one can always fool an adaptive
routine like quad. As well, it is impossible to assure
absolutely a given tolerance. At best one can only
provide a tool which is robust to such failures,
returning a value which is PROBABLY within the
desired tolerance. Worse, one cannot even put a
measure on the probability of success.

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <j8smmf$360$1@newscl01ah.mathworks.com>...
> "Triantafyllos" wrote in message <j8sk7m$pum$1@newscl01ah.mathworks.com>...
> > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <j8shit$ib4$1@newscl01ah.mathworks.com>...
> > > "Triantafyllos" wrote in message <j8s49o$4hf$1@newscl01ah.mathworks.com>...
> > > > Hello,
> > > >
> > > > in order to prove a mathematical statement, I need check the value of an integral which is evaluated numerically in Matlab.
> > > >
> > > > Now, which guarantee do I have that the value is correct up to say the 5th significant digit? Since, if it is only correct some 99.9% of the time, I apparantly can not use this value to rigorously prove the mathematical statement..
> > > >
> > > > Infos/Links on this topic are highly appreciated! Thank you very much in advance,
> > > > Best regards.
> > >
> > > You CANNOT guarantee any fixed tolerance on a numerical
> > > integration. Period.
> > >
> > > One can always provide a function that will cause any adaptive
> > > integration tool such as quad to fail any tolerance you choose.
> > >
> > > Period.
> > >
> > > John
> >
> > I thought about if there was an algorithm which only stopped after checking via the standard error terms (using derivatives) that the desired precision has been reached? However, I understand that evaluating these error terms usually involves evaluating derivatives in certain ranges, something which may in most cases cause at least similar problems as the original problem.
> >
> > And according to your statement John, there is no such algorithm for general functions, which sounds reasonable.
>
> An adaptive numerical integration uses the function
> values at a selected set of points. It then computes
> an estimate of the integral, along with an estimate of
> the error, based on what are typically implicit local
> polynomial approximations to the function.
>
> If those polynomial approximations are inaccurate,
> then one cannot expect the estimate of the integral to
> be of limited quality. For example, can you compute
> the integral of a step function using a tool like quad?
> Since the function is discontinuous, it will be poorly
> approximated near the discontinuity, so the integral
> in that subregion will be poor.
>
> Another problem case is a function that is identically
> zero, except for what is effectively a delta function
> at some location- a very narrow but very high spike,
> making the true integral some non-zero but large value.
> Since quad will almost certainly miss this narrow spike,
> seeing only a function that is zero at every point
> chosen, the adaptive rule will fail.
>
> For yet one more example where you will see problems
> using an adaptive tool like quad, pass quad a function
> that is everywhere constant, and exactly zero. Now,
> save those locations it chooses to evaluate the function
> at. Next create a new function which is identically zero
> at every such location that quad chose on that first pass
> through, but very different from zero at other points.
> One can do this using a Lagrange interpolating
> polynomial for example. The true integral will be
> any arbitrary number, yet at every point that quad
> chooses, the function is identically zero. Therefore,
> quad will perforce predict an integral of zero, yet
> the function may have any integral you choose to
> specify.
>
> My point is that one can always fool an adaptive
> routine like quad. As well, it is impossible to assure
> absolutely a given tolerance. At best one can only
> provide a tool which is robust to such failures,
> returning a value which is PROBABLY within the
> desired tolerance. Worse, one cannot even put a
> measure on the probability of success.
>
> John

Thank you very much for the explanations!

On 2 Nov, 20:05, "Triantafyllos " <xtri...@yahoo.com> wrote:
> Hello,
>
> in order to prove a mathematical statement, I need check the value of an integral which is evaluated numerically in Matlab.

You can't use numerics as *proof* of anything.

Rune

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <j8smmf$360$1@newscl01ah.mathworks.com>...
> "Triantafyllos" wrote in message <j8sk7m$pum$1@newscl01ah.mathworks.com>...
> > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <j8shit$ib4$1@newscl01ah.mathworks.com>...
> > > "Triantafyllos" wrote in message <j8s49o$4hf$1@newscl01ah.mathworks.com>...
>
[Major snip]
>
> Another problem case is a function that is identically
> zero, except for what is effectively a delta function
> at some location- a very narrow but very high spike,
> making the true integral some non-zero but large value.
> Since quad will almost certainly miss this narrow spike,
> seeing only a function that is zero at every point
> chosen, the adaptive rule will fail.
>
> For yet one more example where you will see problems
> using an adaptive tool like quad, pass quad a function
> that is everywhere constant, and exactly zero. Now,
> save those locations it chooses to evaluate the function
> at. Next create a new function which is identically zero
> at every such location that quad chose on that first pass
> through, but very different from zero at other points.
> One can do this using a Lagrange interpolating
> polynomial for example. The true integral will be
> any arbitrary number, yet at every point that quad
> chooses, the function is identically zero. Therefore,
> quad will perforce predict an integral of zero, yet
> the function may have any integral you choose to
> specify.
>
> My point is that one can always fool an adaptive
> routine like quad. As well, it is impossible to assure
> absolutely a given tolerance. At best one can only
> provide a tool which is robust to such failures,
> returning a value which is PROBABLY within the
> desired tolerance. Worse, one cannot even put a
> measure on the probability of success.
>
Good explanation!

(off-center-of-topic...)
But it makes me curious about how quadgk (for example) behaves if one were to do exactly this with a function on an interval [a,b], and then defined a function exactly as you suggests and then tried to evaluate the integral over a slightly shifted interval, say [a,b]+C*abs(b-a), how well would it start to behave when C increases from zero. Ah, back to work, no more fun and games...

Rune Allnor <allnor@tele.ntnu.no> wrote in message <30839444-7c16-4ccb-a411-1a4bcdb5a472@4g2000yqu.googlegroups.com>...
> On 2 Nov, 20:05, "Triantafyllos " <xtri...@yahoo.com> wrote:
> > Hello,
> >
> > in order to prove a mathematical statement, I need check the value of an integral which is evaluated numerically in Matlab.
>
> You can't use numerics as *proof* of anything.
>
> Rune

While your statement Rune certainly depends on your definition of "numerics", regarding what we talk about in this thread, you are wrong.

Example: If I calculate on the computer "a+b" with a,b numbers with many decimals, numerical methods may be used (rounding). Suppose the computer gives the result "a+b=c". Now, if the addition procedure only respects numbers up to the 10th decimal place after the comma then I can guarantee that the mathematical statement "a+b < c + 10^(-9)" is correct.

Also, this counterexample is in no way just pathological since more complicated statements can surely be reduced to a number of such simple statements. As for the "numerical integration" which I was interested in at the beginning: It could have been the case that there is a function in Matlab which evaluates the integral numerically by some standard method, then evaluates the maximal possible error by the known error-terms (e.g. by using that the derivative is monotonic as a sum of well-known other monotonic functions (such a list would have had to be stored in the software); then only a finite number of function evaluations would be needed to estimate the supremum of the derivative over some interval and this could be performed). And this Matlab-function could then return either a value with a guaranteed precision or the note that "it wasnt able to give a value with a guaranteed
precision", e.g. because the derivatives were not combinations of well-known stored monotonic functions. However, such a function seems to be not available and this makes also sense to me.

Thanks to all for your comments! I consider my request solved :)