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

Problem 4

Let $f:R^{n}\rightarrow R\!\,$ be a nonlinear smooth function. To determine a (local) minimum of $f\!\,$ one can use a descent method of the form $x_{k+1}=x_{k}+\alpha _{k}d_{k}\quad (k\geq 0)\quad \quad (1)\!\,$ where $0\leq \alpha _{k}\leq 1\!\,$ is a suitable parameter obtained by backtracking and $d_{k}$ is a descent direction i.e. it satisfies $f(x_{k+1})<f(x_{k})\quad \quad (2)\!\,$

Problem 4a

Write the steepest descent method (or gradient) method and show that there exist $0<\alpha _{k}\leq 1\!\,$ such that the resulting method satisfies (2)

Solution 4a

Steepest Descent Method

$x_{k+1}=x_{k}-\alpha _{k}\nabla f(x_{k})\!\,$

Choose $\alpha _{k}\in (0,1]\!\,$ such that $\alpha _{k}\!\,$ minimizes $f(x_{k}-\alpha _{k}\nabla f(x_{k}))\!\,$ i.e.

$\alpha _{k}:\min _{0<\alpha _{k}\leq 1}f(x_{k}-\alpha _{k}\nabla f(x_{k}))\!\,$

Directional Derivative Negative

To satisfy (2), the directional derivative should be negative i.e.

$\nabla _{d_{k}}f(x_{k})=\lim _{\alpha _{k}\rightarrow 0}{\frac {f(x_{k}+\alpha _{k}d_{k})-f(x_{k})}{\alpha _{k}}}<0\!\,$

which implies

$\underbrace {f(x_{k}+\alpha _{k}d_{k})} _{f(x_{k+1})}<f(x_{k})\!\,$

since $\alpha _{k}\in (0,1]\!\,$

Problem 4b

Write the Newton method and examine whether or not there exist $\alpha _{k}\!\,$ which yield (2). Establish conditions on the Hessian $H(f(x))\!\,$ of $f(x)\!\,$ which guarantee the existence of $\alpha _{k}\!\,$.

Solution 4b

Newton's Method

$x_{k+1}=x_{k}-H^{-1}(f(x_{k}))\nabla f(x_{k})\!\,$

Directional Derivative Negative

To have descent, we want the directional derivative to be negative i.e.

$\nabla _{\alpha _{k}d_{k}}f(x_{k})=\nabla f(x_{k})\cdot \alpha _{k}d_{k}=-\nabla f(x_{k})\cdot H^{-1}(f(x_{k}))\nabla f(x_{k})<0\!\,$

which implies

$\nabla f(x_{k})^{T}H^{-1}(f(x_{k}))\nabla f(x_{k})>0\!\,$

Therefore $H^{-1}(f(x_{k}))\!\,$ is positive definite and therefore $H(f(x_{k}))\!\,$ is positive definite.

Problem 4c

If we replace the Hessian by the matrix $H(f(x))+\gamma _{k}I\!\,$, where $\gamma _{k}\geq 0\!\,$ and $I$ is the identity matrix, we obtain a quasi-Newton method. Find a condition on $\gamma _{k}\!\,$ which leads to (2).

Solution 4c

We now want ${\tilde {H}}(f(x_{k}))=H(f(x_{k}))+\gamma _{k}I\!\,$ to be positive definite.

Let $\lambda _{i}\!\,$, $i=1,2,\ldots ,n\!\,$ be the eigenvalues of $H(f(x_{k}))\!\,$.

Then $\lambda _{i}+\gamma _{k}\cdot 1\!\,$, $i=1,2,\ldots ,n\!\,$ are eigenvalues of ${\tilde {H}}(f(x_{k}))\!\,$.

Since we want ${\tilde {H}}(f(x_{k}))\!\,$ to be positive definite, we equivalently have for $i=1,2,\ldots ,n\!\,$

$\lambda _{i}+\gamma _{k}>0\!\,$

i.e.

