# Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/August 2008
## Problem 1

* Let $A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m},\!\,$ and $p\in \mathbb {R} ^{n}$, with $m>n\!\,$, and let $\delta \!\,$ be a scalar. Show how the constrained least squares problem,
* ${\mbox{minimize }}\|b-Ax\|_{2}\quad \quad {\mbox{ subject to }}p^{T}x=\delta$
* can be reduced to solving a related unconstrained least squares problem. The algorithm should start by finding a Householder transformation $H\!\,$ such that
* $Hp=\|p\|_{2}e_{1}$
* and setting
* $y=Hx\!\,$

## Solution 1

Since Householder Matrices are orthogonal and hermitian (i.e. symmetric if the matrix is real), we have
$y=Hx\Rightarrow x=H^{T}y=Hy$
Then the constraint can be written
${\begin{aligned}p^{T}x&=\delta \\p^{T}(H^{T}y)&=\delta \\(Hp)^{T}y&=\delta \\(\|p\|_{2}e_{1})^{T}y&=\delta \\\|p\|_{2}e_{1}^{T}y&=\delta \\y_{1}&={\frac {\delta }{\|p\|_{2}}}\end{aligned}}$
Hence, the first entry of the column vector $y\!\,$, $y_{1}\!\,$(a scalar), represents our constraint.
Now we want to show that we can write $\|Ax-b\|_{2}\!\,$ as a related unconstrained problem. Substituting for $x\!\,$ in $Ax\!\,$ we get,
$Ax=AHy\!\,$
Let $AH=B={\begin{bmatrix}B_{1}&{\hat {B}}\end{bmatrix}}$ where $B_{1}\!\,$ is the first column of $B\!\,$ and ${\hat {B}}\!\,$ are the remaining columns.
Since,
    $y={\begin{bmatrix}y_{1}\\{\hat {y}}\end{bmatrix}}$
block matrix multiplication yields,
${\begin{aligned}AHy&=By\\&={\begin{bmatrix}B_{1}&{\hat {B}}\end{bmatrix}}{\begin{bmatrix}y_{1}\\{\hat {y}}\end{bmatrix}}\\&=y_{1}B_{1}+{\hat {B}}{\hat {y}}\end{aligned}}$
So $\min _{y}\|b-AHy\|_{2}=\min _{\hat {y}}\|b-y_{1}B_{1}-{\hat {B}}{\hat {y}}\|_{2}$ , which is unconstrained.

## Problem 2

* Prove or disprove the following interpolants exist for all values of $y_{1},y_{2},y_{3}\!\,$ and all distinct values of $x_{1},x_{2},x_{3}\!\,$.

## Problem 2a

* $a.\qquad y_{i}=c_{1}+c_{2}x_{i}+c_{3}x_{i}^{2}\!\,$

## Solution 2a

Substituting into this equation the pairs $x_{i},\,y_{i},\;i=1,2,3,\,$ gives rise to the following matrix equation:
    ${\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}=\underbrace {\begin{bmatrix}1&x_{1}&x_{1}^{2}\\1&x_{2}&x_{2}^{2}\\1&x_{3}&x_{3}^{2}\end{bmatrix}} _{A}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}$
Where A is the Vandermonde matrix, which is know to be non-singular. This proves existence and uniqueness of the coefficients $c_{1},\,c_{2},\,c_{3}$.

## Problem 2b

* $b.\qquad y_{i}=c_{1}+c_{2}x_{i}^{2}+c_{3}x_{i}^{4}\!\,$

## Solution 2b

Now, substituting the pairs $x_{i},\,y_{i},\;i=1,2,3,\,$ gives:
    ${\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}={\begin{bmatrix}1&x_{1}^{2}&x_{1}^{4}\\1&x_{2}^{2}&x_{2}^{4}\\1&x_{3}^{2}&x_{3}^{4}\end{bmatrix}}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}$
Consider the unique set of points $x_{1}=1,\ x_{2}=-1,\ x_{3}=0.\$
The system reduces to
    ${\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}=\underbrace {\begin{bmatrix}1&1&1\\1&1&1\\1&0&0\end{bmatrix}} _{A}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}$
