# Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/Jan09 667

## Problem 4

 One wants to solve the equation ${\displaystyle x+\ln x=0\!\,}$ , whose root is ${\displaystyle r\approx 0.5\!\,}$ , using one or more of the following iterative methods (i) ${\displaystyle x_{k+1}=-\ln x_{k}\!\,}$  (ii) ${\displaystyle x_{k+1}=e^{-x_{k}}\!\,}$  (iii) ${\displaystyle x_{k+1}={\frac {x_{k}+e^{-x_{k}}}{2}}\!\,}$

## Problem 4a

 Which of the three methods can be used?

## Solution 4a

Methods {ii} and {iii} are appropriate fixed point iterations for ${\displaystyle x+\ln(x)=0\!\,}$

### {i} is not a fixed point iteration

To be a suitable fixed point iteration, the range of each iteration must be within the domain of the next iteration. In the case of {i}, ${\displaystyle x_{k+1}=-\ln x_{k}\!\,}$  can return values in ${\displaystyle (-\infty ,\infty )\!\,}$ , but can only take x-values in ${\displaystyle (0,\infty )\!\,}$ .

### {ii} and {iii} are fixed point iterations

Let ${\displaystyle f(x):=e^{-x}\!\,}$  and ${\displaystyle g(x):={\frac {x+e^{-x}}{2}}\!\,}$

It is clear that

${\displaystyle f:(-\infty ,\infty )\to (0,\infty )\!\,}$

and

${\displaystyle g:(-\infty ,\infty )\to (0,\infty )\!\,}$

Also notice that given domain ${\displaystyle D=(0,1)}$

