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

## Problem 4

 Let ${\displaystyle \mathbf {f:} \mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}\!\,}$ , suppose ${\displaystyle \mathbf {f} (x^{*})=0\!\,}$  and assume ${\displaystyle \mathbf {f'} (x^{*})\!\,}$  is nonsingular . Consider the following iteration ${\displaystyle x_{k+1}=x_{k}-B_{k}^{-1}\mathbf {f} (x_{k}),\qquad (k\geq 0)\!\,}$

## Problem 4a

 Derive the following error equation for ${\displaystyle e_{k+1}=x_{k+1}-x^{*}\!\,}$  ${\displaystyle 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

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

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

{\displaystyle {\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 ${\displaystyle 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 ${\displaystyle B\!\,}$  is invertible, ${\displaystyle \|B-f'(x_{*})\|\!\,}$  is bounded, and ${\displaystyle f'\!\,}$  is Lipschitz.

{\displaystyle {\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 ${\displaystyle \|B_{k}-\mathbf {f'} (x_{k})\|\!\,}$  for the convergence to be superlinear. What choice of ${\displaystyle B_{k}\!\,}$  corresponds to the Newton method and what rate of convergence do you expect?

## Solution 4c

### Super linear convergence

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

### Find condition for super linear convergence

From part(b)

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

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

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

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

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

## Problem 5

 Let ${\displaystyle f(t,y)\!\,}$  be uniformly Lipschitz with respect to ${\displaystyle y}$ . Let ${\displaystyle y(t)\!\,}$  be the solution to the initial value problem : ${\displaystyle y'=f(t,y),\;y(0)=y_{0}\!\,}$ . Consider the trapezoid method ${\displaystyle (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 ${\displaystyle h\!\,}$  that ensures (1) can be solved uniquely for ${\displaystyle y_{i+1}\!\,}$ .

## Solution 5a

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

${\displaystyle 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 ${\displaystyle \left|{\frac {\partial g(y_{i+1})}{\partial y_{i+1}}}\right|<1\!\,}$

which implies

${\displaystyle 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 ${\displaystyle f\!\,}$  needed for this estimate.

## Solution 5b

Re-writing (1) and replacing ${\displaystyle 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:

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

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

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

## Problem 5c

 Prove a global error estimate for (1)

## Problem 6

 Consider the 2-point boundary value problem ${\displaystyle (2)\qquad -au''+bu=f(x),\quad 0 , with ${\displaystyle a,b>0\!\,}$  constants and ${\displaystyle f\in C[0,1]\!\,}$ . Let ${\displaystyle {\mathcal {P}}=\{x_{i}\}_{i=0}^{n+1}\!\,}$  be a uniform partition of [0,1] with meshsize ${\displaystyle h\!\,}$ .

## Problem 6a

 Use centered finite differences to discretize (2). Write the system as ${\displaystyle A\mathbf {U} =\mathbf {F} \!\,}$  and identify ${\displaystyle 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

${\displaystyle 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 ${\displaystyle u(0)=u_{0},u(1)=u_{1}\!\,}$  into the equations for ${\displaystyle U_{1}\!\,}$  and ${\displaystyle U_{n}\!\,}$  respectively.

We then have the system

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

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

## Problem 6b

 Define truncation error and derive a bound for this method in terms of ${\displaystyle h\!\,}$ . State without proof an error estimate of the form ${\displaystyle \max _{1\leq i\leq n}|u(x_{i})-U_{i}|\leq Ch^{s}\!\,}$  and specify the order s.

## Solution 6b

### Local Truncation Error

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

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

### Derive Bound for Max Error

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

Then

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

Subtracting the two last equations gives

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

Hence,

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

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

## Problem 6c

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

## Solution 6c

Note that ${\displaystyle A\!\,}$  is a ${\displaystyle M\!\,}$  matrix and hence the discrete maximum principle applies. (See January 05 667 test for definition of ${\displaystyle M\!\,}$  matrix)

### Discrete Maximum Principle

${\displaystyle AU=F\!\,}$

If ${\displaystyle F\leq 0\!\,}$ , then ${\displaystyle U\leq 0\!\,}$ .

Specifically let ${\displaystyle F=f_{1}-f_{2}\!\,}$ , then ${\displaystyle U_{1}-U_{2}\leq 0\!\,}$  which implies ${\displaystyle U_{1}\leq U_{2}\!\,}$