more on orbit problems, ellipsoids, and naive interval analysis

David Hough sun!Eng!dgh
Thu Feb 28 20:37:22 PST 1991


After claiming that naive interval analysis was no panacea, and citing a
very old lecture, I wondered if I could prove what I claimed or at least
come up with some plausible details.
 
It took me all day to figure out what I really wanted to show, and what was
important, which is this:  conventional interval analysis can be appropriate
when the sup-norm is, and can be a bad deal when another norm is appropriate,
such as the two-norm.
 
The example is simpler than I thought at first:
a simple 1-dimensional orbit problem
will suffice (the attractor at the origin has a hole in it for the
satellite to pass through).  The differential equation is
 
        x'' = -x
        x(0) = x0
        x'(0) = x1
 
The solution is
 
        x(t) = x0 * cos(t) + x1 * sin(t)

Suppose that you can solve the differential equation perfectly (no analytical
errors and no rounding errors) so the only cause of dispersion is
error in the initial values x0 and x1.  Setting up as a conventional
linear system

        X(t) = ( x(t) ) = A * X(0) = ( c s) (x0)
               ( x'(t))              (-s c) (x1)

where c=cos(t) and s=sin(t),
we find that any error D(0) in the initial conditions X(0) maps linearly
into the error D(t) = A * D(0) in the evolved solution X(t).
How should we measure the evolved error D(t)?

We could use a p-norm

        Np(D) ** p = sum (|wi * di|**p)

which in one case of interest is

        Ninf(D) = max{ |w0 * d0|, |w1 * d1| }

Ninf(D) corresponds to naive interval analysis: the "size" of a set
is the largest dimension of an enclosing box whose sides are parallel to
the coordinate axes.

The other case of interest is

        N2(D) = sqrt ((w0 * d0)**2 + (w1 * d1)**2)
              = sqrt (D*.W.D)
where
                W = (w0**2 0    )

                    (0     w1**2)

N2(D) corresponds to measuring the size of a set by the largest
dimension of an enclosing ellipsoid.  Note that because A is
orthogonal and W is diagonal,

        N2(D(t)) = sqrt(D(0)*.W.D(0))

independent of t!  There is no growth in the size of the error bound.
That reflects the fact that this is a very stable system.

Ninf(D(t)) doesn't reflect that stability, since it's really

        Ninf(D(t)) = max { w0 * | c * d0 + s * d1 |,
                           w1 * |-s * d0 + c * d1 | }


If Ninf(D(0)) == N0, looking at t=pi/2 and considering the extremes
of the starting enclosing box, where |w0 * d0| == N0 and |w1 * d1| == N0,
we see that

        Ninf(D(pi/2)) = max { w0 * |d1|, w1 * |d0| }
                      = max {w0/w1,w1/w0} * N0

which means that the size of the bounding set must grow by an exponential
factor with time unless w0 == w1; but in that case, consider t=pi/4
whence

        Ninf(D(pi/4)) = w0 * sqrt(0.5) * max {|d0+d1|,|d0-d1|}
                      = w0 * sqrt(0.5) * (|d0|+|d1|)
                      = w0 * sqrt(0.5) * (N0/w0 + N0/w1)
                      = sqrt(2) * N0


so the size of the bounding set must grow by an exponential factor in
this case as well.

What's really going on here is that the actual reachable set is shaped
much more like an ellipsoid than a bounding box, even if it starts
out as a box; bounding that set by
a box incorporates much a much larger set than the reachable set;
and the reachable set from that box will be somewhat larger than from
the ellipsoid; compounding this over many steps, you get exponentially
larger growth in the size of the bounding box than in the bounding
ellipsoid.

People who teach or work with this sort of thing on a daily basis will no doubt
point out the errors in the foregoing, but hopefully the main idea is
correct and instructive.

Realistic orbit problems involve three x dimensions and a corresponding
set of x' dimensions, and the attractor is a lumpy planet with an atmosphere
rather than a point mass, but I think the fundamental issue is the same.




More information about the Numeric-interest mailing list