Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/January 2004

Problem 1

Let $a=x_{0}<x_{1}<\cdots <x_{n}=b\!\,$ be an arbitrary fixed partition of the interval $[a,b]\!\,$. A function $q(x)\!\,$ is a quadratic spline function if (i) $q\in C^{1}[a,b]\!\,$ (ii) On each subinterval $[x_{i},x_{i+1}]\!\,$, $q\!\,$ is a quadratic polynomial The problem is to construct a quadratic spline $q(x)\!\,$ interpolating data points $(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\!\,$. The construction is similar to the construction of the cubic spline but much easier.

Problem 1a

Show that if we know $z_{i}\equiv q'(x_{i}),i=0,\ldots ,n\!\,$, we can construct $q\!\,$.

Solution 1a

Consider interval $[x_{i},x_{i+1}]\!\,$. Since $q'_{i}(x)\!\,$ is linear on this interval, using the point slope form we have

$q_{i}'(x)={\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}(x-x_{i})+z_{i}\!\,$

Integrating, we have

$q_{i}(x)=z_{i}x+{\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}{\frac {(x-x_{i})^{2}}{2}}+K_{i}\!\,$

or, in a more convenient form,

$q_{i}(x)=z_{i}(x-x_{i})+{\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}{\frac {(x-x_{i})^{2}}{2}}+y_{i}\!\,$

Problem 1b

Find equations which enable us to determine the $z_{i}\!\,$. You should find that one of the $z_{i}\!\,$ can be prescribed arbitrarily, for instance $z_{0}=0\!\,$

Solution 1

Since $q\!\,$ is continuous on $[a,b]\!\,$,

$q_{i-1}(x_{i})=q_{i}(x_{i})=y_{i}\!\,$

i.e.

$z_{i-1}(x_{i}-x_{i-1})+{\frac {z_{i}-z_{i-1}}{x_{i}-x_{i-1}}}{\frac {(x_{i}-x_{i-1})^{2}}{2}}+y_{i-1}=y_{i}\!\,$

Simplifying and rearranging terms yields the reoccurrence formula

$z_{i}=-z_{i-1}+{\frac {2(y_{i}-y_{i-1})}{x_{i}-x_{i-1}}}\quad i=1,\ldots n\!\,$

Problem 2a

Give the definition of the $QR\!\,$ algorithm for finding the eigenvalues of a matrix $A\!\,$. Define both the unshifted version and the version with shifts $\chi _{0},\chi _{1},\chi _{2},\ldots \!\,$

Solution 2a

Unshifted Version

$Q_{k}R_{k}=A_{k}\!\,$

$A_{k+1}=R_{k}Q_{k}\!\,$

Shifted Version

$Q_{k}R_{k}=A_{k}-\chi _{k}I\!\,$

$A_{k+1}=R_{k}Q_{k}+\chi _{k}I\!\,$

Problem 2b

Show that in each case the matrices $A_{1},A_{2}\!\,$ generated by the $QR\!\,$ algorithm are unitarily equivalent to $A\!\,$ (i.e. $A_{i}=U_{i}AU_{i}^{H},U_{i}\!\,$ unitary).

Solution 2b

Suppose $A_{m}=U^{T}AU$ for some unitary $U$. Since $R_{m}=Q_{m}^{T}A_{m}$ we have

$A_{m+1}=R_{m}Q_{m}=Q_{m}^{T}A_{m}Q_{m}=Q_{m}^{T}U^{T}AUQ_{m}$

which is as desired as $Q_{m}U$ is unitary.

For the shifted case, the same argument holds using the fact that $R_{m}=Q_{m}^{T}(A_{m}-\chi _{m}I)$.

Problem 2c

Let $A={\begin{pmatrix}3&1\\1&2\end{pmatrix}}\!\,$ Use plane rotations (Givens rotations) to carry out one step of the $QR\!\,$ algorithm on $A\!\,$, first without shifting and then using the shift $\chi _{0}=1\!\,$. Which seems to do better? The eigenvalues of $A\!\,$ are $\lambda _{1}=1.382,\lambda _{2}=3.618\!\,$. (Recall that a plane rotation is a matrix of the form $Q={\begin{pmatrix}c&-s\\s&c\end{pmatrix}}\!\,$ with $c^{2}+s^{2}=1\!\,$

Solution 2c

The shifted iteration appears to work better because its diagonal entries are closer to the actual eigenvalues than the diagonal entries of the unshifted iteration.

Unshifted Iteration

$A_{1}={\begin{pmatrix}3.5&.5\\.5&1.5\end{pmatrix}}\!\,$

Shifted Iteration

$A_{1}={\begin{pmatrix}3.6&.2\\.2&1.4\end{pmatrix}}\!\,$

Problem 3

Let $A\!\,$ be an $N\times N\!\,$ symmetric, positive definite matrix. Then we know that solving $Ax=b\!\,$ is equivalent to minimizing the functional $F(x)={\frac {1}{2}}\langle x,Ax\rangle -\langle b,x\rangle \!\,$ where $\langle \cdot ,\cdot \rangle \!\,$ denotes the standard inner product in $R^{N}\!\,$. To solve the problem by minimization of $F\!\,$ we consider the general iterative method $x_{v+1}=x_{v}+\alpha _{v}d_{v}\!\,$

Problem 3a

When $x_{v}\!\,$ and $d_{v}\!\,$ are given, show that the value of $\alpha _{v}\!\,$ which minimizes $F(x_{v}+\alpha d_{v})\!\,$ as a function of $\alpha \!\,$ is given in terms of the residual $r_{v}\!\,$ $\alpha _{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }},\quad r_{v}=b-Ax_{v}\!\,$

Solution 3a

Useful Relationship

Since $A\!\,$ is symmetric

$(Ax,y)=(x,A^{T}y)=(x,Ay)\!\,$

This relationship will used throughout the solutions.

Substitute into Functional

${\begin{aligned}F(x_{v}+\alpha d_{v})&={\frac {1}{2}}\langle x_{v}+\alpha d_{v},Ax_{v}+\alpha Ad_{v}\rangle -\langle b,x_{v}+\alpha d_{v}\rangle \\&={\frac {\langle d_{v},Ad_{v}\rangle }{2}}\alpha ^{2}+\alpha \langle d_{v},Ax_{v}\rangle -\alpha \langle b,d_{v}\rangle +{\frac {1}{2}}\langle x_{v},Ax_{v}\rangle -\langle b,x_{v}\rangle \end{aligned}}\!\,$

Take Derivative With Respect to Alpha

$F'(x_{v}+\alpha d_{v})=\langle d_{v},Ad_{v}\rangle \alpha +\langle d_{v},Ax_{v}\rangle -\langle b,d_{v}\rangle \!\,$

Set Derivative Equal To Zero

$0=\langle d_{v},Ad_{v}\rangle \alpha +\langle d_{v},Ax_{v}-b\rangle \!\,$

which implies

$\alpha ={\frac {\langle d_{v},r_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}\!\,$

Problem 3b

Let $\{d_{j}\}_{j=1}^{N}\!\,$ be an $A\!\,$-orthogonal basis of $R^{N}\!\,$, $\langle d_{j},Ad_{k}\rangle =0,j\neq k\!\,$. Consider the expansion of the solution $x\!\,$ in this basis: $x=\sum _{j=1}^{N}{\hat {x_{j}}}d_{j}\!\,$ Use that $A-\!\,$orthogonality of the $d_{j}\!\,$ to compute the ${\hat {x}}_{j}\!\,$ in terms of the solution $x\!\,$ and the $d_{j}\!\,$'s

Solution 3b

${\begin{aligned}\langle x,Ad_{k}\rangle &=\langle \sum _{j=1}^{n}{\hat {x}}_{j}d_{j},Ad_{k}\rangle \\&=\sum _{j=1}^{N}{\hat {x}}_{j}\langle d_{j},Ad_{k}\rangle \\&={\hat {x}}_{k}\langle d_{k},Ad_{k}\rangle \end{aligned}}\!\,$

which implies

${\hat {x}}_{k}={\frac {\langle x,Ad_{k}\rangle }{\langle d_{k},Ad_{k}\rangle }}\!\,$

Problem 3c

Let $x_{v}\!\,$ denote the partial sum $x_{v}=\sum _{j=1}^{v-1}{\hat {x}}_{j}d_{j},\quad v=2,3,\ldots \!\,$ so that $x_{v+1}=x_{v}+{\hat {x}}_{v}d_{v}\!\,$ where the ${\hat {x}}_{v}\!\,$'s are the coefficients found in (b). Use the fact that $x_{v}\in {\mbox{span}}\{d_{1},d_{2},\ldots ,d_{v-1}\}\!\,$ and the $A\!\,$-orthogonality of the $d_{j}\!\,$'s to conclude that the coefficient ${\hat {x}}_{v}\!\,$ is given by the optimal $\alpha _{v}\!\,$ i.e. ${\hat {x}}_{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}=\alpha _{v}\!\,$

Solution 3c

${\begin{aligned}\langle r_{v},d_{v}\rangle &=\langle b-Ax_{v},d_{v}\rangle \\&=\langle Ax-Ax_{v},dv\rangle \\&=\langle Ax,d_{v}\rangle -\langle Ax_{v},d_{v}\rangle \\&=\langle x,Ad_{v}\rangle -\underbrace {\langle x_{v},Ad_{v}\rangle } _{0}\\&={\hat {x}}_{v}\langle d_{v},Ad_{v}\rangle \end{aligned}}\!\,$

which implies

${\hat {x}}_{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}\!\,$