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

Problem 4

Suppose that $f:R\rightarrow R\!\,$ is smooth and that the boundary value problem

$u''=f(u){\mbox{ on }}(0,1),\quad u(0)=(1)=0\!\,$

has unique solution.

Problem 4a

For $N\in \mathbb {N} \!\,$ , let $x_{i}={\frac {1}{N}},i=0,\ldots ,N\!\,$ . Write down a system of $N+1\!\,$ equations to obtain an approximation $u_{i}\!\,$ for the solution $u\!\,$ at $x_{i}\!\,$ by replacing the second derivatives by a symmetric difference quotient.

Solution 4a

The symmetric difference quotient is given by

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

Hence we have the following system equations that incorporates the initial conditions $u(0)=u(1)=0\!\,$ .

$\underbrace {{\frac {1}{h^{2}}}{\begin{bmatrix}1&&&&&&\\1&-2&1&&&&\\&1&-2&1&&&\\&&\ddots &\ddots &\ddots &&\\&&&&1&-2&1\\&&&&&&1\end{bmatrix}}} _{A}\underbrace {\begin{bmatrix}u_{0}\\u_{1}\\u_{2}\\\vdots \\\vdots \\u_{n}\end{bmatrix}} _{U}=\underbrace {\begin{bmatrix}0\\f(u_{1})\\f(u_{2})\\\vdots \\f(u_{n-1})\\0\end{bmatrix}} _{f}\!\,$

Problem 4b

Write the system of equations in the form $F(U)=0\!\,$ . Define domain and range of $F\!\,$ and explain the meaning of the variable $U\!\,$ .

Solution 4b

$\underbrace {AU-f} _{F(U)}=0\!\,$

Domain: $R^{N+1}\!\,$

Range: $R^{N+1}\!\,$

$U\!\,$ is a vector containing $N+1\!\,$ approximations $u_{i}\!\,$ for the solution $u\!\,$ at $x_{i}\!\,$

Problem 4c

Formulate Newton's method for the solution of the system in (b) with $U^{(0)}=0\!\,$ . Give explicit expressions for all objects involved (as far as this is reasonable). Determine a sufficient condition that ensures that the iterates $U^{(k)}\!\,$ in the Newton scheme are defined. Without doing any further calculations, can you decide whether the sequence $U^{(k)}\!\,$ converges. Why or why not?

Solution 4c

Newton's Method

