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


Problem 4

edit

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 4a

edit

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

ononon

Solution 4a

edit

Fixed point iteration

edit

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 convergence

edit

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 4b

edit

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 4b

edit

Newton iteration

edit

The Newton iteration solves   and the iteration is given by


 


Let  

Conditions for local convergence

edit

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


Note that


 

Conditions for quadratic convergence

edit

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

Problem 5

edit


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


 

Problem 5a

edit

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

Solution 5a

edit

Trapezoid method (Implicit, Adams-Moulton)

edit

 

Define Local Truncation Error

edit

The local truncation error is given as follows:

 

Find Local Truncation Error Using Taylor Expansion

edit

Note that  . The uniform step size is  . Hence,


 


Therefore, the given equation may be written as


 

Expand Left Hand Side

edit

Expanding about  , we get


 

Expand Right Hand side

edit

Also expanding about   gives

 

Calculate local truncation error

edit

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

Problem 5b

edit

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

 

Solution 5b

edit

We need to show that  


Again, note that  


 

So this method is also consistency order 2.

Problem 5c

edit

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

Solution 5c

edit

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 6

edit

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 6a

edit

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 6a

edit

Weak Form

edit

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 Inequalities

edit

 


Hence we have,


 

Problem 6b

edit


If   is the Lagrange interpolant of  , then prove  . Deduce


 


Solution 6b

edit

Prove equality

edit

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 inequality

edit

Hence we have


 


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


 

Problem 6c

edit

Use (b) to derive the error estimate


 


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

Solution 6c

edit

Show inequality

edit

 

Bound Right Hand Side

edit

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.