Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/August 2004

Problem 1

To compute $\sqrt{2}$, we consider the following Eudoxos iterations: starting with $x_0=y_0=1$, we set $x_{n+1}=x_n+y_n$ followed by $y_{n+1}=x_{n+1}+x_n$. Then $y_n/x_n\to \sqrt{2}$

Problem 1a

Explain the Eudoxos method in terms of the power method.

Solution 1a

The iteration can be represented in matrix formulation as follows:

$\begin{array}{cc}{x}_{n+1}& =x_n+y_n\\ y_{n+1}& =x_{n+1}+x_n=2x_n+y_n\end{array}$

which can be written as

$\underset{A}{\underbrace{\left[\begin{array}{cc}1& 1\\ 2& 1\end{array}\right]}}\left[\begin{array}{c}{x}_n\\ y_n\end{array}\right]=\left[\begin{array}{c}{x}_{n+1}\\ y_{n+1}\end{array}\right]$

Thus the iteration is just the power method since each step is represented by a multiplication by the matrix $A$.

The power method converges to the eigenvector of the largest eigenvalue.

The eigenvalues of $A$ are computed to be $1\pm \sqrt{2}$. Hence the largest eigenvalue is $1+\sqrt{2}$

The corresponding eigenvector is then

$\left[\begin{array}{c}\sqrt{2}\\ 2\end{array}\right]$

Then $y_n/x_n\to \sqrt{2}$ as desired.

Problem 1b

How many iterations are required for an error $|y_n/x_n-\sqrt{2}|\le 10^{-6}$

Solution 1b

Since convergence is linear, 7 steps is required to achieve the error bound.

Problem 2

Let $\{p_n(x)\}$ be a sequence of monic polynomials orthogonal on $[a,b]$ with respect to the positive weight function $w(x)$ ( $p_n$ has degree $n$). Show that $p_n$ satisfy a three term recursion formula of the form $p_n(x)=(x-a_n)p_{n-1}(x)-b_n{p}_{n-2}(x)$ Give expressions for the coefficients $a_n$ and $b_n$

Solution 2a

First notice that $p_n-x{p}_{n-1}\in {\mathrm{\Pi }}^{n-1}$ and therefore we can express it as a linear combination of the monic polynomials of degree $n-1$ or less i.e.

$p_n-x{p}_{n-1}=-a_n{p}_{n-1}-b_n{p}_{n-2}+\sum _{i=0}^{n-3}{\alpha }_i{p}_i(*)$

Taking the inner product of both side of $(*)$ with $p_{n-1}$ yields from the orthogonality of the polynomials:

$-⟨x{p}_{n-1},p_{n-1}⟩=-a_n⟨p_{n-1},p_{n-1}⟩$

Rearranging terms then yields

$a_n=\frac{⟨x{p}_{n-1},p_{n-1}⟩}{⟨p_{n-1},p_{n-1}⟩}$

Similarly, taking the inner product of both side of $(*)$ with $p_{n-2}$ yields from the orthogonality of the polynomials:

$b_n=\frac{⟨x{p}_{n-1},p_{n-2}⟩}{⟨p_{n-2},p_{n-2}⟩}$

Notice that

$\begin{array}{cc}⟨x{p}_{n-1},p_{n-2}⟩& =⟨p_{n-1},x{p}_{n-2}⟩\\ & =⟨p_{n-1},p_{n-1}+\sum _{i=0}^{n-2}{\alpha }_i{p}_i⟩\\ & =⟨p_{n-1},p_{n-1}⟩\end{array}$

Therefore,

$b_n=\frac{⟨p_{n-1},p_{n-1}⟩}{⟨p_{n-2},p_{n-2}⟩}$

Finally, taking inner product of both side of $(*)$ with $p_k,k=0,\dots ,n-3$ yields,

${\alpha }_k=-\frac{⟨x{p}_{n-1},p_k⟩}{⟨p_k,p_k⟩}$

Notice that

$⟨x{p}_{n-1},p_k⟩=⟨p_{n-1},\underset{\in {\mathrm{\Pi }}^{n-2}}{\underbrace{x{p}_k}}⟩=0$

which implies ${\alpha }_k=0$ for $k=0,1\dots ,n-3$

Problem 3a

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}$

Solution 3a

Using Gram Schmidt with inner product defined as

$⟨f,g⟩=\underset{0}{\overset{\mathrm{\infty }}{\int }}w(x)fgdx$

and power basis $1,x,x^2$ as starting vectors, we get

$p_0=1$

$p_1=x-1$

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

Problem 3b

Find the weights and nodes of 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)$ Note: $\underset{0}{\overset{\mathrm{\infty }}{\int }}{x}^n{e}^{-x}dx=n!,0!=1$

Solution 3b

Using test functions $f(x)=1$ and $f(x)=x$ and using the roots of $p_2$ as nodes we find

$x_1=2+\sqrt{2}$

$x_2=2-\sqrt{2}$

$w_1=\frac{2-\sqrt{2}}{4}$

$w_2=\frac{2+\sqrt{2}}{4}$