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

Problem 4a

Given a smooth function $f(x)$, state the secant method for the approximate solution of nonlinear equation in $ℝ$ $f(x)=0$

Solution 4a

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

Problem 4b

State the order of convergence for this method, and explain how to derive it.

Solution 4b

If $f^{″}(x)$ is bounded and $x_0$ is close to $x_{*}$, then the secant method has convergence order $\varphi =\frac{1+\sqrt{5}}{2}\approx 1.6180339887$ (the Golden ratio).

A partial proof of this can be found here

Problem 4c

Are there situations in which the order of convergence is higher? Explain your answers.

Problem 5

Consider the initial value problem $y^{\prime }=f(t,y),y(0)=y_0$

Problem 5a

Write the ODE in integral form and explain how to use the trapezoidal quadrature rule to derive the trapezoidal method with uniform time step $h=\frac{T}{N}$: $y_{n+1}=y_n+\frac{h}{2}(f(t_{n+1},y_{n+1})+f(t_n,y_n))$

Solution 5a

$y(t_{n+1})-y(t_n)=\underset{t_n}{\overset{t_{n+1}}{\int }}{y}^{\prime }=\underset{t_n}{\overset{t_{n+1}}{\int }}f(t,y)\approx \frac{h}{2}(f(t_{n+1},y_{n+1})+f(t_n,y_n))$

Problem 5b

Define the concept of absolute stability. That is, consider applying the method to the case $f(t,y)=\lambda y$ with real $\lambda$. Show that the region of absolute stability contains the entire negative real axis of the complex $h\lambda$ plane.

Solution 5b

Letting $f(t,y)=\lambda y$, we have

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

If we let $h\lambda =z$, and rearrange the equation we have

$y_{n+1}=\underset{M}{\underbrace{\left(\frac{1+\frac{z}{2}}{1-\frac{z}{2}}\right)}}{y}_n$

We require $M<1$. This is true if $\lambda$ is a negative real number.

Problem 5c

Suppose that $f(t,y)=Ay$ where $A\in R^{n\times n}$ is a symmetric matrix and $y\in R^n$. Examine the properties of $A$ which guarantee that the method is absolutely stable (Hint: study the eigenvalues of $A$).

Solution 5

We now want instead

$\Vert \frac{1+\frac{h}{2}A}{1-\frac{h}{2}A}\Vert <1$

i.e.

$\Vert 1+\frac{h}{2}A\Vert <\Vert 1-\frac{h}{2}A\Vert$

or (since $A$ is symmetric)

$\rho (I+\frac{h}{2}Q\mathrm{\Lambda }{Q}^T)<\rho (I-\frac{h}{2}Q\mathrm{\Lambda }{Q}^T)$

or (since multiplying by orthogonal matrices does not affect the norm)

$\rho (I+\frac{h}{2}\mathrm{\Lambda })<\rho (I-\frac{h}{2}\mathrm{\Lambda })$

or (by definition)

$\underset{i}{\max }\{1+\frac{h}{2}{\lambda }_i\}<\underset{i}{\max }\{1-\frac{h}{2}{\lambda }_i\}$

If $A$ is negative definite (all its eigenvalues are negative), the above inequality holds.

Problem 6

Consider the following two-point boundary value problem in $(0,1):$ $(1)-u_{xx}+u=1,u^{\prime }(0)=u^{\prime }(1)=0$

Problem 6a

Give a variation formulation of (1), i.e, express it it as $(2)u\in H:a(u,v)=F(v),\text{ for all }v\in H$ Define the function space $H$, the bilinear form $a$, and the linear functional $F$ and state the relation between $(1)$ and $(2)$. Show that the solution $u$ is unique.

Solution 6a

Variational Form

Derive the variational form by multiplying by test function $v\in H$ and integrating from 0 to 1. Use integration by parts and substitute initial conditions to then have:

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

$\underset{a(u,v)}{\underbrace{\underset{0}{\overset{1}{\int }}{u}^{\prime }{v}^{\prime }+\underset{0}{\overset{1}{\int }}uv}}=\underset{F(v)}{\underbrace{\underset{0}{\overset{1}{\int }}v}}$