${\displaystyle |f(x)-f(y)|\leq |f'(\eta )||x-y|\!\,}$  for some ${\displaystyle \eta \in D\!\,}$

where ${\displaystyle \max _{\eta \in D}|f'(\eta )|=\max _{\eta \in D}|e^{-x}|\leq 1\!\,}$

and

${\displaystyle |g(x)-g(y)|\leq |g'(\eta )||x-y|\!\,}$  for some ${\displaystyle \eta \in D\!\,}$

where ${\displaystyle \max _{\eta \in D}|g'(\eta )|=\max _{\eta \in D}|{\frac {1}{2}}(1-e^{-x})|\approx 0.316060279\!\,}$

That is, f,g are both contractions.

## Problem 4b

 Which method should be used?

## Solution 4b

For the interval (0,1), {iii} is a better fixed point iteration than {ii} since its Lipschitz constant is smaller.

## Problem 4c

 Give an even better iterative formula.

## Solution 4c

Newton's method gives an iterative formula that has quadratic convergence, compared to {iii}'s linear convergence.

## Problem 5

 Consider the boundary value problem ${\displaystyle {\begin{cases}-u''+e^{u}=0&0  Discretize the problem with a finite element method using continuous, piecewise linear functions on an equidistant grid. Quadrature is to be done with the trapezoid rule. Write the method in the form ${\displaystyle AU_{h}+F_{h}(U_{h})=0\!\,}$  where ${\displaystyle U_{h}\in \mathbb {R} ^{m}\!\,}$  denoted by the vector of unknown nodal values of the approximation solutions, ${\displaystyle A\!\,}$  is an ${\displaystyle m\times m\!\,}$  matrix whose elements are independent of the discretization parameter ${\displaystyle h\!\,}$ , and ${\displaystyle F_{h}:\mathbb {R} ^{m}\rightarrow \mathbb {R} ^{m}\!\,}$  is a nonlinear vector-valued function.

## Solution 5

### Finding the weak form

Let ${\displaystyle V=H_{0}^{1}(0,1):=\{v\in H^{1}:v(0)=v(1)=0\}\!\,}$ .

Multiplying by a test function ${\displaystyle v\in V\!\,}$  and integrating by parts we obtain

${\displaystyle \int _{0}^{1}(-u''v)dx=\int _{0}^{1}u'v'dx-\left.u'v\right|_{0}^{1}=\int _{0}^{1}u'v'dx\!\,}$

Then the Variational formulation is: Find ${\displaystyle u\in V\!\,}$  such that

${\displaystyle a(u,v)=\int _{0}^{1}u'v'dx+\int _{0}^{1}e^{u}vdx=l(v)=0\!\,}$  for all ${\displaystyle v\in V\!\,}$

### Define piecewise linear basis functions

Let's consider a partition of the interval ${\displaystyle [0,1]\!\,}$ ,

${\displaystyle {\mathcal {\tau }}_{h}:0=x_{0} .

As our finite element space, we take

${\displaystyle V_{h}=\{v\in V:\left.v\right|_{[x_{i-1},x_{i}]}\in {\mathcal {P}}_{1}([x_{i-1},x_{i}]),i=1,\dots ,m+1,v(0)=v(1)=0\}\!\,}$ .

For our basis of ${\displaystyle V_{h}\!\,}$ , we use the hat functions ${\displaystyle \{\phi _{j}\}_{j=1}^{m}\!\,}$ , i.e., for ${\displaystyle j=1,2,\ldots ,m\!\,}$

${\displaystyle \phi _{j}(x)={\begin{cases}{\frac {x-x_{j-1}}{h}}&{\mbox{for }}x\in [x_{j-1},x_{j}]\\{\frac {x_{j+1}-x}{h}}&{\mbox{for }}x\in [x_{j},x_{j+1}]\\0&{\mbox{otherwise}}\end{cases}}\!\,}$

Therefore,

${\displaystyle \phi _{j}'(x)={\begin{cases}{\frac {1}{h}}&{\mbox{for }}x\in [x_{j-1},x_{j}]\\-{\frac {1}{h}}&{\mbox{for }}x\in [x_{j},x_{j+1}]\\0&{\mbox{otherwise}}\end{cases}}\!\,}$

Thus the discrete formulation reads: Find ${\displaystyle u_{h}\in V_{h}\!\,}$  such that

${\displaystyle a(u_{h},v_{h})=\int _{0}^{1}u_{h}'v_{h}'dx+\int _{0}^{1}e^{u_{h}}v_{h}dx=0,\forall v_{h}\in V_{h}\!\,}$ .

Since ${\displaystyle \{\phi _{j}\}_{j=1}^{m}\!\,}$  is a basis for ${\displaystyle V_{h}\!\,}$ , we have

${\displaystyle u_{h}=\sum _{j=1}^{n}u_{hj}\phi _{j}\!\,}$ .

Then, we obtain the following equivalent discrete problem: Find ${\displaystyle u_{h}=(u_{h1},\ldots ,u_{hm})^{t}\!\,}$  such that

${\displaystyle a(u_{h},\phi _{i})=\sum _{j=1}^{m}u_{hj}\int _{x_{i-1}}^{x_{i+1}}\phi _{j}'\phi _{i}'dx+\int _{x_{i-1}}^{x_{i+1}}e^{\sum _{j=1}^{m}u_{hj}\phi _{j}}\phi _{i}dx=0{\mbox{ for }}i=1,\dots ,m\!\,}$  .

### Rewrite problem in matrix form

The equivalent discrete problem for ${\displaystyle i=1,2,\ldots ,m\!\,}$

${\displaystyle \sum _{j=1}^{m}u_{hj}\int _{x_{i-1}}^{x_{i+1}}\phi _{j}'\phi _{i}'dx+\int _{x_{i-1}}^{x_{i+1}}e^{\sum _{j=1}^{m}u_{hj}\phi _{j}}\phi _{i}dx=0\!\,}$

can be rewritten in matrix form as follows:

${\displaystyle \underbrace {\begin{bmatrix}{\frac {2}{h}}&-{\frac {1}{h}}&&\ldots \\\ddots &\ddots &\ddots &\\&-{\frac {1}{h}}&{\frac {2}{h}}&-{\frac {1}{h}}\\&&-{\frac {1}{h}}&{\frac {2}{h}}\end{bmatrix}} _{A}\underbrace {\begin{bmatrix}u_{h1}\\\vdots \\\vdots \\u_{hm}\end{bmatrix}} _{U_{h}}+\underbrace {h{\begin{bmatrix}e^{u_{h1}}\\e^{u_{h2}}\\\vdots \\e^{u_{hm}}\end{bmatrix}}} _{F_{h}(U_{h})}\!\,}$

The first integral can be computed as follows:

{\displaystyle {\begin{aligned}\int _{0}^{1}\phi _{j}'\phi _{i}'&={\begin{cases}{\frac {2}{h}}&{\mbox{for }}i=j\\-{\frac {1}{h}}&{\mbox{for }}|i-j|=1\\0&{\mbox{otherwise}}\end{cases}}\end{aligned}}\!\,}

The second integral can be approximated using the trapezoidal rule i.e.

{\displaystyle {\begin{aligned}\int _{x_{i-1}}^{x_{i+1}}e^{u_{h}}\phi _{i}(x)&=\int _{x_{i-1}}^{x_{i}}e^{u_{h}}\phi _{i}(x)+\int _{x_{i}}^{x_{i+1}}e^{u_{h}}\phi _{i}(x)\\&\approx \left({\frac {e^{u_{h}(x_{i-1})}\overbrace {\phi _{i}(x_{i-1})} ^{0}+e^{u_{h}(x_{i})}\phi _{i}(x_{i})}{2}}\right)h+\left({\frac {e^{u_{h}(x_{i})}\phi _{i}(x_{i})+e^{u_{h}(x_{i+1})}\overbrace {\phi _{i}(x_{i+1})} ^{0}}{2}}\right)h\\&=he^{u_{h}(x_{i})}\overbrace {\phi _{i}(x_{i})} ^{1}\\&=he^{u_{h}(x_{i})}\\&=he^{\sum _{j=1}^{m}u_{hj}\phi _{j}(x_{i})}\\&=he^{u_{hi}}\end{aligned}}\!\,}

Notice that the boundary conditions impose that ${\displaystyle u_{h0}=u_{h(m+1)}=0\!\,}$ .

## Problem 6

 Determine the local order of accuracy and the stability properties of the two-step scheme ${\displaystyle x_{i+2}-3x_{i+1}+2x_{i}=\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]\!\,}$  as an approximation for the ODE ${\displaystyle x'(t)=f(t,x)\!\,}$ . What is its convergence rate?

## Solution 6

### Local Order of Accuracy

Note that ${\displaystyle x_{i}\approx x(t_{i})\!\,}$ . Also, denote the uniform step size ${\displaystyle \Delta t\!\,}$  as h. Hence,

${\displaystyle t_{i+1}=t_{i}+h\!\,}$

${\displaystyle t_{i+2}=t_{i}+2h\!\,}$

Therefore, the given equation may be written as

${\displaystyle x(t_{i}+2h)-3x(t_{i}+h)+2x(t_{i})\approx h\left[{\frac {13}{12}}x'(t_{i}+2h)-{\frac {5}{3}}x'(t_{i}+h)-{\frac {5}{12}}x'(t_{i})\right]\!\,}$

#### Expand Left Hand Side Using Taylor Expansion

Expanding about ${\displaystyle t_{i}\!\,}$ , we get

${\displaystyle {\begin{array}{|c|c|c|c|c|}{\mbox{Order}}&x(t_{i}+2h)&-3x(t_{i}+h)&2x(t_{i})&\Sigma \\\hline &&&&\\0&x(t_{i})&-3x(t_{i})&2x(t_{i})&0\\&&&&\\1&2x'(t_{i})h&-3x'(t_{i})h&0&-x'(t_{i})h\\&&&&\\2&{\frac {4}{2!}}x''(t_{i})h^{2}&-{\frac {3}{2!}}x''(t_{i})h^{2}&0&{\frac {1}{2}}x''(t_{i})h^{2}\\&&&&\\3&{\frac {8}{3!}}x'''(t_{i})h^{3}&-{\frac {3}{3!}}x'''(t_{i})h^{3}&0&{\frac {5}{6}}x'''(t_{i})h^{3}\\&&&&\\4&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})&0&{\mathcal {O}}(h^{4})\\&&&&\\\hline \end{array}}}$

#### Expand Right Hand Side Using Taylor Expansion

Also expanding about ${\displaystyle t_{i}\!\,}$  gives

${\displaystyle {\begin{array}{|c|c|c|c|c|}{\mbox{Order}}&{\frac {13}{12}}hx'(t_{i}+2h)&-{\frac {5}{3}}hx'(t_{i}+h)&-{\frac {5}{12}}hx'(t_{i})&\Sigma \\\hline &&&&\\0&0&0&0&0\\&&&&\\1&{\frac {13}{12}}hx'(t_{i})&-{\frac {5}{3}}hx'(t_{i})&-{\frac {5}{12}}hx'(t_{i})&-1\cdot hx'(t_{i})\\&&&&\\2&{\frac {13}{12}}(2h)hx''(t_{i})&-{\frac {5}{3}}hhx''(t_{i})&0&{\frac {1}{2}}h^{2}x''(t_{i})\\&&&&\\3&{\frac {13}{12}}(2h)^{2}{\frac {hx'''(t_{i})}{2}}&-{\frac {5}{3}}h^{2}{\frac {hx'''(t_{i})}{2}}&0&{\frac {4}{3}}h^{3}x'''(t_{i})\\&&&&\\4&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})&0&{\mathcal {O}}(h^{4})\\\hline \end{array}}}$

#### Compare Terms to Determine Order

Taking the difference of the left and right hand side Taylor expansions show that the two step equation is of order two since the terms match up to order 2.

${\displaystyle x_{i+2}-3x_{i+1}+2x_{i}-\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]={\mathcal {O}}(\Delta t^{3})\!\,}$

Notice that the order 3 term on the left hand side differs from the order 3 term on the right hand side. (${\displaystyle {\frac {5}{6}}\neq {\frac {4}{3}}\!\,}$ )

### Stability Condition

Our two-step equation is stable if the roots of the equation

${\displaystyle \lambda ^{2}-3\lambda +2=0\!\,}$

Satisfy ${\displaystyle |\lambda _{j}|\leq 1\!\,}$ , and if ${\displaystyle |\lambda _{j}|=1\!\,}$ , then it must be a simple root.

Since ${\displaystyle \lambda ^{2}-3\lambda +2=(\lambda -1)(\lambda -2)=0\!\,}$  yields the roots 1 and 2, the two-step equation is not stable.

### Convergence

A multi-step method is convergent if and only if it is stable and consistent. Our two-step equation is not stable, hence not guaranteed to converge.