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


Problem 4Edit

Consider the problem of solving a nonlinear system of ODE


 


by an implicit method. The  -th step consists of solving for the unknown   a non-linear algebraic system of the form


 


where   is known,   and   is the stepsize. Let  

Problem 4aEdit

Write   as a fixed point iteration and find conditions in   and   that local convergence for this iteration

ononon

Solution 4aEdit

Fixed point iterationEdit

Equation   is conveniently in fixed point iteration form.


 


Notice that the right hand side is only a function of   since   are fixed when solving for the fixed point   where  


Also note that   is the fixed point iteration index.

Conditions for local convergenceEdit

The fixed point iteration will converge when the norm of the Jacobian of   is less than 1 i.e.


 


Since  , we equivalently have the condition


 

Problem 4bEdit

Write the Newton iteration for   and give conditions on   and   that guarantee local convergence for this iteration. State precise additional assumptions on   that guarantee quadratic convergence

Solution 4bEdit

Newton iterationEdit

The Newton iteration solves   and the iteration is given by


 


Let  

Conditions for local convergenceEdit

If   exists, i.e.   is invertible or equivalently non-singular, then local convergence is guaranteed.


Note that


 

Conditions for quadratic convergenceEdit

If   is Lipschitz, then we have quadratic convergence and   is twice continuously differentiable in a neighborhood of the root

Problem 5Edit


This problem is about choosing between a specific single-step and a specific multi-step methods for solving ODE:


 

Problem 5aEdit

Write the trapezoid method, define its local truncation error and estimate it.

Solution 5aEdit

Trapezoid method (Implicit, Adams-Moulton)Edit

 

Define Local Truncation ErrorEdit

The local truncation error is given as follows:

 

Find Local Truncation Error Using Taylor ExpansionEdit

Note that  . The uniform step size is  . Hence,


 


Therefore, the given equation may be written as


 

Expand Left Hand SideEdit

Expanding about  , we get


 

Expand Right Hand sideEdit

Also expanding about   gives

 

Calculate local truncation errorEdit

Since the order 3 terms of   do not agree ( ), the error is of order  .

Problem 5bEdit

Show that the truncation error for the following multistep method is of the same order as in (a):

 

Solution 5bEdit

We need to show that  


Again, note that  


 

So this method is also consistency order 2.

Problem 5cEdit

What could be said about the global convergence rate for these two methods? Justify your conclusions for both methods.

Solution 5cEdit

The trapezoid is stable because its satisfies the root condition. (The root of the characteristic equation is 1 and has a simple root)


The second method is not stable because the characteristic equation has a double root of 1.


Both the trapezoid method and second method are consistent with order  


Note that convergence occurs if and only the method is both stable and consistent.


Therefore, the trapezoid method converges in general but the second method does not. mkmkmkmlmklml

Problem 6Edit

Consider the boundary value problem

 

where   is constant. Let   be a uniform meshsize  .

Let

 

be the corresponding finite element space, and let   be the corresponding finite element solution of (2). Note that   is a projection operator, the Ritz projector, onto the finite dimensional space   with respect to the element scalar product   induced by problem (2).


Problem 6aEdit

Let   be the  -seminorm, namely   for all  . Find the constant   in terms of the parameter   such that


 


Hint: recall the Poincare inequality   for all   where   denotes the  -norm

Solution 6aEdit

Weak FormEdit

Integrating by parts gives, for all  


 


Specifically,


 

Discretized Form (Finite Element Formulation)Edit

Similarly, the finite element formulation is find   such that for all  


 


Specifically,


 

Equate Both Sides and Apply InequalitiesEdit

 


Hence we have,


 

Problem 6bEdit


If   is the Lagrange interpolant of  , then prove  . Deduce


 


Solution 6bEdit

Prove equalityEdit

We have for all  


 


Specifically, for all  


 


The discrete form of the energy scalar product is for all  


 


Subtracting equation (2) from equation (1), we have


 


Let  . Note that by hypothesis  . Then,


 


By ellipticity,


 


which implies


 


i.e.


 

Deduce inequalityEdit

Hence we have


 


Arguing as we did in part (a), we have


 

Problem 6cEdit

Use (b) to derive the error estimate


 


and bound the right hand side by suitable power of  . Make explicit the required regularity of  

Solution 6cEdit

Show inequalityEdit

 

Bound Right Hand SideEdit

For  , Newton's polynomial interpolation error gives for some  

 


Therefore the error on the entire interval is given by


 


which implies


 


  needs to be twice differentiable.