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

Problem 5aEdit

State Newton's method for the approximate solution of


 


where   is a real-valued function of the real variable  

Solution 5aEdit

 

Problem 5bEdit

State and prove a convergence result for the method.

Solution 5bEdit

 

Problem 5cEdit

What is the typical order of convergence? Are there situations in which the order of convergence is higher? Explain your answers to these questions.

Solution 5cEdit

The typical order of local convergence is quadratic.


Consider the Newton's method as a fixed point iteration i.e.:


 


Then


 


 


Expanding   around   gives an expression for the error


 


Note that if  , then we have better than quadratic convergence.

Problem 6Edit


Consider the boundary value problem

 


Problem 6aEdit

Derive a variational formulation for (1).

Solution 6aEdit

Find   such that for all  


 

Problem 6bEdit

What do we mean by Finite Element Approximation   to  

Solution 6bEdit

Let   be a partition of  . Choose a an appropriate discrete subspace   and basis functions  . Then


 


The coefficients   can be found by solving the following system of equations:


For  


 

Problem 6cEdit

State and prove an estimate for


 


Solution 6cEdit

Cea's Lemma:


 


In particular choose   to be the linear interpolant of  .


Then,


 


Alternative Solution 6cEdit

Let   be a discrete mesh of   with step size  . Consider the following integral

 .

For some  ,   as   is just a linear interpolation on this interval. Hence

 .

Similarly, we can bound the   norm of the error in the derivatives with  . With   such intervals we have

 

Problem 6dEdit

Prove the formula


 

Solution 6dEdit

 

Problem 7Edit

Consider the initial value problem


 


where   satisfies the Lipschitz condition


 


for all  . A numerical method called the midpoint rule for solving this problem is defined by


 


where   is a time step and   for  . Here   is given and   is presumed to be computed by some other method.

Problem 7aEdit

Suppose the problem is posed on a finite interval   where  . Show directly,i.e., without citing any major results, that the midpoint rule is stable. That is show that if   and   satisfy


 


then there exists a constant   independent of   such that


 


for  

Solution 7aEdit

 


Subtracting both equations, letting  , and applying the Lipschitz property yields,


 


Therefore,


 

Problem 7bEdit

Suppose instead we are interested in the long term behavior of the midpoint rule applied to a particular example  . That is, let   be fixed and let   so that the rule is applied over a long time interval. Show that in this case the midpoint rule does not produce an accurate approximation to the solution to the initial value problem.

Solution 7bEdit

Substituting into the midpoint rule we have,


 


or


 


The solution of this equation is given by


 


where   or the roots of the quadratic


 


The quadratic formula yields


 


If   is a small negative number, than one of the roots will be greater than 1. Hence,   as   instead of converging to zero since  .