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

## Problem 4a

 Describe Newton's method for finding a root of a smooth function ${\displaystyle f:R\rightarrow R\!\,}$

## Solution 4a

Newton's method:

${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\!\,}$

## Problem 4b

 Assume that ${\displaystyle f:R\rightarrow R\!\,}$ is a smooth function, satisfies ${\displaystyle f'(x)>0,\quad f''(x)>0,\quad {\mbox{ for all }}x\in R\!\,}$ and has a root ${\displaystyle x^{*}\!\,}$. Draw a geometric picture illustrating the convergence of the method and give an analytic proof that Newton's method converges to ${\displaystyle x^{*}\!\,}$ for any initial guess ${\displaystyle x_{0}\in R\!\,}$

## Solution 4b

From the picture, notice that if ${\displaystyle x_{k}, then after one step ${\displaystyle x_{k+1}\!\,}$ will be greater than ${\displaystyle x_{*}\!\,}$. This is because from hypothesis, the function is always increasing and concave up.

Then without loss of generality assume ${\displaystyle x_{k}>x_{*}\!\,}$.

Subtracting ${\displaystyle x_{*}\!\,}$ from both sides of Newton's method gives an expression for the relationship between consecutive errors.

${\displaystyle \underbrace {x_{k+1}-x_{*}} _{e_{k+1}}=\underbrace {x_{k}-x_{*}} _{e_{k}}-{\frac {f(x_{k})}{f'(x_{k})}}\qquad (*)\!\,}$

Expanding ${\displaystyle f(x_{k})\!\,}$ around ${\displaystyle f(x_{*})\!\,}$ using Taylor expansion gives

${\displaystyle f(x_{k})=\underbrace {f(x_{*})} _{0}+f'(\xi )\underbrace {(x_{k}-x_{*})} _{e_{k}}\!\,}$

where ${\displaystyle \xi \in [x_{*},x_{k}]\!\,}$

Substituting this expression into (*), we have

${\displaystyle e_{k+1}=(1-\underbrace {\frac {f'(\xi )}{f'(x_{k})}} _{M})e_{k}\!\,}$

Since ${\displaystyle f'(x)>0\!\,}$ and is always increasing (from hypothesis), ${\displaystyle M\!\,}$ is a positive number less than 1. Therefore the error decreases as ${\displaystyle k\!\,}$ increases which implies the method always converges.

## Problem 5

 The goal of this problem is to solve the boundary value problem ${\displaystyle -u''=f{\mbox{ on }}(0,1),\quad u(0)=0,u(1)=0\!\,}$ in a suitable finite element space.

## Problem 5a

 For ${\displaystyle N\in \mathbb {N} \!\,}$, let ${\displaystyle x_{i}=i/N,i=0,\ldots ,N\!\,}$. Define a suitable ${\displaystyle N-1\!\,}$ dimensional subspace ${\displaystyle V_{N}\!\,}$ in ${\displaystyle H_{0}^{1}\!\,}$ associated with the points ${\displaystyle x_{i}\!\,}$. Let ${\displaystyle \phi _{1},\ldots ,\phi _{N-1}\!\,}$ be any basis in ${\displaystyle V_{N}\!\,}$. Explain how you can determine the coefficients ${\displaystyle u_{i}\!\,}$ in the representation element solution ${\displaystyle u_{N}=\sum _{i=1}^{N-1}u_{i}\phi _{i}\!\,}$ by solving a linear system. Prove that there exists a unique solution

## Solution 5a

### Define Suitable Subspace

${\displaystyle V_{N}=\{v\in H_{0}^{1}[0,1]:v{\mbox{ piecewise linear}}\}\!\,}$

which has a basis the hat functions ${\displaystyle \{\phi _{i}\}_{i=1}^{N-1}\!\,}$ defined as follows:

${\displaystyle \phi _{i}(x)={\begin{cases}{\frac {x-x_{i-1}}{h}}&{\mbox{ for }}x\in [x_{i-1},x_{i}]\\{\frac {x_{i+1}-x}{h}}&{\mbox{ for }}x\in [x_{i},x_{i+1}]\\0&{\mbox{ otherwise}}\end{cases}}\!\,}$

### How to Determine Coefficients

The discrete weak variational form is given as such:

Find ${\displaystyle u_{N}\in V_{N}\!\,}$ such that for all ${\displaystyle v\in V_{N}\!\,}$

${\displaystyle \underbrace {\int _{0}^{1}u_{N}'v_{N}'} _{a(u_{N},v_{N})}=\underbrace {\int _{0}^{1}fv_{N}} _{F(v_{N})}\!\,}$

Since we have a basis ${\displaystyle \{\phi _{i}\}_{i=1}^{N-1}\!\,}$, we have a system of equations (that can be expressed in matrix form):

For ${\displaystyle j=1,2,\ldots ,N-1\!\,}$

${\displaystyle \sum _{i=1}^{N-1}u_{i}\int _{0}^{1}\phi _{i}\phi _{j}=\int _{0}^{1}f\phi _{j}\!\,}$

### Existence of Unique Solution

The existence of a unique solution follows from Lax-Milgram.

Note the following:

• bilinear form continuous (bounded) e.g. ${\displaystyle a(u_{N},v_{N})\leq \|u_{N}\|_{1}\|v_{N}\|_{1}\!\,}$

{\displaystyle {\begin{aligned}a(u,v)&=\int u'v'\\&\leq |u|_{1}|v|_{1}{\mbox{ Cauchy Schwartz in L2 }}\\&\leq \|u\|_{1}\|v\|_{1}{\mbox{ dominance of spaces }}\end{aligned}}\!\,}

• bilinear form coercive e.g. ${\displaystyle a(u_{N},u_{N})\geq C\|u_{N}\|_{1}^{2}\!\,}$

{\displaystyle {\begin{aligned}a(v,v)&=\int v'^{2}\\&=|v|_{1}^{2}\\&\geq C\|v\|_{1}^{2}{\mbox{ Poincare inequality}}\end{aligned}}\!\,}

Poincare Inequality: ${\displaystyle \|v\|_{0}\leq \|v\|_{1}\leq C|v|_{1}\!\,}$

• ${\displaystyle F(v_{N})\leq C\|v_{N}\|_{1}\!\,}$

{\displaystyle {\begin{aligned}\int fv&\leq \|f\|_{0}\|v\|_{0}\\&\leq \|f\|_{1}\|v\|_{1}\end{aligned}}\!\,}

## Problem 5b

 Show that ${\displaystyle a(u,v)=\int _{0}^{1}u'v'dx\!\,}$ defines an inner product on ${\displaystyle H_{0}^{1}\!\,}$ and thus a notion of orthogonality in ${\displaystyle H_{0}^{1}\!\,}$

## Solution 5b

• ${\displaystyle a(u,v)=a(v,u)\!\,}$

• ${\displaystyle a(\alpha u,v)=\int \alpha u'v'=\alpha \int u'v'=\alpha a(u,v)\!\,}$

• ${\displaystyle a(u+w,v)=\int (u'+w')v'=\int u'v'+\int w'v'=a(u,v)+a(w,v)\!\,}$

• ${\displaystyle a(u,u)=\int u'^{2}\neq 0{\mbox{ if }}u\neq 0\!\,}$

## Problem 5c

 Let ${\displaystyle \phi _{1}=1-2|x-{\frac {1}{2}}|\!\,}$ be the basis of the one-dimensional space ${\displaystyle V_{2}\!\,}$. Find an orthogonal basis in ${\displaystyle V_{4}\!\,}$ that contains the basis function ${\displaystyle \phi _{1}\!\,}$. Sketch the basis functions. Indicate how you would construct a basis of ${\displaystyle V_{2^{n}}\!\,}$ that contains the basis of ${\displaystyle V^{2^{n-1}}\!\,}$

## Solution 5c

${\displaystyle \phi _{1}={\begin{cases}2x&{\mbox{ for }}x\in [0,{\frac {1}{2}}]\\2-2x&{\mbox{ for }}x\in [{\frac {1}{2}},1]\end{cases}}\!\,}$

${\displaystyle \phi _{2}={\begin{cases}8x&{\mbox{ for }}x\in [0,{\frac {1}{4}}]\\-8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{4}},{\frac {1}{2}}]\\0&{\mbox{ otherwise }}\end{cases}}\!\,}$

${\displaystyle \phi _{3}={\begin{cases}8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{2}},{\frac {3}{4}}]\\-8(x-1)&{\mbox{ for }}x\in [{\frac {1}{4}},1]\\0&{\mbox{ otherwise }}\end{cases}}\!\,}$

Define a new hat function on each new pair of adjoining subintervals. The hat functions should have all have the same height as the previous basis's hat functions.

## Problem 5d

 What is the structure of the linear system in (a) for this special basis?

## Solution 5d

For our system in (a), this system yields a diagonal matrix.

## Problem 6

 For solving the equation ${\displaystyle y'=f(x,y)\!\,}$, consider the scheme ${\displaystyle y_{n+1}=y_{n}+{\frac {h}{2}}(y_{n}'+y'_{n+1})+{\frac {h^{2}}{12}}(y''_{n}-y''_{n+1})\!\,}$ where ${\displaystyle y_{n}'=f(x_{n},y_{n})\!\,}$ and ${\displaystyle y_{n}''=f_{x}(x_{n},y_{n})+f(x_{n},y_{n})f_{y}(x_{n},y_{n})\!\,}$

## Problem 6a

 Show that this scheme is fourth-order accurate.

## Solution 6a

${\displaystyle {\begin{array}{|c|c|c|c|c|c|c|c|}{\mbox{Order}}&y(t+h)&-y(t)&-{\frac {h}{2}}y'(t)&-{\frac {h}{2}}y'(t+h)&-{\frac {h^{2}}{12}}y''(t)&{\frac {h^{2}}{12}}y''(t+h)&\Sigma \\\hline &&&&&&&\\0&y(t)&-y(t)&0&0&0&0&0\\1&y'(t)h&0&-{\frac {h}{2}}y'(t)&-{\frac {h}{2}}y'(t)&0&0&0\\2&{\frac {y''(t)h^{2}}{2}}&0&0&-{\frac {h}{2}}y''(t)h&-{\frac {h^{2}}{12}}y''(t)&{\frac {h^{2}}{12}}y''(t)&0\\3&{\frac {y'''(t)h^{3}}{6}}&0&0&-{\frac {h}{2}}{\frac {y'''(t)}{2}}h^{2}&0&{\frac {h^{2}}{12}}y'''(t)h&0\\4&y''''(t){\frac {h^{4}}{24}}&0&0&-{\frac {h}{2}}y''''(t){\frac {h^{3}}{6}}&0&{\frac {h^{2}}{12}}y''''(t){\frac {h^{2}}{2}}&0\\5&O(h^{5})&0&0&O(h^{5})&0&O(h^{5})&O(h^{5})\\\hline \end{array}}}$

## Problem 6b

 For stability analysis, one takes ${\displaystyle f(x,y)=\lambda y\!\,}$. State what it means for ${\displaystyle {\overline {\lambda }}=h\lambda \!\,}$ to belong to the region of absolute stability for this scheme, and show that the region of absolute stability contains the entire negative real axis.

## Solution 6b

${\displaystyle y_{n}''={\frac {d}{dx}}\lambda y+\lambda y{\frac {d}{dy}}\lambda y=\lambda ^{2}y\!\,}$

${\displaystyle y_{n+1}=y_{n}+{\frac {h}{2}}\lambda y_{n}+{\frac {h}{2}}\lambda y_{n+1}+{\frac {h^{2}}{12}}[\lambda ^{2}y_{n}-\lambda ^{2}y_{n+1}]\!\,}$

Letting ${\displaystyle z=h\lambda \!\,}$ and rearranging terms gives

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

If ${\displaystyle z\!\,}$ is a negative real number, then ${\displaystyle M<1\!\,}$