\magnification=\magstep1
\vsize=9truein
\hsize=6.5truein
%\parindent=0.8truein
\def\C{{\bf C}}
\def\R{{\bf R}}
\def\N{{\bf N}}
\def\span{{\rm span}}
\font\sc=cmcsc10
\font\smalltt=cmtt10 scaled840
\font\smseven=cmr7 scaled840

%verbatim environment
\def\uncatcodespecials{\def\do##1{\catcode`##1=12 }\dospecials}
\newcount\lineno
\def\listing#1{\par\begingroup\setupverbatim #1\endgroup}
\def\setupverbatimc{\parindent=1truecm\tt
    \smalltt\baselineskip=10pt plus 1pt minus 1pt
    \def\par{\leavevmode\endgraf}\catcode`\`=\active\obeylines
    \uncatcodespecials\obeyspaces
    \everypar{\global\advance\lineno by 1\llap{\smseven\the\lineno\ \ }}}
\def\setupverbatimb{\parindent=1truecm
    \global\lineno=0\smalltt\baselineskip=10pt plus 1pt minus 1pt
    \def\par{\leavevmode\endgraf}\catcode`\`=\active\obeylines
    \uncatcodespecials\obeyspaces
    \everypar{\advance\lineno by 1{}}}
\def\setupverbatim{\global\lineno=0\setupverbatimc}

{\obeyspaces\global\let =\ }

\def\beginverbatim{\par\begingroup\setupverbatim\doverbatim}
{\catcode`\|=0\catcode`\\=12\catcode`|`=|active|gdef`{|relax|lq}%
|obeylines|gdef|doverbatim^^M#1\endverbatim{#1|endgroup}}

\def\beginverbatimb{\par\begingroup\setupverbatimb\doverbatim}
\def\listing#1{\medskip
    \begingroup\setupverbatim\input#1\endgroup\medskip
    \noindent\ignorespaces}
\def\listout#1{\medskip
    \begingroup\setupverbatimb\input#1\endgroup\medskip
    \noindent\ignorespaces}
\def\macinput#1{{\catcode`\$=10\catcode`@=3 \input #1 }}

