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

## Problem 4a

 Given a smooth function ${\displaystyle f(x)\!\,}$ , state the secant method for the approximate solution of nonlinear equation in ${\displaystyle \mathbb {R} \!\,}$  ${\displaystyle f(x)=0\!\,}$

## Solution 4a

${\displaystyle 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 ${\displaystyle f''(x)\!\,}$  is bounded and ${\displaystyle x_{0}\!\,}$  is close to ${\displaystyle x_{*}\!\,}$ , then the secant method has convergence order ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle h={\frac {T}{N}}\!\,}$ : ${\displaystyle y_{n+1}=y_{n}+{\frac {h}{2}}(f(t_{n+1},y_{n+1})+f(t_{n},y_{n}))\!\,}$

## Solution 5a

${\displaystyle 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 ${\displaystyle f(t,y)=\lambda y\!\,}$  with real ${\displaystyle \lambda \!\,}$ . Show that the region of absolute stability contains the entire negative real axis of the complex ${\displaystyle h\lambda \!\,}$  plane.

## Solution 5b

Letting ${\displaystyle f(t,y)=\lambda y\!\,}$ , we have

${\displaystyle y_{n+1}=y_{n}+{\frac {h}{2}}\lambda y_{n+1}+{\frac {h}{2}}\lambda y_{n}\!\,}$

If we let ${\displaystyle h\lambda =z\!\,}$ , and rearrange the equation we have

${\displaystyle y_{n+1}=\underbrace {\left({\frac {1+{\frac {z}{2}}}{1-{\frac {z}{2}}}}\right)} _{M}y_{n}\!\,}$

We require ${\displaystyle M<1\!\,}$ . This is true if ${\displaystyle \lambda \!\,}$  is a negative real number.

## Problem 5c

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

## Solution 5

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

i.e.

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

or (since ${\displaystyle A\!\,}$  is symmetric)

${\displaystyle \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)

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

or (by definition)

${\displaystyle \max _{i}\{1+{\frac {h}{2}}\lambda _{i}\}<\max _{i}\{1-{\frac {h}{2}}\lambda _{i}\}\!\,}$

If ${\displaystyle A\!\,}$  is negative definite (all its eigenvalues are negative), the above inequality holds.

## Problem 6

 Consider the following two-point boundary value problem in ${\displaystyle (0,1):\!\,}$  ${\displaystyle (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 ${\displaystyle (2)\qquad u\in H:a(u,v)=F(v),{\mbox{ for all }}v\in H\!\,}$  Define the function space ${\displaystyle H\!\,}$ , the bilinear form ${\displaystyle a\!\,}$ , and the linear functional ${\displaystyle F\!\,}$  and state the relation between ${\displaystyle (1)\!\,}$  and ${\displaystyle (2)\!\,}$ . Show that the solution ${\displaystyle u\!\,}$  is unique.

## Solution 6a

### Variational Form

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

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

${\displaystyle \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: ${\displaystyle a(u,v)\leq C\|u\|_{1}\|v\|_{1}\!\,}$

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

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

{\displaystyle {\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 ${\displaystyle P=\{x_{i}=(i-1)h\}_{i=1}^{N}\!\,}$  with meshsize ${\displaystyle h={\frac {1}{N-1}}\!\,}$ . If ${\displaystyle U=(u_{i})_{i=1}^{N}\!\,}$  is the vector of nodal values of the finite element solution, find the stiffness matrix ${\displaystyle A\!\,}$  and right hand side ${\displaystyle F\!\,}$  such that ${\displaystyle AU=F\!\,}$ . Show that ${\displaystyle A\!\,}$  is symmetric and positive definite. Show that solution ${\displaystyle U\!\,}$  is unique

## Solution 6b

Define hat functions ${\displaystyle \{\phi _{i}\}_{i=1}^{N}\!\,}$  as basis of the discrete space. Note that ${\displaystyle \phi _{0}\!\,}$  and ${\displaystyle \phi _{n}\!\,}$  have only half the support as the other basis functions. Using this basis we have

${\displaystyle \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 ${\displaystyle A\!\,}$  is symmetric. It is positive definite by Gergoshin's theorem. The solution ${\displaystyle U\!\,}$  is unique since ${\displaystyle A\!\,}$  is diagonally dominant.

## Problem 6c

 Consider two partitions ${\displaystyle P_{1}\!\,}$  and ${\displaystyle P_{2}\!\,}$  of ${\displaystyle [0,1]\!\,}$ , with ${\displaystyle P_{2}\!\,}$  a refinement of ${\displaystyle P_{1}\!\,}$ . Let ${\displaystyle V_{1}\!\,}$  and ${\displaystyle V_{2}\!\,}$  be the corresponding piecewise linear finite element spaces. Show that ${\displaystyle V_{1}\!\,}$  is a subspace of ${\displaystyle V_{2}\!\,}$

## Solution 6c

If ${\displaystyle v\in V_{1}\!\,}$  then it is also in ${\displaystyle V_{2}\!\,}$  since ${\displaystyle P_{2}\!\,}$  is a refinement of ${\displaystyle P_{1}\!\,}$ . In other words, since ${\displaystyle V_{1}\!\,}$  is piecewise linear over each intervals, it is also piecewise linear over a refinement of its interval.

## Problem 6d

 Let ${\displaystyle u_{1}\in V_{1}\!\,}$  and ${\displaystyle u_{2}\in V_{2}\!\,}$  be the finite element solutions. Show the orthogonality equality. ${\displaystyle \|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

${\displaystyle a(u-u_{h},v_{h})=0\!\,}$  for all ${\displaystyle v\in V_{h}\!\,}$

Specifically,

${\displaystyle a(u-u_{2},u_{1}-u_{2})=0\!\,}$

Then

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