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

Problem 1

Given $f\in C[a,b]$, let $p_n^{*}$ denote the best uniform approximation to $f$ among polynomials of degree $\le n$, i.e. $\underset{x\in [a,b]}{\max }|f(x)-p_n(x)|$ is minimized by the choice $p_n=p_n^{*}$. Let $e(x)=f(x)-p_n^{*}(x)$. Prove that there are at least two points $x_1,x_2\in [a,b]$ such that $|e(x_1)|=|e(x_2)|=\underset{x\in [a,b]}{\max }|f(x)-p_n^{*}(x)|$ and $e(x_1)=-e(x_2)$

Solution 1

Since both $f(x)$ and $p_n^{*}(x)$ are continuous, so is the function

$e(x)=f(x)-p_n^{*}(x)$

and therefore $e(x)$ attains both a maximum and a minimum on $[a,b]$.

Let $M=\underset{x\in [a,b]}{\max }e(x)$ and $m=\underset{x\in [a,b]}{\min }e(x)$

If $M\ne -m$, then there exists a polynomial $q(x)=p_n^{*}(x)+\frac{M+m}{2}$ (a vertical shift of the supposed best approximation $p_n^{*}(x))$ which is a better approximation to $f(x)$.

$\begin{array}{cc}f(x)-q(x)& =f(x)-p_n^{*}(x)-\frac{M+m}{2}\\ & \le M-\frac{M+m}{2}\\ & =\frac{M-m}{2}\\ \\ \\ f(x)-q(x)& \ge m-\frac{M+m}{2}\\ & =\frac{m-M}{2}\end{array}$

Therefore,

$\Vert f(x)-q(x)\Vert \le \frac{M-m}{2}\le \Vert f-p_n^{*}\Vert =M$

Equality holds if and only if $m=-M$.

Problem 2a

Find the node $x_1$ and the weight $w_1$ so that the integration rule $I=\underset{0}{\overset{1}{\int }}{x}^{-\frac{1}{2}}f(x)dx\approx w_{1}f(x_1)$ is exact for linear functions. (No knowledge of orthogonal polynomials is required.)

Solution 2a

Let $f(x)=1$. Then

$\underset{0}{\overset{1}{\int }}\frac{1}{x^{\frac{1}{2}}}=w_1\cdot 1$

which implies after computation

$w_1=2$

Let $f(x)=x$. Then

$\underset{0}{\overset{1}{\int }}\frac{x}{x^{\frac{1}{2}}}=w_1\cdot x_1=2x_1$

which implies after computation

$x_1=\frac{1}{3}$

Problem 2b

Show that no one-point rule for approximating $I$ can be exact for quadratics.

Solution 2b

Suppose there is a one-point rule for approximating $I$ that is exact for quadratics.

Let $f(x)=x^2$.

Then,

$\underset{0}{\overset{1}{\int }}\frac{x^2}{x^{\frac{1}{2}}}=\frac{2}{5}$

but

$w_1{x}_1^2=2(\frac{1}{3}{)}^2=\frac{2}{9}$,

a contradiction.

Problem 2c

In fact $I-w_{1}f(x_1)=c{f}^{″}(\xi )\text{ for some }\xi \in [0,1]$ Find $c$.

Solution 2c

Let $f(x)=x^2$. Then $f^{″}(x)=2$

Using the values computed in part (b), we have

$\frac{2}{5}-\frac{2}{9}=c\cdot 2$

which implies

$c=\frac{4}{45}$

Problem 2d

Let $f(x)$ and $g(x)$ be two polynomials of degree $\le 3$. Suppose $f$ and $g$ agree at $x=a$, $x=b$, and $x=(a+b)/2$. Show $\underset{a}{\overset{b}{\int }}f(x)dx=\underset{a}{\overset{b}{\int }}g(x)dx$

Solution 2d

There exist $w_1,w_2,w_3$ such that if $f(x)$ is a polynomial of degree $\le 3$

$\underset{a}{\overset{b}{\int }}f(x)dx=w_{1}f(a)+w_{2}f(b)+w_{3}f(\frac{a+b}{2})$

Hence,

$\begin{array}{cc}\underset{a}{\overset{b}{\int }}f(x)dx& =w_{1}f(a)+w_{2}f(b)+w_{3}f(\frac{a+b}{2})\\ & =w_{1}g(a)+w_{2}g(b)+w_{3}g(\frac{a+b}{2})\\ & =\underset{a}{\overset{b}{\int }}g(x)dx\end{array}$

Problem 3

Let $A\in R^{n\times n}$ be nonsingular and $b\in R^n$. Consider the following iteration for the solution $Ax=b$ $x_{k+1}=x_k+\alpha (b-A{x}_k)$

Problem 3a

Show that if all eigenvalues of $A$ have positive real part then there will be some real $\alpha$ such that the iterates converge for any starting vector $x_0$. Discuss how to choose $\alpha$ optimally in case $A$ is symmetric and determine the rate of convergence.

Solution 3a

Convergence of any starting vector

Using the iteration $x_{k+1}=x_k+\alpha (b-A{x}_k)$, we have that

$\begin{array}{cc}{e}_{k+1}& =x_{k+1}-x^{*}\\ & =x_k-x^{*}+\alpha (b-A{x}_k)\\ & =x_k-x^{*}+\alpha (A{x}^{*}-A{x}_k)\\ & =e_k-\alpha A{e}_k\\ & =(I-\alpha A)e_k\end{array}$

Then, computing norms we obtain

$\Vert e_{k+1}\Vert \le \Vert I-\alpha A\Vert \Vert e_k\Vert$.

In particular, considering $\Vert \cdot {\Vert }_2$, we have that

$\Vert e_{k+1}{\Vert }_2\le \Vert I-\alpha A{\Vert }_2\Vert e_k{\Vert }_2$.

