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}\rightarrow {\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{aligned}x_{n+1}&=x_{n}+y_{n}\\y_{n+1}&=x_{n+1}+x_{n}=2x_{n}+y_{n}\end{aligned}}\!\,$

which can be written as

$\underbrace {\begin{bmatrix}1&1\\2&1\end{bmatrix}} _{A}{\begin{bmatrix}x_{n}\\y_{n}\end{bmatrix}}={\begin{bmatrix}x_{n+1}\\y_{n+1}\end{bmatrix}}\!\,$

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

${\begin{bmatrix}{\sqrt {2}}\\2\end{bmatrix}}\!\,$

Then $y_{n}/x_{n}\rightarrow {\sqrt {2}}\!\,$ as desired.

Problem 1b

How many iterations are required for an error $|y_{n}/x_{n}-{\sqrt {2}}|\leq 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}-xp_{n-1}\in \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}-xp_{n-1}=-a_{n}p_{n-1}-b_{n}p_{n-2}+\sum _{i=0}^{n-3}\alpha _{i}p_{i}\qquad (*)\!\,$

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

$-\langle xp_{n-1},p_{n-1}\rangle =-a_{n}\langle p_{n-1},p_{n-1}\rangle \!\,$

Rearranging terms then yields

$a_{n}={\frac {\langle xp_{n-1},p_{n-1}\rangle }{\langle p_{n-1},p_{n-1}\rangle }}\!\,$

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

$b_{n}={\frac {\langle xp_{n-1},p_{n-2}\rangle }{\langle p_{n-2},p_{n-2}\rangle }}\!\,$

Notice that

${\begin{aligned}\langle xp_{n-1},p_{n-2}\rangle &=\langle p_{n-1},xp_{n-2}\rangle \\&=\langle p_{n-1},p_{n-1}+\sum _{i=0}^{n-2}\alpha _{i}p_{i}\rangle \\&=\langle p_{n-1},p_{n-1}\rangle \end{aligned}}\!\,$

Therefore,

$b_{n}={\frac {\langle p_{n-1},p_{n-1}\rangle }{\langle p_{n-2},p_{n-2}\rangle }}\!\,$

Finally, taking inner product of both side of $(*)\!\,$ with $p_{k},k=0,\ldots ,n-3\!\,$ yields,

$\alpha _{k}=-{\frac {\langle xp_{n-1},p_{k}\rangle }{\langle p_{k},p_{k}\rangle }}\!\,$

Notice that

$\langle xp_{n-1},p_{k}\rangle =\langle p_{n-1},\underbrace {xp_{k}} _{\in \Pi ^{n-2}}\rangle =0\!\,$

which implies $\alpha _{k}=0\!\,$ for $k=0,1\ldots ,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,\infty )\!\,$ with respect to the weight function $w(x)=e^{-x}\!\,$

Solution 3a

Using Gram Schmidt with inner product defined as

$\langle f,g\rangle =\int _{0}^{\infty }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 $\int _{0}^{\infty }f(x)e^{-x}dx\approx w_{1}f(x_{1})+w_{2}f(x_{2})\!\,$ Note: $\int _{0}^{\infty }x^{n}e^{-x}dx=n!,\quad 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}}\!\,$