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

* Describe Newton's method for finding a root of a smooth function $f:R\rightarrow R\!\,$

## Solution 4a

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

## Problem 4b

* Assume that $f:R\rightarrow R\!\,$ is a smooth function, satisfies
* $f'(x)>0,\quad f''(x)>0,\quad {\mbox{ for all }}x\in R\!\,$
* and has a root $x^{*}\!\,$. Draw a geometric picture illustrating the convergence of the method and give an analytic proof that Newton's method converges to $x^{*}\!\,$ for any initial guess $x_{0}\in R\!\,$

## Solution 4b

From the picture, notice that if $x_{k}<x_{*}\!\,$, then after one step $x_{k+1}\!\,$ will be greater than $x_{*}\!\,$. This is because from hypothesis, the function is always increasing and concave up.
Then without loss of generality assume $x_{k}>x_{*}\!\,$.
Subtracting $x_{*}\!\,$ from both sides of Newton's method gives an expression for the relationship between consecutive errors.
$\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}=\underbrace {x_{k}-x_{*}} _{e_{k}}-{\frac {f(x_{k})}{f'(x_{k})}}\qquad (*)\!\,$
Expanding $f(x_{k})\!\,$ around $f(x_{*})\!\,$ using Taylor expansion gives
$f(x_{k})=\underbrace {f(x_{*})} _{0}+f'(\xi )\underbrace {(x_{k}-x_{*})} _{e_{k}}\!\,$
where $\xi \in [x_{*},x_{k}]\!\,$
Substituting this expression into (*), we have
$e_{k+1}=(1-\underbrace {\frac {f'(\xi )}{f'(x_{k})}} _{M})e_{k}\!\,$
Since $f'(x)>0\!\,$ and is always increasing (from hypothesis), $M\!\,$ is a positive number less than 1. Therefore the error decreases as $k\!\,$ increases which implies the method always converges.

## Problem 5

* The goal of this problem is to solve the boundary value problem
* $-u''=f{\mbox{ on }}(0,1),\quad u(0)=0,u(1)=0\!\,$
* in a suitable finite element space.

## Problem 5a

* For $N\in \mathbb {N} \!\,$, let $x_{i}=i/N,i=0,\ldots ,N\!\,$. Define a suitable $N-1\!\,$ dimensional subspace $V_{N}\!\,$ in $H_{0}^{1}\!\,$ associated with the points $x_{i}\!\,$. Let $\phi _{1},\ldots ,\phi _{N-1}\!\,$ be any basis in $V_{N}\!\,$. Explain how you can determine the coefficients $u_{i}\!\,$ in the representation element solution
* $u_{N}=\sum _{i=1}^{N-1}u_{i}\phi _{i}\!\,$
* by solving a linear system. Prove that there exists a unique solution

## Solution 5a
### Define Suitable Subspace

$V_{N}=\{v\in H_{0}^{1}[0,1]:v{\mbox{ piecewise linear}}\}\!\,$
which has a basis the hat functions $\{\phi _{i}\}_{i=1}^{N-1}\!\,$ defined as follows:
$\phi _{i}(x)={\begin{cases}{\frac {x-x_{i-1}}{h}}&{\mbox{ for }}x\in [x_{i-1},x_{i}]\\{\frac {x_{i+1}-x}{h}}&{\mbox{ for }}x\in [x_{i},x_{i+1}]\\0&{\mbox{ otherwise}}\end{cases}}\!\,$

### How to Determine Coefficients

The discrete weak variational form is given as such:
Find $u_{N}\in V_{N}\!\,$ such that for all $v\in V_{N}\!\,$
$\underbrace {\int _{0}^{1}u_{N}'v_{N}'} _{a(u_{N},v_{N})}=\underbrace {\int _{0}^{1}fv_{N}} _{F(v_{N})}\!\,$
Since we have a basis $\{\phi _{i}\}_{i=1}^{N-1}\!\,$, we have a system of equations (that can be expressed in matrix form):
For $j=1,2,\ldots ,N-1\!\,$
$\sum _{i=1}^{N-1}u_{i}\int _{0}^{1}\phi _{i}\phi _{j}=\int _{0}^{1}f\phi _{j}\!\,$

### Existence of Unique Solution

The existence of a unique solution follows from Lax-Milgram.
Note the following:
* bilinear form continuous (bounded) e.g. $a(u_{N},v_{N})\leq \|u_{N}\|_{1}\|v_{N}\|_{1}\!\,$
${\begin{aligned}a(u,v)&=\int u'v'\\&\leq |u|_{1}|v|_{1}{\mbox{ Cauchy Schwartz in L2 }}\\&\leq \|u\|_{1}\|v\|_{1}{\mbox{ dominance of spaces }}\end{aligned}}\!\,$
* bilinear form coercive e.g. $a(u_{N},u_{N})\geq C\|u_{N}\|_{1}^{2}\!\,$
${\begin{aligned}a(v,v)&=\int v'^{2}\\&=|v|_{1}^{2}\\&\geq C\|v\|_{1}^{2}{\mbox{ Poincare inequality}}\end{aligned}}\!\,$
Poincare Inequality: $\|v\|_{0}\leq \|v\|_{1}\leq C|v|_{1}\!\,$
* $F(v_{N})\leq C\|v_{N}\|_{1}\!\,$
${\begin{aligned}\int fv&\leq \|f\|_{0}\|v\|_{0}\\&\leq \|f\|_{1}\|v\|_{1}\end{aligned}}\!\,$

## Problem 5b

* Show that
* $a(u,v)=\int _{0}^{1}u'v'dx\!\,$
* defines an inner product on $H_{0}^{1}\!\,$ and thus a notion of orthogonality in $H_{0}^{1}\!\,$

## Solution 5b

* $a(u,v)=a(v,u)\!\,$
* $a(\alpha u,v)=\int \alpha u'v'=\alpha \int u'v'=\alpha a(u,v)\!\,$
* $a(u+w,v)=\int (u'+w')v'=\int u'v'+\int w'v'=a(u,v)+a(w,v)\!\,$
* $a(u,u)=\int u'^{2}\neq 0{\mbox{ if }}u\neq 0\!\,$

## Problem 5c

* Let $\phi _{1}=1-2|x-{\frac {1}{2}}|\!\,$ be the basis of the one-dimensional space $V_{2}\!\,$. Find an orthogonal basis in $V_{4}\!\,$ that contains the basis function $\phi _{1}\!\,$. Sketch the basis functions. Indicate how you would construct a basis of $V_{2^{n}}\!\,$ that contains the basis of $V^{2^{n-1}}\!\,$

## Solution 5c

$\phi _{1}={\begin{cases}2x&{\mbox{ for }}x\in [0,{\frac {1}{2}}]\\2-2x&{\mbox{ for }}x\in [{\frac {1}{2}},1]\end{cases}}\!\,$
$\phi _{2}={\begin{cases}8x&{\mbox{ for }}x\in [0,{\frac {1}{4}}]\\-8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{4}},{\frac {1}{2}}]\\0&{\mbox{ otherwise }}\end{cases}}\!\,$
$\phi _{3}={\begin{cases}8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{2}},{\frac {3}{4}}]\\-8(x-1)&{\mbox{ for }}x\in [{\frac {1}{4}},1]\\0&{\mbox{ otherwise }}\end{cases}}\!\,$
Define a new hat function on each new pair of adjoining subintervals. The hat functions should have all have the same height as the previous basis's hat functions.

