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

  where  


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.

StabilityEdit

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

ConsistencyEdit

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

 


Hence,


 

Bound for L2 norm of wEdit

From  , we have


 


Then,


 

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.


Now,  


Then, we have obtained