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