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