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

## Problem 1

 Let ${\displaystyle a=x_{0}  be an arbitrary fixed partition of the interval ${\displaystyle [a,b]\!\,}$ . A function ${\displaystyle q(x)\!\,}$  is a quadratic spline function if (i) ${\displaystyle q\in C^{1}[a,b]\!\,}$  (ii) On each subinterval ${\displaystyle [x_{i},x_{i+1}]\!\,}$ , ${\displaystyle q\!\,}$  is a quadratic polynomial The problem is to construct a quadratic spline ${\displaystyle q(x)\!\,}$  interpolating data points ${\displaystyle (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 ${\displaystyle z_{i}\equiv q'(x_{i}),i=0,\ldots ,n\!\,}$ , we can construct ${\displaystyle q\!\,}$ .

## Solution 1a

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

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

Integrating, we have

${\displaystyle 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,

${\displaystyle 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 ${\displaystyle z_{i}\!\,}$ . You should find that one of the ${\displaystyle z_{i}\!\,}$  can be prescribed arbitrarily, for instance ${\displaystyle z_{0}=0\!\,}$

## Solution 1

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

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

i.e.

${\displaystyle 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

${\displaystyle 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 ${\displaystyle QR\!\,}$  algorithm for finding the eigenvalues of a matrix ${\displaystyle A\!\,}$ . Define both the unshifted version and the version with shifts ${\displaystyle \chi _{0},\chi _{1},\chi _{2},\ldots \!\,}$

## Solution 2a

### Unshifted Version

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

### Shifted Version

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

## Problem 2b

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

## Solution 2b

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

${\displaystyle 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 ${\displaystyle Q_{m}U}$  is unitary.

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

## Problem 2c

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

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

### Shifted Iteration

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

## Problem 3

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

## Problem 3a

 When ${\displaystyle x_{v}\!\,}$  and ${\displaystyle d_{v}\!\,}$  are given, show that the value of ${\displaystyle \alpha _{v}\!\,}$  which minimizes ${\displaystyle F(x_{v}+\alpha d_{v})\!\,}$  as a function of ${\displaystyle \alpha \!\,}$  is given in terms of the residual ${\displaystyle r_{v}\!\,}$  ${\displaystyle \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 ${\displaystyle A\!\,}$  is symmetric

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

This relationship will used throughout the solutions.

### Substitute into Functional

{\displaystyle {\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

${\displaystyle 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

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

which implies

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

## Problem 3b

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

## Solution 3b

{\displaystyle {\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

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

## Problem 3c

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

## Solution 3c

{\displaystyle {\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

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