Numerical inversion of Z-transform?

I'm trying to do some research into existing methods for doing
numerical inverse discrete laplace transform (a.k.a.. Z-transform).

My problem is that numerical methods are really needed when you have
non-rational Z-transform expression which do
not posess a closed form inverse. For rational expressions in z this
is not really a problem since you can always do them
"manually" (or perhaps by plotting the impulse response in matlab)

(Just to be clear I'm not after calculating the frequencey response,
i.e. z=exp(j*w) for some w, since that is "trivial"
as long as numerical stability is not a big concern.)

For laplace transform there is a multitude of suggestions for
numerical inverse but this does not seem to be
the case for Z transforms. Perhaps due to the fact that most signal
processing applications the Z-transform
will be rational and then the inverse is trivial in the mathematical
since (but can of course still be very tedious).

Even though it might be full of mathematical nastiness would it be
feasible e to do a conversion from the
z plane to the w/s plane, e.g. doing some "suitable" substitution of
z=f(s), to get a representation of the
Z-transform as a continuous Laplace transform? (I suspect any kind of
error analysis in this case would
would be really difficult.)

Is anyone aware of some published work in this area? I haven't really
been able to find anything really relevant?

/J

On Sun, 24 Jan 2010 14:33:29 -0800, johan162 wrote:

> I'm trying to do some research into existing methods for doing numerical
> inverse discrete laplace transform (a.k.a.. Z-transform).
> 
> My problem is that numerical methods are really needed when you have
> non-rational Z-transform expression which do not posess a closed form
> inverse. For rational expressions in z this is not really a problem
> since you can always do them "manually" (or perhaps by plotting the
> impulse response in matlab)
> 
> (Just to be clear I'm not after calculating the frequencey response,
> i.e. z=exp(j*w) for some w, since that is "trivial" as long as numerical
> stability is not a big concern.)
> 
> For laplace transform there is a multitude of suggestions for numerical
> inverse but this does not seem to be the case for Z transforms. Perhaps
> due to the fact that most signal processing applications the Z-transform
> will be rational and then the inverse is trivial in the mathematical
> since (but can of course still be very tedious).
> 
> Even though it might be full of mathematical nastiness would it be
> feasible e to do a conversion from the z plane to the w/s plane, e.g.
> doing some "suitable" substitution of z=f(s), to get a representation of
> the Z-transform as a continuous Laplace transform? (I suspect any kind
> of error analysis in this case would
> would be really difficult.)
> 
> Is anyone aware of some published work in this area? I haven't really
> been able to find anything really relevant?
> 
> /J

So you're starting with an expression in z that's 'hard' -- i.e. that 
doesn't have a nice rational polynomial in the denominator, and you want 
to find an algorithm that either gives you an impulse response or that 
gives you the system's response to a known signal?

I _think_ that you can do this numerically using an inverse Fourier 
transform.  Practically, this would mean using the expression in z to 
find the frequency response at an adequate number of points around the 
unit circle, then performing an inverse FFT to get the time-domain 
response.  There are probably clever rules of thumb to figure out how 
many points you need, but I would do it by giving it a whirl, checking to 
see if the response dies off, and adding more points if it doesn't.

-- 
www.wescottdesign.com

