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

Problem 4

Let $f:R^n\to 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(k\ge 0)(1)$ where $0\le {\alpha }_k\le 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)(2)$

Problem 4a

Write the steepest descent method (or gradient) method and show that there exist $0<{\alpha }_k\le 1$ such that the resulting method satisfies (2)

Solution 4a

Steepest Descent Method

$x_{k+1}=x_k-{\alpha }_k\mathrm{\nabla }f(x_k)$

Choose ${\alpha }_k\in (0,1]$ such that ${\alpha }_k$ minimizes $f(x_k-{\alpha }_k\mathrm{\nabla }f(x_k))$ i.e.

${\alpha }_k:\underset{0<{\alpha }_k\le 1}{\min }f(x_k-{\alpha }_k\mathrm{\nabla }f(x_k))$

Directional Derivative Negative

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

${\mathrm{\nabla }}_{d_k}f(x_k)=\underset{{\alpha }_k\to 0}{\lim }\frac{f(x_k+{\alpha }_k{d}_k)-f(x_k)}{{\alpha }_k}<0$

which implies

$\underset{f(x_{k+1})}{\underbrace{f(x_k+{\alpha }_k{d}_k)}}<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))\mathrm{\nabla }f(x_k)$

Directional Derivative Negative

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

${\mathrm{\nabla }}_{{\alpha }_k{d}_k}f(x_k)=\mathrm{\nabla }f(x_k)\cdot {\alpha }_k{d}_k=-\mathrm{\nabla }f(x_k)\cdot H^{-1}(f(x_k))\mathrm{\nabla }f(x_k)<0$

which implies

$\mathrm{\nabla }f(x_k{)}^T{H}^{-1}(f(x_k))\mathrm{\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\ge 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,\dots ,n$ be the eigenvalues of $H(f(x_k))$.

Then ${\lambda }_i+{\gamma }_k\cdot 1$, $i=1,2,\dots ,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,\dots ,n$

${\lambda }_i+{\gamma }_k>0$

i.e.

${\gamma }_k>-{\lambda }_{i}i=1,2,\dots ,n$

Problem 5

Consider the following nonlinear autonomous initial value problem in $R$ with $f\in C^2$. $y^{\prime }=f(y)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)=\underset{x_n}{\overset{x_{n+1}}{\int }}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{array}{cc}|e_{n+1}|& =|y(t_{n+1})-y_{n+1}|\\ & \le |y(t_n)-y_n|+h\underset{\le \frac{\gamma }{2}|y(t_{n+1})-y(t_n)-y_{n+1}+y_n|}{\underbrace{|f\left(\frac{y(t_{n+1})-y(t_n)}{2}\right)-f\left(\frac{y_{n+1}-y_n}{2}\right)|}}+𝒪(h^3)\\ & \le |e_n|+\frac{h\gamma }{2}(|e_{n+1}|+|e_n|)+𝒪(h^3)\end{array}$

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

$|e_{n+1}|\le \underset{C}{\underbrace{\frac{1+\frac{h\gamma }{2}}{1-\frac{h\gamma }{2}}}}|e_n|+𝒪(h^3)$

In particular, $|e_1|\le C\underset{0}{\underbrace{|e_0|}}+𝒪(h^3)$

Then $e_N$ is given by

$\begin{array}{cc}{e}_N& =(C^{N-1}+C^{N-2}+\cdots +C+1)𝒪(h^3)\\ & =\frac{C^N-1}{C-1}𝒪(h^3)\\ & \le K𝒪(h^2)\end{array}$

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^{\prime }(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}^{\prime }(t_{n+1})+\frac{h}{2}{y}^{\prime }(t_n)+T_n$

which implies

$y(t_{n+1})-y(t_n)-\frac{h}{2}{y}^{\prime }(t_{n+1})-\frac{h}{2}{y}^{\prime }(t_n)=T_n$

Expanding each term around ${\tau }_n=t_n+\frac{h}{2}$ yields $T_n$.

$\begin{array}{cccccc}\text{Order }h& y(t_{n+1})& -y(t_n)& -\frac{h}{2}{y}^{\prime }(t_{n+1})& -\frac{h}{2}{y}^{\prime }(t_n)& \mathrm{\Sigma }\\ & & & & & \\ 0& y(t_n+\frac{h}{2})& -y(t_n+\frac{h}{2})& ---& ---& 0\\ & & & & & \\ 1& y^{\prime }(t_n+\frac{h}{2})\frac{h}{2}& -y^{\prime }(t_n+\frac{h}{2})(-\frac{h}{2})& -\frac{h}{2}{y}^{\prime }(t_n+\frac{h}{2})& -\frac{h}{2}{y}^{\prime }(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)\end{array}$

Problem 6

Consider the following boundary two-point boundary value problem in $(0,1)$ with $ϵ<<1\le b:$ $-ϵu_{xx}+b{u}_x=1,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

