reduce-historical/r36/doc/ZTRANS.TEX

\documentstyle[11pt,reduce]{article}
\title{{\bf $Z$-Transform Package for {\tt REDUCE}}}
\author{Wolfram Koepf \\ Lisa Temme \\ email: {\tt Koepf@zib-berlin.de}}
\date{April 1995 : ZIB Berlin}
\begin{document}
\maketitle
\section{$Z$-Transform}

  The $Z$-Transform of a sequence $\{f_n\}$ is the discrete analogue
  of the Laplace Transform, and
  \[{\cal Z}\{f_n\} = F(z) = \sum^\infty_{n=0} f_nz^{-n}\;.\] \\
  This series converges in the region outside the circle
  $|z|=|z_0|= \limsup\limits_{n \rightarrow \infty} \sqrt[n]{|f_n|}\;.$


\begin{tabbing}

{\bf SYNTAX:}\ \ {\tt ztrans($f_n$, n,  z)}\ \ \ \ \ \ \ \
  \=where $f_n$ is an expression, and $n$,$z$ \\
  \> are identifiers.\\
\end{tabbing}


\section{Inverse $Z$-Transform}
  The calculation of the Laurent coefficients of a regular function
  results in the following inverse formula for the $Z$-Transform:
  \\
  If $F(z)$ is a regular function in the region $|z|> \rho$ then
  $\exists$ a sequence \{$f_n$\} with ${\cal Z} \{f_n\}=F(z)$
  given by
  \[f_n = \frac{1}{2 \pi i}\oint F(z) z^{n-1} dz\]


\begin{tabbing}

{\bf SYNTAX:}\ \ {\tt invztrans($F(z)$, z,  n)}\ \ \ \ \ \ \ \
  \=where $F(z)$ is an expression, \\
  \> and $z$,$n$ are identifiers.
\end{tabbing}


\section{Input for the $Z$-Transform}
\begin{tabbing}
  This pack\=age can compute the \= $Z$-Transforms of the \=following
  list of $f_n$, and \\ certain combinations thereof.\\ \\

\>$1$
\>$e^{\alpha n}$
\>$\frac{1}{(n+k)}$               \\ \\
\>$\frac{1}{n!}$
\>$\frac{1}{(2n)!}$
\>$\frac{1}{(2n+1)!}$             \\ \\
\>$\frac{\sin(\beta n)}{n!}$
\>$\sin(\alpha n+\phi)$
\>$e^{\alpha n} \sin(\beta n)$    \\ \\
\>$\frac{\cos(\beta n)}{n!}$
\>$\cos(\alpha n+\phi)$
\>$e^{\alpha n} \cos(\beta n)$    \\ \\
\>$\frac{\sin(\beta (n+1))}{n+1}$
\>$\sinh(\alpha n+\phi)$
\>$\frac{\cos(\beta (n+1))}{n+1}$ \\ \\
\>$\cosh(\alpha n+\phi)$
\>${n+k \choose m}$\\
\end{tabbing}

\begin{tabbing}
\underline {{\bf Other Combinations}}\= \\ \\

\underline {Linearity}
  \>${\cal Z} \{a f_n+b g_n \} = a{\cal Z} \{f_n\}+b{\cal Z}\{g_n\}$
  \\ \\
\underline {Multiplication by $n$}
  \>${\cal Z} \{n^k \cdot f_n\} = -z \frac{d}{dz} \left({\cal Z}\{n^{k-1} \cdot f_n,n,z\} \right)$
  \\ \\
\underline {Multiplication by $\lambda^n$}
  \>${\cal Z} \{\lambda^n \cdot f_n\}=F \left(\frac{z}{\lambda}\right)$
  \\ \\
\underline {Shift Equation}
  \>${\cal Z} \{f_{n+k}\} =
           z^k \left(F(z) - \sum\limits^{k-1}_{j=0} f_j z^{-j}\right)$
  \\ \\
