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


 


where  


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):


For  


 

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