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

Problem 4Edit

Let  , suppose   and assume   is nonsingular . Consider the following iteration

 

Problem 4aEdit

Derive the following error equation for  

 

Solution 4aEdit

Note the following identity

 


The error   is given by

 

Problem 4bEdit

Let   be a fixed matrix. Find conditions on B that guarentee local convergence. What rate of convergence do you expect and why?

Solution 4bEdit

Assume   is invertible,   is bounded, and   is Lipschitz.

 


This implies local superlinear convergence.

Problem 4cEdit

Find sufficient conditions on   for the convergence to be superlinear. What choice of   corresponds to the Newton method and what rate of convergence do you expect?

Solution 4cEdit

Super linear convergenceEdit

  as  

Find condition for super linear convergenceEdit

From part(b)


 


Since  , if


 


as  , we have super linear convergence i.e.


 

Problem 5Edit

Let   be uniformly Lipschitz with respect to  . Let   be the solution to the initial value problem :  . Consider the trapezoid method

 .

Problem 5aEdit

Find a condition on the stepsize   that ensures (1) can be solved uniquely for  .

Solution 5aEdit

The implicit method can be viewed as a fix point iteration:


 


We want  


which implies


 

Problem 5bEdit

Define a local truncation error and estimate it. Examine the additional regularity of   needed for this estimate.

Solution 5bEdit

Re-writing (1) and replacing   we have a formula for consistency of order p:


 


For uniform stepsize h

 

Expanding in Taylor Series about   gives

Problem 5cEdit

Prove a global error estimate for (1)

Solution 5cEdit

Problem 6Edit

Consider the 2-point boundary value problem

 ,

with   constants and  . Let   be a uniform partition of [0,1] with meshsize  .

Problem 6aEdit

Use centered finite differences to discretize (2). Write the system as

 

and identify  . Prove that A is nonsingular.

Solution 6aEdit

Using Taylor Expansions, we can approximate the second derivative as follows


 


We can eliminate two equations from the n+2 equations by substituting the initial conditions   into the equations for   and   respectively.


We then have the system


 


  is nonsingular since it is diagonally dominant.

Problem 6bEdit

Define truncation error and derive a bound for this method in terms of  . State without proof an error estimate of the form

 

and specify the order s.

Solution 6bEdit

Local Truncation ErrorEdit

 

Bound for Local Truncation ErrorEdit

 

Derive Bound for Max ErrorEdit

Let  ,  , and   is the local truncation error.


Then


 


Subtracting the two last equations gives


 


Hence,


 

 , that is the error has order 2.

Problem 6cEdit

Prove the following discrete monotonicity property: If   is the solution corresponding to a forcing  , for  , and   then   componentwise.

Solution 6cEdit

Note that   is a   matrix and hence the discrete maximum principle applies. (See January 05 667 test for definition of   matrix)


Discrete Maximum PrincipleEdit

 


If  , then  .


Specifically let  , then   which implies