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

Problem 4

Let $\mathbf {f:} \mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}\!\,$ , suppose $\mathbf {f} (x^{*})=0\!\,$ and assume $\mathbf {f'} (x^{*})\!\,$ is nonsingular . Consider the following iteration

$x_{k+1}=x_{k}-B_{k}^{-1}\mathbf {f} (x_{k}),\qquad (k\geq 0)\!\,$

Problem 4a

Derive the following error equation for $e_{k+1}=x_{k+1}-x^{*}\!\,$

$e_{k+1}=B_{k}^{-1}\left((B_{k}-\mathbf {f'} (x^{*}))e_{k}-\int _{0}^{1}(\mathbf {f'} (sx_{k}+(1-s)x^{*})-\mathbf {f'} (x^{*}))e_{k}\,ds\right)\!\,$

Solution 4a

Note the following identity

F(x)-F(y)=\int _{0}^{1}F'(sx+(1-s)y)(x-y)ds\qquad (*)\!\,

The error $e_{k+1}\!\,$ is given by

${\begin{aligned}e_{k+1}&=x_{k+1}-x_{*}\\&=\underbrace {x_{k}-x_{*}} _{e_{k}}-B_{k}^{-1}f(x_{k})\\&=e_{k}-B_{k}^{-1}(f(x_{k})-\underbrace {f(x_{*})} _{0})\\&=B_{k}^{-1}\left\{(B_{k}-f'(x_{*}))e_{k}-\int _{0}^{1}\left[f'(sx_{k}+(1-s)x_{*})-f'(x_{*})\right]e_{k}ds\right\}\\\end{aligned}}$

Problem 4b

Let $B_{k}=B\in \mathbb {R} ^{n\times n}\!\,$ be a fixed matrix. Find conditions on B that guarentee local convergence. What rate of convergence do you expect and why?

Solution 4b

Assume $B\!\,$ is invertible, $\|B-f'(x_{*})\|\!\,$ is bounded, and $f'\!\,$ is Lipschitz.

${\begin{aligned}\|e_{k+1}\|&\leq \|B^{-1}\|\left\{\|B-f'(x_{*})\|\|e_{k}\|-\int _{0}^{1}\underbrace {\|f'(sx_{k}+(1-s)x_{*})-f'(x_{*})\|} _{\leq L\|sx_{k}+(1-s)x_{*}-x_{*}\|}\|e_{k}\|ds\right\}\\&\leq \|B^{-1}\|\left\{\|B-f'(x_{*})\|\|e_{k}\|-\int _{0}^{1}L\|e_{k}\|^{2}sds\right\}\\&\leq \|B^{-1}\|\left\{\|B-f'(x_{*})\|-{\frac {L}{2}}\|e_{k}\|\right\}\|e_{k}\|\end{aligned}}$

This implies local superlinear convergence.

Problem 4c

Find sufficient conditions on $\|B_{k}-\mathbf {f'} (x_{k})\|\!\,$ for the convergence to be superlinear. What choice of $B_{k}\!\,$ corresponds to the Newton method and what rate of convergence do you expect?

Solution 4c

Super linear convergence

${\frac {\|e_{k+1}\|}{\|e_{k}\|}}\rightarrow 0\!\,$ as $k\rightarrow \infty \!\,$

Find condition for super linear convergence

From part(b)

${\frac {\|e_{k+1}\|}{\|e_{k}\|}}\leq \|B_{k}^{-1}\|\{\|B_{k}-f'(x_{*})\|-{\frac {L}{2}}\|e_{k}\|\}\!\,$

Since $\|e_{k}\|\rightarrow 0{\mbox{ as }}k\rightarrow \infty \!\,$ , if

$\|B_{k}-f'(x_{*})\|\rightarrow 0\!\,$

as $k\rightarrow 0\!\,$ , we have super linear convergence i.e.

$B_{k}=f'(x_{k}){\mbox{ Newton Iteration form}}\!\,$

Problem 5

Let $f(t,y)\!\,$ be uniformly Lipschitz with respect to $y$ . Let $y(t)\!\,$ be the solution to the initial value problem : $y'=f(t,y),\;y(0)=y_{0}\!\,$ . Consider the trapezoid method

$(1)\qquad y_{i+1}=y_{i}+{h \over 2}\left(f(t_{i},y_{i})+f(t_{i+1},y_{i+1})\right),\qquad (i\geq 0)\!\,$ .

Problem 5a

Find a condition on the stepsize $h\!\,$ that ensures (1) can be solved uniquely for $y_{i+1}\!\,$ .

Solution 5a

The implicit method can be viewed as a fix point iteration:

$y_{i+1}=\underbrace {y_{i}+{\frac {h}{2}}(f(t_{i},y_{i})+f(t_{i+1},y_{i+1}))} _{g(y_{i+1})}\!\,$

We want $\left|{\frac {\partial g(y_{i+1})}{\partial y_{i+1}}}\right|<1\!\,$

which implies

$h<{\frac {2}{\left|{\frac {\partial f(t_{i+1},y_{i+1})}{\partial y_{i+1}}}\right|}}\!\,$

Problem 5b

Define a local truncation error and estimate it. Examine the additional regularity of $f\!\,$ needed for this estimate.

Solution 5b

Re-writing (1) and replacing $y_{k}{\mbox{ with }}y(t_{k}){\mbox{ and }}f(t_{k},y_{k}){\mbox{ with }}y'(t_{k})\!\,$ we have a formula for consistency of order p:

$y(t_{i+1})-y(t_{i})-{h \over 2}y'(t_{i})-{h \over 2}y(t_{i+1})={\mathcal {O}}(h^{p+1})\!\,$

For uniform stepsize h

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

Expanding in Taylor Series about $t_{i}\!\,$ gives

Problem 5c

Prove a global error estimate for (1)

Solution 5c

Problem 6

Consider the 2-point boundary value problem

$(2)\qquad -au''+bu=f(x),\quad 0<x<1,\qquad u(0)=u_{0},\,u(1)=u_{1}\!\,$ ,

with $a,b>0\!\,$ constants and $f\in C[0,1]\!\,$ . Let ${\mathcal {P}}=\{x_{i}\}_{i=0}^{n+1}\!\,$ be a uniform partition of [0,1] with meshsize $h\!\,$ .

Problem 6a

Use centered finite differences to discretize (2). Write the system as

$A\mathbf {U} =\mathbf {F} \!\,$

and identify $A\in \mathbb {R} ^{n\times n}{\mbox{ and }}\mathbf {U} ,\mathbf {F} \in \mathbb {R} ^{n}\!\,$ . Prove that A is nonsingular.

Solution 6a

Using Taylor Expansions, we can approximate the second derivative as follows

$u''(x)={\frac {u(x+h)-2u(x)+u(x-h)}{h^{2}}}\!\,$

We can eliminate two equations from the n+2 equations by substituting the initial conditions $u(0)=u_{0},u(1)=u_{1}\!\,$ into the equations for $U_{1}\!\,$ and $U_{n}\!\,$ respectively.

We then have the system

$\underbrace {\begin{bmatrix}{\frac {2a}{h^{2}}}+b&-{\frac {a}{h^{2}}}&&&&&\\-{\frac {a}{h^{2}}}&{\frac {2a}{h^{2}}}+b&-{\frac {a}{h^{2}}}&&&&\\&-{\frac {a}{h^{2}}}&{\frac {2a}{h^{2}}}+b&-{\frac {a}{h^{2}}}&&\\&&\ddots &\ddots &\ddots &\\&&&&-{\frac {a}{h^{2}}}&{\frac {2a}{h^{2}}}+b\end{bmatrix}} _{A}\underbrace {\begin{bmatrix}U_{1}\\U_{2}\\U_{3}\\\vdots \\U_{n}\end{bmatrix}} _{U}=\underbrace {\begin{bmatrix}f(x_{1})+{\frac {a}{h^{2}}}u_{0}\\f(x_{2})\\f(x_{3})\\\vdots \\f(x_{n})+{\frac {a}{h^{2}}}u_{1}\end{bmatrix}} _{F}\!\,$

$A\!\,$ is nonsingular since it is diagonally dominant.

Problem 6b

Define truncation error and derive a bound for this method in terms of $h\!\,$ . State without proof an error estimate of the form

$\max _{1\leq i\leq n}|u(x_{i})-U_{i}|\leq Ch^{s}\!\,$

and specify the order s.

Solution 6b

Local Truncation Error

$LTE={\frac {u(x_{i}+h)+u(x_{i}-h)-2u(x_{i})}{h^{2}}}-u''(x_{i})={\frac {u^{(4)}(\xi )}{12}}h^{2}\!\,$

Bound for Local Truncation Error

${\frac {1}{12}}\|u^{(4)}\|_{\infty }h^{2}\!\,$

Derive Bound for Max Error

Let $L=-a\partial _{xx}+b\!\,$ , $L_{h}=A\!\,$ , and $R_{h}\!\,$ is the local truncation error.

Then

${\begin{aligned}Lu&=f\\L_{h}u&=f+R_{h}\\L_{h}U&=f\end{aligned}}\!\,$

Subtracting the two last equations gives

$L_{h}(u-U)=R_{h}\!\,$

Hence,

$\|u-U\|_{\infty }\leq \|L_{h}^{-1}\|\|R_{h}\|\!\,$

$\|u-U\|_{\infty }\leq Ch^{2}\!\,$ , that is the error has order 2.

Problem 6c

Prove the following discrete monotonicity property: If $\mathbf {U} _{i}\!\,$ is the solution corresponding to a forcing $f_{i}\!\,$ , for $i=1,2\!\,$ , and $f_{1}\leq f_{2}\!\,$ then $\mathbf {U} _{1}\leq \mathbf {U} _{2}\!\,$ componentwise.