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).