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

Problem 1

Let $f\!\,$ be continuous on $[0,1]\!\,$. A polynomial $p\!\,$ of degree not greater than $n\!\,$ is said to be a best (or Chebyshev) approximation to $f\!\,$ if $p\!\,$ minimizes the expression $E(p)=\max _{x\in [0,1]}|f(x)-p(x)|\!\,$

Problem 1a

Show that a sufficient condition for $p\!\,$ to be a best approximation is that there exists points $x_{0}<x_{1}<\cdots <x_{n+1}\;{\mbox{in}}\;[0,1]\!\,$ such that $f(x_{i})-p(x_{i})=-[f(x_{i+1})-p(x_{i+1})]=\pm E(p),\qquad i=0,1,2,\dots ,n\!\,$.

Solution 1a

Assume there exists $q\in \Pi ^{n}\!\,$ such that

$E(q)<E(p)\!\,$

Then for $i=0,1,\ldots ,n\!\,$

$|f(x_{i})-q(x_{i})|\leq |f(x_{i})-p(x_{i})|\!\,$

Let $e(q)=f(x)-q(x)\!\,$ and $e(p)=f(x)-p(x)\!\,$.

Then $e\equiv e(q(x))-e(p(x))\!\,$ takes on the sign of $e(p)\!\,$ since

$|e(p(x_{i}))|\geq |e(q(x_{i}))|\!\,$

Since $e(p)\!\,$ changes signs $n+1\!\,$ times (by hypothesis), $e\!\,$ has $n+1\!\,$ zeros.

However $e=p-q\!\,$ and thus can only have at most $n\!\,$ zeros. Therefore $e\equiv 0\!\,$ and $p=q\!\,$

Problem 1b

Compute the best linear approximation to $x^{2}\;{\mbox{in}}\;[0,1]\!\,$. [Hint: Drawing a line through the parabola will allow you to conjecture where two points of oscillation must lie. Use conditions from (a) to determine the third point and coefficients of $p\!\,$.]

Solution 1b

First we need to find the roots of $T_{2}(x)\!\,$ in [0,1], which are given by

$x_{k}={\frac {1}{2}}+{\frac {1}{2}}\cos({\frac {2k-1}{4}}\pi )\!\,$

So our points at which to interpolate are

$x_{1}={\frac {1}{2}}+{\frac {1}{2}}\cos({\frac {\pi }{4}})\!\,$

$x_{2}={\frac {1}{2}}+{\frac {1}{2}}\cos({\frac {3\pi }{4}})={\frac {1}{2}}-{\frac {1}{2}}\cos({\frac {\pi }{4}})\!\,$

Our linear interpolant passes through the points $(x_{1},x_{1}^{2})\!\,$ and $(x_{2},x_{2}^{2})\!\,$, which using point-slope form gives the equation

$y-x_{1}^{2}={\frac {x_{2}^{2}-x_{1}^{2}}{x_{2}-x_{1}}}(x-x_{1})\!\,$

or

$y=x-{\frac {1}{8}}\!\,$

Problem 2

We will be concerned with the least squares problem of minimizing $\rho ^{2}(x)=\|b-Ax\|^{2}\!\,$. Here $A\!\,$ is an $m\times n\!\,$ matrix of rank $n\!\,$ (which implies $m\geq n\!\,$) and $\|\cdot \|\!\,$ is the Euclidean vector norm. Let $A={\begin{pmatrix}Q_{1}&Q_{2}\end{pmatrix}}{\begin{pmatrix}R\\0\end{pmatrix}}\!\,$ be the QR decomposition of $A\!\,$. Here $Q_{1},Q_{2}\;{\mbox{and}}\;R\!\,$ are respectively $m\times n,m\times (m-n),\;{\mbox{and}}\;n\times n\!\,$.

Problem 2a

Show that the solution of the least squares problem satisfies the QR equation $Rx=Q_{1}^{T}b\!\,$ and that the solution is unique. Further show that $\rho (x)=\|Q_{2}^{T}b\|\!\,$.

Solution 2a

The two problems are equivalent

First notice

$A={\begin{pmatrix}Q_{1}Q_{2}\end{pmatrix}}{\begin{pmatrix}R\\0\end{pmatrix}}=Q_{1}R$

Then we can write

${\begin{aligned}\|b-Ax\|&=\|b-Q_{1}Rx\|\\&=\|Q_{1}^{T}b-Q_{1}^{T}Q_{1}Rx\|\\&=\|Q_{1}^{T}b-Rx\|\end{aligned}}$

Note that multiplying by orthogonal matrices does not affect the norm.

