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 $\leq n\!\,$, i.e. $\max _{x\in [a,b]}|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})|=\max _{x\in [a,b]}|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=\max _{x\in [a,b]}e(x)\!\,$ and $m=\min _{x\in [a,b]}e(x)\!\,$

If $M\neq -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{aligned}f(x)-q(x)&=f(x)-p_{n}^{*}(x)-{\frac {M+m}{2}}\\&\leq M-{\frac {M+m}{2}}\\&={\frac {M-m}{2}}\\\\\\f(x)-q(x)&\geq m-{\frac {M+m}{2}}\\&={\frac {m-M}{2}}\end{aligned}}\!\,$

Therefore,

$\|f(x)-q(x)\|\leq {\frac {M-m}{2}}\leq \|f-p_{n}^{*}\|=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=\int _{0}^{1}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

$\int _{0}^{1}{\frac {1}{x^{\frac {1}{2}}}}=w_{1}\cdot 1\!\,$

which implies after computation

$w_{1}=2\!\,$

Let $f(x)=x\!\,$. Then

$\int _{0}^{1}{\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,

$\int _{0}^{1}{\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})=cf''(\xi ){\mbox{ 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 $\leq 3\!\,$. Suppose $f\!\,$ and $g\!\,$ agree at $x=a\!\,$, $x=b\!\,$, and $x=(a+b)/2\!\,$. Show $\int _{a}^{b}f(x)dx=\int _{a}^{b}g(x)dx\!\,$

Solution 2d

There exist $w_{1},w_{2},w_{3}\!\,$ such that if $f(x)\!\,$ is a polynomial of degree $\leq 3\!\,$

$\int _{a}^{b}f(x)dx=w_{1}f(a)+w_{2}f(b)+w_{3}f({\frac {a+b}{2}})\!\,$

Hence,

${\begin{aligned}\int _{a}^{b}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}})\\&=\int _{a}^{b}g(x)dx\end{aligned}}\!\,$

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-Ax_{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-Ax_{k})$, we have that

${\begin{aligned}e_{k+1}&=x_{k+1}-x^{*}\\&=x_{k}-x^{*}+\alpha (b-Ax_{k})\\&=x_{k}-x^{*}+\alpha (Ax^{*}-Ax_{k})\\&=e_{k}-\alpha Ae_{k}\\&=(I-\alpha A)e_{k}\end{aligned}}$

Then, computing norms we obtain

$\,\!\|e_{k+1}\|\leq \|I-\alpha A\|\|e_{k}\|$.

In particular, considering $\,\!\|\cdot \|_{2}$, we have that

$\,\!\|e_{k+1}\|_{2}\leq \|I-\alpha A\|_{2}\|e_{k}\|_{2}$.

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

${\begin{aligned}\|I-\alpha A\|_{2}^{2}&=\rho \left((I-\alpha A)(I-\alpha A)^{*}\right)\\&=\rho \left(I-\alpha A^{*}-\alpha A+|\alpha |^{2}AA^{*}\right)\end{aligned}}$

Let's denote by $\,\!\lambda$ an eigenvalue of the matrix $\,\!A$. Then $\rho \left((I-\alpha A)(I-\alpha A)^{*}\right)<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\quad \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 \left((I-\alpha A)(I-\alpha A)^{*}\right)<1$, i.e., the method converges.

Choosing alpha if A symmetric

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

${\begin{aligned}\|I-\alpha A\|_{2}&=\|I-\alpha \Lambda \|_{2}\\&=\rho (I-\alpha \Lambda )\\&=\max _{i=1,\dots ,n}(1-\alpha \lambda _{i})\\\end{aligned}}$

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}\Lambda )_{i,i}=1-{\frac {2}{\lambda _{1}+\lambda _{n}}}\lambda _{i},$

which implies that

$\,\!\|I-\alpha _{opt}\Lambda \|_{2}={\frac {\lambda _{n}-\lambda _{1}}{\lambda _{1}+\lambda _{n}}}$.

Finally, we've obtained that

$\,\!\|e_{k+1}\|_{2}\leq {\frac {\lambda _{n}-\lambda _{1}}{\lambda _{1}+\lambda _{n}}}\|e_{k}\|_{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,\ldots ,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,\ldots ,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=\|I-\alpha A\|<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 $\|x-x_{k+1}\|\leq {\frac {\rho }{1-\rho }}\|x_{k}-x_{k+1}\|\!\,$ (The proof of this is short but a little tricky)

Solution 3c

${\begin{aligned}\|x-x_{k+1}\|&\leq p\|x-x_{k+1}+x_{k+1}-x_{k}\|\\&\leq p\|x-x_{k+1}\|+p\|x_{k+1}-x_{k}\|\\(1-p)\|x-x_{k+1}\|&\leq p\|x_{k+1}-x_{k}\|\\\|x-x_{k+1}\|&\leq {\frac {p}{1-p}}\|x_{k+1}-x_{k}\|\end{aligned}}\!\,$

Problem 3d

Let $A\!\,$ be the tridiagonal matrix ${\begin{pmatrix}3&1&0&0&\cdots &0\\-1&3&1&0&\cdots &0\\\vdots &\ddots &\ddots &\ddots &\vdots &\vdots \\\vdots &\vdots &\ddots &\ddots &\ddots &\vdots \\\vdots &\vdots &\vdots &\ddots &3&1\\0&\cdots &\cdots &\cdots &-1&3\end{pmatrix}}\!\,$ 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)=\max _{i}(|1-\alpha \lambda _{i}|)\leq |1-\alpha 5|\!\,$

We want

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

Therefore,

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