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

Problem 5a

State Newton's method for the approximate solution of $f(x)=0$ where $f(x)$ is a real-valued function of the real variable $x$

Solution 5a

$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$

Problem 5b

State and prove a convergence result for the method.

Solution 5b

$\begin{array}{cc}{x}_{k+1}& =x_k-f^{\prime }(x_k{)}^{-1}f(x_k)\\ \underset{e_{k+1}}{\underbrace{x_{k+1}-x_{*}}}& =\underset{e_k}{\underbrace{x_k-x_{*}}}-f^{\prime }(x_k{)}^{-1}f(x_k)\\ & =f^{\prime }(x_k{)}^{-1}[f^{\prime }(x_k)e_k-(f(x_k)-\underset{0}{\underbrace{f(x_{*})}}))\\ & =f^{\prime }(x_k{)}^{-1}[f^{\prime }(x_k)e_k-e_k\underset{0}{\overset{1}{\int }}{f}^{\prime }(s{x}_k+(1-s)x_{*})ds]\\ & =f^{\prime }(x_k{)}^{-1}[f^{\prime }(x_k)e_k-f^{\prime }(x_{*})e_k-e_k\underset{0}{\overset{1}{\int }}(f^{\prime }(s{x}_k+(1-s)x_{*})-f^{\prime }(x_{*}))ds]\\ \Vert e_{k+1}\Vert & \le \Vert f^{\prime }(x_k{)}^{-1}\Vert [L\Vert e_k{\Vert }^2+\frac{L}{2}\Vert e_k{\Vert }^2]\text{ where L is Lipschitz constant of }{f}^{\prime }\\ & =\Vert f^{\prime }(x_k{)}^{-1}\Vert \frac{3}{2}L\Vert e_k{\Vert }^2\end{array}$

Problem 5c

What is the typical order of convergence? Are there situations in which the order of convergence is higher? Explain your answers to these questions.

Solution 5c

The typical order of local convergence is quadratic.

Consider the Newton's method as a fixed point iteration i.e.:

$x_{k+1}=\underset{g(x_k)}{\underbrace{x_k-\frac{f(x_k)}{f^{\prime }(x_k)}}}$

Then

$g^{\prime }(x_k)=1-\frac{f^{\prime }(x_k{)}^2-f^{\prime }(x_k)f(x_k)}{f^{\prime }(x_k{)}^2}$

$g^{\prime }(x_{*})=0$

Expanding $g(x_k)$ around $x_{*}$ gives an expression for the error

$\underset{x_{k+1}}{\underbrace{g(x_k)}}=\underset{x_{*}}{\underbrace{g(x_{*})}}+\underset{0}{\underbrace{g^{\prime }(x_{*})}}{e}_k+\frac{g^{″}(x_{*})}{2}{e}_k^2+\frac{g^{‴}(\xi )}{6}{e}_k^3$

Note that if $g^{″}(x_{*})=0$, then we have better than quadratic convergence.

Problem 6

