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})](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^{\prime }=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{array}{cc}{y}^{\prime }(x_n)& =y^{\prime }(a_0+hn)\\ & =y^{\prime }(a_0)+hn{y}^{″}(a_0)+h^2{n}^2{y}^{‴}(a_0)/2+𝒪(h^3)\\ \\ \\ y^{\prime }(x_{n-1})& =y^{\prime }(a_0+h(n-1))\\ & =y^{\prime }(a_0)+h(n-1)y^{″}(a_0)+h^2(n-1{)}^2{y}^{‴}(a_0)/2+𝒪(h^3)\end{array}$

Substituting into the second term on the right hand side of $(1)$ and simplifying yields

$\begin{array}{cc}h[\frac{5}{2}{y}^{\prime }(x_n)+\frac{1}{2}{y}^{\prime }(x_{n-1})]& =\frac{5}{2}[h{y}^{\prime }(a_0)+h^{2}n{y}^{″}(a_0)+𝒪(h^3)]+\frac{1}{2}[h{y}^{\prime }(a_0)+h^2(n-1)y^{″}(a_0)+𝒪(h^3)]\\ & =3h{y}^{\prime }(a_0)+\frac{1}{2}(6n-1)y^{″}(a_0)+𝒪(h^3)\end{array}$

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{array}{cc}y(x_{n+1})& =y(a_0)+h(n+1)y^{\prime }(a_0)+h^2(n+1{)}^2{y}^{″}(a_0)/2+𝒪(h^3)\\ \\ \\ y(x_n)& =y(a_0)+hn{y}^{\prime }(a_0)+h^2{n}^2{y}^{″}(a_0)/2+𝒪(h^3)\\ \\ \\ y(x_{n-1})& =y(a_0)+h(n-1)y^{\prime }(a_0)+h^2(n-1{)}^2{y}^{″}(a_0)/2+𝒪(h^3)\end{array}$

Substituting and simplifying yields,

$y_{n+1}+y_n-2y_{n-1}=3h{y}^{\prime }(a_0)+\frac{1}{2}(6n-1)y^{″}(a_0)+𝒪(h^3)$

Take Difference of Taylor Expansions

Hence $y_{n+1}+y_n-2y_{n-1}-h[\frac{5}{2}{y}^{\prime }(x_n)+\frac{1}{2}{y}^{\prime }(x_{n-1})]=𝒪(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|\le 1$

Problem 4b

Give an example to show that the method (1) need not converge when solving $y^{\prime }=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\ne 0$, then $y_n\to \mathrm{\infty }$ as $n\to \mathrm{\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\ne y_1$, then $C_1\ne 0$.

Problem 5

Consider the boundary value problem $-u^{″}+(1+x)u=x^2{u}^{\prime }(0)=1,u(1)=1(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=0u^{\prime }(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$

$\underset{0}{\overset{1}{\int }}{u}^{\prime }{v}^{\prime }+\underset{0}{\overset{1}{\int }}(1+x)uv=0$

Let $v=u$. Then, we have

$\underset{0}{\overset{1}{\int }}(u^{\prime }{)}^2+\underset{0}{\overset{1}{\int }}(1+x)u^2=0$

Since $(u^{\prime }{)}^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,\dots ,n,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

$\left[\begin{array}{ccccccc}-\frac{1}{h^2}& & & \frac{2}{h^2}+(1+ih)& & & -\frac{1}{h^2}\end{array}\right]\left[\begin{array}{c}{u}_{i-1}\\ u_i\\ u_{i+1}\end{array}\right]=(ih{)}^2$

Equation for i=1

We can eliminate the $u_0$ variable by using the approximation

$u^{\prime }(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

$\left[\begin{array}{cccc}\frac{1}{h^2}+(1+h)& & & -\frac{1}{h^2}\end{array}\right]\left[\begin{array}{c}{u}_1\\ u_2\end{array}\right]=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.

$\left[\begin{array}{cccc}-\frac{1}{h^2}& & & \frac{2}{h^2}+(1+(n-1)h)\end{array}\right]\left[\begin{array}{c}{u}_{n-2}\\ u_{n-1}\end{array}\right]=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)w^{\prime }(0)=0,w(1)=0$

$-v^{″}+(1+x)v=g(x)v^{\prime }(0)=1,v(1)=1(*)$

$-u^{″}+(1+x)u=x^2=f(x)+g(x)u^{\prime }(0)=1,u(1)=1$

Suppose $v(x)=ax+b$. Then

$v^{\prime }(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{w}^{\prime }(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)=\underset{0}{\overset{1}{\int }}{v}^{\prime }{w}^{\prime }+\underset{0}{\overset{1}{\int }}(1+x)vw=-\underset{0}{\overset{1}{\int }}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{array}{cc}a(v,w)& =\underset{0}{\overset{1}{\int }}{v}^{\prime }{w}^{\prime }+\underset{0}{\overset{1}{\int }}\underset{\le 2}{\underbrace{(1+x)}}vw\\ & \le 2[\underset{0}{\overset{1}{\int }}{v}^{\prime }{w}^{\prime }+\underset{0}{\overset{1}{\int }}vw]\\ & \le 2[{\left[\underset{0}{\overset{1}{\int }}v{\text{'}}^2\right]}^{\frac{1}{2}}{\left[\underset{0}{\overset{1}{\int }}w{\text{'}}^2\right]}^{\frac{1}{2}}+{\left[\underset{0}{\overset{1}{\int }}{v}^2\right]}^{\frac{1}{2}}{\left[\underset{0}{\overset{1}{\int }}{w}^2\right]}^{\frac{1}{2}}]\text{ Cauchy-Schwartz in L2 }\\ & \le 2\left[{[\underset{0}{\overset{1}{\int }}v{\text{'}}^2+\underset{0}{\overset{1}{\int }}{v}^2]}^{\frac{1}{2}}{[\underset{0}{\overset{1}{\int }}w{\text{'}}^2+\underset{0}{\overset{1}{\int }}{w}^2]}^{\frac{1}{2}}\right]\text{ Cauchy-Schwartz in R2 }\\ & =2\Vert w{\Vert }_1\Vert v{\Vert }_1\end{array}$

a(v,v) coercive

$\begin{array}{cc}a(v,v)& =\underset{0}{\overset{1}{\int }}v{\text{'}}^2+\underset{0}{\overset{1}{\int }}\underset{\ge 1}{\underbrace{(1+v)}}{v}^2\\ & \ge \underset{0}{\overset{1}{\int }}v{\text{'}}^2+\int v^2\\ & =\Vert v{\Vert }_1^2\end{array}$

F(v) bounded

$|F(v)|=|-\underset{0}{\overset{1}{\int }}xv|\le |\underset{0}{\overset{1}{\int }}v|\le \Vert v{\Vert }_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 $\Vert v-v_h{\Vert }_H\le Ch$ and indicate how the constant $C$ depends on the derivatives of $v$.

Problem 6

Let $f:ℝ\to ℝ$ be a nonlinear function with zero $x_{*}$: $f(x,y)=\left[\begin{array}{c}{x}^2-2x+y\\ 2x-y^2-1\end{array}\right]$, $x_{*}=\left[\begin{array}{c}1\\ 1\end{array}\right]$. Consider the iteration $x_{n+1}=x_n-Af(x_n)$, $A=\left[\begin{array}{cc}1& \frac{1}{2}\\ 1& 0\end{array}\right](4)$.

Problem 6a

Prove (4) is locally convergent.

Solution 6a

$\varphi (x_n):=x_{n+1}=x_n-Af(x_n)$ is a fixed point iteration. By the contraction mapping theorem, if $\varphi (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 $\Vert \varphi (x)-\varphi (y)\Vert \le \gamma \Vert x-y\Vert$.

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

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

Calculating the Jacobian

$D\varphi =Dx-ADf$

$Dx=I$

$Df=\left(\begin{array}{cc}2x-2& 1\\ 2& -2y\end{array}\right)$

$\begin{array}{cc}D\varphi (x_{*})& =I-AD\varphi (x_{*})\\ & =\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)-\left(\begin{array}{cc}1& \frac{1}{2}\\ 1& 0\end{array}\right)\left(\begin{array}{cc}2(1)-2& 1\\ 2& -2(1)\end{array}\right)\\ & =\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)-\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)\\ & =\left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right)\\ \Vert D\varphi (x_{*})\Vert & =0\end{array}$

$$

Problem 6b

Show that the convergence is at least quadratic.

Solution 6b

$\begin{array}{cc}{e}_{n+1}& =x_{n+1}-x_{*}\\ & =\underset{\varphi (x_n)}{\underbrace{x_n-Af(x_n)}}-x_{*}\\ & =\varphi (x_n)-x_{*}\\ & =(\varphi (x_{*})+(x_n-x_{*}{)}^T\underset{0}{\underbrace{D_{\varphi }(x_{*})}}+(x_n-x_{*}{)}^T\frac{H_{\varphi }(x_{*})}{2!}(x_n-x_{*})+R(x_n,x_{*}))-x_{*}\\ & =(x_{*}+A\underset{0}{\underbrace{f(x_{*})}}+\frac{H_{\varphi }(x_{*})}{2!}\underset{e_n^2}{\underbrace{(x_n-x_{*}{)}^T(x_n-x_{*})}}+R(x_n,x_{*}))-x_{*}\\ & \le C{e}_n^2+R(x_n,x_{*})\end{array}$

where $R(x_n,x_{*})$ satisfies $\frac{\Vert R(x_n,x_{*})\Vert }{\Vert x_n-x_{*}\Vert }\to 0$ when $\Vert x_n-x_{*}\Vert \to 0$.

Then, we obtain $\Vert e_{n+1}\Vert \le C\Vert e_n{\Vert }^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)$

$\left[\begin{array}{c}{x}_{n+1}\\ y_{n+1}\end{array}\right]=\left[\begin{array}{c}{x}_n\\ y_n\end{array}\right]-\underset{B}{\underbrace{{\left[\begin{array}{cc}2x_n-2& 1\\ 2& -2y_n\end{array}\right]}^{-1}}}\left[\begin{array}{c}{x}_n^2-2x_n+y_n\\ 2x_n-y_n^2-1\end{array}\right]$

Where B is the inverse of the Jacobian of f.

$B(x_{*})={\left[\begin{array}{cc}2(1)-2& 1\\ 2& -2(1)\end{array}\right]}^{-1}={\left[\begin{array}{cc}0& 1\\ 2& -2\end{array}\right]}^{-1}=\left[\begin{array}{cc}1& \frac{1}{2}\\ 1& 0\end{array}\right]=A$

That is, $B(x_{*})$ in the Newton Iteration gives (4).

Template:BookCat