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)=\underset{x\in [0,1]}{\max }|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}\text{in}[0,1]$ such that $f(x_i)-p(x_i)=-[f(x_{i+1})-p(x_{i+1})]=\pm E(p),i=0,1,2,\dots ,n$.

Solution 1a

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

$E(q)<E(p)$

Then for $i=0,1,\dots ,n$

$|f(x_i)-q(x_i)|\le |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))|\ge |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\text{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)=\Vert b-Ax{\Vert }^2$. Here $A$ is an $m\times n$ matrix of rank $n$ (which implies $m\ge n$) and $\Vert \cdot \Vert$ is the Euclidean vector norm. Let $A=\left(\begin{array}{cc}{Q}_1& Q_2\end{array}\right)\left(\begin{array}{c}R\\ 0\end{array}\right)$ be the QR decomposition of $A$. Here $Q_1,Q_2\text{and}R$ are respectively $m\times n,m\times (m-n),\text{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)=\Vert Q_2^{T}b\Vert$.

Solution 2a

The two problems are equivalent

First notice

$A=\left(\begin{array}{c}{Q}_1{Q}_2\end{array}\right)\left(\begin{array}{c}R\\ 0\end{array}\right)=Q_{1}R$

Then we can write

$\begin{array}{cc}\Vert b-Ax\Vert & =\Vert b-Q_{1}Rx\Vert \\ & =\Vert Q_1^{T}b-Q_1^T{Q}_{1}Rx\Vert \\ & =\Vert Q_1^{T}b-Rx\Vert \end{array}$

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

Then solving $\underset{x}{\min }\Vert b-Ax{\Vert }^2$ is equivalent to solving $\underset{x}{\min }\Vert Q_1^{T}b-Rx{\Vert }^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)=\Vert Q_2^{T}b\Vert$

Similarly

$\begin{array}{cc}\Vert b-Ax\Vert & =\Vert b-Q_{1}Rx\Vert \\ & =\Vert Q_2^{T}b-\underset{0}{\underbrace{Q_2^T{Q}_1}}Rx\Vert \\ & =\Vert Q_2^{T}b\Vert \end{array}$

Then

${\rho }^2(x)=\Vert b-Ax{\Vert }^2=\Vert Q_2^{T}b{\Vert }^2$, or simply $\rho (x)=\Vert Q_2^{T}b\Vert$, 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{array}{cc}{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\underset{Rx}{\underbrace{Q_1^{T}b}}\\ & =R^{T}Rx\end{array}$

Problem 3

$$ Let $A$ be real symmetric and let $u_0\ne 0$ be given. For $k=1,2,\dots$, define $u_{k+1}$ as the linear combination of the vectors $A{u}_k,u_k,\dots ,u_0$ with the coefficient of $A{u}_k$ equal to one and orthogonal to the vectors $u_k,\dots ,u_0$; i.e. $u_{k+1}=A{u}_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{array}{cc}{\alpha }_k& =\frac{(A{u}_k,u_k)}{\Vert u_k{\Vert }^2}\\ {\beta }_k& =\frac{(A{u}_k,u_{k-1})}{\Vert u_{k-1}{\Vert }^2}\end{array}$

Problem 3b

Show that ${\gamma }_k={\delta }_k=\dots =0$ Where do you use the symmetry of $A$?

Solution 3b

Since

${\gamma }_k=\frac{(A{u}_k,u_{k-2})}{\Vert u_{k-2}{\Vert }^2}$

, if ${\gamma }_k=0$, then

$(A{u}_k,u_{k-2})=0$

Since $A$ is symmetric,

$(A{u}_k,u_{k-2})=(u_k,A^T{u}_{k-2})=(u_k,A{u}_{k-2})$

From hypothesis, $(u_i,u_j)=\{\begin{array}{cc}1& \text{if }i=j\\ 0& \text{if }i\ne j\end{array}$

Also from hypothesis,

$\begin{array}{cc}A{u}_k& =u_{k+1}+{\alpha }_k{u}_k+{\beta }_k{u}_{k-1}+{\gamma }_k{u}_{k-2}+\dots \\ A{u}_{k-2}& =u_{k-1}+{\alpha }_{k-2}{u}_{k-2}+{\beta }_{k-2}{u}_{k-3}+{\gamma }_{k-2}{u}_{k-4}+\dots \end{array}$

Using the above results we have,

$\begin{array}{cc}(A{u}_k,u_{k-2})& =(u_k,A{u}_{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}+\dots )\\ & =(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})+\dots )\\ & =0\end{array}$

Problem 3c

For which non-zero vectors $u_0$ does $u_1=0$ hold?

Solution 3c

For $k=0$,

$u_1=A{u}_0-{\alpha }_0{u}_0$

If $u_1=0$, then

$A{u}_0={\alpha }_0{u}_0$

Since ${\alpha }_0$ is a scalar, $u_0$ is an eigenvector of $A$.

Template:Reflist