# 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^Tx=\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^Ty = Hy$

Then the constraint can be written

\begin{align} p^Tx &= \delta \\ p^T(H^Ty) &= \delta \\ (Hp)^Ty &= \delta \\ (\|p\|_2e_1)^Ty &= \delta \\ \|p\|_2e_1^Ty &= \delta \\ y_1 &= \frac{\delta}{\|p\|_2} \end{align}

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{align} AHy &=By \\ &=\begin{bmatrix}B_1 & \hat{B}\end{bmatrix} \begin{bmatrix}y_1 \\ \hat{y}\end{bmatrix} \\ &= y_1B_1 + \hat{B}\hat{y} \end{align}

So $\min_y \|b - AHy\|_2 = \min_{\hat{y}}\|b - y_1B_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_2x_i+c_3x_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_2x_i^2+c_3x_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_kp_k$ $\!\,r_{k+1}=r_k-\alpha_kAp_k$ $\!\,\beta_k=(r_{k+1},r_{k+1})/(r_k,r_k)$ $\!\,p_{k+1}=r_{k+1}+\beta_kp_k$ end  where $\!\,(v,w)=\sum_{i=1}^nv_iw_i$ is the Euclidean inner product. Let $\!\,Q$ be some other symmetric[1] 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{align} \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^Tv,w) \\ &= (Av,w) \\ \\ \langle Q^{-1}Av,v\rangle_Q &= (QQ^{-1}Av,v) \\ &= (Av,v) \\ &> 0 \\ \end{align}

## 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

Choose $\!\,x_0$
$\!\,r_0=b-Ax_0$
$\tilde{r}_0$ :  solve $Q\tilde{r}_0 = r_0\!\,$
$\!\,p_0=\tilde{r}_0$
for $\!\,k=0,1,2,...$ until convergence
$\!\,\alpha_k=(r_k,\tilde{r}_k)/(p_k,Ap_k)$
$\!\,x_{k+1}=x_k+\alpha_kp_k$
$\!\,r_{k+1}=r_k-\alpha_kAp_k$
<Test for Convergence>
$\tilde{r}_{k+1}$ :  solve $Q\tilde{r}_{k+1} = r_{k+1}\!\,$
$\!\,\beta_k=(r_{k+1},\tilde{r}_{k+1})/(r_k,\tilde{r}_k)$
$\!\,p_{k+1}=\tilde{r}_{k+1}+\beta_kp_k$
end


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

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