## Problem 5d

* What is the structure of the linear system in (a) for this special basis?

## Solution 5d

For our system in (a), this system yields a diagonal matrix.

## Problem 6

* For solving the equation $y'=f(x,y)\!\,$, consider the scheme
* $y_{n+1}=y_{n}+{\frac {h}{2}}(y_{n}'+y'_{n+1})+{\frac {h^{2}}{12}}(y''_{n}-y''_{n+1})\!\,$
* where $y_{n}'=f(x_{n},y_{n})\!\,$ and $y_{n}''=f_{x}(x_{n},y_{n})+f(x_{n},y_{n})f_{y}(x_{n},y_{n})\!\,$

## Problem 6a

* Show that this scheme is fourth-order accurate.

## Solution 6a

${\begin{array}{|c|c|c|c|c|c|c|c|}{\mbox{Order}}&y(t+h)&-y(t)&-{\frac {h}{2}}y'(t)&-{\frac {h}{2}}y'(t+h)&-{\frac {h^{2}}{12}}y''(t)&{\frac {h^{2}}{12}}y''(t+h)&\Sigma \\\hline &&&&&&&\\0&y(t)&-y(t)&0&0&0&0&0\\1&y'(t)h&0&-{\frac {h}{2}}y'(t)&-{\frac {h}{2}}y'(t)&0&0&0\\2&{\frac {y''(t)h^{2}}{2}}&0&0&-{\frac {h}{2}}y''(t)h&-{\frac {h^{2}}{12}}y''(t)&{\frac {h^{2}}{12}}y''(t)&0\\3&{\frac {y'''(t)h^{3}}{6}}&0&0&-{\frac {h}{2}}{\frac {y'''(t)}{2}}h^{2}&0&{\frac {h^{2}}{12}}y'''(t)h&0\\4&y''''(t){\frac {h^{4}}{24}}&0&0&-{\frac {h}{2}}y''''(t){\frac {h^{3}}{6}}&0&{\frac {h^{2}}{12}}y''''(t){\frac {h^{2}}{2}}&0\\5&O(h^{5})&0&0&O(h^{5})&0&O(h^{5})&O(h^{5})\\\hline \end{array}}$

## Problem 6b

* For stability analysis, one takes $f(x,y)=\lambda y\!\,$. State what it means for ${\overline {\lambda }}=h\lambda \!\,$ to belong to the region of absolute stability for this scheme, and show that the region of absolute stability contains the entire negative real axis.

## Solution 6b

$y_{n}''={\frac {d}{dx}}\lambda y+\lambda y{\frac {d}{dy}}\lambda y=\lambda ^{2}y\!\,$
$y_{n+1}=y_{n}+{\frac {h}{2}}\lambda y_{n}+{\frac {h}{2}}\lambda y_{n+1}+{\frac {h^{2}}{12}}[\lambda ^{2}y_{n}-\lambda ^{2}y_{n+1}]\!\,$
Letting $z=h\lambda \!\,$ and rearranging terms gives
$y_{n+1}=\underbrace {\left({\frac {1+{\frac {z}{2}}+{\frac {z^{2}}{12}}}{1-{\frac {z}{2}}+{\frac {z^{2}}{12}}}}\right)} _{M}y_{n}\!\,$
If $z\!\,$ is a negative real number, then $M<1\!\,$