Now, in order to study the convergence of the method, we need to analyze $\Vert I-\alpha A{\Vert }_2$. We use the following characterization:

$\begin{array}{cc}\Vert I-\alpha A{\Vert }_2^2& =\rho ((I-\alpha A)(I-\alpha A{)}^{*})\\ & =\rho (I-\alpha A^{*}-\alpha A+|\alpha {|}^{2}A{A}^{*})\end{array}$

Let's denote by $\lambda$ an eigenvalue of the matrix $A$. Then $\rho ((I-\alpha A)(I-\alpha A{)}^{*})<1$ implies

$1-2\alpha Re(\lambda )+{\alpha }^2|\lambda {|}^2<1$

i.e.

$-2\alpha Re(\lambda )+{\alpha }^2|\lambda {|}^2<0$

The above equation is quadratic with respect to $\alpha$ and opens upward. Hence using the quadratic formula we can find the roots of the equation to be

${\alpha }_1=0{\alpha }_2=2\frac{Re(\lambda )}{|\lambda {|}^2}$

Then, if $Re(\lambda )>0$ for all the eigenvalues of the matrix $A$, we can find $\alpha \in (0,2\frac{Re(\lambda )}{|\lambda {|}^2})$ such that $\rho ((I-\alpha A)(I-\alpha A{)}^{*})<1$, i.e., the method converges.

Choosing alpha if A symmetric

On the other hand, if the matrix $A$ is symmetric, we have that $\Vert I-\alpha A{\Vert }_2=\rho (I-\alpha A)$. Then using the Schur decomposition, we can find a unitary matrix $U$ and a diagonal matrix $\mathrm{\Lambda }$ such that $A=U^{*}\mathrm{\Lambda }U$, and in consequence,

$\begin{array}{cc}\Vert I-\alpha A{\Vert }_2& =\Vert I-\alpha \mathrm{\Lambda }{\Vert }_2\\ & =\rho (I-\alpha \mathrm{\Lambda })\\ & =\underset{i=1,\dots ,n}{\max }(1-\alpha {\lambda }_i)\\ \end{array}$

This last expression is minimized if $(1-\alpha {\lambda }_1)=-(1-\alpha {\lambda }_n)$, i.e, if ${\alpha }_{opt}=2/({\lambda }_1+{\lambda }_n)$. With this optimal value of $\alpha$, we obtain that

$(I-{\alpha }_{opt}\mathrm{\Lambda }{)}_{i,i}=1-\frac{2}{{\lambda }_1+{\lambda }_n}{\lambda }_i,$

which implies that

$\Vert I-{\alpha }_{opt}\mathrm{\Lambda }{\Vert }_2=\frac{{\lambda }_n-{\lambda }_1}{{\lambda }_1+{\lambda }_n}$.

Finally, we've obtained that

$\Vert e_{k+1}{\Vert }_2\le \frac{{\lambda }_n-{\lambda }_1}{{\lambda }_1+{\lambda }_n}\Vert e_k{\Vert }_2$.

Problem 3b

Show that if some eigenvalues of $A$ have negative real part and some have positive real part, then there is no real $\alpha$ for which the iterations converge.

Solution 3b

If $Re({\lambda }_i)>0$ for $i=1,2,\dots ,n$, then convergence occurs if

$\alpha \in (0,2\frac{Re(\lambda )}{|\lambda {|}^2})$

Hence $\alpha >0$.

Similarly, if $Re({\lambda }_i)<0$ for $i=1,2,\dots ,n$, then convergence occurs if

$\alpha \in (2\frac{Re(\lambda )}{|\lambda {|}^2},0)$

Hence $\alpha <0$.

If some eigenvalues are positive and some negative, there does not exist a real $\alpha$ for which the iterations converge since $\alpha$ cannot be both positive and negative simultaneously.

Problem 3c

Let $p=\Vert I-\alpha A\Vert <1$ for a matrix norm associated to a vector norm. Show that the error can be expressed in terms of the difference between consecutive iterates, namely $\Vert x-x_{k+1}\Vert \le \frac{\rho }{1-\rho }\Vert x_k-x_{k+1}\Vert$ (The proof of this is short but a little tricky)

Solution 3c

$\begin{array}{cc}\Vert x-x_{k+1}\Vert & \le p\Vert x-x_{k+1}+x_{k+1}-x_k\Vert \\ & \le p\Vert x-x_{k+1}\Vert +p\Vert x_{k+1}-x_k\Vert \\ (1-p)\Vert x-x_{k+1}\Vert & \le p\Vert x_{k+1}-x_k\Vert \\ \Vert x-x_{k+1}\Vert & \le \frac{p}{1-p}\Vert x_{k+1}-x_k\Vert \end{array}$

Problem 3d

Let $A$ be the tridiagonal matrix $\left(\begin{array}{cccccc}3& 1& 0& 0& \cdots & 0\\ -1& 3& 1& 0& \cdots & 0\\ ⋮& \ddots & \ddots & \ddots & ⋮& ⋮\\ ⋮& ⋮& \ddots & \ddots & \ddots & ⋮\\ ⋮& ⋮& ⋮& \ddots & 3& 1\\ 0& \cdots & \cdots & \cdots & -1& 3\end{array}\right)$ Find a value of $\alpha$ that guarantees convergence

Solution 3d

By Gerschgorin's theorem, the magnitude of all the eigenvalues are between 1 and 5 i.e.

$1<|\lambda |<5$

Therefore,

$\rho (I-\alpha A)=\underset{i}{\max }(|1-\alpha {\lambda }_i|)\le |1-\alpha 5|$

We want

$\rho (I-\alpha A)<|1-\alpha 5|<1$

Therefore,

$0<\alpha <\frac{2}{5}$