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

Problem 4aEdit

Describe Newton's method for finding a root of a smooth function  

Solution 4aEdit

Newton's method:


Problem 4bEdit

Assume that   is a smooth function, satisfies


and has a root  . Draw a geometric picture illustrating the convergence of the method and give an analytic proof that Newton's method converges to   for any initial guess  

Solution 4bEdit

From the picture, notice that if  , then after one step   will be greater than  . This is because from hypothesis, the function is always increasing and concave up.

Then without loss of generality assume  .

Subtracting   from both sides of Newton's method gives an expression for the relationship between consecutive errors.


Expanding   around   using Taylor expansion gives



Substituting this expression into (*), we have


Since   and is always increasing (from hypothesis),   is a positive number less than 1. Therefore the error decreases as   increases which implies the method always converges.

Problem 5Edit

The goal of this problem is to solve the boundary value problem


in a suitable finite element space.

Problem 5aEdit

For  , let  . Define a suitable   dimensional subspace   in   associated with the points  . Let   be any basis in  . Explain how you can determine the coefficients   in the representation element solution


by solving a linear system. Prove that there exists a unique solution

Solution 5aEdit

Define Suitable SubspaceEdit


which has a basis the hat functions   defined as follows:


How to Determine CoefficientsEdit

The discrete weak variational form is given as such:

Find   such that for all  


Since we have a basis  , we have a system of equations (that can be expressed in matrix form):



Existence of Unique SolutionEdit

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

Note the following:

  • bilinear form continuous (bounded) e.g.  


  • bilinear form coercive e.g.  


Poincare Inequality:  



Problem 5bEdit

Show that


defines an inner product on   and thus a notion of orthogonality in  

Solution 5bEdit





Problem 5cEdit

Let   be the basis of the one-dimensional space  . Find an orthogonal basis in   that contains the basis function  . Sketch the basis functions. Indicate how you would construct a basis of   that contains the basis of  

Solution 5cEdit




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 5dEdit

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

Solution 5dEdit

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

Problem 6Edit

For solving the equation  , consider the scheme


where   and  

Problem 6aEdit

Show that this scheme is fourth-order accurate.

Solution 6aEdit


Problem 6bEdit

For stability analysis, one takes  . State what it means for   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 6bEdit



Letting   and rearranging terms gives


If   is a negative real number, then