# Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/January 2000
## Problem 1

* Let $f\!\,$ be a function with 3 continuous derivatives. Let $q\!\,$ be a quadratic polynomial that interpolates $f\!\,$ at $x_{0}<x_{1}<x_{2}\!\,$. Let $h=max(x_{1}-x_{0},x_{2}-x_{1})\!\,$ and
* $\max _{x_{0}\leq x\leq x_{2}}|f'''(x)|=K\!\,$.

## Problem 1a

* Show that
* $\max _{x_{0}\leq x\leq x_{2}}|f''(x)-q''(x)|=Ch^{\alpha }\!\,$,
* where $C>0\!\,$ depends only on $K\!\,$ and determine $\alpha _{i}\!\,$. (Hint: the key to this is to prove that $f''(x)-q''(x)\!\,$ vanishes at some point in $[x_{0},x_{2}]\!\,$. The result can then be obtained by integration.)

## Solution 1a
### Proof of Hint

Claim: There exists $\eta \in (x_{0},x_{2})\!\,$ such that $f^{\prime \prime }(\eta )-q^{\prime \prime }(\eta )=0\!\,$
Proof: The interpolation polynomial may be expressed using dividing difference coefficients i.e.
$q(x)=f[x_{0}]+f[x_{0},x_{1}](x-x_{0})+f[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})\!\,$
which implies
$q^{\prime \prime }(x)=2f[x_{0},x_{1},x_{2}]\!\,$
In general, the divided difference coefficients may be expressed as a factorial weighted point of a derivative of $f\!\,$ i.e.
$(\triangle )\qquad f[x_{0},\ldots ,x_{n}]={\frac {f^{(n)}(\xi )}{(n)!}}\qquad \xi \in I[x_{0},\ldots ,x_{n}]\!\,$
Hence,
$f[x_{0},x_{1},x_{2}]={\frac {f^{\prime \prime }(\eta )}{2!}}\qquad \eta \in [x_{0},x_{2}]\!\,$
which implies
$q^{\prime \prime }(\eta )-f^{\prime \prime }(\eta )=0\!\,$

### Application of Hint

From the hint we know that
$f^{\prime \prime }(\eta )-q^{\prime \prime }(\eta )=0\!\,$
which implies
$f^{\prime \prime }(x)-q^{\prime \prime }(x)=f^{\prime \prime }(x)-q^{\prime \prime }(x)-f^{\prime \prime }(\eta )+q^{\prime \prime }(\eta )\!\,$
Since $q(x)\!\,$ is quadratic, $q^{\prime \prime }(x)\!\,$ is constant i.e. $q^{\prime \prime }(x)=K\!\,$ for all $x\!\,$
Therefore,
$f^{\prime \prime }(x)-q^{\prime \prime }(x)=f^{\prime \prime }(x)-q^{\prime \prime }(x)-f^{\prime \prime }(\eta )+q^{\prime \prime }(\eta )=f^{\prime \prime }(x)-f^{\prime \prime }(\eta )\!\,$
By the fundamental theorem of calculus,
${\begin{aligned}f^{\prime \prime }(x)-f^{\prime \prime }(\eta )&=\int _{\eta }^{x}f^{\prime \prime \prime }(t)dt\\&\leq \|f^{\prime \prime \prime }(x)\|_{\infty }|x-\eta |\\&\leq 2h\|f^{\prime \prime \prime }\|_{\infty }\end{aligned}}$
Therefore,
$\max _{x\in [x_{0},x_{2}]}|f^{\prime \prime }(x)-q^{\prime \prime }(x)|\leq \underbrace {2\|f^{\prime \prime \prime }(x)\|_{\infty }} _{C}h^{1}\!\,$

## Problem 1b

* Now suppose $h=x_{2}-x_{1}=x_{1}-x_{0}\!\,$ and $f\!\,$ has 4 continuous derivatives. In this case show
* $|f''(x_{1})-q''(x_{1})|\leq C'h^{\beta }\!\,$
* where $\beta >\alpha \!\,$. What is $C'\!\,$ in terms of the derivatives of $f\!\,$?

## Solution 1b
### Third Derivative of f has Zero

We know that $f[x_{0},x_{1},x_{2},x]=0\!\,$, because $p\in P_{2}\!\,$. Now, by $(\triangle )\!\,$ we can conclude that there exists $\eta ^{*}\in I[x_{0},x_{1},x_{2},x]\!\,$ such that $f'''(\eta ^{*})=0\!\,$.

