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

* Show that the two-step method
* $y_{n+1}=2y_{n-1}-y_{n}+h[{\frac {5}{2}}f(x_{n},y_{n})+{\frac {1}{2}}f(x_{n-1},y_{n-1})]\qquad (1)\!\,$
* is of order 2 but does not satisfy the root condition.

## Solution 4a
### Method of Order 2

Method $(1)\!\,$ finds an approximation for $y\!\,$ such that $y'=f(x,y)\!\,$.
Let $x_{n}=a_{0}+hn\!\,$ be the $n\!\,$th point of evaluation where $a_{0}\!\,$ is the starting point and $h\!\,$ is the step size.

#### Taylor Expansion of y' about a_0

${\begin{aligned}y'(x_{n})&=y'(a_{0}+hn)\\&=y'(a_{0})+hny''(a_{0})+h^{2}n^{2}y'''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y'(x_{n-1})&=y'(a_{0}+h(n-1))\\&=y'(a_{0})+h(n-1)y''(a_{0})+h^{2}(n-1)^{2}y'''(a_{0})/2+{\mathcal {O}}(h^{3})\end{aligned}}$
Substituting into the second term on the right hand side of $(1)\!\,$ and simplifying yields
${\begin{aligned}h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]&={\frac {5}{2}}[hy'(a_{0})+h^{2}ny''(a_{0})+{\mathcal {O}}(h^{3})]+{\frac {1}{2}}[hy'(a_{0})+h^{2}(n-1)y''(a_{0})+{\mathcal {O}}(h^{3})]\\&=3hy'(a_{0})+{\frac {1}{2}}(6n-1)y''(a_{0})+{\mathcal {O}}(h^{3})\end{aligned}}\!\,$

#### Taylor Expansion of y about a_0

Since $y_{n}\approx y(x_{n})\!\,$, we also take Taylor Expansion of $y\!\,$ about $a_{0}\!\,$
${\begin{aligned}y(x_{n+1})&=y(a_{0})+h(n+1)y'(a_{0})+h^{2}(n+1)^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y(x_{n})&=y(a_{0})+hny'(a_{0})+h^{2}n^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y(x_{n-1})&=y(a_{0})+h(n-1)y'(a_{0})+h^{2}(n-1)^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\end{aligned}}$
Substituting and simplifying yields,
    $y_{n+1}+y_{n}-2y_{n-1}=3hy'(a_{0})+{\frac {1}{2}}(6n-1)y''(a_{0})+{\mathcal {O}}(h^{3})\!\,$

#### Take Difference of Taylor Expansions

Hence $y_{n+1}+y_{n}-2y_{n-1}-h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]={\mathcal {O}}(h^{3})\!\,$ shows that (1) is a method of order 2.

### Does Not Satisfy Root Condition

The Characteristic equation of (1) is
    $\lambda ^{2}+\lambda -2=0\!\,$
Giving the roots
    $\lambda _{1}=1\!\,$
    $\lambda _{2}=-2\!\,$
$\lambda _{2}\!\,$ clearly does not satisfy $|\lambda _{j}|\leq 1\!\,$

## Problem 4b

* Give an example to show that the method (1) need not converge when solving $y'=f(x,y)\!\,$.

## Solution 4b

Let $f(x,y)=0,y(0)=y_{0}=1\!\,$. Then $y(t)=1\!\,$. We have the difference equation
$y_{n+1}+y_{n}-2y_{n-1}=0\!\,$
which has general solution (use the roots)
$y_{n}=C_{1}(-2)^{n}+C_{2}\cdot 1^{n}\!\,$
If $C_{1}\neq 0\!\,$, then $y_{n}\rightarrow \infty \!\,$ as $n\rightarrow \infty \!\,$
$y_{0}=C_{1}+C_{2}\!\,$
$y_{1}=-2C_{1}+C_{2}\!\,$
Hence, ${\frac {y_{0}-y_{1}}{3}}=C_{1}\!\,$. Therefore if $y_{0}\neq y_{1}\!\,$, then $C_{1}\neq 0\!\,$.