On 24 Jan, 23:53, Tim Wescott <t...@seemywebsite.com> wrote:
> On Sun, 24 Jan 2010 14:33:29 -0800, johan162 wrote:
> > I'm trying to do some research into existing methods for doing numerical
> > inverse discrete laplace transform (a.k.a.. Z-transform).
>
> > My problem is that numerical methods are really needed when you have
> > non-rational Z-transform expression which do not posess a closed form
> > inverse. For rational expressions in z this is not really a problem
> > since you can always do them "manually" (or perhaps by plotting the
> > impulse response in matlab)
>
> > (Just to be clear I'm not after calculating the frequencey response,
> > i.e. z=exp(j*w) for some w, since that is "trivial" as long as numerical
> > stability is not a big concern.)
>
> > For laplace transform there is a multitude of suggestions for numerical
> > inverse but this does not seem to be the case for Z transforms. Perhaps
> > due to the fact that most signal processing applications the Z-transform
> > will be rational and then the inverse is trivial in the mathematical
> > since (but can of course still be very tedious).
>
> > Even though it might be full of mathematical nastiness would it be
> > feasible e to do a conversion from the z plane to the w/s plane, e.g.
> > doing some "suitable" substitution of z=f(s), to get a representation of
> > the Z-transform as a continuous Laplace transform? (I suspect any kind
> > of error analysis in this case would
> > would be really difficult.)
>
> > Is anyone aware of some published work in this area? I haven't really
> > been able to find anything really relevant?
>
> > /J
>
> So you're starting with an expression in z that's 'hard' -- i.e. that
> doesn't have a nice rational polynomial in the denominator, and you want
> to find an algorithm that either gives you an impulse response or that
> gives you the system's response to a known signal?
>
> I _think_ that you can do this numerically using an inverse Fourier
> transform. &#4294967295;Practically, this would mean using the expression in z to
> find the frequency response at an adequate number of points around the
> unit circle, then performing an inverse FFT to get the time-domain
> response. &#4294967295;There are probably clever rules of thumb to figure out how
> many points you need, but I would do it by giving it a whirl, checking to
> see if the response dies off, and adding more points if it doesn't.
>
> --www.wescottdesign.com


Yes, I believe this is a feasible way (this is similar in the way some
suggested numerical inverse laplace transform method works).
Unfortunately it seems to be very difficult to do some theoretical
error analysis for these kind of operations and I guess one could
(depending on the assumed sampling rate) get into numerical issues for
small angles. Although I'm not an expert in numerical methods or
quadrature so I might be wrong here.

It just seems odd to me that so little work (if any) seems to have
been done in this area of numerical inverse..

/J

On 24 Jan, 23:33, johan162 <johan...@gmail.com> wrote:
> I'm trying to do some research into existing methods for doing
> numerical inverse discrete laplace transform (a.k.a.. Z-transform).
>
> My problem is that numerical methods are really needed when you have
> non-rational Z-transform expression which do
> not posess a closed form inverse. For rational expressions in z this
> is not really a problem since you can always do them
> "manually" (or perhaps by plotting the impulse response in matlab)
>
> (Just to be clear I'm not after calculating the frequencey response,
> i.e. z=exp(j*w) for some w, since that is "trivial"
> as long as numerical stability is not a big concern.)
>
> For laplace transform there is a multitude of suggestions for
> numerical inverse but this does not seem to be
> the case for Z transforms. Perhaps due to the fact that most signal
> processing applications the Z-transform
> will be rational and then the inverse is trivial in the mathematical
> since (but can of course still be very tedious).
>
> Even though it might be full of mathematical nastiness would it be
> feasible e to do a conversion from the
> z plane to the w/s plane, e.g. doing some "suitable" substitution of
> z=f(s), to get a representation of the
> Z-transform as a continuous Laplace transform? (I suspect any kind of
> error analysis in this case would
> would be really difficult.)
>
> Is anyone aware of some published work in this area? I haven't really
> been able to find anything really relevant?

There are a couple of guys, Sven Ivansson and Ilkka Karasalo, who
published a lot on methods for the numeric evaluation of contour
integrals in the early/mid '90s. I know they came up with a method
to compute what is effectively the inverse ZT for implicitly known
functions that have both poles and branch cuts, to high precision
and with error control etc.

I do not know if the functions they worked with were really
irrational, as you are asking for, but Ivansson and Karasalo's
various papers might be a starting point for further searches.

Just be aware that they published mostly on applications of the
models for very specific purposes. Most on their papers are on
numerical modeling on underwater acoustics, but with the odd
math paper thrown in inbetween as need be.