\input epsf

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item{1.} [Kincaid and Cheney Exercise 1.3\#11a] \ Give bases consisting
of real sequences for the solution space of 
$(4I-3E^2+E^3)x=0$.

\medskip\noindent
This problem maybe reformulated as finding a basis for the solutions
to 
$$p(E)x=0\quad\hbox{where}\quad p(\lambda)=4-3\lambda^2+\lambda^3.$$
Factor $p$ as $p(\lambda)=(\lambda+1)(\lambda-2)^2$.  
It follows that
$\lambda_1=-1$ is a root with multiplicity 1 and $\lambda_2=2$ 
is a root with multiplicity $2$.
In this case, the solutions $u_1$ and $u_2$ defined by
$$
    u_1=(\lambda_1,\lambda_1^2,\lambda_1^3,\ldots)\quad\hbox{and}\quad
    u_2=(\lambda_2,\lambda_2^2,\lambda_2^3,\ldots)
$$
do not span the space of all solutions.  However, a third linearly
independent solution may be obtained by setting 
$x_\lambda=(\lambda,\lambda^2,\lambda^3,\ldots)$ and
differentiating with respect to $\lambda$ to obtain
$$
    u_3={dx_\lambda\over d\lambda}\Big|_{\lambda=\lambda_2}
        = (1,2\lambda_2,3\lambda_2^2,\ldots).
$$
The fact that $u_3$ is linearly independent from $u_1$ and $u_2$ is
automatic but also may be seen by taking the determinant of the matrix
$$M=
        \left[ \matrix{\lambda_1&\lambda_2&1\cr
            \lambda_1^2&\lambda_2^2&2\lambda_2\cr
            \lambda_1^3&\lambda_2^3&3\lambda_2^2}\right]
        =\left[ \matrix{-1&2&1\cr 1&4&4\cr -1&6&12}\right]
\quad\hbox{as}\quad
        \det(M)=-46.
$$
That $u_3$ is a solution follows from
$$\eqalign{
    p(E)u_3&=p(E) {dx_\lambda\over d\lambda}\Big|_{\lambda=\lambda_2}=
    {d \over d\lambda} \big(p(E)x_\lambda\big)\Big|_{\lambda=\lambda_2}=
{d \over d\lambda} \big(p(\lambda)x_\lambda\big)\Big|_{\lambda=\lambda_2}\cr
    &=\Big(p(\lambda) {dx_\lambda\over d\lambda}+p'(\lambda)x_\lambda
        \Big)\Big|_{\lambda=\lambda_2}
    =p(\lambda_2) u_3+p'(\lambda_2)u_2=0
}$$
since both $p(\lambda_2)=0$ and $p'(\lambda_2)=0$ on account of
$\lambda_2$ being a root of multiplicity 2.
It follows that $\{\,u_1,u_2,u_3\,\}$ is a basis for the solution space.
\vfill\eject

\item{2.} [Kincaid and Cheney Exercise 1.3\#11c] \ Give bases consisting
of real sequences for the solution space of 
$(2E^6-9E^5+12E^4-4E^3)x=0$.

\medskip\noindent
This problem maybe reformulated as finding a basis for the solutions to
$$p(E)x=0\quad\hbox{where}\quad 
    p(\lambda)=2\lambda^6-9\lambda^5+12\lambda^4-4\lambda^3.$$
Factor $p$ as 
    $p(\lambda)=\lambda^3(2\lambda-1)(\lambda-2)^2$.
It follows that
$\lambda_1=0$ is a root with multiplicity 3, $\lambda_2=1/2$
is a root with multiplicity $1$ and $\lambda_3=2$ is a
root with multiplicity 2.  Define 
$$x_\lambda=(1,\lambda,\lambda^2,\lambda^3,\lambda^4,\ldots)$$ 
and set
$$\eqalign{
    u_1&=x_\lambda\Big|_{\lambda=\lambda_1}
        =\big(1,\lambda_1,\lambda_1^2,\lambda_1^3,\lambda_1^4,\lambda_1^5,
        \ldots\big)\cr
    u_2&={dx_\lambda\over d\lambda}\Big|_{\lambda=\lambda_1}
       =\big(0,1,2\lambda_1,3\lambda_1^2,4\lambda_1^3,5\lambda_1^4,
        \ldots\big)\cr
    u_3&={dx_\lambda\over d\lambda}\Big|_{\lambda=\lambda_1}
       =\big(0,0,2,(3)(2)\lambda_1,(4)(3)\lambda_1^2,(5)(4)\lambda_1^3,
        \ldots\big)\cr
    u_4&=x_\lambda\Big|_{\lambda=\lambda_2}
        =\big(1,\lambda_2,\lambda_2^2,\lambda_2^3,\lambda_2^4,\lambda_2^5,
        \ldots\big)\cr
    u_5&=x_\lambda\Big|_{\lambda=\lambda_3}
        =\big(1,\lambda_3,\lambda_3^2,\lambda_3^3,\lambda_3^4,\lambda_3^5,
        \ldots\big)\cr
    u_6&={dx_\lambda\over d\lambda}\Big|_{\lambda=\lambda_3}
       =\big(0,1,2\lambda_2,3\lambda_2^2,4\lambda_2^3,5\lambda_2^4,
        \ldots\big).\cr
}$$
The fact that the vectors $\{\, u_1,\ldots,u_6\,\}$ are independent is 
automatic
but also may be seen by taking the determinant of the matrix
$$
    M=\left[\matrix{
            u_{1,1}&\cdots&u_{6,1}\cr
            \vdots&\ddots&\vdots\cr
            u_{1,6}&\cdots&u_{6,6}}
%            u_{1,1}&u_{2,1}&u_{3,1}&u_{4,1}&u_{5,1}&u_{6,1}\cr
%            u_{1,2}&u_{2,2}&u_{3,2}&u_{4,2}&u_{5,2}&u_{6,2}\cr
%            u_{1,3}&u_{2,3}&u_{3,3}&u_{4,3}&u_{5,3}&u_{6,3}\cr
%            u_{1,4}&u_{2,4}&u_{3,4}&u_{4,4}&u_{5,4}&u_{6,4}\cr
%            u_{1,5}&u_{2,5}&u_{3,5}&u_{4,5}&u_{5,5}&u_{6,5}\cr
%            u_{1,6}&u_{2,6}&u_{3,6}&u_{4,6}&u_{5,6}&u_{6,6}}
\right]=
    \left[\matrix{
        1&0&0&1&1&0\cr
        0&1&0&{1/2}&2&1\cr
        0&0&2&{1/4}&4&4\cr
        0&0&0&{1/8}&8&12\cr
        0&0&0&{1/16}&16&32\cr
        0&0&0&{1/32}&32&80\cr
    }\right]
\quad\hbox{as}\quad
    \det(M)=36.
$$
Since $p(\lambda_1)=0$, $p'(\lambda_1)=0$, $p''(\lambda_1)=0$,
    $p(\lambda_2)=0$, $p(\lambda_3)=0$ and $p'(\lambda_3)=0$, then
$$\eqalign{
    p(E)u_1&=p(\lambda_1)u_1=0\cr
    p(E)u_2&=p(\lambda_1)u_2+p'(\lambda_1)u_1=0\cr
    p(E)u_3&=p(\lambda_1)u_3+2p'(\lambda_1)u_2+p''(\lambda_1)u_1=0\cr
    p(E)u_4&=p(\lambda_2)u_4=0\cr
    p(E)u_5&=p(\lambda_3)u_5=0\cr
    p(E)u_6&=p(\lambda_3)u_6+p'(\lambda_3)u_5=0}$$
and therefore $\{\,u_1,\ldots,u_6\,\}$ is a basis for the solution space.
\vfill\eject
\item{3.} [Kincaid and Cheney Exercise 1.3\#14] \ Define an operator
$\Delta$ by putting
$$
    \Delta x=(\,x_2-x_1,x_3-x_2,x_4-x_3,\ldots\,).
$$
Show that $E=I+\Delta$.  Show that if $p$ is a polynomial, then
$$
    p(E)=p(I)+p'(I)\Delta+{1\over 2}p''(I)\Delta^2+
        {1\over 3!}p'''(I)\Delta^3+\cdots+{1\over m!}p^{(m)}(I)\Delta^m.
$$

\medskip\noindent
Since
$$\eqalign{
    (I+\Delta)x    =x+\Delta x
        &=(x_1,x_2,x_3,\ldots) + (\,x_2-x_1,x_3-x_2,x_4-x_3,\ldots\,)\cr
        &=(x_2,x_3,x_4,\ldots) = Ex.}
$$
for every $x=(x_1,x_2,x_3,\ldots)$, then $E=I+\Delta.$  To show the
equality in the second part of this homework is valid we prove first
the following lemma:
\medskip\noindent
{\bf Lemma 1.} \ 
Let $\pi_n\colon\R^\infty\to\R^\infty$ be the projection onto
the first $n$ coordinates defined by
$$
    \pi_n (x_1,x_2,x_3,\ldots) = (x_1,x_2,\ldots,x_n,0,0,\ldots).$$
Suppose $K\colon\R^\infty\to\R^\infty$ and
$L\colon\R^\infty\to\R^\infty$ are linear operators 
such that $K x_\lambda= L x_\lambda$ for every $\lambda\in\R$
where $x_\lambda=(\lambda,\lambda^2,\lambda^3,\ldots).$ 
If there exists $r\in\N$ such that $\pi_n K  x = \pi_n K \pi_{n+r} x$ and
$\pi_n L  x = \pi_n L \pi_{n+r} x$ hold for every $x\in\R^\infty$
and $n\in\N$, then $K=L$.

\medskip\noindent
{\bf Proof:} \ 
Define $u_i=\pi_{n+r} x_{\lambda_i}$ where 
$\lambda_i=i$ for $i=1,2, \ldots, n+r$.
The matrix
$$
    M=\left[\matrix{
        u_{1,1}&\cdots& u_{n+r,1}\cr
        \vdots&\ddots&\vdots\cr
        u_{1,n+r}&\cdots& u_{n+r,n+r}
        }\right]
    =\left[\matrix{ 
        1&2&\cdots&n+r\cr
        1&2^2&\cdots&(n+r)^2\cr
        \vdots&\vdots&\ddots&\vdots\cr
        1&2^{n+r}&\cdots&(n+r)^{n+r}}\right]
        \in\R^{(n+r)\times(n+r)}
$$
is a Vandermonde matrix and therefore non-singular.  
Now, given any $x\in \R^\infty$ there is 
a unique $\beta\in\R^{n+r}$ such that 
$\pi_{n+r} x=\beta_1 u_1+\beta_2 u_2+\cdots+\beta_{n+r} u_{n+r}$.  Let 
$z=\beta_1 x_{\lambda_1}+\beta_2 x_{\lambda_2}+\cdots 
        +\beta_{n+r} x_{\lambda_{n+r}}$.
%$v_i=\pi_{n+r} x_{\lambda_i}$ for $i=1,2,\ldots,n+r$.
Then $\pi_{n+r} x=\pi_{n+r} z$.  By hypothesis 
$$\pi_n K u_i
    =\pi_n K \pi_{n+r} x_{\lambda_i}
    =\pi_n K x_{\lambda_i}
    =\pi_n L x_{\lambda_i}
    =\pi_n L \pi_{n+r} x_{\lambda_i}
    =\pi_n L u_i
$$
for $i=1,2,\ldots,n+r$ and therefore 
$$\eqalign{
    \pi_n K x
        &=\pi_n K \pi_{n+r} x
        =\pi_n K \pi_{n+r} z
        =\beta_1 Ku_1+\beta_2 Ku_2+\cdots+\beta_{n+r} Ku_{n+r}\cr
        &=\beta_1 Lu_1+\beta_2 Lu_2+\cdots+\beta_{n+r} Lu_{n+r}
        =\pi_n L \pi_{n+r} z
        =\pi_n L \pi_{n+r} x
    =\pi_n Lx.}
$$
Since $\pi_n Kx=\pi_n Lx$ for any $x\in\R^\infty$, then $\pi_n K=\pi_n L$.
As this holds for every $n\in\N$, we conclude that $K=L$.  This
finishes the proof of Lemma 1.

\medskip\noindent
Claim $\pi_n\Delta^r x=\pi_n\Delta^r\pi_{n+r} x$ for every $x\in\R^\infty$,
$n\in\N$
and $r\in\N$.  We shall prove this claim by induction.
For the base case notice that
$$
    \pi_n \Delta x = (x_2-x_1,\ldots,x_{n+1}-x_n,0,0,\ldots)=
        \pi_n \Delta \pi_{n+1} x
\quad\hbox{for every}\quad n\in\N.
$$
Now suppose $\pi_n\Delta^r x=\pi_n\Delta^r\pi_{n+r} x$ for every
$x\in\R^\infty$ and all $n\in N$.  Then
$$\eqalign{
    \pi_n\Delta^{r+1} x&=\pi_n\Delta (\Delta^{r} x)
        =\pi_n \Delta \pi_{n+1}(\Delta^{r} x)
        =\pi_n \Delta (\pi_{n+1} \Delta^{r} x)
        =\pi_n \Delta (\pi_{n+1}\Delta^{r} \pi_{n+r+1} x)\cr
        &=\pi_n \Delta \pi_{n+1}(\Delta^{r} \pi_{n+r+1} x)
        =\pi_n \Delta (\Delta^{r} \pi_{n+r+1} x)
        =\pi_n \Delta^{r+1}\pi_{n+r+1} x.}
$$
This completes the induction and proves the claim.
Similarly $\pi_n E^r x=\pi_n E^r \pi_{n+r} x$.
\medskip\noindent
Now let 
$$\eqalignno{K&=p(E)=\sum_{i=0}^m c_i E^i \cr
\noalign{\noindent and}
L&=p(I)+p'(I)\Delta+{1\over 2}p''(I)\Delta^2+
        {1\over 3!}p'''(I)\Delta^3+\cdots+{1\over m!}p^{(m)}(I)\Delta^m.}
$$
From what we just proved, it follows that
$$
    \pi_n K x =\pi_n K\pi_{n+m} x\quad\hbox{and}\quad
    \pi_n L x =\pi_n L\pi_{n+m} x.$$
We finish by noting that
$$
    Ex_\lambda=\lambda x_\lambda\quad\hbox{and}\quad
    \Delta x_\lambda= (E-I) x_\lambda=\lambda x_\lambda-x_\lambda
        =(\lambda-1)x_\lambda
$$
along with Taylor's theorem
$$
    p(\lambda)=\sum_{i=0}^m c_i\lambda^i
        =p(1)+p'(1) (\lambda-1)
        +{1\over 2!}p''(1)(\lambda-1)^2
%        +{1\over 3!}p'''(1)(\lambda-1)^3
        +\cdots
        +{1\over m!}p^{(m)}(1)(\lambda-1)^m
$$
yields
$$\eqalignno{
%    K x_\lambda&=p(E)x_\lambda=p(\lambda) x_\lambda\cr
%\noalign{\noindent and}
    L x_\lambda&=
        p(1) x_\lambda+p'(1) (\lambda-1) x_\lambda
        +{1\over 2!}p''(1)(\lambda-1)^2 x_\lambda
%        +{1\over 3!}p'''(1)(\lambda-1)^3 x_\lambda
        +\cdots
        +{1\over m!}p^{(m)}(1)(\lambda-1)^m x_\lambda\cr
        &=\Big(p(1)+p'(1) (\lambda-1)
        +{1\over 2!}p''(1)(\lambda-1)^2
%        +{1\over 3!}p'''(1)(\lambda-1)^3
        +\cdots
        +{1\over m!}p^{(m)}(1)(\lambda-1)^m\Big) x_\lambda\cr
        &=p(\lambda)x_\lambda=p(E)x_\lambda=K x_\lambda.
}$$
Therefore, the hypothesis of Lemma 1 are satified with $r=m$.
The result
$K=L$ follows.
\vfill\eject
\item{4.} [Kincaid and Cheney Exercise 1.3\#15] \ Prove that if
$x=(\lambda,\lambda^2,\lambda^3,\ldots)$ and $p$ is a polynomial,
then $p(\Delta)x=p(\lambda-1)x$.  Describe how to solve a
difference equation written in the form $p(\Delta)x=0$.
\def\P{{\cal P}}%
\medskip\noindent
Let $\P_n$ be
the set of all polynomials of degree $n$ and $\P$ be the set of
all polynomials.  We use induction to prove that
$$
    p(\Delta)x_\lambda=p(\lambda-1)x_\lambda
\qquad\hbox{for all}\qquad p\in\P.$$

{\bf Base case:} 
Let $p_0\in P_0$.  Then $p_0(\eta)=c$ for some $c\in\C$.  Therefore
$$p_0(\Delta)x_\lambda=c x_\lambda=p_0(\lambda-1)x_\lambda.$$

{\bf Induction step:}
For induction suppose $p_n(\Delta)x_\lambda=p_n(\lambda-1)x_\lambda$
for every $p_n\in\P_n$.  
Let $p_{n+1}\in\P_{n+1}$.  
Write
$p_{n+1}(\eta)=\eta p_n(\eta)+c$ for some 
$p_n\in\P_n$ and $c\in\C$.
To complete the induction we need to show
$p_{n+1}(\Delta)x_\lambda=p_{n+1}(\lambda-1)x_\lambda$.
By
the induction
hypothesis we have that
$p_n(\Delta)x_\lambda=p_n(\lambda-1)x_\lambda$.  Therefore
$$\eqalign{
    p_{n+1}(\Delta)x_\lambda
        &=\big(\Delta p_n(\Delta)+cI\big)x_\lambda
        =\Delta p_n(\Delta)x_\lambda+cx_\lambda
        =\Delta \big(p_n(\lambda-1)x_\lambda\big)+c x_\lambda\cr
        &
        =\big(p_n(\lambda-1)\big) \Delta x_\lambda+c x_\lambda
        =\big(p_n(\lambda-1)\big)(E-I)x_\lambda+c x_\lambda\cr
        &
        =\big(p_n(\lambda-1)\big)(\lambda-1)x_\lambda+c x_\lambda
        =\big((\lambda-1)p_n(\lambda-1)+c\big)x_\lambda\cr
        &
        =p_{n+1}(\lambda-1)x_\lambda.
}$$
This completes the induction.

To solve the difference equation $p(\Delta)=0$ define 
$q(\lambda)=p(\lambda-1)$.
By Taylor's theorem
$$
    q(\lambda)=\sum_{i=0}^m {q^{(i)}(1)\over i!}(\lambda-1)^i.
$$
where $m$ is the degree of the polynomial $q$.  Therefore
$$
    p(\eta)=\sum_{i=0}^m {q^{(i)}(1)\over i!}\eta^i.
$$
Applying Kincaid and Cheney Exercise 1.3\#14 to the polynomial $q$
we obtain that
$$
    q(E)=\sum_{i=0}^m {q^{(i)}(I)\over i!}\Delta^i.$$
Since $q^{(i)}(I)=q^{(i)}(1)I$, then
$$
    q(E)=\sum_{i=0}^m {q^{(1)}\over i!}\Delta^i=p(\Delta).
$$
Now solve $p(\Delta)x=0$ by solving $q(E)x=0$ using
the method of Kincaid and Cheney chapter 1.3 pages 31--32.
\vfill\eject
\item{5.} [Kincaid and Cheney Exercise 1.3\#16] \ Show that
$$
    \Delta^n=(-1)^n
        \Big(E^0-nE+{1\over 2}n(n-1)E^2-{1\over 3!}n(n-1)(n-2)E^3+
        \cdots +(-1)^n E^n\Big).$$
\medskip\noindent
Define $p(\eta)=\eta^n$ and $q(\lambda)=p(\lambda-1)$.  By the
binomial theorem
$$\eqalign{
    q(\lambda)&=(\lambda-1)^n
        =\sum_{i=0}^n {n\choose i}\lambda^i (-1)^{n-i}
        =(-1)^n\sum_{i=0}^n {n\choose i}\lambda^i (-1)^{i}\cr
    &
    =(-1)^n
        \Big(\lambda^0-n\lambda+{1\over 2}n(n-1)\lambda^2
        -{1\over 3!}n(n-1)(n-2)\lambda^3+
        \cdots +(-1)^n \lambda^n\Big).
}$$
From Kincaid and Cheney Exercise 1.3\#15 we have
that $p(\Delta)=q(E)$.  Therefore
$$\eqalign{
    \Delta^n&=p(\Delta)=q(E)\cr
        &=\Big(E^0-nE+{1\over 2}n(n-1)E^2-{1\over 3!}n(n-1)(n-2)E^3+
        \cdots +(-1)^n E^n\Big).
}$$
as desired.
\vfill\eject
\item{6.} [Kincaid and Cheney Computer Exercise 1.3\#4abc] \ Compute
the particular solution to the recurrence relation
$x_n=2(x_{n-1}+x_{n-2})$ in Problem 1.3.27 for $n=1,2,\ldots, 100$ in the 
following three ways and compare the results.
\itemitem{a.} $x_n$ directly from the recurrence relation.
\itemitem{b.} $y_n=\beta(1-\sqrt 3)^n$
\itemitem{c.} $z_n=\alpha(1+\sqrt 3)^n+\beta(1-\sqrt 3)^n$
where $\alpha$ is the computer's unit roundoff error.
\medskip\noindent
We will be using a computer which implements the IEEE 754
standard for double precision floating point arithemetic.
For this hardware the mantissa consists of 52 binary digits
with an implicit leading bit for 53 binary digits of precision.
Equation (6) on page 45 of Kincaid and Cheney defines the
unit roundoff error by
$$
    \alpha=\max\big\{\,|\delta| : {\rm fl(x)}=x(1+\delta)\,\big\}.
$$
In the case of IEEE 754 double precision $\alpha=2^{-54}$.
The following program performs the desired calculations.
\listing{prog6.c}
The output of this program is
\listout{prog6.out}
Note that $x_n$ and $z_n$ exhibit exponential growth 
by the $n=100$ term whereas $y_n$ continues to decay.
Rounding error in the early calculations of $x_n$ introduce
errors that are approximately equal to $\alpha$.  These
errors grow exponentially with order
$\alpha(1+\sqrt 3)^n$.
\vfill
\eject
\item{7.} [Kincaid and Cheney Exercise 2.3\#2] \ Find
analytically the solution of this difference equation with
the given initial values
$$
    \cases{x_0=1\qquad x_1=0.9\cr
        x_{n+1}=-0.2x_n+0.99x_{n-1}}
$$
Without computing the solution recursively, predict whether
such a computation would be stable.
\medskip\noindent
The characteristic polynomial for this difference equation is
$$
    p(\lambda)=\lambda^2+0.2\lambda-0.99 = (\lambda-0.9)(\lambda+1.1).
$$
Solving $p(\lambda)=0$ we obtain $\lambda_1=0.9$ and $\lambda_2=-1.1$.
It follows
that any solution $x_n$ of this difference equation may
be written in the form
$$
    x_n=
        \alpha (0.9)^n+
        \beta (-1.1)^n
$$
for a suitable choice of $\alpha$ and $\beta$.  Solving
for $\alpha$ and $\beta$ to satisfy the initial conditions
$$\cases{
    \alpha+\beta=1\cr
    0.9 \alpha -1.1\beta=0.9\cr
}$$
yields
$$
    \alpha=1\qquad\hbox{and}\qquad
    \beta=0.
$$
It follows that $x_n=(0.9)^n$ and so $x_n\to 0$ as $n\to\infty$.

Any perturbation to the initial conditions $x_0$ and $x_1$ leads
to a perturbation in the constants $\alpha$ and $\beta$.  As the set
of perturbations which leave $\beta=0$ is a one-dimensional subset
of the two-dimensional space of perturbations, it follows
that $\beta\ne 0$ after a generic perturbation.
In particular, since it is not possible to represent the
condition $x_1=0.9$ exactly using a base-2 floating point number,
any computation made from the recurrence relation
will involve rounding errors that lead to a perturbation
where $\beta\ne 0$.  In this case
$$
    |x_n|\ge |\beta| (1.1)^n-|\alpha|(0.9)^n\to \infty
\qquad \hbox{as}\qquad n\to\infty,
$$
which shows that the recursive computation is unstable.
\vfill\eject

\item{8.} [Kincaid and Cheney Exercise 2.3\#5b] \ Compute
the condition number for $f(x)=\ln x$ and
determine where the condition number is large.
\medskip\noindent
The condition number $\kappa_f$ is
$$
    \kappa_f={xf'(x)\over f(x)}={1\over \ln x}.
$$
Since $|\kappa_f|\to \infty$ as $x\to 1$, the condition number is large 
when $x\approx 1$.
\vfill\eject

\item{9.} [Kincaid and Cheney Exercise 2.3\#5c] \ Compute
the condition number for $g(x)=\sin x$ and
determine where the condition number is large.
\medskip\noindent
The condition number $\kappa_g$ is
$$
    \kappa_g={xg'(x)\over g(x)}={x\cos x\over\sin x}.
$$
Since $|\sin x|\le |x|\le |\tan x|$ for $|x|<\pi/2$
it follows that $|k_g|\le 1$ for $|x|<\pi/2$.
On the other hand $|\kappa_g|\to\infty$ as $x\to k\pi$ for any
integer $k\ne 0$.  Therefore the condition number is large
when $x\approx k\pi$ for any interger $k\ne 0$.
\vfill\eject
\item{10.} [Kincaid and Cheney Computer Exercise 2.3\#1] \ Let
sequences $a_n$ and $b_n$ be generated as follows
$$
    \cases{a_0=0\qquad a_1=1\cr
        a_n=na_{n-1}+a_{n-2}}
    \qquad\qquad
    \cases{b_0=1\qquad b_1=1\cr
        b_n=nb_{n-1}+b_{n-2}.}
$$
What is $\lim_{n\to\infty} (a_n/b_n)$?
\medskip\noindent
I wrote a program to compute this limit.  The program was
\listing{prog10.c}
and the output was
\listout{prog10.out}
Thus 
$\lim_{n\to\infty} (a_n/b_n)\approx 0.6977746579640079$.
\vfill\eject

\item{11.} [Kincaid and Cheney Computer Exercise 2.3\#2] \ The
Bessel functions $Y_n$ satisfy the recurrence formula
$$
    Y_n(x)=2(n-1)x^{-1}Y_{n-1}(x)-Y_{n-2}(x).
$$
For $Y_n(1)$ the starting values are 
$$\left\{\eqalign{
        Y_0(1)&\approx  0.0882569642\cr
        Y_1(1)&\approx -0.7812128213.\cr
}\right.$$
Compute $Y_2(1),Y_3(1),\ldots,Y_{20}(1)$ using the
recurrence formula.
Try to decide whether the results are reliable.
\medskip\noindent
The program
\listing{prog11.c}
computes the values of $Y_n(1)$ for $n=0,1,\ldots 20$ as
\listout{prog11.out}
To determine whether the results are reliable
perturbed starting values given by
$$\left\{\eqalign{
    Z_0&=Y_0(1)(1+\alpha)\cr
    Z_1&=Y_1(1)(1+\beta)\cr
}\right.$$
where $\alpha$ and $\beta$ are uniformly
distributed random variables on the interval $[-0.1,0.1]$
were used and the results compared to the results
with the unperturbed starting values.
The program
\listing{prog11b.c}
compares the relative errors
$$
    E_{\rm rel}={\sqrt{\sum_{n=0}^{20} |Z_n-Y_n(1)|^2}
        \bigg/ \sqrt{\sum_{n=0}^{20} |Y_n(1)|^2}}
$$
for 20 different perturbations.  The output
\listout{prog11b.out}
indicates that the relative error $E_{\rm rel}$ has
magnitude similar to $\alpha$ and $\beta$.  This is
evidence that the results are reliable.
\vfill
\eject
\item{12.} [Kincaid and Cheney Computer Exercise 2.3\#6] \ The
Bessel functions $J_0(x),J_1(x),\ldots$ can be computed
by the recurrence relation
$$
    J_n(x)=2(n-1)x^{-1}J_{n-1}(x)-J_{n-2}(x)
$$
if it is used with descending $n$.  Thus, we start with $n=N$
and proceed downward by the formula
$$
    J_{n-1}(x)=2n x^{-1} J_n(x)-J_{n+1}(x)
\qquad\hbox{for}\qquad n=N,N-1,\ldots,1.
$$
To get started, we set $J_{N+1}(x)=0$ and $J_N(x)=1$.
These are tentative values.  After computing
$J_{N-1}(x),J_{N-2}(x),\ldots,J_0(x)$ we scale them by
using the identity
$$
    J_0(x)^2+2\sum_{n=1}^\infty J_n(x)^2=1.
$$
Obviously $N$ must be large enough so taking $J_{N+1}(x)=0$
is reasonable for the precision expected.  Use $N=51$
to compute $J_0(1),J_1(1),\ldots,J_{50}(1).$
\medskip\noindent
The program was
\listing{prog12.c}
and the output was
\listout{prog12.out}
I checked the output with the values $J_0(1)\approx 0.7651976866$
and $J_1(1)\approx 0.4400505857$ appearing on page 36 in Kincaid
and Cheney as well as with Maple.
\end
