# 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 $f:R\rightarrow R\!\,$ ## Solution 4a

Newton's method:

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\!\,$ ## Problem 4b

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

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

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

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

$\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}=\underbrace {x_{k}-x_{*}} _{e_{k}}-{\frac {f(x_{k})}{f'(x_{k})}}\qquad (*)\!\,$ Expanding $f(x_{k})\!\,$ around $f(x_{*})\!\,$ using Taylor expansion gives

$f(x_{k})=\underbrace {f(x_{*})} _{0}+f'(\xi )\underbrace {(x_{k}-x_{*})} _{e_{k}}\!\,$ where $\xi \in [x_{*},x_{k}]\!\,$ Substituting this expression into (*), we have

$e_{k+1}=(1-\underbrace {\frac {f'(\xi )}{f'(x_{k})}} _{M})e_{k}\!\,$ Since $f'(x)>0\!\,$ and is always increasing (from hypothesis), $M\!\,$ is a positive number less than 1. Therefore the error decreases as $k\!\,$ increases which implies the method always converges.

## Problem 5

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

## Problem 5a

 For $N\in \mathbb {N} \!\,$ , let $x_{i}=i/N,i=0,\ldots ,N\!\,$ . Define a suitable $N-1\!\,$ dimensional subspace $V_{N}\!\,$ in $H_{0}^{1}\!\,$ associated with the points $x_{i}\!\,$ . Let $\phi _{1},\ldots ,\phi _{N-1}\!\,$ be any basis in $V_{N}\!\,$ . Explain how you can determine the coefficients $u_{i}\!\,$ in the representation element solution $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

$V_{N}=\{v\in H_{0}^{1}[0,1]:v{\mbox{ piecewise linear}}\}\!\,$ which has a basis the hat functions $\{\phi _{i}\}_{i=1}^{N-1}\!\,$ defined as follows:

$\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 $u_{N}\in V_{N}\!\,$ such that for all $v\in V_{N}\!\,$ $\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 $\{\phi _{i}\}_{i=1}^{N-1}\!\,$ , we have a system of equations (that can be expressed in matrix form):

For $j=1,2,\ldots ,N-1\!\,$ $\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. $a(u_{N},v_{N})\leq \|u_{N}\|_{1}\|v_{N}\|_{1}\!\,$ {\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. $a(u_{N},u_{N})\geq C\|u_{N}\|_{1}^{2}\!\,$ {\begin{aligned}a(v,v)&=\int v'^{2}\\&=|v|_{1}^{2}\\&\geq C\|v\|_{1}^{2}{\mbox{ Poincare inequality}}\end{aligned}}\!\, Poincare Inequality: $\|v\|_{0}\leq \|v\|_{1}\leq C|v|_{1}\!\,$ • $F(v_{N})\leq C\|v_{N}\|_{1}\!\,$ {\begin{aligned}\int fv&\leq \|f\|_{0}\|v\|_{0}\\&\leq \|f\|_{1}\|v\|_{1}\end{aligned}}\!\, ## Problem 5b

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

• $a(u,v)=a(v,u)\!\,$ • $a(\alpha u,v)=\int \alpha u'v'=\alpha \int u'v'=\alpha a(u,v)\!\,$ • $a(u+w,v)=\int (u'+w')v'=\int u'v'+\int w'v'=a(u,v)+a(w,v)\!\,$ • $a(u,u)=\int u'^{2}\neq 0{\mbox{ if }}u\neq 0\!\,$ ## Problem 5c

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

$\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}}\!\,$ $\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}}\!\,$ $\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 $y'=f(x,y)\!\,$ , consider the scheme $y_{n+1}=y_{n}+{\frac {h}{2}}(y_{n}'+y'_{n+1})+{\frac {h^{2}}{12}}(y''_{n}-y''_{n+1})\!\,$ where $y_{n}'=f(x_{n},y_{n})\!\,$ and $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

${\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 $f(x,y)=\lambda y\!\,$ . State what it means for ${\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

$y_{n}''={\frac {d}{dx}}\lambda y+\lambda y{\frac {d}{dy}}\lambda y=\lambda ^{2}y\!\,$ $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 $z=h\lambda \!\,$ and rearranging terms gives

$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 $z\!\,$ is a negative real number, then $M<1\!\,$ 