$\gamma _{k}>-\lambda _{i}\quad i=1,2,\ldots ,n\!\,$

Problem 5

Consider the following nonlinear autonomous initial value problem in $R$ with $f\in C^{2}$. $y'=f(y)\quad \quad y(0)=y_{0}$

Problem 5a

Write the ODE in integral form and use the mid-point quadrature rule to derive the mid-point method with uniform time-step $h={\frac {T}{N}}$: $y_{n+1}=y_{n}+hf({\frac {y_{n+1}+y_{n}}{2}})$

Solution 5a

For $x\in [x_{n},x_{n+1}]\!\,$,

$y(x_{n+1})-y(x_{n})=\int _{x_{n}}^{x_{n+1}}f(y(x))dx\approx h\cdot f\left({\frac {y_{n+1}+y_{n}}{2}}\right)\!\,$

Problem 5b

Define truncation error $T_{n}\!\,$. Assuming that $T_{n}=O(h^{3})\!\,$, show an estimate for the error $|y(t_{N})-y_{N}|\!\,$. What is the order of the method? (Hint: use that $f\!\,$ is Lipschitz continuous.

Solution 5b

${\begin{aligned}|e_{n+1}|&=|y(t_{n+1})-y_{n+1}|\\&\leq |y(t_{n})-y_{n}|+h\underbrace {\left|f\left({\frac {y(t_{n+1})-y(t_{n})}{2}}\right)-f\left({\frac {y_{n+1}-y_{n}}{2}}\right)\right|} _{\leq {\frac {\gamma }{2}}|y(t_{n+1})-y(t_{n})-y_{n+1}+y_{n}|}+{\mathcal {O}}(h^{3})\\&\leq |e_{n}|+{\frac {h\gamma }{2}}\left(|e_{n+1}|+|e_{n}|\right)+{\mathcal {O}}(h^{3})\end{aligned}}$

where $\gamma \!\,$ is the Lipschitz constant of $f\!\,$. Rearranging terms we get

$|e_{n+1}|\leq \underbrace {\frac {1+{\frac {h\gamma }{2}}}{1-{\frac {h\gamma }{2}}}} _{C}|e_{n}|+{\mathcal {O}}(h^{3})\!\,$

In particular, $|e_{1}|\leq C\underbrace {|e_{0}|} _{0}+{\mathcal {O}}(h^{3})\!\,$

Then $e_{N}\!\,$ is given by

${\begin{aligned}e_{N}&=\left(C^{N-1}+C^{N-2}+\cdots +C+1\right){\mathcal {O}}(h^{3})\\&={\frac {C^{N}-1}{C-1}}{\mathcal {O}}(h^{3})\\&\leq K{\mathcal {O}}(h^{2})\end{aligned}}\!\,$

Problem 5c

Prove that $T_{n}=O(h^{3})\!\,$ for this method. (Hint: expand first $y(t_{n+1})\!\,$ and $y(t_{n})\!\,$ around $\tau _{n}=t_{n}+{\frac {h}{2}}\!\,$ and next expand $f({\frac {1}{2}}(y(t_{n+1})+y(t_{n}))).\!\,$ Also expand $y'(t)\!\,$ around $\tau _{n}\!\,$.)

Solution 5c

The midpoint method may be rewritten as follows:

$y(t_{n+1})=y(t_{n})+{\frac {h}{2}}y'(t_{n+1})+{\frac {h}{2}}y'(t_{n})+T_{n}\!\,$

which implies

$y(t_{n+1})-y(t_{n})-{\frac {h}{2}}y'(t_{n+1})-{\frac {h}{2}}y'(t_{n})=T_{n}\!\,$

Expanding each term around $\tau _{n}=t_{n}+{\frac {h}{2}}\!\,$ yields $T_{n}\!\,$.

${\begin{array}{|c|c|c|c|c|c|}{\mbox{Order }}h&y(t_{n+1})&-y(t_{n})&-{\frac {h}{2}}y'(t_{n+1})&-{\frac {h}{2}}y'(t_{n})&\Sigma \\\hline &&&&&\\0&y(t_{n}+{\frac {h}{2}})&-y(t_{n}+{\frac {h}{2}})&---&---&0\\&&&&&\\1&y'(t_{n}+{\frac {h}{2}}){\frac {h}{2}}&-y'(t_{n}+{\frac {h}{2}})(-{\frac {h}{2}})&-{\frac {h}{2}}y'(t_{n}+{\frac {h}{2}})&-{\frac {h}{2}}y'(t_{n}+{\frac {h}{2}})&0\\&&&&&\\2&{\frac {y''(t_{n}+{\frac {h}{2}})}{2}}{\frac {h^{2}}{4}}&-{\frac {y''(t_{n}+{\frac {h}{2}}}{2}}{\frac {h^{2}}{4}}&-{\frac {h}{2}}y''(t_{n}+{\frac {h}{2}}){\frac {h}{2}}&-{\frac {h}{2}}y''(t_{n}+{\frac {h}{2}})(-{\frac {h}{2}})&0\\&&&&&\\3&O(h^{3})&O(h^{3})&O(h^{3})&O(h^{3})&O(h^{3})\\\hline \end{array}}$

Problem 6

Consider the following boundary two-point boundary value problem in $(0,1)\!\,$ with $\epsilon <<1\leq b:\!\,$ $-\epsilon u_{xx}+bu_{x}=1,\quad u(0)=u(1)=0\!\,$

Problem 6a

Write the finite element method with piecewise linear elements over a uniform partition of $(0,1)\!\,$ with meshsize $h\!\,$. If $U={U_{i}}_{i=0}^{I+1}\!\,$ is the vector of nodal values of the finite element solution, find the (stiffness) matrix $A\!\,$ and right-hand side $F\!\,$ such that $AU=F\!\,$. Is $A\!\,$ symmetric? Is $A\!\,$ positive definite?

Solution 6a

Weak Variational Formulation

Multiplying the given equation by a test function $v\in H_{0}^{1}[0,1]\!\,$ and integrating from 0 to 1 gives the equivalent weak variational formulation:

Find $u\in H_{0}^{1}[0,1]\!\,$ such that for all $v\in H_{0}^{1}[0,1]\!\,$ the following holds

$\underbrace {\epsilon \int _{0}^{1}u'v'dx+b\int _{0}^{1}u'vdx} _{a(u,v)}=\underbrace {\int _{0}^{1}vdx} _{f(v)}\!\,$

Discrete Variational Formulation

Let $V_{h}=\{v\in H_{0}^{1}[0,1]:\left.v_{h}\right|_{[x_{i-1},x_{i}]}{\mbox{ linear }}\!\,$ for $i=1,2,\ldots ,n\}\!\,$

Then we have the discrete variational formulation which is an approximation to the weak variational formulation.

Find $u_{h}\in V_{h}\!\,$ such that for all $v_{h}\in V_{h}\!\,$

$a(u_{h},v_{h})=f(v_{h})\!\,$

Define basis for V_h

Let $\{\phi _{i}\}_{i=1}^{n}\!\,$ be the linear "hat" functions which defines a basis for $V_{h}\!\,$.

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

Then calculation yields the following: (draw pictures)

$\int _{0}^{1}\phi _{i}(x)dx=h\!\,$

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

$\int _{0}^{1}\phi _{i}'(x)\phi _{j}'(x)dx={\begin{cases}{\frac {2}{h}}&{\mbox{ if }}i=j\\-{\frac {1}{h}}&{\mbox{ if }}|i-j|=1\\0&{\mbox{ otherwise }}\end{cases}}\!\,$

$\int _{0}^{1}\phi _{i}(x)\phi _{j}'(x)dx={\begin{cases}0&{\mbox{ if }}i=j\\{\frac {1}{2}}&{\mbox{ if }}i-j=1\\-{\frac {1}{2}}&{\mbox{ if }}i-j=-1\\0&{\mbox{ otherwise }}\end{cases}}\!\,$

Discrete Variational Formulation in Matrix Form

Since $\{\phi _{i}\}_{i=1}^{n}\!\,$ is a basis for $V_{h}\!\,$,

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

Also, the discrete variational formulation may be expressed as

$\epsilon \sum _{i=1}^{n}u_{hi}\int _{0}^{1}\phi _{i}'(x)\phi _{j}'(x)dx+b\sum _{i=1}^{n}u_{hi}\int _{0}^{1}\phi _{i}'(x)\phi _{j}(x)dx=\int _{0}^{1}\phi _{j}(x)dx{\mbox{ for }}j=1,2,\ldots ,n\!\,$

which in matrix form is

$\underbrace {\begin{bmatrix}2{\frac {\epsilon }{h}}&-{\frac {\epsilon }{h}}+{\frac {b}{2}}&0&\cdots &\cdots &0\\-{\frac {\epsilon }{h}}-{\frac {b}{2}}&2{\frac {\epsilon }{h}}&-{\frac {\epsilon }{h}}+{\frac {b}{2}}&0&\cdots &0\\0&\ddots &\ddots &\ddots &\cdots &0\\0&\cdots &\cdots &0&-{\frac {\epsilon }{h}}-{\frac {b}{2}}&2{\frac {\epsilon }{h}}\end{bmatrix}} _{A}{\begin{bmatrix}u_{1}\\u_{2}\\\vdots \\u_{n}\end{bmatrix}}={\begin{bmatrix}h\\h\\\vdots \\h\end{bmatrix}}\!\,$

$A\!\,$ is not symmetric. $A\!\,$ is positive definite if

${\frac {\epsilon }{h}}>{\frac {b}{2}}\!\,$

Problem 6b

Find a relation between the three parameters $h,\epsilon ,b\!\,$ for $A\!\,$ to be an $M-\!\,$matrix, i.e. to have $a_{ii}>0,a_{ij}\leq 0\!\,$ if $i\neq j\!\,$ and $a_{ii}\geq -\sum _{i\neq j}a_{ij}\!\,$

Solution 6b

The first, second, and last rows all yield the same inequality for $A\!\,$ to be an $M\!\,$-matrix:

${\frac {\epsilon }{h}}>{\frac {b}{2}}\!\,$

Problem 6c

Consider the upwind modification of the ODE $-(\epsilon +{\frac {b}{2}}h)u_{xx}+bu_{x}=1\!\,$ Show that the resulting matrix $A\!\,$ is an M-matrix without restrictions on $h,\epsilon \!\,$ and $b\!\,$.

Solution 6c

Substituting $\epsilon +{\frac {b}{2}}h\!\,$ for $\epsilon \!\,$ yields the following matrix $A\!\,$:

${\begin{bmatrix}2{\frac {\epsilon }{h}}+b&-{\frac {\epsilon }{h}}&0&\cdots &\cdots &0\\-{\frac {\epsilon }{h}}-b&2{\frac {\epsilon }{h}}+b&-{\frac {\epsilon }{h}}&0&\cdots &0\\0&\ddots &\ddots &\ddots &\cdots &0\\0&\cdots &\cdots &0&-{\frac {\epsilon }{h}}-b&2{\frac {\epsilon }{h}}+b\end{bmatrix}}\!\,$

All off diagonal entries are $\leq 0\!\,$. Diagonal entries are $>0\!\,$

The first row meets the last condition since

$2{\frac {\epsilon }{h}}+b\geq {\frac {\epsilon }{h}}\!\,$

The second row through (n-1) rows meets the last condition since

$2{\frac {\epsilon }{h}}+b\geq {\frac {\epsilon }{h}}+b+{\frac {\epsilon }{b}}\!\,$

The last row meets the last condition since

$2{\frac {\epsilon }{h}}+b\geq {\frac {\epsilon }{h}}+b\!\,$