Relationship between (1) and (2)

(2) is an equivalent formulation of (1) but it does not involve second derivatives.

Existence of Unique Solution

By the Lax-Milgram theorem, we have the existence of a unique solution.

• bilinear form continuous/bounded: $a(u,v)\le C\Vert u{\Vert }_1\Vert v{\Vert }_1$

• bilinear form coercive: $a(u,u)\ge 1\cdot \Vert u{\Vert }_1^2$

• functional bounded: $F(v)\le \Vert v{\Vert }_1$

$\begin{array}{cc}\int v& =\int 1\cdot v\\ & \le \Vert 1\Vert \Vert v{\Vert }_0\\ & \le \Vert v{\Vert }_1\end{array}$

Problem 6b

Write the finite element method with piecewise linear elements over a uniform partition $P=\{x_i=(i-1)h{\}}_{i=1}^N$ with meshsize $h=\frac{1}{N-1}$. If $U=(u_i{)}_{i=1}^N$ 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$. Show that $A$ is symmetric and positive definite. Show that solution $U$ is unique

Solution 6b

Define hat functions $\{{\varphi }_i{\}}_{i=1}^N$ as basis of the discrete space. Note that ${\varphi }_0$ and ${\varphi }_n$ have only half the support as the other basis functions. Using this basis we have

$\underset{A}{\underbrace{\left[\begin{array}{ccccccc}\frac{h}{3}+\frac{1}{h}& \frac{h}{6}-\frac{1}{h}& & & & & \\ \frac{h}{6}-\frac{1}{h}& \frac{2}{3}h+\frac{2}{h}& \frac{h}{6}-\frac{1}{h}& & & & \\ & \ddots & \ddots & \ddots & & & \\ & & & & & \frac{h}{6}-\frac{1}{h}& \frac{h}{3}+\frac{1}{h}\end{array}\right]}}\underset{U}{\underbrace{\left[\begin{array}{c}{u}_1\\ u_2\\ ⋮\\ u_n\end{array}\right]}}=\underset{F}{\underbrace{\left[\begin{array}{c}\frac{h}{2}\\ h\\ ⋮\\ \frac{h}{2}\end{array}\right]}}$

Observe that $A$ is symmetric. It is positive definite by Gergoshin's theorem. The solution $U$ is unique since $A$ is diagonally dominant.

Problem 6c

Consider two partitions $P_1$ and $P_2$ of $[0,1]$, with $P_2$ a refinement of $P_1$. Let $V_1$ and $V_2$ be the corresponding piecewise linear finite element spaces. Show that $V_1$ is a subspace of $V_2$

Solution 6c

If $v\in V_1$ then it is also in $V_2$ since $P_2$ is a refinement of $P_1$. In other words, since $V_1$ is piecewise linear over each intervals, it is also piecewise linear over a refinement of its interval.

Problem 6d

Let $u_1\in V_1$ and $u_2\in V_2$ be the finite element solutions. Show the orthogonality equality. $\Vert u-u_1{\Vert }_{H^1}^2=\Vert u-u_2{\Vert }_{H^1}^2+\Vert u_1-u_2{\Vert }_{H^1}^2$

Solution 6

From orthogonality of error, we have

$a(u-u_h,v_h)=0$ for all $v\in V_h$

Specifically,

$a(u-u_2,u_1-u_2)=0$

Then

$\underset{\Vert u-u_1{\Vert }_{H^1}^2}{\underbrace{a(u-u_1,u-u_1)}}+2\underset{0}{\underbrace{a(u-u_2,u_1-u_2)}}=\underset{\Vert u-u_2{\Vert }_{H^1}^2}{\underbrace{a(u-u_2,u-u_2)}}+\underset{\Vert u_1-u_2{\Vert }_{H^1}^2}{\underbrace{a(u_1-u_2,u_1-u_2)}}$

Template:BookCat