### Application of Fundamental Theorem of Calculus (Twice)

    ${\begin{aligned}f''(x_{1})-f''(\eta )&=\int _{\eta }^{x_{1}}f^{(3)}(x)dx\\&=\int _{\eta }^{x_{1}}f^{(3)}(x)-\underbrace {f^{(3)}(\eta ^{*})} _{0}dx\\&=\int _{\eta }^{x_{1}}\int _{\eta *}^{x}f^{(4)}(t)dtdx\\&\leq \|f^{(4)}\|_{\infty }|x-\eta ^{*}||x_{1}-\eta |\\&\leq \underbrace {2\|f^{(4)}\|_{\infty }} _{C'}h^{2},\end{aligned}}$

## Problem 2a

* Find $\{p_{0},p_{1},p_{2}\}\!\,$ such that $p_{i}\!\,$ is a polynomial of degree $i\!\,$ and this set is orthogonal on $[0,\infty )\!\,$ with respect to the weight function $w(x)=e^{-x}\!\,$. (Note: $\int _{0}^{\infty }x^{n}e^{-x}dx=n!\!\,$, $0!=1.\!\,$)

## Solution 2a
### Apply Gram Schmidt

To find orthogonal $\{p_{0},p_{1},p_{2}\}\!\,$ use the Gram Schmidt method.
Let $\{v_{0}=1,v_{1}=x,v_{2}=x^{2}\}\!\,$ be a basis of $P_{2}\!\,$.

### Calculate p_0

Choose $p_{0}=v_{0}=1\!\,$.

### Calculate p_1

From Gram Schmidt, we have
$p_{1}=\underbrace {x} _{v_{1}}-{\frac {(v_{1},p_{0})}{(p_{0}\cdot ,p_{0})}}\cdot \underbrace {1} _{p_{0}}\!\,$, where
$(v_{1},p_{0})=\int _{0}^{\infty }e^{-x}\cdot 1\cdot xdx=1\!\,$
$(p_{0},p_{0})=\int _{0}^{\infty }e^{-x}\cdot 1\cdot 1dx=1\!\,$
Therefore $p_{1}=x-1\!\,$

### Calculate p_2

Proceeding with Gram Schmidt, we have
$p_{2}=\underbrace {x^{2}} _{v_{2}}-{\frac {(v_{2},p_{1})}{(p_{1},p_{1})}}\cdot \underbrace {(x-1)} _{p_{1}}-{\frac {(v_{2},p_{0})}{(p_{0},p_{0})}}\cdot \underbrace {1} _{p_{0}}\!\,$ where
${\begin{aligned}(v_{2},p_{1})&=\int _{0}^{\infty }e^{-x}\cdot x^{2}\cdot (x-1)dx\\&=\underbrace {\int _{0}^{\infty }e^{-x}\cdot x^{3}dx} _{3!}-\underbrace {\int _{0}^{\infty }e^{-x}\cdot x^{2}dx} _{2!}\\&=4\end{aligned}}$
${\begin{aligned}(p_{1},p_{1})&=\int _{0}^{\infty }e^{-x}\cdot (x-1)\cdot (x-1)dx\\&=\int _{0}^{\infty }e^{-x}\cdot (x^{2}-2x+1)dx\\&=\underbrace {\int _{0}^{\infty }e^{-x}x^{2}dx} _{2!}-2\underbrace {\int _{0}^{\infty }e^{-x}\cdot xdx} _{1!}+\underbrace {\int _{0}^{\infty }e^{-x}\cdot 1dx} _{0!}\\&=1\end{aligned}}$
$(v_{2},p_{0})=\int _{0}^{\infty }e^{-x}\cdot x^{2}\cdot 1dx=2!=2\!\,$
$(p_{0},p_{0})=\int _{0}^{\infty }e^{-x}\cdot 1\cdot 1dx=1\!\,$
Therefore
$p_{2}=x^{2}-4x+2\!\,$

## Problem 2b

* Derive the 2-point Gaussian formula
* $\int _{0}^{\infty }f(x)e^{-x}dx\approx w_{1}f(x_{1})+w_{2}f(x_{2})\!\,$
* i.e. find the weights and nodes

## Solution 2b
### Find the Nodes

The nodes $x_{1}\!\,$ and $x_{2}\!\,$ are the roots of the $n\!\,$th orthogonal polynomial i.e. $p_{2}(x)=x^{2}-4x+2\!\,$
Applying the quadratic formula yields the roots:
$x_{1}=2-{\sqrt {2}}\!\,$
$x_{2}=2+{\sqrt {2}}\!\,$

### Find the Weights

The approximation is exact for polynomials at most of degree $2n-1=3\!\,$. Hence, we have the following system of equations
$\int _{0}^{\infty }e^{-x}dx=1=w_{1}\cdot \underbrace {1} _{f(x_{1})}+w_{2}\cdot \underbrace {1} _{f(x_{2})}\!\,$
$\int _{0}^{\infty }x\cdot e^{-x}dx=1=w_{1}\cdot \underbrace {(2-{\sqrt {2}})} _{f(x_{1})}+w_{2}\cdot \underbrace {(2+{\sqrt {2}})} _{f(x_{2})}\!\,$
Solving the solving the system of equation by substitution yields the weights:
$w_{1}={\frac {2+{\sqrt {2}}}{4}}\!\,$
$w_{2}={\frac {2-{\sqrt {2}}}{4}}\!\,$

## Problem 3

* Let $A\!\,$ be an $n\times n\!\,$ nonsingular matrix, and consider the linear system $Ax=b\!\,$

## Problem 3a

* Write down the Jacobi iteration for solving $Ax=b\!\,$ in a way that it would be programmed on a computer

## Solution 3a

Choose $x_{0}\!\,$
for $k=0,1,2,\dots \!\,$
    $x^{(i+1)}=D^{-1}(b-(L+U)x^{(i)})\!\,$
    <convergence condition>
end
Where $A=D+L+U\!\,$, $D\!\,$ is diagonal, $L{\mbox{ and }}U\!\,$ are lower and upper triangular, respectively.

## Problem 3b

* Suppose $A\!\,$ has $m\!\,$ non-zero elements with $m<<n^{2}\!\,$. How many operations per iteration does the Jacobi iteration take?

## Solution 3b

The $n\!\,$ diagonal entries of $A\!\,$ are non-zero since otherwise $D^{-1}\!\,$ would not exist.
Therefore $A\!\,$ contains $m-n\!\,$ off-diagonal non-zero entries.
The computation during each iteration is given by
$x^{(i+1)}=\underbrace {D^{-1}(b-\underbrace {(L+U)x^{(i)}} _{m-n{\mbox{ multiplies}}})} _{n{\mbox{ multiplies}}}\!\,$
Therefore there are $(m-n)+n=m\!\,$ multiplies in each iteration.

## Problem 3c

* Assume that $A\!\,$ is strictly diagonally dominant: for $i=1,\ldots ,n,\!\,$
* $|a_{ii}|>\sum _{j=1,j\neq 1}^{n}|a_{ij}|\!\,$
* Show that the Jacobi iteration converges for any guess $x^{(0)}\!\,$. (Hint: You may use Gerschgorin's theorem without proving it.)

## Solution 3c

Let $E:=D^{-1}(L+U)\,\!$.
Theorem 8.2.1 [SB] states that $\rho (E)<1\,\!$ if and only if the Jacobi iteration converges.
Matrix multiplication and the definitions of $D^{-1},L,U\!\,$ gives the explicit entrywise value of $E\!\,$
$e_{ij}={\frac {a_{ij}}{a_{ii}}}\,\!$ for $j\neq i\!\,$ and $e_{ii}=0\,\!$
Then, using Gerschgorin's Theorem and diagonal dominance, we have the result.
    $|\lambda -\underbrace {e_{ii}} _{0}|<\sum _{\underset {j\neq i}{j=1}}^{n}|e_{ij}|=\sum _{\underset {j\neq i}{j=1}}^{n}{\frac {|a_{ij}|}{|a_{ii}|}}<1\!\,$