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

## Problem 1

 To compute ${\displaystyle {\sqrt {2}}\!\,}$ , we consider the following Eudoxos iterations: starting with ${\displaystyle x_{0}=y_{0}=1\!\,}$ , we set ${\displaystyle x_{n+1}=x_{n}+y_{n}\!\,}$  followed by ${\displaystyle y_{n+1}=x_{n+1}+x_{n}\!\,}$ . Then ${\displaystyle 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:

{\displaystyle {\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

${\displaystyle \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 ${\displaystyle A\!\,}$ .

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

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

The corresponding eigenvector is then

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

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

## Problem 1b

 How many iterations are required for an error ${\displaystyle |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 ${\displaystyle \{p_{n}(x)\}\!\,}$  be a sequence of monic polynomials orthogonal on ${\displaystyle [a,b]\!\,}$  with respect to the positive weight function ${\displaystyle w(x)\!\,}$  ( ${\displaystyle p_{n}\!\,}$  has degree ${\displaystyle n\!\,}$ ). Show that ${\displaystyle p_{n}\!\,}$  satisfy a three term recursion formula of the form ${\displaystyle p_{n}(x)=(x-a_{n})p_{n-1}(x)-b_{n}p_{n-2}(x)\!\,}$  Give expressions for the coefficients ${\displaystyle a_{n}\!\,}$  and ${\displaystyle b_{n}\!\,}$

## Solution 2a

First notice that ${\displaystyle 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 ${\displaystyle n-1\!\,}$  or less i.e.

${\displaystyle 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 ${\displaystyle (*)\!\,}$  with ${\displaystyle p_{n-1}\!\,}$  yields from the orthogonality of the polynomials:

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

Rearranging terms then yields

${\displaystyle 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 ${\displaystyle (*)\!\,}$  with ${\displaystyle p_{n-2}\!\,}$  yields from the orthogonality of the polynomials:

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

Notice that

{\displaystyle {\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,

${\displaystyle 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 ${\displaystyle (*)\!\,}$  with ${\displaystyle p_{k},k=0,\ldots ,n-3\!\,}$  yields,

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

Notice that

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

which implies ${\displaystyle \alpha _{k}=0\!\,}$  for ${\displaystyle k=0,1\ldots ,n-3\!\,}$

## Problem 3a

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

## Solution 3a

Using Gram Schmidt with inner product defined as

${\displaystyle \langle f,g\rangle =\int _{0}^{\infty }w(x)fgdx\!\,}$

and power basis ${\displaystyle 1,x,x^{2}\!\,}$  as starting vectors, we get

${\displaystyle p_{0}=1\!\,}$

${\displaystyle p_{1}=x-1\!\,}$

${\displaystyle p_{2}=x^{2}-4x+2\!\,}$

## Problem 3b

 Find the weights and nodes of the 2 point Gaussian formula ${\displaystyle \int _{0}^{\infty }f(x)e^{-x}dx\approx w_{1}f(x_{1})+w_{2}f(x_{2})\!\,}$  Note: ${\displaystyle \int _{0}^{\infty }x^{n}e^{-x}dx=n!,\quad 0!=1\!\,}$

## Solution 3b

Using test functions ${\displaystyle f(x)=1\!\,}$  and ${\displaystyle f(x)=x\!\,}$  and using the roots of ${\displaystyle p_{2}\!\,}$  as nodes we find

${\displaystyle x_{1}=2+{\sqrt {2}}\!\,}$

${\displaystyle x_{2}=2-{\sqrt {2}}\!\,}$

${\displaystyle w_{1}={\frac {2-{\sqrt {2}}}{4}}\!\,}$

${\displaystyle w_{2}={\frac {2+{\sqrt {2}}}{4}}\!\,}$