## Problem 5

* Consider the boundary value problem
* $-u''+(1+x)u=x^{2}\quad u'(0)=1,u(1)=1\qquad (2)\!\,$

## Problem 5a

* Prove that $(2)\!\,$ has at most one solution

## Solution 5a

Let $u_{1}\!\,$ and $u_{2}\!\,$ be solutions. Let $u\equiv u_{1}-u_{2}\!\,$.
By subtracting the two equations and their conditions we have
$-u''+(1+x)u=0\quad u'(0)=0,u(1)=0\!\,$
Multiplying by test function $v\in V=\{v\in H^{1}:v(1)=0\}\!\,$ and integrating by parts from 0 to 1, we want to find $u\in V\!\,$ such that for all $v\in V\!\,$
$\int _{0}^{1}u'v'+\int _{0}^{1}(1+x)uv=0\!\,$
Let $v=u\!\,$. Then, we have
$\int _{0}^{1}(u')^{2}+\int _{0}^{1}(1+x)u^{2}=0\!\,$
Since $(u')^{2}\!\,$, $(1+x)\!\,$, and $u^{2}\!\,$ are all $>0\!\,$, $u^{2}=0\!\,$. Hence $u_{1}=u_{2}\!\,$.

## Problem 5b

* Discretize the problem. Take a uniform partition of $[0,1]:\!\,$
* $x_{i}=ih,i=0,1,2,\ldots ,n,\quad h={\frac {1}{n}}\!\,$
* Use the three point difference formula for $u''\!\,$ and the simplest difference formula for the boundary condition at $x=0\!\,$. Write the resulting system as a matrix vector equation $Ax=b\!\,$ where $x=(u_{1},u_{2},\cdots ,u_{n-1})^{T}\!\,$

## Solution 5b

The three point difference formula for $u''\!\,$ is given by
$u''(x)={\frac {u(x+h)-2u(x)+u(x-h)}{h^{2}}}\!\,$

### Equations for i=2,...,n-2

Substituting into $(2)\!\,$ with our difference formula we have in matrix formulation
${\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+(1+ih)&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{i-1}\\u_{i}\\u_{i+1}\end{bmatrix}}=(ih)^{2}$

### Equation for i=1

We can eliminate the $u_{0}\!\,$ variable by using the approximation
$u'(0)={\frac {u_{1}-u_{0}}{h}}=1\!\,$
which implies
$u_{0}=u_{1}-h\!\,$
Using this relationship and the three difference formula, we have
${\begin{bmatrix}{\frac {1}{h^{2}}}+(1+h)&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{1}\\u_{2}\end{bmatrix}}=h^{2}-{\frac {1}{h}}\!\,$

### Equations for i=n-1

Since $u(1)=u_{n}=1\!\,$, we can eliminate the $u_{n}\!\,$ variable by substituting into the n-1 equation.
${\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+(1+(n-1)h)\end{bmatrix}}{\begin{bmatrix}u_{n-2}\\u_{n-1}\end{bmatrix}}=h^{2}-((n-1)h)^{2}+{\frac {1}{h^{2}}}$

## Problem 5c

* Prove that the equation found in $(b)\!\,$ has a unique solution

## Solution 5c

Since the matrix $A\!\,$ is diagonally dominant, the system $Ax=b\!\,$ has unique solution.

## Problem 5d

* Transform the problem $(2)\!\,$ into an equivalent problem with homogeneous boundary conditions.

## Solution 5d

Let $u\!\,$,a solution of the boundary value problem, be represented as the sum of solutions to two different boundary value problems i.e.
$u=w+v\!\,$ where
$-w''+(1+x)w=f(x)\quad w'(0)=0,w(1)=0\!\,$
$-v''+(1+x)v=g(x)\quad v'(0)=1,v(1)=1\qquad (*)\!\,$
$-u''+(1+x)u=x^{2}=f(x)+g(x)\quad u'(0)=1,u(1)=1\!\,$
Suppose $v(x)=ax+b\!\,$. Then
$v'(0)=a=1\!\,$ and $v(1)=1+b=1\!\,$ which implies $b=0\!\,$ and hence
$v(x)=x\!\,$
Substituting into $(*)\!\,$, we then have
$-0+(1+x)x=g(x)\!\,$
which implies
$g(x)=x^{2}+x\!\,$
Since $f(x)+g(x)=x^{2}\!\,$, we have $f(x)=-x\!\,$
Therefore an equivalent boundary value problem with hemogenous boundary conditions is given by
$-w''+(1+x)w=-x\quad w'(0)=0,w(1)=0\!\,$

## Problem 5e

* Obtain the variational formulation of the problem formulated in $(d)\!\,$. Specify the Sobolev space $H\!\,$ involved. Prove that this problem has a unique solution, which we denote by $v\!\,$.

## Solution 5e
### Variational Formulation and Sobolev space

Using the problem's notation, we want to find $v\in H=\{w\in H^{1}:w(1)=0\}\!\,$ such that for all $w\in H\!\,$, we have
$a(v,w)=\int _{0}^{1}v'w'+\int _{0}^{1}(1+x)vw=-\int _{0}^{1}xw=F(w)\!\,$
The above comes from integrating by parts and applying the boundary conditions.

### Unique Solution

To show that $v\!\,$ is unique, we show that the hypothesis of the Lax-Milgram Theorem are met.

#### a(v,w) bounded and continuous

${\begin{aligned}a(v,w)&=\int _{0}^{1}v'w'+\int _{0}^{1}\underbrace {(1+x)} _{\leq 2}vw\\&\leq 2\left[\int _{0}^{1}v'w'+\int _{0}^{1}vw\right]\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}\right]^{\frac {1}{2}}+\left[\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]\quad {\mbox{ Cauchy-Schwartz in L2 }}\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}+\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}+\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]{\mbox{ Cauchy-Schwartz in R2 }}\\&=2\|w\|_{1}\|v\|_{1}\end{aligned}}\!\,$

