Interpolation matrix

<clay@claysturner.com> wrote:

>On Mar 3, 12:27&#4294967295;pm, spop...@speedymail.org (Steve Pope) wrote:

>> I have a question: is the "barycentric" form a
>> better-behaved numerical formula for the same interpolator
>> as a standard Lagrangian, or is it a different interpolator function?

>Yes the barycentric form is numerically superior to the standard
>Lagrangian form. Ideally they will both give the same results.

Thanks.

I do not actually think the standard formula is mis-behaved
if you compute it in the correct order.

The formula for a Lagrange coefficient is similar to that of
a binomial coefficient in that there are a large number of
factors in both numerator and denominator; if you were to compute
either of these by itself you might run into a range problem,
but you don't have to.

For example one of the formulas I gave is a constant times:

             (prod over t=1..n)(p + n/2 - t)
        __________________________________________________

                ((n-2)/2 + k)! (n/2 - k)! 

It is clear there are n terms in the numerator, and n-1
in the denominator, so by pairing these up you should 
avoid any range problem even for large n.

This is not to say the barycentric formula isn't numerically
superior, just that the original formula is also reasonable.

Steve

On Mar 3, 2:03�pm, spop...@speedymail.org (Steve Pope) wrote:
> <c...@claysturner.com> wrote:
> >On Mar 3, 12:27&#4294967295;pm, spop...@speedymail.org (Steve Pope) wrote:
> >> I have a question: is the "barycentric" form a
> >> better-behaved numerical formula for the same interpolator
> >> as a standard Lagrangian, or is it a different interpolator function?
> >Yes the barycentric form is numerically superior to the standard
> >Lagrangian form. Ideally they will both give the same results.
>
> Thanks.
>
> I do not actually think the standard formula is mis-behaved
> if you compute it in the correct order.
>
> The formula for a Lagrange coefficient is similar to that of
> a binomial coefficient in that there are a large number of
> factors in both numerator and denominator; if you were to compute
> either of these by itself you might run into a range problem,
> but you don't have to.
>
> For example one of the formulas I gave is a constant times:
>
> &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;(prod over t=1..n)(p + n/2 - t)
> &#4294967295; &#4294967295; &#4294967295; &#4294967295; __________________________________________________
>
> &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; ((n-2)/2 + k)! (n/2 - k)!
>
> It is clear there are n terms in the numerator, and n-1
> in the denominator, so by pairing these up you should
> avoid any range problem even for large n.
>
> This is not to say the barycentric formula isn't numerically
> superior, just that the original formula is also reasonable.
>
> Steve

To get an idea of the issue is look at using equally spaced data and
when you get up to around 50 points, the dynamic range of the weights
will be near 15 orders of magnitude. At this point double precision
floating point will start to have serious round off issues. The
barycentric form (form 2) is neat in that the numerator and the
denominator's errors tend to cancel each other out. The "standard"
Lagrange form is quite problematic.

Clay

<clay@claysturner.com> wrote:

>On Mar 3, 2:03&#4294967295;pm, spop...@speedymail.org (Steve Pope) wrote:

>> I do not actually think the standard formula is mis-behaved
>> if you compute it in the correct order.

>To get an idea of the issue is look at using equally spaced data and
>when you get up to around 50 points, the dynamic range of the weights
>will be near 15 orders of magnitude. At this point double precision
>floating point will start to have serious round off issues.

Thanks.

I've never needed to use a Lagrangian interpolator with anywhere
near that many points.  Often just four points results in 
a signal distortion of -60 dBc.  I would randomly guess that
50 points would give you a residual that is hundreds of dB down.

Depending on scenario, etc.

Steve