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

Problem 4Edit

Consider the system


Problem 4aEdit

Show that if the parameter   is chosen sufficiently small, then this system has a unique solution   within some rectangular region.

Solution 4aEdit

The system of equations may be expressed in matrix notation.


The Jacobian of  ,  , is computed using partial deriatives


If   is sufficiently small and   are restricted to a bounded region  ,


From the mean value theorem, for  , there exists   such that


Since   is bounded in the region   give sufficiently small  


Therefore,   is a contraction and from the contraction mapping theorem there exists an unique fixed point (solution) in a rectangular region.

Problem 4bEdit

Derive a fixed point iteration scheme for solving the system and show that it converges.  

Solution 4bEdit

Use Newton MethodEdit

To solve this problem, we can use the Newton Method. In fact, we want to find the zeros of


The Jacobian of  ,  , is computed using partial deriatives


Then, the Newton method for solving this linear system of equations is given by


Show convergence by showing Newton hypothesis holdEdit

Jacobian of g is LipschitzEdit

We want to show that   is a Lipschitz function. In fact,


and now, using that   is Lipschitz, we have


Jacobian of g is invertibleEdit

Since   is a contraction, the spectral radius of the Jacobian of   is less than 1 i.e.


On the other hand, we know that the eigenvalues of   are  .

Then, it follows that   or equivalently   is invertible.

inverse of Jacobian of g is boundedEdit


Since   exists,  . Given a bounded region (bounded  ), each entry of the above matrix is bounded. Therefore the norm is bounded.

norm of (Jacobian of g)^-1 (x_0) * g(x_0) boundedEdit

  since   and   is bounded.

Then, using a good enough approximation  , we have that the Newton's method is at least quadratically convergent, i.e,


Problem 5aEdit

Outline the derivation of the Adams-Bashforth methods for the numerical solution of the initial value problem  .

Solution 5aEdit

We want to solve the following initial value problem:  .

First, we integrate this expression over  , to obtain


To approximate the integral on the right hand side, we approximate its integrand   using an appropriate interpolation polynomial of degree   at  .

This idea generates the Adams-Bashforth methods.


where,   denotes the approximated solution,   and   denotes the associated Lagrange polynomial.

Problem 5bEdit

Derive the Adams-Bashforth formula


Solution 5bEdit

From (a) we have


Then if we let  , where h is the fixed step size we get



So we have the Adams-Bashforth method as desired


Problem 5cEdit

Analyze the method (1). To be specific, find the local truncation error, prove convergence and find the order of convergence.

Solution 5cEdit

Find Local Truncation Error Using Taylor ExpansionEdit

Note that  . Also, denote the uniform step size   as h. 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


Show Convergence by Showing Stability and ConsistencyEdit

A method is convergent if and only if it is both stable and consistent.


It is easy to show that the method is zero stable as it satisfies the root condition. So stable.


Truncation error is of order 2. Truncation error tends to zero as h tends to zeros. So the method is consistent.

Order of ConvergenceEdit

Dahlquist principle: consistency + stability = convergent. Order of convergence will be 2.

Problem 6Edit

Consider the problem


Problem 6aEdit

Give a variational formulation of (2), i.e. express (2) as


Define the Space H, the bilinear form B and the linear functional F, and state the relation between (2) and (3).

Solution 6aEdit

Multiplying (2) by a test function and using integration by parts we obtain:



Thus, the weak form or variational form associated with the problem (2) reads as follows: Find   such that

  for all  

where  .

Problem 6bEdit

Let   be a mesh on   with  , and let


Define the finite element approximation,   based on the approximation space  . What can be said about   the error on the Sobolev norm on  ?

Solution 6bEdit

Define piecewise linear basisEdit

For our basis of  , we use the set of hat functions  , i.e., for  


Define u_hEdit

Since   is a basis for  , and   we have


Discrete ProblemEdit

Now, we can write the discrete problem: Find   such that

  for all  

If we consider that   is a basis of   and the linearity of the bilinear form   and the functional  , we obtain the equivalent problem:

Find   such that


This last problem can be formulated as a matrix problem as follows:

Find   such that


where   and  .

Bound errorEdit

In general terms, we can use Cea's Lemma to obtain


In particular, we can consider   as the Lagrange interpolant, which we denote by  . Then,


It's easy to prove that the finite element solution is nodally exact. Then it coincides with the Lagrange interpolant, and we have the following punctual estimation:


Problem 6cEdit

Derive the estimate for  , the error in  . Hint: Let w solve

(#) : 

We characterize   variationally as


Let   to get


Use formula (4) to estimate  .

Solution 6cEdit

Continuity of Bilinear FormEdit


Orthogonality of the ErrorEdit


Bound for L2 norm of wEdit




Bound for L2 norm of wEdit

From  , we have




Bound L2 ErrorEdit


Finally, from (#), we have that  . Then,


or equivalently,


Problem 6dEdit

Suppose   is a basis for  . Show that


where   is the stiffness matrix.

Solution 6dEdit

We know that


where the substitution in the last lines come from the orthogonality of error.


Then, we have obtained