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

Problem 4

One wants to solve the equation $x+\ln x=0$, whose root is $r\approx 0.5$, using one or more of the following iterative methods (i) $x_{k+1}=-\ln x_k$ (ii) $x_{k+1}=e^{-x_k}$ (iii) $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 $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}, $x_{k+1}=-\ln x_k$ can return values in $(-\mathrm{\infty },\mathrm{\infty })$, but can only take x-values in $(0,\mathrm{\infty })$.

{ii} and {iii} are fixed point iterations

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

It is clear that

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

and

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

Also notice that given domain $D=(0,1)$

$|f(x)-f(y)|\le |f^{\prime }(\eta )||x-y|$ for some $\eta \in D$

where $\underset{\eta \in D}{\max }|f^{\prime }(\eta )|=\underset{\eta \in D}{\max }|e^{-x}|\le 1$

and

$|g(x)-g(y)|\le |g^{\prime }(\eta )||x-y|$ for some $\eta \in D$

where $\underset{\eta \in D}{\max }|g^{\prime }(\eta )|=\underset{\eta \in D}{\max }|\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 $\{\begin{array}{cc}-u^{″}+e^u=0& 0<x<1\\ u(0)=u(1)=0& \end{array}$ 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 $A{U}_h+F_h(U_h)=0$ where $U_h\in {ℝ}^m$ denoted by the vector of unknown nodal values of the approximation solutions, $A$ is an $m\times m$ matrix whose elements are independent of the discretization parameter $h$, and $F_h:{ℝ}^m\to {ℝ}^m$ is a nonlinear vector-valued function.

Solution 5

Finding the weak form

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

Multiplying by a test function $v\in V$ and integrating by parts we obtain

$\underset{0}{\overset{1}{\int }}(-u^{″}v)dx=\underset{0}{\overset{1}{\int }}{u}^{\prime }{v}^{\prime }dx-{u^{\prime }v|}_0^1=\underset{0}{\overset{1}{\int }}{u}^{\prime }{v}^{\prime }dx$

Then the Variational formulation is: Find $u\in V$ such that

$a(u,v)=\underset{0}{\overset{1}{\int }}{u}^{\prime }{v}^{\prime }dx+\underset{0}{\overset{1}{\int }}{e}^{u}vdx=l(v)=0$ for all $v\in V$

Define piecewise linear basis functions

Let's consider a partition of the interval $[0,1]$,

${\mathcal{\tau }}_h:0=x_0<x_1<\dots <x_{m+1}=1$.

As our finite element space, we take

$V_h=\{v\in V:{v|}_{[x_{i-1},x_i]}\in {𝒫}_1([x_{i-1},x_i]),i=1,\dots ,m+1,v(0)=v(1)=0\}$.

For our basis of $V_h$, we use the hat functions $\{{\varphi }_j{\}}_{j=1}^m$, i.e., for $j=1,2,\dots ,m$

${\varphi }_j(x)=\{\begin{array}{cc}\frac{x-x_{j-1}}{h}& \text{for }x\in [x_{j-1},x_j]\\ \frac{x_{j+1}-x}{h}& \text{for }x\in [x_j,x_{j+1}]\\ 0& \text{otherwise}\end{array}$

Therefore,

${{\varphi }_j}^{\prime }(x)=\{\begin{array}{cc}\frac{1}{h}& \text{for }x\in [x_{j-1},x_j]\\ -\frac{1}{h}& \text{for }x\in [x_j,x_{j+1}]\\ 0& \text{otherwise}\end{array}$

Thus the discrete formulation reads: Find $u_h\in V_h$ such that

$a(u_h,v_h)=\underset{0}{\overset{1}{\int }}{u_h}^{\prime }{v_h}^{\prime }dx+\underset{0}{\overset{1}{\int }}{e}^{u_h}{v}_{h}dx=0,\mathrm{\forall }{v}_h\in V_h$.

Since $\{{\varphi }_j{\}}_{j=1}^m$ is a basis for $V_h$, we have

$u_h=\sum _{j=1}^n{u}_{hj}{\varphi }_j$.

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

$a(u_h,{\varphi }_i)=\sum _{j=1}^m{u}_{hj}\underset{x_{i-1}}{\overset{x_{i+1}}{\int }}{{\varphi }_j}^{\prime }{{\varphi }_i}^{\prime }dx+\underset{x_{i-1}}{\overset{x_{i+1}}{\int }}{e}^{\sum _{j=1}^m{u}_{hj}{\varphi }_j}{\varphi }_{i}dx=0\text{ for }i=1,\dots ,m$ .

Rewrite problem in matrix form

The equivalent discrete problem for $i=1,2,\dots ,m$

$\sum _{j=1}^m{u}_{hj}\underset{x_{i-1}}{\overset{x_{i+1}}{\int }}{{\varphi }_j}^{\prime }{{\varphi }_i}^{\prime }dx+\underset{x_{i-1}}{\overset{x_{i+1}}{\int }}{e}^{\sum _{j=1}^m{u}_{hj}{\varphi }_j}{\varphi }_{i}dx=0$

can be rewritten in matrix form as follows:

$\underset{A}{\underbrace{\left[\begin{array}{cccc}\frac{2}{h}& -\frac{1}{h}& & \dots \\ \ddots & \ddots & \ddots & \\ & -\frac{1}{h}& \frac{2}{h}& -\frac{1}{h}\\ & & -\frac{1}{h}& \frac{2}{h}\end{array}\right]}}\underset{U_h}{\underbrace{\left[\begin{array}{c}{u}_{h1}\\ ⋮\\ ⋮\\ u_{hm}\end{array}\right]}}+\underset{F_h(U_h)}{\underbrace{h\left[\begin{array}{c}{e}^{u_{h1}}\\ e^{u_{h2}}\\ ⋮\\ e^{u_{hm}}\end{array}\right]}}$

The first integral can be computed as follows:

$\begin{array}{cc}\underset{0}{\overset{1}{\int }}{{\varphi }_j}^{\prime }{{\varphi }_i}^{\prime }& =\{\begin{array}{cc}\frac{2}{h}& \text{for }i=j\\ -\frac{1}{h}& \text{for }|i-j|=1\\ 0& \text{otherwise}\end{array}\end{array}$

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

$\begin{array}{cc}\underset{x_{i-1}}{\overset{x_{i+1}}{\int }}{e}^{u_h}{\varphi }_i(x)& =\underset{x_{i-1}}{\overset{x_i}{\int }}{e}^{u_h}{\varphi }_i(x)+\underset{x_i}{\overset{x_{i+1}}{\int }}{e}^{u_h}{\varphi }_i(x)\\ & \approx \left(\frac{e^{u_h(x_{i-1})}\stackrel{0}{\overbrace{{\varphi }_i(x_{i-1})}}+e^{u_h(x_i)}{\varphi }_i(x_i)}{2}\right)h+\left(\frac{e^{u_h(x_i)}{\varphi }_i(x_i)+e^{u_h(x_{i+1})}\stackrel{0}{\overbrace{{\varphi }_i(x_{i+1})}}}{2}\right)h\\ & =h{e}^{u_h(x_i)}\stackrel{1}{\overbrace{{\varphi }_i(x_i)}}\\ & =h{e}^{u_h(x_i)}\\ & =h{e}^{\sum _{j=1}^m{u}_{hj}{\varphi }_j(x_i)}\\ & =h{e}^{u_{hi}}\end{array}$

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

Problem 6

Determine the local order of accuracy and the stability properties of the two-step scheme $x_{i+2}-3x_{i+1}+2x_i=\mathrm{\Delta }t\cdot [\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)]$ as an approximation for the ODE $x^{\prime }(t)=f(t,x)$. What is its convergence rate?

Solution 6

Local Order of Accuracy

Note that $x_i\approx x(t_i)$. Also, denote the uniform step size $\mathrm{\Delta }t$ as h. Hence,

$t_{i+1}=t_i+h$

$t_{i+2}=t_i+2h$

Therefore, the given equation may be written as

$x(t_i+2h)-3x(t_i+h)+2x(t_i)\approx h[\frac{13}{12}{x}^{\prime }(t_i+2h)-\frac{5}{3}{x}^{\prime }(t_i+h)-\frac{5}{12}{x}^{\prime }(t_i)]$

Expand Left Hand Side Using Taylor Expansion

Expanding about $t_i$, we get

$\begin{array}{ccccc}\text{Order}& x(t_i+2h)& -3x(t_i+h)& 2x(t_i)& \mathrm{\Sigma }\\ & & & & \\ 0& x(t_i)& -3x(t_i)& 2x(t_i)& 0\\ & & & & \\ 1& 2x^{\prime }(t_i)h& -3x^{\prime }(t_i)h& 0& -x^{\prime }(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& 𝒪(h^4)& 𝒪(h^4)& 0& 𝒪(h^4)\\ & & & & \end{array}$

Expand Right Hand Side Using Taylor Expansion

Also expanding about $t_i$ gives

$\begin{array}{ccccc}\text{Order}& \frac{13}{12}h{x}^{\prime }(t_i+2h)& -\frac{5}{3}h{x}^{\prime }(t_i+h)& -\frac{5}{12}h{x}^{\prime }(t_i)& \mathrm{\Sigma }\\ & & & & \\ 0& 0& 0& 0& 0\\ & & & & \\ 1& \frac{13}{12}h{x}^{\prime }(t_i)& -\frac{5}{3}h{x}^{\prime }(t_i)& -\frac{5}{12}h{x}^{\prime }(t_i)& -1\cdot h{x}^{\prime }(t_i)\\ & & & & \\ 2& \frac{13}{12}(2h)h{x}^{″}(t_i)& -\frac{5}{3}hh{x}^{″}(t_i)& 0& \frac{1}{2}{h}^2{x}^{″}(t_i)\\ & & & & \\ 3& \frac{13}{12}(2h{)}^2\frac{h{x}^{‴}(t_i)}{2}& -\frac{5}{3}{h}^2\frac{h{x}^{‴}(t_i)}{2}& 0& \frac{4}{3}{h}^3{x}^{‴}(t_i)\\ & & & & \\ 4& 𝒪(h^4)& 𝒪(h^4)& 0& 𝒪(h^4)\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.

$x_{i+2}-3x_{i+1}+2x_i-\mathrm{\Delta }t\cdot [\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)]=𝒪(\mathrm{\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. ($\frac{5}{6}\ne \frac{4}{3}$)

Stability Condition

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

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

Satisfy $|{\lambda }_j|\le 1$, and if $|{\lambda }_j|=1$, then it must be a simple root.

Since ${\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.