\underline {Symbolic Sums}

  \> ${\cal Z} \left\{ \sum\limits_{k=0}^{n} f_k \right\} =
                       \frac{z}{z-1} \cdot {\cal Z} \{f_n\}$ \\ \\

  \>${\cal Z} \left\{ \sum\limits_{k=p}^{n+q} f_k \right\}$
  \ \ \ combination of the above \\ \\
  where $k$,$\lambda \in$ {\bf N}$- \{0\}$; and $a$,$b$ are variables
  or fractions; and $p$,$q \in$ {\bf Z} or \\
  are functions of $n$; and $\alpha$, $\beta$ \& $\phi$ are angles
  in radians.
\end{tabbing}

\section{Input for the Inverse $Z$-Transform}
\begin{tabbing}
  This \= package can compute the Inverse \= Z-Transforms of any
  rational function, \\ whose denominator can be factored over
  ${\bf Q}$, in addition to the following list \\ of $F(z)$.\\ \\

\> $\sin \left(\frac{\sin (\beta)}{z} \ \right)
    e^{\left(\frac{\cos (\beta)}{z} \ \right)}$
\> $\cos \left(\frac{\sin (\beta)}{z} \ \right)
    e^{\left(\frac{\cos (\beta)}{z} \ \right)}$ \\ \\
\> $\sqrt{\frac{z}{A}} \sin \left( \sqrt{\frac{z}{A}} \ \right)$
\> $\cos \left( \sqrt{\frac{z}{A}} \ \right)$ \\ \\
\> $\sqrt{\frac{z}{A}} \sinh \left( \sqrt{\frac{z}{A}} \ \right)$
\> $\cosh \left( \sqrt{\frac{z}{A}} \ \right)$ \\ \\
\> $z \ \log \left(\frac{z}{\sqrt{z^2-A z+B}} \ \right)$
\> $z \ \log \left(\frac{\sqrt{z^2+A z+B}}{z} \ \right)$ \\ \\
\> $\arctan \left(\frac{\sin (\beta)}{z+\cos (\beta)} \ \right)$
\\
\end{tabbing}

  where $k$,$\lambda \in$ {\bf N}$ -  \{0\}$ and $A$,$B$ are fractions
  or variables ($B>0$) and $\alpha$,$\beta$, \&  $\phi$ are angles
  in radians.

\section{Application of the $Z$-Transform}
\underline {{\bf Solution of difference equations}}\\

  In the same way that a Laplace Transform can be used to
  solve differential equations, so $Z$-Transforms can be used
  to solve difference equations.\\ \\
  Given a linear difference equation of $k$-th order
\begin{equation}
  f_{n+k} + a_1 f_{n+k-1}+ \ldots + a_k f_n = g_n
\label{eq:1}
\end{equation}

  with initial conditions
  $f_0 = h_0$, $f_1 = h_1$, $\ldots$, $f_{k-1} = h_{k-1}$ (where $h_j$
  are given), it is possible to solve it in the following way.
   If the coefficients $a_1, \ldots , a_k$ are constants, then the
  $Z$-Transform of (\ref{eq:1}) can be calculated using the shift
  equation, and results in a solvable linear equation for
  ${\cal Z} \{f_n\}$. Application of the Inverse $Z$-Transform
  then results in the solution of \ (\ref{eq:1}).\\
  If the coefficients $a_1, \ldots , a_k$ are polynomials in $n$ then
  the $Z$-Transform of (\ref{eq:1}) constitutes a differential
  equation for ${\cal Z} \{f_n\}$. If this differential equation can
  be solved then the Inverse $Z$-Transform once again yields the
  solution of (\ref{eq:1}).
  Some examples of these methods of solution can be found in
  $\S$\ref{sec:Examples}.

\section{EXAMPLES}
\label{sec:Examples}
\underline {{\bf Here are some examples for the $Z$-Transform}}\\
\begin{verbatim}
1: ztrans((-1)^n*n^2,n,z);

    z*( - z + 1)
---------------------
  3      2
 z  + 3*z  + 3*z + 1

2: ztrans(cos(n*omega*t),n,z);

   z*(cos(omega*t) - z)
---------------------------
                     2
 2*cos(omega*t)*z - z  - 1

