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

## Problem 4a

 Show that the two-step method ${\displaystyle 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 ${\displaystyle (1)\!\,}$  finds an approximation for ${\displaystyle y\!\,}$  such that ${\displaystyle y'=f(x,y)\!\,}$ .

Let ${\displaystyle x_{n}=a_{0}+hn\!\,}$  be the ${\displaystyle n\!\,}$ th point of evaluation where ${\displaystyle a_{0}\!\,}$  is the starting point and ${\displaystyle h\!\,}$  is the step size.

#### Taylor Expansion of y' about a_0

{\displaystyle {\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 ${\displaystyle (1)\!\,}$  and simplifying yields

{\displaystyle {\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 ${\displaystyle y_{n}\approx y(x_{n})\!\,}$ , we also take Taylor Expansion of ${\displaystyle y\!\,}$  about ${\displaystyle a_{0}\!\,}$

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

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

${\displaystyle \lambda ^{2}+\lambda -2=0\!\,}$

Giving the roots

${\displaystyle \lambda _{1}=1\!\,}$
${\displaystyle \lambda _{2}=-2\!\,}$

${\displaystyle \lambda _{2}\!\,}$  clearly does not satisfy ${\displaystyle |\lambda _{j}|\leq 1\!\,}$

## Problem 4b

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

## Solution 4b

Let ${\displaystyle f(x,y)=0,y(0)=y_{0}=1\!\,}$ . Then ${\displaystyle y(t)=1\!\,}$ . We have the difference equation

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

which has general solution (use the roots)

${\displaystyle y_{n}=C_{1}(-2)^{n}+C_{2}\cdot 1^{n}\!\,}$

If ${\displaystyle C_{1}\neq 0\!\,}$ , then ${\displaystyle y_{n}\rightarrow \infty \!\,}$  as ${\displaystyle n\rightarrow \infty \!\,}$

${\displaystyle y_{0}=C_{1}+C_{2}\!\,}$

${\displaystyle y_{1}=-2C_{1}+C_{2}\!\,}$

Hence, ${\displaystyle {\frac {y_{0}-y_{1}}{3}}=C_{1}\!\,}$ . Therefore if ${\displaystyle y_{0}\neq y_{1}\!\,}$ , then ${\displaystyle C_{1}\neq 0\!\,}$ .

## Problem 5

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

## Problem 5a

 Prove that ${\displaystyle (2)\!\,}$  has at most one solution

## Solution 5a

Let ${\displaystyle u_{1}\!\,}$  and ${\displaystyle u_{2}\!\,}$  be solutions. Let ${\displaystyle u\equiv u_{1}-u_{2}\!\,}$ .

By subtracting the two equations and their conditions we have

${\displaystyle -u''+(1+x)u=0\quad u'(0)=0,u(1)=0\!\,}$

Multiplying by test function ${\displaystyle v\in V=\{v\in H^{1}:v(1)=0\}\!\,}$  and integrating by parts from 0 to 1, we want to find ${\displaystyle u\in V\!\,}$  such that for all ${\displaystyle v\in V\!\,}$

${\displaystyle \int _{0}^{1}u'v'+\int _{0}^{1}(1+x)uv=0\!\,}$

Let ${\displaystyle v=u\!\,}$ . Then, we have

${\displaystyle \int _{0}^{1}(u')^{2}+\int _{0}^{1}(1+x)u^{2}=0\!\,}$

Since ${\displaystyle (u')^{2}\!\,}$ , ${\displaystyle (1+x)\!\,}$ , and ${\displaystyle u^{2}\!\,}$  are all ${\displaystyle >0\!\,}$ , ${\displaystyle u^{2}=0\!\,}$ . Hence ${\displaystyle u_{1}=u_{2}\!\,}$ .

## Problem 5b

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

## Solution 5b

The three point difference formula for ${\displaystyle u''\!\,}$  is given by

${\displaystyle u''(x)={\frac {u(x+h)-2u(x)+u(x-h)}{h^{2}}}\!\,}$

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

Substituting into ${\displaystyle (2)\!\,}$  with our difference formula we have in matrix formulation

${\displaystyle {\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 ${\displaystyle u_{0}\!\,}$  variable by using the approximation

${\displaystyle u'(0)={\frac {u_{1}-u_{0}}{h}}=1\!\,}$

which implies

${\displaystyle u_{0}=u_{1}-h\!\,}$

Using this relationship and the three difference formula, we have

${\displaystyle {\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 ${\displaystyle u(1)=u_{n}=1\!\,}$ , we can eliminate the ${\displaystyle u_{n}\!\,}$  variable by substituting into the n-1 equation.

${\displaystyle {\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 ${\displaystyle (b)\!\,}$  has a unique solution

## Solution 5c

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

## Problem 5d

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

## Solution 5d

Let ${\displaystyle u\!\,}$ ,a solution of the boundary value problem, be represented as the sum of solutions to two different boundary value problems i.e.

${\displaystyle u=w+v\!\,}$  where

${\displaystyle -w''+(1+x)w=f(x)\quad w'(0)=0,w(1)=0\!\,}$

${\displaystyle -v''+(1+x)v=g(x)\quad v'(0)=1,v(1)=1\qquad (*)\!\,}$

${\displaystyle -u''+(1+x)u=x^{2}=f(x)+g(x)\quad u'(0)=1,u(1)=1\!\,}$

Suppose ${\displaystyle v(x)=ax+b\!\,}$ . Then

${\displaystyle v'(0)=a=1\!\,}$  and ${\displaystyle v(1)=1+b=1\!\,}$  which implies ${\displaystyle b=0\!\,}$  and hence

${\displaystyle v(x)=x\!\,}$

Substituting into ${\displaystyle (*)\!\,}$ , we then have

${\displaystyle -0+(1+x)x=g(x)\!\,}$

which implies

${\displaystyle g(x)=x^{2}+x\!\,}$

Since ${\displaystyle f(x)+g(x)=x^{2}\!\,}$ , we have ${\displaystyle f(x)=-x\!\,}$

Therefore an equivalent boundary value problem with hemogenous boundary conditions is given by

${\displaystyle -w''+(1+x)w=-x\quad w'(0)=0,w(1)=0\!\,}$

## Problem 5e

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

## Solution 5e

### Variational Formulation and Sobolev space

Using the problem's notation, we want to find ${\displaystyle v\in H=\{w\in H^{1}:w(1)=0\}\!\,}$  such that for all ${\displaystyle w\in H\!\,}$ , we have

${\displaystyle 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 ${\displaystyle v\!\,}$  is unique, we show that the hypothesis of the Lax-Milgram Theorem are met.

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

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

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

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

## Problem 5f

 Consider the approximation of ${\displaystyle 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 ${\displaystyle \|v-v_{h}\|_{H}\leq Ch\!\,}$  and indicate how the constant ${\displaystyle C\!\,}$  depends on the derivatives of ${\displaystyle v\!\,}$ .

## Problem 6

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

## Problem 6a

 Prove (4) is locally convergent.

## Solution 6a

${\displaystyle \phi (x_{n}):=x_{n+1}=x_{n}-Af(x_{n})\!\,}$  is a fixed point iteration. By the contraction mapping theorem, if ${\displaystyle \phi (x)\!\,}$  is a contraction in some neighborhood of ${\displaystyle x_{*}\!\,}$  then the iteration converges at least linearly.

We have to show there exists ${\displaystyle \gamma <1\!\,}$  such that ${\displaystyle \|\phi (x)-\phi (y)\|\leq \gamma \|x-y\|\!\,}$ .

By the mean value theorem we have that ${\displaystyle \|\phi (x)-\phi (y)\|\leq \|D\phi (\xi )\|\|x-y\|\!\,}$ , that is ${\displaystyle \gamma =D\phi (\xi )\!\,}$  for some ${\displaystyle \xi \!\,}$  in our neighborhood of ${\displaystyle x_{*}\!\,}$ .

In particular, ${\displaystyle \|D\phi (x_{*})\|=\|I-AD\phi (x_{*})\|=0<1\!\,}$ , implying that ${\displaystyle \phi (x)\!\,}$  is a contraction and that the iterative method converges at least linearly.

### Calculating the Jacobian

${\displaystyle D\phi =Dx-ADf\!\,}$

${\displaystyle Dx=I\!\,}$

${\displaystyle Df={\begin{pmatrix}2x-2&1\\2&-2y\end{pmatrix}}\!\,}$

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

${\displaystyle \!\,}$

## Problem 6b

 Show that the convergence is at least quadratic.

## Solution 6b

{\displaystyle {\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 ${\displaystyle R(x_{n},x_{*})\!\,}$  satisfies ${\displaystyle {\frac {\|R(x_{n},x_{*})\|}{\|x_{n}-x_{*}\|}}\rightarrow 0\!\,}$  when ${\displaystyle \|x_{n}-x_{*}\|\rightarrow 0\!\,}$ .

Then, we obtain ${\displaystyle \|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:

${\displaystyle x_{n+1}=x_{n}-B(x_{n})f(x_{n})\!\,}$

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

${\displaystyle 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, ${\displaystyle B(x_{*})\!\,}$  in the Newton Iteration gives (4).