Consider the boundary value problem $\{\begin{array}{c}-u^{″}(x)+u(x)=f(x),0\le x\le 1\\ u^{\prime }(0)=2,u(1)=0\end{array}(1)$

Problem 6a

Derive a variational formulation for (1).

Solution 6a

Find $u\in H$ such that for all $v\in H=\{v\in H^1[0,1]:v(1)=0\}$

$\underset{a(u,v)}{\underbrace{\underset{0}{\overset{1}{\int }}{u}^{\prime }{v}^{\prime }dx+\underset{0}{\overset{1}{\int }}uv}}=\underset{f(v)}{\underbrace{\underset{0}{\overset{1}{\int }}fv-2v(0)}}$

Problem 6b

What do we mean by Finite Element Approximation $u_h$ to $u$

Solution 6b

Let $P=\{x_i{\}}_{i=0}^N$ be a partition of $[0,1]$. Choose a an appropriate discrete subspace $V_h$ and basis functions $\{{\varphi }_i{\}}_{i=0}^N$. Then

$u_h=\sum _{i=0}^N{u}_{hi}{\varphi }_i$

The coefficients $u_{hi}$ can be found by solving the following system of equations:

For $j=0,1,\dots ,N$

$\sum _{i=0}^N{u}_{hi}\underset{0}{\overset{1}{\int }}{{\varphi }_i}^{\prime }{{\varphi }_j}^{\prime }dx+\sum _{i=0}^N{u}_{hi}\underset{0}{\overset{1}{\int }}{\varphi }_i{\varphi }_{j}dx=\underset{0}{\overset{1}{\int }}f{\varphi }_j-2{\varphi }_j(0)$

Problem 6c

State and prove an estimate for $\Vert u-u_h{\Vert }_1\equiv {(\underset{0}{\overset{1}{\int }}|u(x)-u_h(x){|}^{2}dx+\underset{0}{\overset{1}{\int }}|u^{\prime }(x)-{u_h}^{\prime }(x){|}^{2}dx)}^{\frac{1}{2}}$

Solution 6c

Cea's Lemma:

$\Vert u-u_h{\Vert }_1\le \underset{v\in V_h}{\inf }C\Vert u-v{\Vert }_1$

In particular choose $v_I$ to be the linear interpolant of $u$.

Then,

$\Vert u-u_h\Vert \le C\Vert u^{″}{\Vert }_{\mathrm{\infty }}h$

Alternative Solution 6c

Let $\{x_k{\}}_0^n$ be a discrete mesh of $[0,1]$ with step size $h$. Consider the following integral

$\underset{x_k}{\overset{x_{k+1}}{\int }}|u(x)-u_h(x){|}^{2}dx$.

For some ${\xi }_k\in [x_k,x_{k+1}]$, $u(x)-u_h(x)=u^{\prime }({\xi }_k)*h$ as $u_h$ is just a linear interpolation on this interval. Hence

$\underset{x_k}{\overset{x_{k+1}}{\int }}|u(x)-u_h(x){|}^{2}dx=\underset{x_k}{\overset{x_{k+1}}{\int }}{h}^2{u}^{\prime }({\xi }_k{)}^{2}dx=h^3{u}^{\prime }({\xi }_k{)}^2\le h^3||u^{\prime }|{|}_{\mathrm{\infty }}$.

Similarly, we can bound the $L_2(x_k,x_k+h)$ norm of the error in the derivatives with $h^3||u^{″}|{|}_{\mathrm{\infty }}$. With $n=1/h$ such intervals we have

$||u-u_h\Vert {|}^2\le 2n{h}^3\max (||u^{\prime }|{|}_{\mathrm{\infty }}^2,||u^{″}|{|}_{\mathrm{\infty }}^2)=2h^2\max (||u^{\prime }|{|}_{\mathrm{\infty }}^2,||u^{″}|{|}_{\mathrm{\infty }}^2).$

Problem 6d

Prove the formula $\Vert u-u_h{\Vert }_1^2=\Vert u{\Vert }_1^2-\Vert u_h{\Vert }_1^2$

Solution 6d

$\begin{array}{cc}\underset{\Vert u-u_h{\Vert }_1^2}{\underbrace{a(u-u_h,u-u_h)}}+2\underset{0}{\underbrace{a(u-u_h,u_h)}}& =a(u,u)-2a(u,u_h)+a(u_h,u_h)+2a(u,u_h)-2a(u_h,u_h)\\ & =a(u,u)-a(u_h,u_h)\\ & =\Vert u{\Vert }_1^2-\Vert u_h{\Vert }_1^2\end{array}$

Problem 7

Consider the initial value problem $y^{\prime }=f(t,y),y(t_0)=y_0$ where $f$ satisfies the Lipschitz condition $|f(t,y)-f(t,z)|\le L|y-z|$ for all $t,y,z$. A numerical method called the midpoint rule for solving this problem is defined by $y_{n+1}=y_{n-1}+2hf(t_n,y_n)$ where $h$ is a time step and $y_n\approx y(t_n)$ for $t_n=t_0+nh$. Here $y_0$ is given and $y_1$ is presumed to be computed by some other method.

Problem 7a

Suppose the problem is posed on a finite interval $t_0\le t\le b$ where $h=\frac{(b-t_0)}{M}$. Show directly,i.e., without citing any major results, that the midpoint rule is stable. That is show that if $\widehat{y_0}$ and $\widehat{y_1}$ satisfy $|y_0-\widehat{y_0}|\le ϵ,|y_1-\widehat{y_1}|\le ϵ$ then there exists a constant $C$ independent of $h$ such that $|y_n-\widehat{y_n}|\le Cϵ$ for $0\le n\le M$

Solution 7a

$\begin{array}{cc}{y}_{n+1}& =y_{n-1}+2hf(t_n,y_n)\\ {\hat{y}}_{n+1}& ={\hat{y}}_{n-1}+2hf(t_n,{\hat{y}}_n)\end{array}$

Subtracting both equations, letting $e_n\equiv y_n-{\hat{y}}_n$, and applying the Lipschitz property yields,

$\begin{array}{cc}{e}_{n+1}& \le e_{n-1}+2hL{e}_n\\ & \le (1+2hL)\max \{e_n,e_{n-1}\}\end{array}$

Therefore,

$\begin{array}{cc}{e}_n& \le (1+2hL{)}^{n-1}ϵ\\ & \le (1+2hL{)}^nϵ\\ & \le e^{2Lhn}ϵ\\ & \le e^{2L(t_n-t_0)}ϵ\end{array}$

Problem 7b

Suppose instead we are interested in the long term behavior of the midpoint rule applied to a particular example $f(t,y)=\lambda y$. That is, let $h$ be fixed and let $n\to \mathrm{\infty }$ so that the rule is applied over a long time interval. Show that in this case the midpoint rule does not produce an accurate approximation to the solution to the initial value problem.

Solution 7b

Substituting into the midpoint rule we have,

$y_{n+1}=y_{n-1}+2h\lambda y_n$

or

$y_{n+1}-2h\lambda y_n-y_{n-1}=0$

The solution of this equation is given by

$y_n=C_1{z}_1^n+C_2{z}_2^n$

where $z_1,z_2$ or the roots of the quadratic

$z^2-2h\lambda z-1$

The quadratic formula yields

$z=h\lambda (1\pm \sqrt{1+\frac{4}{4h^2{\lambda }^2}})$

If $\lambda$ is a small negative number, than one of the roots will be greater than 1. Hence, $y_n\to \mathrm{\infty }$ as $n\to \mathrm{\infty }$ instead of converging to zero since $y(t)=e^{\lambda t}$.