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 $\underset{x_0\le x\le x_2}{\max }|f^{‴}(x)|=K$.

Problem 1a

Show that $\underset{x_0\le x\le x_2}{\max }|f^{″}(x)-q^{″}(x)|=C{h}^{\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.

$(\mathrm{△})f[x_0,\dots ,x_n]=\frac{f^{(n)}(\xi )}{(n)!}\xi \in I[x_0,\dots ,x_n]$

Hence,

$f[x_0,x_1,x_2]=\frac{f^{\prime \prime }(\eta )}{2!}\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{array}{cc}{f}^{\prime \prime }(x)-f^{\prime \prime }(\eta )& =\underset{\eta }{\overset{x}{\int }}{f}^{\prime \prime \prime }(t)dt\\ & \le \Vert f^{\prime \prime \prime }(x){\Vert }_{\mathrm{\infty }}|x-\eta |\\ & \le 2h\Vert f^{\prime \prime \prime }{\Vert }_{\mathrm{\infty }}\end{array}$

Therefore,

$\underset{x\in [x_0,x_2]}{\max }|f^{\prime \prime }(x)-q^{\prime \prime }(x)|\le \underset{C}{\underbrace{2\Vert f^{\prime \prime \prime }(x){\Vert }_{\mathrm{\infty }}}}{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)|\le C^{\prime }{h}^{\beta }$ where $\beta >\alpha$. What is $C^{\prime }$ 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 $(\mathrm{△})$ 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{array}{cc}{f}^{″}(x_1)-f^{″}(\eta )& =\underset{\eta }{\overset{x_1}{\int }}{f}^{(3)}(x)dx\\ & =\underset{\eta }{\overset{x_1}{\int }}{f}^{(3)}(x)-\underset{0}{\underbrace{f^{(3)}({\eta }^{*})}}dx\\ & =\underset{\eta }{\overset{x_1}{\int }}\underset{\eta *}{\overset{x}{\int }}{f}^{(4)}(t)dtdx\\ & \le \Vert f^{(4)}{\Vert }_{\mathrm{\infty }}|x-{\eta }^{*}||x_1-\eta |\\ & \le \underset{C^{\prime }}{\underbrace{2\Vert f^{(4)}{\Vert }_{\mathrm{\infty }}}}{h}^2,\end{array}$

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,\mathrm{\infty })$ with respect to the weight function $w(x)=e^{-x}$. (Note: $\underset{0}{\overset{\mathrm{\infty }}{\int }}{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=\underset{v_1}{\underbrace{x}}-\frac{(v_1,p_0)}{(p_0\cdot ,p_0)}\cdot \underset{p_0}{\underbrace{1}}$, where

$(v_1,p_0)=\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot 1\cdot xdx=1$

$(p_0,p_0)=\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot 1\cdot 1dx=1$

Therefore $p_1=x-1$

Calculate p_2

Proceeding with Gram Schmidt, we have

$p_2=\underset{v_2}{\underbrace{x^2}}-\frac{(v_2,p_1)}{(p_1,p_1)}\cdot \underset{p_1}{\underbrace{(x-1)}}-\frac{(v_2,p_0)}{(p_0,p_0)}\cdot \underset{p_0}{\underbrace{1}}$ where

$\begin{array}{cc}(v_2,p_1)& =\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot x^2\cdot (x-1)dx\\ & =\underset{3!}{\underbrace{\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot x^{3}dx}}-\underset{2!}{\underbrace{\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot x^{2}dx}}\\ & =4\end{array}$

$\begin{array}{cc}(p_1,p_1)& =\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot (x-1)\cdot (x-1)dx\\ & =\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot (x^2-2x+1)dx\\ & =\underset{2!}{\underbrace{\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}{x}^{2}dx}}-2\underset{1!}{\underbrace{\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot xdx}}+\underset{0!}{\underbrace{\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot 1dx}}\\ & =1\end{array}$

$(v_2,p_0)=\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot x^2\cdot 1dx=2!=2$

$(p_0,p_0)=\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}\cdot 1\cdot 1dx=1$

Therefore

$p_2=x^2-4x+2$

Problem 2b

Derive the 2-point Gaussian formula $\underset{0}{\overset{\mathrm{\infty }}{\int }}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

$\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-x}dx=1=w_1\cdot \underset{f(x_1)}{\underbrace{1}}+w_2\cdot \underset{f(x_2)}{\underbrace{1}}$

$\underset{0}{\overset{\mathrm{\infty }}{\int }}x\cdot e^{-x}dx=1=w_1\cdot \underset{f(x_1)}{\underbrace{(2-\sqrt{2})}}+w_2\cdot \underset{f(x_2)}{\underbrace{(2+\sqrt{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\text{ 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)}=\underset{n\text{ multiplies}}{\underbrace{D^{-1}(b-\underset{m-n\text{ multiplies}}{\underbrace{(L+U)x^{(i)}}})}}$

Therefore there are $(m-n)+n=m$ multiplies in each iteration.

Problem 3c

Assume that $A$ is strictly diagonally dominant: for $i=1,\dots ,n,$ $|a_{ii}|>\sum _{j=1,j\ne 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\ne i$ and $e_{ii}=0$

Then, using Gerschgorin's Theorem and diagonal dominance, we have the result.

$|\lambda -\underset{0}{\underbrace{e_{ii}}}|<\sum _{\underset{j\ne i}{j=1}}^n|e_{ij}|=\sum _{\underset{j\ne i}{j=1}}^n\frac{|a_{ij}|}{|a_{ii}|}<1$