# 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}}\!\,$