# Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/Aug04 667
## Problem 5a

* State Newton's method for the approximate solution of
* $f(x)=0\!\,$
* where $f(x)\!\,$ is a real-valued function of the real variable $x\!\,$

## Solution 5a

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\!\,$

## Problem 5b

* State and prove a convergence result for the method.

## Solution 5b

${\begin{aligned}x_{k+1}&=x_{k}-f'(x_{k})^{-1}f(x_{k})\\\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}&=\underbrace {x_{k}-x_{*}} _{e_{k}}-f'(x_{k})^{-1}f(x_{k})\\&=f'(x_{k})^{-1}[f'(x_{k})e_{k}-(f(x_{k})-\underbrace {f(x_{*})} _{0}))\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-e_{k}\int _{0}^{1}f'(sx_{k}+(1-s)x_{*})ds\right]\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-f'(x_{*})e_{k}-e_{k}\int _{0}^{1}(f'(sx_{k}+(1-s)x_{*})-f'(x_{*}))ds\right]\\\|e_{k+1}\|&\leq \|f'(x_{k})^{-1}\|\left[L\|e_{k}\|^{2}+{\frac {L}{2}}\|e_{k}\|^{2}\right]{\mbox{ where L is Lipschitz constant of }}f'\\&=\|f'(x_{k})^{-1}\|{\frac {3}{2}}L\|e_{k}\|^{2}\end{aligned}}\!\,$

## Problem 5c

* What is the typical order of convergence? Are there situations in which the order of convergence is higher? Explain your answers to these questions.

## Solution 5c

The typical order of local convergence is quadratic.
Consider the Newton's method as a fixed point iteration i.e.:
$x_{k+1}=\underbrace {x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}} _{g(x_{k})}\!\,$
Then
$g'(x_{k})=1-{\frac {f'(x_{k})^{2}-f'(x_{k})f(x_{k})}{f'(x_{k})^{2}}}\!\,$
$g'(x_{*})=0\!\,$
Expanding $g(x_{k})\!\,$ around $x_{*}\!\,$ gives an expression for the error
$\underbrace {g(x_{k})} _{x_{k+1}}=\underbrace {g(x_{*})} _{x_{*}}+\underbrace {g'(x_{*})} _{0}e_{k}+{\frac {g''(x_{*})}{2}}e_{k}^{2}+{\frac {g'''(\xi )}{6}}e_{k}^{3}\!\,$
Note that if $g''(x_{*})=0\!\,$, then we have better than quadratic convergence.

## Problem 6

* Consider the boundary value problem
* ${\begin{cases}-u''(x)+u(x)=f(x),0\leq x\leq 1\\u'(0)=2,u(1)=0\end{cases}}\qquad (1)\!\,$

## Problem 6a

* Derive a variational formulation for (1).

## Solution 6a

Find $u\in H\!\,$ such that for all $v\in H=\{v\in H^{1}[0,1]:v(1)=0\}\!\,$
$\underbrace {\int _{0}^{1}u'v'dx+\int _{0}^{1}uv} _{a(u,v)}=\underbrace {\int _{0}^{1}fv-2v(0)} _{f(v)}\!\,$

## Problem 6b

* What do we mean by Finite Element Approximation $u_{h}\!\,$ to $u\!\,$

## Solution 6b

Let $P=\{x_{i}\}_{i=0}^{N}\!\,$ be a partition of $[0,1]\!\,$. Choose a an appropriate discrete subspace $V_{h}\!\,$ and basis functions $\{\phi _{i}\}_{i=0}^{N}\!\,$. Then
$u_{h}=\sum _{i=0}^{N}u_{hi}\phi _{i}\!\,$
The coefficients $u_{hi}\!\,$ can be found by solving the following system of equations:
For $j=0,1,\ldots ,N\!\,$
$\sum _{i=0}^{N}u_{hi}\int _{0}^{1}\phi _{i}'\phi _{j}'dx+\sum _{i=0}^{N}u_{hi}\int _{0}^{1}\phi _{i}\phi _{j}dx=\int _{0}^{1}f\phi _{j}-2\phi _{j}(0)\!\,$

## Problem 6c

* State and prove an estimate for
* $\|u-u_{h}\|_{1}\equiv \left(\int _{0}^{1}|u(x)-u_{h}(x)|^{2}dx+\int _{0}^{1}|u'(x)-u_{h}'(x)|^{2}dx\right)^{\frac {1}{2}}\!\,$

## Solution 6c

Cea's Lemma:
$\|u-u_{h}\|_{1}\leq \inf _{v\in V_{h}}C\|u-v\|_{1}\!\,$
In particular choose $v_{I}\!\,$ to be the linear interpolant of $u\!\,$.
Then,
$\|u-u_{h}\|\leq C\|u''\|_{\infty }h\!\,$

## Alternative Solution 6c

Let $\{x_{k}\}_{0}^{n}$ be a discrete mesh of $[0,1]$ with step size $h$. Consider the following integral
$\int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx$.
For some $\xi _{k}\in [x_{k},x_{k+1}]$, $u(x)-u_{h}(x)=u'(\xi _{k})*h$ as $u_{h}$ is just a linear interpolation on this interval. Hence
$\int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx=\int _{x_{k}}^{x_{k+1}}h^{2}u'(\xi _{k})^{2}dx=h^{3}u'(\xi _{k})^{2}\leq h^{3}||u'||_{\infty }$.
Similarly, we can bound the $L_{2}(x_{k},x_{k}+h)$ norm of the error in the derivatives with $h^{3}||u''||_{\infty }$. With $n=1/h$ such intervals we have
$\ ||u-u_{h}\||^{2}\leq 2nh^{3}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2})=2h^{2}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2}).$

