# 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)

## 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.

## Solution 6c

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

### Discrete Maximum Principle

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