Then solving $\min _{x}\|b-Ax\|^{2}\!\,$ is equivalent to solving $\min _{x}\|Q_{1}^{T}b-Rx\|^{2}\!\,$, which is equivalent to solving $Rx=Q_{1}^{T}b\!\,$. Note that a solution exists and is unique since $R\!\,$ is n-by-n and non-singular.

Show that $\rho (x)=\|Q_{2}^{T}b\|$

Similarly

${\begin{aligned}\|b-Ax\|&=\|b-Q_{1}Rx\|\\&=\|Q_{2}^{T}b-\underbrace {Q_{2}^{T}Q_{1}} _{0}Rx\|\\&=\|Q_{2}^{T}b\|\end{aligned}}$

Then

$\rho ^{2}(x)=\|b-Ax\|^{2}=\|Q_{2}^{T}b\|^{2}$, or simply $\rho (x)=\|Q_{2}^{T}b\|$, as desired.

Problem 2b

Use the QR equation to show that the least squares solution satisfies the normal equations $(A^{T}A)x=A^{T}b\!\,$.

Solution 2b

${\begin{aligned}A^{T}Ax&=(Q_{1}R)^{T}Q_{1}Rx\\&=R^{T}Q_{1}^{T}Q_{1}Rx\\&=R^{T}Rx\\\\A^{T}b&=(Q_{1}R)^{T}b\\&=R^{T}\underbrace {Q_{1}^{T}b} _{Rx}\\&=R^{T}Rx\end{aligned}}\!\,$

Problem 3

$\!\,$ Let $\!\,A$ be real symmetric and let $u_{0}\neq 0\!\,$ be given. For $k=1,2,\ldots \!\,$, define $u_{k+1}\!\,$ as the linear combination of the vectors $Au_{k},u_{k},\ldots ,u_{0}\!\,$ with the coefficient of $Au_{k}\!\,$ equal to one and orthogonal to the vectors $u_{k},\ldots ,u_{0}\!\,$; i.e. $u_{k+1}=Au_{k}-\alpha _{k}u_{k}-\beta _{k}u_{k-1}-\gamma _{k}u_{k-2}-\cdots \!\,$

Problem 3a

Find formulas for $\alpha _{k}\!\,$ and $\beta _{k}\!\,$

Solution 3a

Using Gram Schmidit, we have

${\begin{aligned}\alpha _{k}&={\frac {(Au_{k},u_{k})}{\|u_{k}\|^{2}}}\\\beta _{k}&={\frac {(Au_{k},u_{k-1})}{\|u_{k-1}\|^{2}}}\end{aligned}}$

Problem 3b

Show that $\gamma _{k}=\delta _{k}=\ldots =0\!\,$ Where do you use the symmetry of $A\!\,$?

Solution 3b

Since

$\gamma _{k}={\frac {(Au_{k},u_{k-2})}{\|u_{k-2}\|^{2}}}$

, if $\gamma _{k}=0\!\,$, then

$(Au_{k},u_{k-2})=0\!\,$

Since $A\!\,$ is symmetric,

$(Au_{k},u_{k-2})=(u_{k},A^{T}u_{k-2})=(u_{k},Au_{k-2})\!\,$

From hypothesis, $(u_{i},u_{j})={\begin{cases}1&{\mbox{if }}i=j\\0&{\mbox{if }}i\neq j\end{cases}}$

Also from hypothesis,

${\begin{aligned}Au_{k}&=u_{k+1}+\alpha _{k}u_{k}+\beta _{k}u_{k-1}+\gamma _{k}u_{k-2}+\ldots \\Au_{k-2}&=u_{k-1}+\alpha _{k-2}u_{k-2}+\beta _{k-2}u_{k-3}+\gamma _{k-2}u_{k-4}+\ldots \end{aligned}}$

Using the above results we have,

${\begin{aligned}(Au_{k},u_{k-2})&=(u_{k},Au_{k-2})\\&=(u_{k},u_{k-1}+\alpha _{k-2}u_{k-2}+\beta _{k-2}u_{k-3}+\gamma _{k-2}u_{k-4}+\ldots )\\&=(u_{k},u_{k-1})+\alpha _{k-2}(u_{k},u_{k-2})+\beta _{k-2}(u_{k},u_{k-3})+\gamma _{k-2}(u_{k},u_{k-4})+\ldots )\\&=0\end{aligned}}$

Problem 3c

For which non-zero vectors $u_{0}\!\,$ does $u_{1}=0\!\,$ hold?

Solution 3c

For $k=0\!\,$,

$u_{1}=Au_{0}-\alpha _{0}u_{0}\!\,$

If $u_{1}=0\!\,$, then

$Au_{0}=\alpha _{0}u_{0}\!\,$

Since $\alpha _{0}\!\,$ is a scalar, $u_{0}\!\,$ is an eigenvector of $A\!\,$.