## Problem 6d

* Prove the formula
* $\|u-u_{h}\|_{1}^{2}=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\!\,$

## Solution 6d

${\begin{aligned}\underbrace {a(u-u_{h},u-u_{h})} _{\|u-u_{h}\|_{1}^{2}}+2\underbrace {a(u-u_{h},u_{h})} _{0}&=a(u,u)-2a(u,u_{h})+a(u_{h},u_{h})+2a(u,u_{h})-2a(u_{h},u_{h})\\&=a(u,u)-a(u_{h},u_{h})\\&=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\end{aligned}}\!\,$

## Problem 7

* Consider the initial value problem
* $y'=f(t,y),\quad y(t_{0})=y_{0}\!\,$
* where $f\!\,$ satisfies the Lipschitz condition
* $|f(t,y)-f(t,z)|\leq L|y-z|\!\,$
* for all $t,y,z\!\,$. A numerical method called the midpoint rule for solving this problem is defined by
* $y_{n+1}=y_{n-1}+2hf(t_{n},y_{n})\!\,$
* where $h\!\,$ is a time step and $y_{n}\approx y(t_{n})\!\,$ for $t_{n}=t_{0}+nh\!\,$. Here $y_{0}\!\,$ is given and $y_{1}\!\,$ is presumed to be computed by some other method.

## Problem 7a

* Suppose the problem is posed on a finite interval $t_{0}\leq t\leq b\!\,$ where $h={\frac {(b-t_{0})}{M}}\!\,$. Show directly,i.e., without citing any major results, that the midpoint rule is stable. That is show that if ${\hat {y_{0}}}\!\,$ and ${\hat {y_{1}}}\!\,$ satisfy
* $|y_{0}-{\hat {y_{0}}}|\leq \epsilon ,\quad |y_{1}-{\hat {y_{1}}}|\leq \epsilon \!\,$
* then there exists a constant $C\!\,$ independent of $h\!\,$ such that
* $|y_{n}-{\hat {y_{n}}}|\leq C\epsilon \!\,$
* for $0\leq n\leq M\!\,$

## Solution 7a

${\begin{aligned}y_{n+1}&=y_{n-1}+2hf(t_{n},y_{n})\\{\hat {y}}_{n+1}&={\hat {y}}_{n-1}+2hf(t_{n},{\hat {y}}_{n})\end{aligned}}$
Subtracting both equations, letting $e_{n}\equiv y_{n}-{\hat {y}}_{n}\!\,$, and applying the Lipschitz property yields,
${\begin{aligned}e_{n+1}&\leq e_{n-1}+2hLe_{n}\\&\leq (1+2hL)\max\{e_{n},e_{n-1}\}\end{aligned}}\!\,$
Therefore,
${\begin{aligned}e_{n}&\leq (1+2hL)^{n-1}\epsilon \\&\leq (1+2hL)^{n}\epsilon \\&\leq e^{2Lhn}\epsilon \\&\leq e^{2L(t_{n}-t_{0})}\epsilon \end{aligned}}\!\,$

## Problem 7b

* Suppose instead we are interested in the long term behavior of the midpoint rule applied to a particular example $f(t,y)=\lambda y\!\,$. That is, let $h\!\,$ be fixed and let $n\rightarrow \infty \!\,$ so that the rule is applied over a long time interval. Show that in this case the midpoint rule does not produce an accurate approximation to the solution to the initial value problem.

## Solution 7b

Substituting into the midpoint rule we have,
$y_{n+1}=y_{n-1}+2h\lambda y_{n}\!\,$
or
$y_{n+1}-2h\lambda y_{n}-y_{n-1}=0\!\,$
The solution of this equation is given by
$y_{n}=C_{1}z_{1}^{n}+C_{2}z_{2}^{n}\!\,$
where $z_{1},z_{2}\!\,$ or the roots of the quadratic
$z^{2}-2h\lambda z-1\!\,$
The quadratic formula yields
$z=h\lambda \left(1\pm {\sqrt {1+{\frac {4}{4h^{2}\lambda ^{2}}}}}\right)\!\,$
If $\lambda \!\,$ is a small negative number, than one of the roots will be greater than 1. Hence, $y_{n}\rightarrow \infty \!\,$ as $n\rightarrow \infty \!\,$ instead of converging to zero since $y(t)=e^{\lambda t}\!\,$.