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

## Problem 1

 Let ${\displaystyle A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m},\!\,}$  and ${\displaystyle p\in \mathbb {R} ^{n}}$ , with ${\displaystyle m>n\!\,}$ , and let ${\displaystyle \delta \!\,}$  be a scalar. Show how the constrained least squares problem, ${\displaystyle {\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 ${\displaystyle H\!\,}$  such that ${\displaystyle Hp=\|p\|_{2}e_{1}}$  and setting ${\displaystyle y=Hx\!\,}$

## Solution 1

Since Householder Matrices are orthogonal and hermitian (i.e. symmetric if the matrix is real), we have

${\displaystyle y=Hx\Rightarrow x=H^{T}y=Hy}$

Then the constraint can be written

{\displaystyle {\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 ${\displaystyle y\!\,}$ , ${\displaystyle y_{1}\!\,}$ (a scalar), represents our constraint.

Now we want to show that we can write ${\displaystyle \|Ax-b\|_{2}\!\,}$  as a related unconstrained problem. Substituting for ${\displaystyle x\!\,}$  in ${\displaystyle Ax\!\,}$  we get,

${\displaystyle Ax=AHy\!\,}$

Let ${\displaystyle AH=B={\begin{bmatrix}B_{1}&{\hat {B}}\end{bmatrix}}}$  where ${\displaystyle B_{1}\!\,}$  is the first column of ${\displaystyle B\!\,}$  and ${\displaystyle {\hat {B}}\!\,}$  are the remaining columns.

Since,

${\displaystyle y={\begin{bmatrix}y_{1}\\{\hat {y}}\end{bmatrix}}}$

block matrix multiplication yields,

{\displaystyle {\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 ${\displaystyle \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 ${\displaystyle y_{1},y_{2},y_{3}\!\,}$  and all distinct values of ${\displaystyle x_{1},x_{2},x_{3}\!\,}$ .

## Problem 2a

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

## Solution 2a

Substituting into this equation the pairs ${\displaystyle x_{i},\,y_{i},\;i=1,2,3,\,}$  gives rise to the following matrix equation:

${\displaystyle {\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 ${\displaystyle c_{1},\,c_{2},\,c_{3}}$ .

## Problem 2b

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

## Solution 2b

Now, substituting the pairs ${\displaystyle x_{i},\,y_{i},\;i=1,2,3,\,}$  gives:

${\displaystyle {\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 ${\displaystyle x_{1}=1,\ x_{2}=-1,\ x_{3}=0.\ }$

The system reduces to

${\displaystyle {\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 ${\displaystyle A\!\,}$  is clearly singular.

More generally, the determinant of the matrix ${\displaystyle A}$  is given by

${\displaystyle \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 ${\displaystyle x_{j}=-x_{i}}$  for any ${\displaystyle i\neq j}$

## Problem 3

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

## Problem 3a

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

## Solution 3a

{\displaystyle {\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 ${\displaystyle 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 ${\displaystyle Q=I\,\!}$ .

## Solution 3b

Choose ${\displaystyle \!\,x_{0}}$
${\displaystyle \!\,r_{0}=b-Ax_{0}}$
${\displaystyle {\tilde {r}}_{0}}$  :  solve ${\displaystyle Q{\tilde {r}}_{0}=r_{0}\!\,}$
${\displaystyle \!\,p_{0}={\tilde {r}}_{0}}$
for ${\displaystyle \!\,k=0,1,2,...}$  until convergence
${\displaystyle \!\,\alpha _{k}=(r_{k},{\tilde {r}}_{k})/(p_{k},Ap_{k})}$
${\displaystyle \!\,x_{k+1}=x_{k}+\alpha _{k}p_{k}}$
${\displaystyle \!\,r_{k+1}=r_{k}-\alpha _{k}Ap_{k}}$
<Test for Convergence>
${\displaystyle {\tilde {r}}_{k+1}}$  :  solve ${\displaystyle Q{\tilde {r}}_{k+1}=r_{k+1}\!\,}$
${\displaystyle \!\,\beta _{k}=(r_{k+1},{\tilde {r}}_{k+1})/(r_{k},{\tilde {r}}_{k})}$
${\displaystyle \!\,p_{k+1}={\tilde {r}}_{k+1}+\beta _{k}p_{k}}$
end


One additional cost is computing ${\displaystyle Q^{-1}\,\!}$ .

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

## Problem 3c

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

## Solution 3c

We want ${\displaystyle Q^{-1}A\!\,}$  to have eigenvalues whose values are close together. This accelerates convergence. Furthermore, if there are only ${\displaystyle k\!\,}$  distinct eigenvalues, the algorithm will terminate in ${\displaystyle 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)