# 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}}\!\,$