# 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 }}\!\,$