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

## Problem 5a

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

## Solution 5a

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

{\displaystyle {\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.:

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

Then

${\displaystyle g'(x_{k})=1-{\frac {f'(x_{k})^{2}-f'(x_{k})f(x_{k})}{f'(x_{k})^{2}}}\!\,}$

${\displaystyle g'(x_{*})=0\!\,}$

Expanding ${\displaystyle g(x_{k})\!\,}$  around ${\displaystyle x_{*}\!\,}$  gives an expression for the error

${\displaystyle \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 ${\displaystyle g''(x_{*})=0\!\,}$ , then we have better than quadratic convergence.

## Problem 6

 Consider the boundary value problem ${\displaystyle {\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 ${\displaystyle u\in H\!\,}$  such that for all ${\displaystyle v\in H=\{v\in H^{1}[0,1]:v(1)=0\}\!\,}$

${\displaystyle \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 ${\displaystyle u_{h}\!\,}$  to ${\displaystyle u\!\,}$

## Solution 6b

Let ${\displaystyle P=\{x_{i}\}_{i=0}^{N}\!\,}$  be a partition of ${\displaystyle [0,1]\!\,}$ . Choose a an appropriate discrete subspace ${\displaystyle V_{h}\!\,}$  and basis functions ${\displaystyle \{\phi _{i}\}_{i=0}^{N}\!\,}$ . Then

${\displaystyle u_{h}=\sum _{i=0}^{N}u_{hi}\phi _{i}\!\,}$

The coefficients ${\displaystyle u_{hi}\!\,}$  can be found by solving the following system of equations:

For ${\displaystyle j=0,1,\ldots ,N\!\,}$

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

${\displaystyle \|u-u_{h}\|_{1}\leq \inf _{v\in V_{h}}C\|u-v\|_{1}\!\,}$

In particular choose ${\displaystyle v_{I}\!\,}$  to be the linear interpolant of ${\displaystyle u\!\,}$ .

Then,

${\displaystyle \|u-u_{h}\|\leq C\|u''\|_{\infty }h\!\,}$

## Alternative Solution 6c

Let ${\displaystyle \{x_{k}\}_{0}^{n}}$  be a discrete mesh of ${\displaystyle [0,1]}$  with step size ${\displaystyle h}$ . Consider the following integral

${\displaystyle \int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx}$ .

For some ${\displaystyle \xi _{k}\in [x_{k},x_{k+1}]}$ , ${\displaystyle u(x)-u_{h}(x)=u'(\xi _{k})*h}$  as ${\displaystyle u_{h}}$  is just a linear interpolation on this interval. Hence

${\displaystyle \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 ${\displaystyle L_{2}(x_{k},x_{k}+h)}$  norm of the error in the derivatives with ${\displaystyle h^{3}||u''||_{\infty }}$ . With ${\displaystyle n=1/h}$  such intervals we have

${\displaystyle \ ||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 ${\displaystyle \|u-u_{h}\|_{1}^{2}=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\!\,}$

## Solution 6d

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

## Problem 7a

 Suppose the problem is posed on a finite interval ${\displaystyle t_{0}\leq t\leq b\!\,}$  where ${\displaystyle 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 ${\displaystyle {\hat {y_{0}}}\!\,}$  and ${\displaystyle {\hat {y_{1}}}\!\,}$  satisfy ${\displaystyle |y_{0}-{\hat {y_{0}}}|\leq \epsilon ,\quad |y_{1}-{\hat {y_{1}}}|\leq \epsilon \!\,}$  then there exists a constant ${\displaystyle C\!\,}$  independent of ${\displaystyle h\!\,}$  such that ${\displaystyle |y_{n}-{\hat {y_{n}}}|\leq C\epsilon \!\,}$  for ${\displaystyle 0\leq n\leq M\!\,}$

## Solution 7a

{\displaystyle {\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 ${\displaystyle e_{n}\equiv y_{n}-{\hat {y}}_{n}\!\,}$ , and applying the Lipschitz property yields,

{\displaystyle {\begin{aligned}e_{n+1}&\leq e_{n-1}+2hLe_{n}\\&\leq (1+2hL)\max\{e_{n},e_{n-1}\}\end{aligned}}\!\,}

Therefore,

{\displaystyle {\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 ${\displaystyle f(t,y)=\lambda y\!\,}$ . That is, let ${\displaystyle h\!\,}$  be fixed and let ${\displaystyle 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,

${\displaystyle y_{n+1}=y_{n-1}+2h\lambda y_{n}\!\,}$

or

${\displaystyle y_{n+1}-2h\lambda y_{n}-y_{n-1}=0\!\,}$

The solution of this equation is given by

${\displaystyle y_{n}=C_{1}z_{1}^{n}+C_{2}z_{2}^{n}\!\,}$

where ${\displaystyle z_{1},z_{2}\!\,}$  or the roots of the quadratic

${\displaystyle z^{2}-2h\lambda z-1\!\,}$

${\displaystyle z=h\lambda \left(1\pm {\sqrt {1+{\frac {4}{4h^{2}\lambda ^{2}}}}}\right)\!\,}$
If ${\displaystyle \lambda \!\,}$  is a small negative number, than one of the roots will be greater than 1. Hence, ${\displaystyle y_{n}\rightarrow \infty \!\,}$  as ${\displaystyle n\rightarrow \infty \!\,}$  instead of converging to zero since ${\displaystyle y(t)=e^{\lambda t}\!\,}$ .