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 $\mathbb {R} \!\,$ $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 $\phi ={\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'=f(t,y),\quad 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})=\int _{t_{n}}^{t_{n+1}}y'=\int _{t_{n}}^{t_{n+1}}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}=\underbrace {\left({\frac {1+{\frac {z}{2}}}{1-{\frac {z}{2}}}}\right)} _{M}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

$\left\|{\frac {1+{\frac {h}{2}}A}{1-{\frac {h}{2}}A}}\right\|<1\!\,$

i.e.

$\|1+{\frac {h}{2}}A\|<\|1-{\frac {h}{2}}A\|\!\,$

or (since $A\!\,$ is symmetric)

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

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

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

or (by definition)

$\max _{i}\{1+{\frac {h}{2}}\lambda _{i}\}<\max _{i}\{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)\qquad -u_{xx}+u=1,\quad u'(0)=u'(1)=0\!\,$

Problem 6a

Give a variation formulation of (1), i.e, express it it as $(2)\qquad u\in H:a(u,v)=F(v),{\mbox{ 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\!\,$

$\underbrace {\int _{0}^{1}u'v'+\int _{0}^{1}uv} _{a(u,v)}=\underbrace {\int _{0}^{1}v} _{F(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)\leq C\|u\|_{1}\|v\|_{1}\!\,$

• bilinear form coercive: $a(u,u)\geq 1\cdot \|u\|_{1}^{2}\!\,$

• functional bounded: $F(v)\leq \|v\|_{1}\!\,$

${\begin{aligned}\int v&=\int 1\cdot v\\&\leq \|1\|\|v\|_{0}\\&\leq \|v\|_{1}\end{aligned}}\!\,$

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 $\{\phi _{i}\}_{i=1}^{N}\!\,$ as basis of the discrete space. Note that $\phi _{0}\!\,$ and $\phi _{n}\!\,$ have only half the support as the other basis functions. Using this basis we have

$\underbrace {\begin{bmatrix}{\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{bmatrix}} _{A}\underbrace {\begin{bmatrix}u_{1}\\u_{2}\\\vdots \\u_{n}\end{bmatrix}} _{U}=\underbrace {\begin{bmatrix}{\frac {h}{2}}\\h\\\vdots \\{\frac {h}{2}}\end{bmatrix}} _{F}\!\,$

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. $\|u-u_{1}\|_{H^{1}}^{2}=\|u-u_{2}\|_{H^{1}}^{2}+\|u_{1}-u_{2}\|_{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

$\underbrace {a(u-u_{1},u-u_{1})} _{\|u-u_{1}\|_{H^{1}}^{2}}+2\underbrace {a(u-u_{2},u_{1}-u_{2})} _{0}=\underbrace {a(u-u_{2},u-u_{2})} _{\|u-u_{2}\|_{H^{1}}^{2}}+\underbrace {a(u_{1}-u_{2},u_{1}-u_{2})} _{\|u_{1}-u_{2}\|_{H^{1}}^{2}}\!\,$