3: ztrans(cos(b*(n+2))/(n+2),n,z);

                                 z
z*( - cos(b) + log(------------------------------)*z)
                                          2
                    sqrt( - 2*cos(b)*z + z  + 1)

4: ztrans(n*cos(b*n)/factorial(n),n,z);

  cos(b)/z       sin(b)                 sin(b)
 e        *(cos(--------)*cos(b) - sin(--------)*sin(b))
                   z                      z
---------------------------------------------------------
                            z
5: ztrans(sum(1/factorial(k),k,0,n),n,z);

  1/z
 e   *z
--------
 z - 1

6: operator f$

7: ztrans((1+n)^2*f(n),n,z);

                          2
df(ztrans(f(n),n,z),z,2)*z  - df(ztrans(f(n),n,z),z)*z
+ ztrans(f(n),n,z)

\end{verbatim}

\underline {{\bf Here are some examples for the Inverse $Z$-Transform}}
\begin{verbatim}

8: invztrans((z^2-2*z)/(z^2-4*z+1),z,n);

              n       n                n
 (sqrt(3) - 2) *( - 1)  + (sqrt(3) + 2)
-----------------------------------------
                    2

9: invztrans(z/((z-a)*(z-b)),z,n);

  n    n
 a  - b
---------
  a - b

10: invztrans(z/((z-a)*(z-b)*(z-c)),z,n);

  n      n      n      n      n      n
 a *b - a *c - b *a + b *c + c *a - c *b
-----------------------------------------
  2      2        2      2    2        2
 a *b - a *c - a*b  + a*c  + b *c - b*c

11: invztrans(z*log(z/(z-a)),z,n);

  n
 a *a
-------
 n + 1

12: invztrans(e^(1/(a*z)),z,n);

        1
-----------------
  n
 a *factorial(n)

13: invztrans(z*(z-cosh(a))/(z^2-2*z*cosh(a)+1),z,n);

cosh(a*n)


\end{verbatim}

\underline {{\bf Examples: Solutions of Difference Equations}}\\ \\
\begin{tabbing}
{\bf I} \ \ \ \ \ \ \=

  (See \cite{BS}, p.\ 651, Example 1).\\
  \> Consider the \= homogeneous linear difference equation\\ \\
  \>\>  $f_{n+5} - 2 f_{n+3} + 2 f_{n+2} - 3 f_{n+1} + 2 f_{n}=0$\\ \\

  \> with \ initial conditions \ $f_0=0$, $f_1=0$, $f_2=9$, $f_3=-2$,
     $f_4=23$. \  The\\
  \> $Z$-Transform of the left hand side can be written as
     $F(z)=P(z)/Q(z)$ \\
  \> where \ $P(z)=9z^3-2z^2+5z$ \
     and \ $Q(z)=z^5-2z^3+2z^2-3z+2$ \ $=$\\
  \> $(z-1)^2(z+2)(z^2+1)$, \ which can be inverted to give\\ \\

 \>\>  $f_n = 2n + (-2)^n - \cos \frac{\pi}{2}n\;.$ \\ \\

  \> The following REDUCE session shows how the present package can
\\ \> be used to solve the above problem.

\end{tabbing}
\begin{verbatim}
14: operator f$ f(0):=0$ f(1):=0$ f(2):=9$ f(3):=-2$ f(4):=23$


20: equation:=ztrans(f(n+5)-2*f(n+3)+2*f(n+2)-3*f(n+1)+2*f(n),n,z);

                              5                       3
equation := ztrans(f(n),n,z)*z  - 2*ztrans(f(n),n,z)*z

                                   2
             + 2*ztrans(f(n),n,z)*z  - 3*ztrans(f(n),n,z)*z

                                       3      2
             + 2*ztrans(f(n),n,z) - 9*z  + 2*z  - 5*z


21: ztransresult:=solve(equation,ztrans(f(n),n,z));

                                             2
                                       z*(9*z  - 2*z + 5)
ztransresult := {ztrans(f(n),n,z)=----------------------------}
                                    5      3      2
                                   z  - 2*z  + 2*z  - 3*z + 2