Here, the matrix $A\!\,$ is clearly singular.
More generally, the determinant of the matrix $A$ is given by
$\left|{\begin{array}{ccc}1&x_{1}^{2}&x_{1}^{4}\\1&x_{2}^{2}&x_{2}^{4}\\1&x_{3}^{2}&x_{3}^{4}\end{array}}\right|=(x_{2}^{2}-x_{1}^{2})(x_{3}^{2}-x_{1}^{2})(x_{3}^{2}-x_{2}^{2})=0$ if $x_{j}=-x_{i}$ for any $i\neq j$

## Problem 3

* Consider the linear system of equations $\!\,Ax=b$ where $\!\,A$ is a symmetric positive definite matrix of order $\!\,n$. The conjugate gradient method (CG) for solving this system is
* Choose $\!\,x_{0}$, compute $\!\,r_{0}=b-Ax_{0}$
* Set $\!\,p_{0}=r_{0}$
* for $\!\,k=0$ until convergence
* $\!\,\alpha _{k}=(r_{k},r_{k})/(p_{k},Ap_{k})$
* $\!\,x_{k+1}=x_{k}+\alpha _{k}p_{k}$
* $\!\,r_{k+1}=r_{k}-\alpha _{k}Ap_{k}$
* <Test for Convergence>
* $\!\,\beta _{k}=(r_{k+1},r_{k+1})/(r_{k},r_{k})$
* $\!\,p_{k+1}=r_{k+1}+\beta _{k}p_{k}$
* end
* where $\!\,(v,w)=\sum _{i=1}^{n}v_{i}w_{i}$ is the Euclidean inner product.
* Let $\!\,Q$ be some other symmetric positive-definite matrix of order $\!\,n$. We know that the forms
* $\langle v,w\rangle _{A}\equiv (Av,w)\quad \quad \quad \langle v,w\rangle _{Q}\equiv (Qv,w)$
* are inner products on $\!\,R^{n}$. In addition, a matrix $M\,\!$ is symmetric with respect to the $Q\,\!$ inner product $\langle \,,\,\rangle _{Q}\,\!$ if $\langle Mv,w\rangle _{Q}=\langle v,Mw\rangle _{Q}\,\!$ for all $v,w\,\!$ in $R^{n}\,\!$, and $M\,\!$ is positive definite with respect to $\langle \,,\,\rangle _{Q}\,\!$ if $\langle Mv,v\rangle _{Q}>0\,\!$ for all nonzero $v\,\!$

## Problem 3a

* Show that $Q^{-1}A\,\!$ is symmetric and positive-definite with respect to the $Q\,\!$-inner product.

## Solution 3a

    ${\begin{aligned}\langle Q^{-1}Av,w\rangle _{Q}&=(QQ^{-1}Av,w)\\&=(Av,w)\\\langle v,Q^{-1}Aw\rangle _{Q}&=(Qv,Q^{-1}Aw)\\&=(Q^{-T}Qv,Aw)\\&=(Q^{-1}Qv,Aw)\\&=(v,Aw)\\&=(A^{T}v,w)\\&=(Av,w)\\\\\langle Q^{-1}Av,v\rangle _{Q}&=(QQ^{-1}Av,v)\\&=(Av,v)\\&>0\\\end{aligned}}$

## Problem 3b

* In light of this fact, CG can be used to solve the system $Q^{-1}Ax=Q^{-1}b\,\!$ in an appropriate manner. Specify this algorithm and identify any extra costs required that would not be present with $Q=I\,\!$.

## Solution 3b

One additional cost is computing $Q^{-1}\,\!$.
Another one-time cost is multiplying $Q^{-1}A\,\!$ which has cost $n^{3}\,\!$ and $Q^{-1}b\,\!$ which has cost $n^{2}\,\!$.

## Problem 3c

* Use any facts you know about the conjugate gradient method to identify properties of $Q$ that would be desirable for computing the solution $x$ efficiently.

## Solution 3c

We want $Q^{-1}A\!\,$ to have eigenvalues whose values are close together. This accelerates convergence. Furthermore, if there are only $k\!\,$ distinct eigenvalues, the algorithm will terminate in $k\!\,$ steps.

## Notes

* ↑ Omitted on the actual exam. This made the problem ambiguous and the word symmetric should have been included. (Howard Elman, 12/16/08)