#### a(v,v) coercive

${\begin{aligned}a(v,v)&=\int _{0}^{1}v'^{2}+\int _{0}^{1}\underbrace {(1+v)} _{\geq 1}v^{2}\\&\geq \int _{0}^{1}v'^{2}+\int v^{2}\\&=\|v\|_{1}^{2}\end{aligned}}$

#### F(v) bounded

$|F(v)|=|-\int _{0}^{1}xv|\leq |\int _{0}^{1}v|\leq \|v\|_{1}^{2}\!\,$

## Problem 5f

* Consider the approximation of $v\!\,$ by piecewise linear finite elements. Define precisely the piecewise linear finite element subspace (use the partition (3)). Show that the finite element problem has a unique solution.

## Problem 5g

* Show that $\|v-v_{h}\|_{H}\leq Ch\!\,$ and indicate how the constant $C\!\,$ depends on the derivatives of $v\!\,$.

## Problem 6

* Let $f:\mathbb {R} \to \mathbb {R} \!\,$ be a nonlinear function with zero $x_{*}\!\,$:
* $f(x,y)={\begin{bmatrix}x^{2}-2x+y\\2x-y^{2}-1\end{bmatrix}}\!\,$, $x_{*}={\begin{bmatrix}1\\1\end{bmatrix}}\!\,$.
* Consider the iteration
* $x_{n+1}=x_{n}-Af(x_{n})\!\,$, $A={\begin{bmatrix}1&{\frac {1}{2}}\\1&0\end{bmatrix}}\qquad (4)\!\,$.

## Problem 6a

* Prove (4) is locally convergent.

## Solution 6a

