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

Problem 4

Let $𝐟\mathbf{:}{ℝ}^n\to {ℝ}^n$, suppose $𝐟(x^{*})=0$ and assume ${𝐟}^{\prime }(x^{*})$ is nonsingular . Consider the following iteration $x_{k+1}=x_k-B_k^{-1}𝐟(x_k),(k\ge 0)$

Problem 4a

Derive the following error equation for $e_{k+1}=x_{k+1}-x^{*}$ $e_{k+1}=B_k^{-1}((B_k-{𝐟}^{\prime }(x^{*}))e_k-\underset{0}{\overset{1}{\int }}({𝐟}^{\prime }(s{x}_k+(1-s)x^{*})-{𝐟}^{\prime }(x^{*}))e_{k}ds)$

Solution 4a

Note the following identity

$F(x)-F(y)=\underset{0}{\overset{1}{\int }}{F}^{\prime }(sx+(1-s)y)(x-y)ds(*)$

The error $e_{k+1}$ is given by

$\begin{array}{cc}{e}_{k+1}& =x_{k+1}-x_{*}\\ & =\underset{e_k}{\underbrace{x_k-x_{*}}}-B_k^{-1}f(x_k)\\ & =e_k-B_k^{-1}(f(x_k)-\underset{0}{\underbrace{f(x_{*})}})\\ & =B_k^{-1}\{(B_k-f^{\prime }(x_{*}))e_k-\underset{0}{\overset{1}{\int }}[f^{\prime }(s{x}_k+(1-s)x_{*})-f^{\prime }(x_{*})]e_{k}ds\}\\ \end{array}$

Problem 4b

Let $B_k=B\in {ℝ}^{n\times n}$ be a fixed matrix. Find conditions on B that guarentee local convergence. What rate of convergence do you expect and why?

Solution 4b

Assume $B$ is invertible, $\Vert B-f^{\prime }(x_{*})\Vert$ is bounded, and $f^{\prime }$ is Lipschitz.

$\begin{array}{cc}\Vert e_{k+1}\Vert & \le \Vert B^{-1}\Vert \{\Vert B-f^{\prime }(x_{*})\Vert \Vert e_k\Vert -\underset{0}{\overset{1}{\int }}\underset{\le L\Vert s{x}_k+(1-s)x_{*}-x_{*}\Vert }{\underbrace{\Vert f^{\prime }(s{x}_k+(1-s)x_{*})-f^{\prime }(x_{*})\Vert }}\Vert e_k\Vert ds\}\\ & \le \Vert B^{-1}\Vert \{\Vert B-f^{\prime }(x_{*})\Vert \Vert e_k\Vert -\underset{0}{\overset{1}{\int }}L\Vert e_k{\Vert }^{2}sds\}\\ & \le \Vert B^{-1}\Vert \{\Vert B-f^{\prime }(x_{*})\Vert -\frac{L}{2}\Vert e_k\Vert \}\Vert e_k\Vert \end{array}$

This implies local superlinear convergence.

Problem 4c

Find sufficient conditions on $\Vert B_k-{𝐟}^{\prime }(x_k)\Vert$ for the convergence to be superlinear. What choice of $B_k$ corresponds to the Newton method and what rate of convergence do you expect?

Solution 4c

Super linear convergence

$\frac{\Vert e_{k+1}\Vert }{\Vert e_k\Vert }\to 0$ as $k\to \mathrm{\infty }$

Find condition for super linear convergence

From part(b)

$\frac{\Vert e_{k+1}\Vert }{\Vert e_k\Vert }\le \Vert B_k^{-1}\Vert \{\Vert B_k-f^{\prime }(x_{*})\Vert -\frac{L}{2}\Vert e_k\Vert \}$

Since $\Vert e_k\Vert \to 0\text{ as }k\to \mathrm{\infty }$, if

$\Vert B_k-f^{\prime }(x_{*})\Vert \to 0$

as $k\to 0$, we have super linear convergence i.e.

$B_k=f^{\prime }(x_k)\text{ Newton Iteration form}$

Problem 5

Let $f(t,y)$ be uniformly Lipschitz with respect to $y$. Let $y(t)$ be the solution to the initial value problem : $y^{\prime }=f(t,y),y(0)=y_0$. Consider the trapezoid method $(1)y_{i+1}=y_i+\frac{h}{2}(f(t_i,y_i)+f(t_{i+1},y_{i+1})),(i\ge 0)$.

Problem 5a

Find a condition on the stepsize $h$ that ensures (1) can be solved uniquely for $y_{i+1}$.

Solution 5a

The implicit method can be viewed as a fix point iteration:

$y_{i+1}=\underset{g(y_{i+1})}{\underbrace{y_i+\frac{h}{2}(f(t_i,y_i)+f(t_{i+1},y_{i+1}))}}$

