Re: Q about Interval arithmetic
- To: mathgroup@smc.vnet.net
- Subject: [mg10520] Re: [mg10465] Q about Interval arithmetic
- From: Daniel Lichtblau <danl@wolfram.com>
- Date: Tue, 20 Jan 1998 02:23:06 -0500
- References: <199801160934.EAA08259@smc.vnet.net.>
Ersek_Ted%PAX1A@mr.nawcad.navy.mil wrote:
>
> In the following lines Interval arithmetic gives an Interval that
> contains the range of poly[x] for the domain = Interval[{ -1.0, 0.5
> }].
>
> In[1]:=
> poly[x_] := 15*x^7 + 15*x^2 - 13*x + 15;
>
> In[2]:=
> poly[ Interval [{ -1.0, 0.5 }] ]
>
> Out[2]=
> Interval[{-6.5, 43.1172}]
>
I should mention that nothing magical is happening here. The code that
handles Interval sums computes the interval endpoints for each term
individually, then sums low values and high values of these intervals.
For example:
lis = Apply[List, poly[x]];
In[19]:= ivals = lis /. x->Interval [{ -1.0, 0.5 }]
Out[19]= {15, Interval[{-6.5, 13.}], Interval[{0, 15.}],
> Interval[{-15., 0.117188}]}
In[20]:= Apply[Plus, ivals]
Out[20]= Interval[{-6.5, 43.1172}]
> Roots[eqn, vars] can not find the roots of poly'[x] in closed form.
> This is probably because it isn't possible to do so...
Actually, algebraic numbers represented as Root[] objects constitute a
quite useful representation. I use them to find the exact interval
below.
> ...Hence I would
> figure it's not possible to determine the exact range of poly[x] over
> the given domain.
> However, the exact range is a subset of the Interval in Out[2]. As I
> understand it this should always be the case.
>
> In the lines below I used Plot and FindMimimum to convince myself that a
> smaller Interval containing the exact range and nearly equal to the
> exact range is:
> Interval[{ 12.221, 32.082 }]
>
> Questions:
> Is it possible to improve on the built in algorithm (developed by
> Wolfram Research)?
Yes. But it is not possible to do so better than we can. If you write an
algorithm better than mine, then I'll just get Michael Trott to write
one better than yours. (Such outrageous remarks are a good way to
maintain the vigilance of the moderator).
> Is there a known algorithm that can be used to obtain the smaller (
> preferred ) Interval?
The code at the bottom may be what you have in mind.
> I am not looking for an approach that uses Numerical methods as I did
> below. I want is something that provides gaurenteed results, and works
> on high order polynomials.
>
> In[3]:=
> Plot[poly[x],{x,-1.0,0.5}]
>
> In[4]:=
> FindMinimum[poly[x],{x,0.41}]
>
> Out[4]=
> {12.2202, {x -> 0.4154}}
>
> In[5]:=
> FindMinimum[ -poly[x], {x,-0.8} ] //MapAt[ Minus, # ,1]&
>
> Out[5]=
> {32.0813, {x -> -0.84552}}
>
> Ted Ersek
In the fragment below I assume without checking that poly is a
univariate polynomial in the variable x.
minMax[poly_, x_, low_, high_] := Module[
{testpoints,vals},
testpoints = Apply[List, Map[#[[2]]&,
Roots[D[poly,x]==0, x, Cubics->False, Quartics->False]]];
testpoints = Join[{low,high},
Select[testpoints,
(Head[N[#]]===Real && #>low && #<high)&]];
vals = poly /. x->testpoints;
{Min[vals], Max[vals]}
]
poly = 15*x^7 + 15*x^2 - 13*x + 15;
In[31]:= minMax[poly, x, -1, 1/2] // InputForm Out[31]//InputForm=
{15 - 13*Root[-13 + 30*#1 + 105*#1^6 & , 2] +
15*Root[-13 + 30*#1 + 105*#1^6 & , 2]^2 +
15*Root[-13 + 30*#1 + 105*#1^6 & , 2]^7,
15 - 13*Root[-13 + 30*#1 + 105*#1^6 & , 1] +
15*Root[-13 + 30*#1 + 105*#1^6 & , 1]^2 +
15*Root[-13 + 30*#1 + 105*#1^6 & , 1]^7}
In[32]:= N[%]
Out[32]= {12.2202, 32.0813}
Daniel Lichtblau
Wolfram Research
- References:
- Q about Interval arithmetic
- From: Ersek_Ted%PAX1A@mr.nawcad.navy.mil
- Q about Interval arithmetic