$\underset{a(u,v)}{\underbrace{ϵ\underset{0}{\overset{1}{\int }}{u}^{\prime }{v}^{\prime }dx+b\underset{0}{\overset{1}{\int }}{u}^{\prime }vdx}}=\underset{f(v)}{\underbrace{\underset{0}{\overset{1}{\int }}vdx}}$

Discrete Variational Formulation

Let $V_h=\{v\in H_0^1[0,1]:{v_h|}_{[x_{i-1},x_i]}\text{ linear }$ for $i=1,2,\dots ,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 $\{{\varphi }_i{\}}_{i=1}^n$ be the linear "hat" functions which defines a basis for $V_h$.

${\varphi }_i(x)=\{\begin{array}{cc}\frac{x-x_{i-1}}{h}& \text{ if }x\in [x_{i-1},x_i]\\ \frac{x_{i+1}-x}{h}& \text{ if }x\in [x_i,x_{i+1}]\\ 0& \text{ otherwise }\end{array}$

Then calculation yields the following: (draw pictures)

$\underset{0}{\overset{1}{\int }}{\varphi }_i(x)dx=h$

${{\varphi }_i}^{\prime }(x)=\{\begin{array}{cc}\frac{1}{h}& \text{ if }x\in [x_{i-1},x_i]\\ -\frac{1}{h}& \text{ if }x\in [x_i,x_{i+1}]\\ 0& \text{ otherwise }\end{array}$

$\underset{0}{\overset{1}{\int }}{{\varphi }_i}^{\prime }(x){{\varphi }_j}^{\prime }(x)dx=\{\begin{array}{cc}\frac{2}{h}& \text{ if }i=j\\ -\frac{1}{h}& \text{ if }|i-j|=1\\ 0& \text{ otherwise }\end{array}$

$\underset{0}{\overset{1}{\int }}{\varphi }_i(x){{\varphi }_j}^{\prime }(x)dx=\{\begin{array}{cc}0& \text{ if }i=j\\ \frac{1}{2}& \text{ if }i-j=1\\ -\frac{1}{2}& \text{ if }i-j=-1\\ 0& \text{ otherwise }\end{array}$

Discrete Variational Formulation in Matrix Form

Since $\{{\varphi }_i{\}}_{i=1}^n$ is a basis for $V_h$,

$u_h=\sum _{i=1}^n{u}_{hi}{\varphi }_i$

Also, the discrete variational formulation may be expressed as

$ϵ\sum _{i=1}^n{u}_{hi}\underset{0}{\overset{1}{\int }}{{\varphi }_i}^{\prime }(x){{\varphi }_j}^{\prime }(x)dx+b\sum _{i=1}^n{u}_{hi}\underset{0}{\overset{1}{\int }}{{\varphi }_i}^{\prime }(x){\varphi }_j(x)dx=\underset{0}{\overset{1}{\int }}{\varphi }_j(x)dx\text{ for }j=1,2,\dots ,n$

which in matrix form is

$\underset{A}{\underbrace{\left[\begin{array}{cccccc}2\frac{ϵ}{h}& -\frac{ϵ}{h}+\frac{b}{2}& 0& \cdots & \cdots & 0\\ -\frac{ϵ}{h}-\frac{b}{2}& 2\frac{ϵ}{h}& -\frac{ϵ}{h}+\frac{b}{2}& 0& \cdots & 0\\ 0& \ddots & \ddots & \ddots & \cdots & 0\\ 0& \cdots & \cdots & 0& -\frac{ϵ}{h}-\frac{b}{2}& 2\frac{ϵ}{h}\end{array}\right]}}\left[\begin{array}{c}{u}_1\\ u_2\\ ⋮\\ u_n\end{array}\right]=\left[\begin{array}{c}h\\ h\\ ⋮\\ h\end{array}\right]$

$A$ is not symmetric. $A$ is positive definite if

$\frac{ϵ}{h}>\frac{b}{2}$

Problem 6b

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

Solution 6b

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

$\frac{ϵ}{h}>\frac{b}{2}$

Problem 6c

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

Solution 6c

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

$\left[\begin{array}{cccccc}2\frac{ϵ}{h}+b& -\frac{ϵ}{h}& 0& \cdots & \cdots & 0\\ -\frac{ϵ}{h}-b& 2\frac{ϵ}{h}+b& -\frac{ϵ}{h}& 0& \cdots & 0\\ 0& \ddots & \ddots & \ddots & \cdots & 0\\ 0& \cdots & \cdots & 0& -\frac{ϵ}{h}-b& 2\frac{ϵ}{h}+b\end{array}\right]$

All off diagonal entries are $\le 0$. Diagonal entries are $>0$

The first row meets the last condition since

$2\frac{ϵ}{h}+b\ge \frac{ϵ}{h}$

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

$2\frac{ϵ}{h}+b\ge \frac{ϵ}{h}+b+\frac{ϵ}{b}$

The last row meets the last condition since

$2\frac{ϵ}{h}+b\ge \frac{ϵ}{h}+b$