We want $\left|\frac{\partial g(y_{i+1})}{\partial y_{i+1}}\right|<1$

which implies

$h<\frac{2}{\left|\frac{\partial f(t_{i+1},y_{i+1})}{\partial y_{i+1}}\right|}$

Problem 5b

Define a local truncation error and estimate it. Examine the additional regularity of $f$ needed for this estimate.

Solution 5b

Re-writing (1) and replacing $y_k\text{ with }y(t_k)\text{ and }f(t_k,y_k)\text{ with }{y}^{\prime }(t_k)$ we have a formula for consistency of order p:

$y(t_{i+1})-y(t_i)-\frac{h}{2}{y}^{\prime }(t_i)-\frac{h}{2}y(t_{i+1})=𝒪(h^{p+1})$

For uniform stepsize h

$t_{i+1}=t_i+h$

Expanding in Taylor Series about $t_i$ gives

Problem 5c

Prove a global error estimate for (1)

Problem 6

Consider the 2-point boundary value problem $(2)-a{u}^{″}+bu=f(x),0<x<1,u(0)=u_0,u(1)=u_1$, with $a,b>0$ constants and $f\in C[0,1]$. Let $𝒫=\{x_i{\}}_{i=0}^{n+1}$ be a uniform partition of [0,1] with meshsize $h$.

Problem 6a

Use centered finite differences to discretize (2). Write the system as $A𝐔=𝐅$ and identify $A\in {ℝ}^{n\times n}\text{ and }𝐔,𝐅\in {ℝ}^n$. Prove that A is nonsingular.

Solution 6a

Using Taylor Expansions, we can approximate the second derivative as follows

$u^{″}(x)=\frac{u(x+h)-2u(x)+u(x-h)}{h^2}$

We can eliminate two equations from the n+2 equations by substituting the initial conditions $u(0)=u_0,u(1)=u_1$ into the equations for $U_1$ and $U_n$ respectively.

We then have the system

$\underset{A}{\underbrace{\left[\begin{array}{ccccccc}\frac{2a}{h^2}+b& -\frac{a}{h^2}& & & & & \\ -\frac{a}{h^2}& \frac{2a}{h^2}+b& -\frac{a}{h^2}& & & & \\ & -\frac{a}{h^2}& \frac{2a}{h^2}+b& -\frac{a}{h^2}& & \\ & & \ddots & \ddots & \ddots & \\ & & & & -\frac{a}{h^2}& \frac{2a}{h^2}+b\end{array}\right]}}\underset{U}{\underbrace{\left[\begin{array}{c}{U}_1\\ U_2\\ U_3\\ ⋮\\ U_n\end{array}\right]}}=\underset{F}{\underbrace{\left[\begin{array}{c}f(x_1)+\frac{a}{h^2}{u}_0\\ f(x_2)\\ f(x_3)\\ ⋮\\ f(x_n)+\frac{a}{h^2}{u}_1\end{array}\right]}}$

$A$ is nonsingular since it is diagonally dominant.

Problem 6b

Define truncation error and derive a bound for this method in terms of $h$. State without proof an error estimate of the form $\underset{1\le i\le n}{\max }|u(x_i)-U_i|\le C{h}^s$ and specify the order s.

Solution 6b

Local Truncation Error

$LTE=\frac{u(x_i+h)+u(x_i-h)-2u(x_i)}{h^2}-u^{″}(x_i)=\frac{u^{(4)}(\xi )}{12}{h}^2$

Bound for Local Truncation Error

$\frac{1}{12}\Vert u^{(4)}{\Vert }_{\mathrm{\infty }}{h}^2$

Derive Bound for Max Error

Let $L=-a{\partial }_{xx}+b$, $L_h=A$, and $R_h$ is the local truncation error.

Then

$\begin{array}{cc}Lu& =f\\ L_{h}u& =f+R_h\\ L_{h}U& =f\end{array}$

Subtracting the two last equations gives

$L_h(u-U)=R_h$

Hence,

$\Vert u-U{\Vert }_{\mathrm{\infty }}\le \Vert L_h^{-1}\Vert \Vert R_h\Vert$

$\Vert u-U{\Vert }_{\mathrm{\infty }}\le C{h}^2$, that is the error has order 2.

Problem 6c

Prove the following discrete monotonicity property: If ${𝐔}_i$ is the solution corresponding to a forcing $f_i$, for $i=1,2$, and $f_1\le f_2$ then ${𝐔}_1\le {𝐔}_2$ componentwise.

Solution 6c

Note that $A$ is a $M$ matrix and hence the discrete maximum principle applies. (See January 05 667 test for definition of $M$ matrix)

Discrete Maximum Principle

$AU=F$

If $F\le 0$, then $U\le 0$.

Specifically let $F=f_1-f_2$, then $U_1-U_2\le 0$ which implies $U_1\le U_2$

Template:BookCat