22: result:=invztrans(part(first(ztransresult),2),z,n);

                   n    n       n    n
           2*( - 2)  - i *( - 1)  - i  + 4*n
result := -----------------------------------
                          2

\end{verbatim}

\begin{tabbing}
\\ \\
{\bf II} \ \ \ \ \ \ \=

  (See \cite{BS}, p.\ 651, Example 2).\\
  \>    Consider the \= inhom\=ogeneous difference equation:\\ \\
  \>\>  $f_{n+2} - 4 f_{n+1} + 3 f_{n} = 1$\\ \\

  \> with initial conditions $f_0=0$, $f_1=1$. Giving  \\ \\
\>\> $F(z)$\>$ = {\cal Z}\{1\} \left( \frac{1}{z^2-4z+3} + \frac{z}{z^2-4z+3} \right)$\\ \\
\>\>\>       $ = \frac{z}{z-1} \left( \frac{1}{z^2-4z+3} + \frac{z}{z^2-4z+3} \right)$.
\\ \\
  \> The Inverse $Z$-Transform results in the solution\\ \\


\>\>
$f_n = \frac{1}{2} \left( \frac{3^{n+1}-1}{2}-(n+1) \right)$.\\ \\

  \> The following REDUCE session shows how the present package can\\
  \> be used to solve the above problem.

\end{tabbing}
\begin{verbatim}

23: clear(f)$ operator f$ f(0):=0$ f(1):=1$


27: equation:=ztrans(f(n+2)-4*f(n+1)+3*f(n)-1,n,z);

                               3                       2
equation := (ztrans(f(n),n,z)*z  - 5*ztrans(f(n),n,z)*z

                                                           2
    + 7*ztrans(f(n),n,z)*z - 3*ztrans(f(n),n,z) - z )/(z - 1)

28: ztransresult:=solve(equation,ztrans(f(n),n,z));

                                      2
                                     z
result := {ztrans(f(n),n,z)=---------------------}
                              3      2
                             z  - 5*z  + 7*z - 3

29: result:=invztrans(part(first(ztransresult),2),z,n);

              n
           3*3  - 2*n - 3
result := ----------------
                 4
\end{verbatim}

\begin{tabbing}
\\ \\
{\bf III} \ \ \ \ \ \ \=

    Consider the \=following difference equation, which has a
    differential\\
 \> equation for ${\cal Z}\{f_n\}$.\\ \\

 \>\> $(n+1) \cdot f_{n+1}-f_n=0$\\ \\

 \> with initial conditions $f_0=1$, $f_1=1$. It can be solved in REDUCE\\
 \>  using the present package in the following way.\\

\end{tabbing}
\begin{verbatim}
30: clear(f)$ operator f$ f(0):=1$ f(1):=1$


34: equation:=ztrans((n+1)*f(n+1)-f(n),n,z);

                                        2
equation :=  - (df(ztrans(f(n),n,z),z)*z  + ztrans(f(n),n,z))

35: operator tmp;

36: equation:=sub(ztrans(f(n),n,z)=tmp(z),equation);

                              2
equation :=  - (df(tmp(z),z)*z  + tmp(z))

37: load(odesolve);

38: ztransresult:=odesolve(equation,tmp(z),z);

                         1/z
ztransresult := {tmp(z)=e   *arbconst(1)}

39: preresult:=invztrans(part(first(ztransresult),2),z,n);

              arbconst(1)
preresult := --------------
              factorial(n)

40: solve({sub(n=0,preresult)=f(0),sub(n=1,preresult)=f(1)},
arbconst(1));

{arbconst(1)=1}

41: result:=preresult where ws;

                1
result := --------------
           factorial(n)

\end{verbatim}

\begin{thebibliography}{9}
\bibitem{BS} Bronstein, I.N. and Semedjajew, K.A.,
{\it Taschenbuch der Mathematik},
Verlag Harri Deutsch, Thun und Frankfurt(Main),
 1981.\\ISBN 3 87144 492 8.
\end{thebibliography}

\end{document}