$\phi (x_{n}):=x_{n+1}=x_{n}-Af(x_{n})\!\,$ is a fixed point iteration. By the contraction mapping theorem, if $\phi (x)\!\,$ is a contraction in some neighborhood of $x_{*}\!\,$ then the iteration converges at least linearly.
We have to show there exists $\gamma <1\!\,$ such that $\|\phi (x)-\phi (y)\|\leq \gamma \|x-y\|\!\,$.
By the mean value theorem we have that $\|\phi (x)-\phi (y)\|\leq \|D\phi (\xi )\|\|x-y\|\!\,$, that is $\gamma =D\phi (\xi )\!\,$ for some $\xi \!\,$ in our neighborhood of $x_{*}\!\,$.
In particular, $\|D\phi (x_{*})\|=\|I-AD\phi (x_{*})\|=0<1\!\,$, implying that $\phi (x)\!\,$ is a contraction and that the iterative method converges at least linearly.

### Calculating the Jacobian

$D\phi =Dx-ADf\!\,$
$Dx=I\!\,$
$Df={\begin{pmatrix}2x-2&1\\2&-2y\end{pmatrix}}\!\,$
${\begin{aligned}D\phi (x_{*})&=I-AD\phi (x_{*})\\&={\begin{pmatrix}1&0\\0&1\end{pmatrix}}-{\begin{pmatrix}1&{\frac {1}{2}}\\1&0\end{pmatrix}}{\begin{pmatrix}2(1)-2&1\\2&-2(1)\end{pmatrix}}\\&={\begin{pmatrix}1&0\\0&1\end{pmatrix}}-{\begin{pmatrix}1&0\\0&1\end{pmatrix}}\\&={\begin{pmatrix}0&0\\0&0\end{pmatrix}}\\\|D\phi (x_{*})\|&=0\end{aligned}}$

## Problem 6b

* Show that the convergence is at least quadratic.

## Solution 6b

${\begin{aligned}e_{n+1}&=x_{n+1}-x_{*}\\&=\underbrace {x_{n}-Af(x_{n})} _{\phi (x_{n})}-x_{*}\\&=\phi (x_{n})-x_{*}\\&=\left(\phi (x_{*})+(x_{n}-x_{*})^{T}\underbrace {D_{\phi }(x_{*})} _{0}+(x_{n}-x_{*})^{T}{\frac {H_{\phi }(x_{*})}{2!}}(x_{n}-x_{*})+R(x_{n},x_{*})\right)-x_{*}\\&=\left(x_{*}+A\underbrace {f(x_{*})} _{0}+{\frac {H_{\phi }(x_{*})}{2!}}\underbrace {(x_{n}-x_{*})^{T}(x_{n}-x_{*})} _{e_{n}^{2}}+R(x_{n},x_{*})\right)-x_{*}\\&\leq Ce_{n}^{2}+R(x_{n},x_{*})\end{aligned}}\!\,$
where $R(x_{n},x_{*})\!\,$ satisfies ${\frac {\|R(x_{n},x_{*})\|}{\|x_{n}-x_{*}\|}}\rightarrow 0\!\,$ when $\|x_{n}-x_{*}\|\rightarrow 0\!\,$.
Then, we obtain $\|e_{n+1}\|\leq C\|e_{n}\|^{2}\!\,$.

## Problem 6c

* Write the Newton iteration and compare it with (4)

## Solution 6c

The Newton iteration looks like this:
$x_{n+1}=x_{n}-B(x_{n})f(x_{n})\!\,$
${\begin{bmatrix}x_{n+1}\\y_{n+1}\end{bmatrix}}={\begin{bmatrix}x_{n}\\y_{n}\end{bmatrix}}-\underbrace {{\begin{bmatrix}2x_{n}-2&1\\2&-2y_{n}\end{bmatrix}}^{-1}} _{B}{\begin{bmatrix}x_{n}^{2}-2x_{n}+y_{n}\\2x_{n}-y_{n}^{2}-1\end{bmatrix}}$
Where B is the inverse of the Jacobian of f.
$B(x_{*})={\begin{bmatrix}2(1)-2&1\\2&-2(1)\end{bmatrix}}^{-1}={\begin{bmatrix}0&1\\2&-2\end{bmatrix}}^{-1}={\begin{bmatrix}1&{\frac {1}{2}}\\1&0\end{bmatrix}}=A$
That is, $B(x_{*})\!\,$ in the Newton Iteration gives (4).