$U^{k+1}=U^{k}-J(F(U^{(k)})^{-1}F(U^{(k)})\!\,$

where $J(A)\!\,$ denotes the Jacobian of a matrix $A\!\,$ .

Specifically,

$J(F(U^{(k)})=J(AU-F)=A-J(F)\!\,$

Sufficient Condition

If $J(F(U^{(k)})^{-1}\!\,$ exists, then $U^{(k)}\!\,$ iterates are defined.

Convergence of sequence

We cannot decide if the sequence converges since Newton's method only guarantees local convergence.

In general, for local convergence of Newton's method we need:

$F\!\,$ differentriable

$D(F(U^{*}))\!\,$ invertible

$D(F)\!\,$ Lipschitz

$U^{(0)}\!\,$ close to solution $U^{*}\!\,$

Problem 5

Consider the boundary value problem

-u''=f,\quad 0<x<1\!\,

with boundary conditions $u(0)=0\!\,$ and $u'(1)+\alpha u(1)=0\!\,$ . Here $\alpha \!\,$ is a given positive number.

Problem 5a

Describe a Galerkin method to solve this problem using piecewise linear functions with respect to a uniform mesh.

Weak Formulation

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

$\int _{0}^{1}-u''v=\int _{0}^{1}fv\!\,$

which after integrating by parts and plugging in initial conditions we have

$\int _{0}^{1}u'v'=\int _{0}^{1}fv-\alpha u(1)v(1)\!\,$

Let $\{x_{i}\}_{i=0}^{N+1}\!\,$ be the nodes of a uniform partition of $[0,1]\!\,$ where $x_{0}=0\!\,$ and $x_{i}=ih\!\,$ .

Let $\{\phi _{i}\}_{i=0}^{N+1}\!\,$ be the standard "hat" functions defined as follows:

For $i=1,2\ldots ,N\!\,$

$\phi _{i}={\begin{cases}{\frac {x-x_{i-1}}{h}}&{\mbox{ for }}x\in [x_{i-1},x_{i}]\\{\frac {x_{i+1}-x}{h}}&{\mbox{ for }}x\in [x_{i},x_{i+1}]\\0&{\mbox{ otherwise }}\end{cases}}\!\,$

$\phi _{N+1}={\begin{cases}{\frac {x-x_{N}}{h}}&{\mbox{ for }}x\in [x_{N},x_{N+1}]\\0&{\mbox{ otherwise }}\end{cases}}$

Also $\phi _{0}=0\!\,$ since $u(0)=0\!\,$

Then $\{\phi _{i}\}_{i=0}^{N+1}\!\,$ forms a basis for the discrete space $U_{h}=\{u\in H^{1}[0,1]:u(0)=0,u{\mbox{ piecewise linear }}\}\!\,$

Problem 5b

Derive the matrix equations for this Galerkin method. Write out explicitly that equation of the linear system which involves $\alpha \!\,$

Discrete Weak Formulation

Find $u_{h}\in U_{h}\!\,$ such that for all $v\in U_{h}\!\,$

$\int _{0}^{1}u_{h}'v_{h}'=\int _{0}^{1}fv_{h}-\alpha u(1)v(1)\!\,$

Since $\{\phi _{i}\}_{i=0}^{N+1}\!\,$ forms a basis, we have

$u_{h}=\sum _{i=0}^{N+1}u_{hi}\phi _{i}\!\,$

Also for $j=1,\ldots ,N+1\!\,$

$\sum _{i=0}^{N+1}u_{hi}\int _{0}^{1}\phi _{i}'\phi _{j}'=\int _{0}^{1}f\phi _{j}+\alpha \sum _{i=0}^{N+1}u_{hi}\phi _{i}(1)\phi _{j}(1)\!\,$

In matrix form

${\begin{bmatrix}{\frac {2}{h}}&-{\frac {1}{h}}&&&&\\-{\frac {1}{h}}&{\frac {2}{h}}&-{\frac {1}{h}}&&&\\&\ddots &\ddots &\ddots &&\\&&&&-{\frac {1}{h}}&{\frac {2}{h}}+\alpha \end{bmatrix}}{\begin{bmatrix}u_{h_{1}}\\u_{h_{2}}\\\vdots \\u_{h_{N+1}}\end{bmatrix}}={\begin{bmatrix}\int _{0}^{1}f\phi _{1}\\\int _{0}^{1}f\phi _{2}\\\vdots \\\int _{0}^{1}f\phi _{N+1}\end{bmatrix}}\!\,$

Problem 6

Consider the linear multistep method

$y_{n+1}={\frac {4}{3}}y_{n}-{\frac {1}{3}}y_{n-1}+{\frac {2}{3}}hf(x_{n+1},y_{n+1})\!\,$

for the solution of the initial value problem $y'(x)=f(x,y(x)),y(0)=y_{0}\!\,$

Problem 6a

Show that the truncation error is of order 2.

Problem 6b

State the condition for consistency of a linear multistep method and verify it for the scheme in this problem.

Solution 6b

${\begin{aligned}y_{n+1}&=\sum _{j=0}^{p}a_{j}y_{n-j}+h\sum _{j=-1}^{p}b_{j}f(t_{n-j},y_{n-j})\\&=a_{0}y_{n}+a_{1}y_{n-1}+\ldots +a_{p}y_{n-p}+h[b_{-1}f(t_{n+1},y_{n+1})+b_{0}f(t_{n},y_{n})+b_{1}f(t_{n-1},y_{n-1})+\ldots +b_{p}f(t_{n-p},y_{n-p})]\end{aligned}}\!\,$