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


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



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  .



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  




Discretized Form (Finite Element Formulation)Edit

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




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




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.