Make sure you read the abstracts of their papers very carefully
if you have to pay $$$ before you download them. Most of their
papers will be irrelevant to you - two or three might be very
relevant.

Rune

On 24 Jan., 23:33, johan162 <johan...@gmail.com> wrote:
> I'm trying to do some research into existing methods for doing
> numerical inverse discrete laplace transform (a.k.a.. Z-transform).
>
> My problem is that numerical methods are really needed when you have
> non-rational Z-transform expression which do
> not posess a closed form inverse.

Can you give a simple example of the type of non-rational z-transform
functions? For some non-rational z-transforms (e.g. semi-integrators
and semi-differentiators) closed-form solutions exist.

> For rational expressions in z this
> is not really a problem since you can always do them
> "manually" (or perhaps by plotting the impulse response in matlab)
>
> (Just to be clear I'm not after calculating the frequencey response,
> i.e. z=exp(j*w) for some w, since that is "trivial"
> as long as numerical stability is not a big concern.)
>
> For laplace transform there is a multitude of suggestions for
> numerical inverse but this does not seem to be
> the case for Z transforms.

I find quite a few hits for "numerical inversion z transform", the
second one is a relevant paper by Papoulis giving a short description
of an algorithm to invert the z transform using real z-values only.

Regards,
Andor

On Jan 24, 11:33&#4294967295;pm, johan162 <johan...@gmail.com> wrote:
> I'm trying to do some research into existing methods for doing
> numerical inverse discrete laplace transform (a.k.a.. Z-transform).
>
> My problem is that numerical methods are really needed when you have
> non-rational Z-transform expression which do
> not posess a closed form inverse. For rational expressions in z this
> is not really a problem since you can always do them
> "manually" (or perhaps by plotting the impulse response in matlab)
>
> (Just to be clear I'm not after calculating the frequencey response,
> i.e. z=exp(j*w) for some w, since that is "trivial"
> as long as numerical stability is not a big concern.)
>
> For laplace transform there is a multitude of suggestions for
> numerical inverse but this does not seem to be
> the case for Z transforms. Perhaps due to the fact that most signal
> processing applications the Z-transform
> will be rational and then the inverse is trivial in the mathematical
> since (but can of course still be very tedious).
>
> Even though it might be full of mathematical nastiness would it be
> feasible e to do a conversion from the
> z plane to the w/s plane, e.g. doing some "suitable" substitution of
> z=f(s), to get a representation of the
> Z-transform as a continuous Laplace transform? (I suspect any kind of
> error analysis in this case would
> would be really difficult.)
>
> Is anyone aware of some published work in this area? I haven't really
> been able to find anything really relevant?
>
> /J

Apart from the almost 40 year old short note (which is a slightly
restricted method)

"Numerical inversion of the z-transform", Papoulis, A.,
IEEE Transactions on Circuit Theory, vol 20,(4), 1973

I've found one more interesting article which has a quite different
approach by using quantum-calculus where the authors define an optimal
(in a sense) orthogonal base sequence and shows how the projection of
the true inverse sequence on this new orthogonal sequence can be
calculated from H(z) as an approximation of the true inverse sequence.
The nice thing with this approach is that it is possible give a very
good error estimate. The simulation by the authors seems quite
promising but before I have really penetrated all the mathematical
details in the paper I'm not sure how well it will work. The paper is:

"A Method for numerical evaluating of inverse Z-transform",
Predrag M. Rajkovi&#4294967295;, Miomir S. Stankovi&#4294967295;, Sla&#4294967295;ana D. Marinkovi&#4294967295;,
 Mechanics, Automatic Control and Robotics Vol. 4, No 16, 2004, pp.
133 - 139

As was pointed out in this thread there are a number of proposed
numerical methods for contour integrals (and in the extension the
inverse Z-transform) but I cannot help thinking that this approach is
to general and one does not make use of the knowledge that the H(z)
function comes from a Z-transform (this becomes more a general
quadrature problem)

Anyway I will make some simulation with some of the proposed methods
and make some comparisons.

/J