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

Problem 4Edit

One wants to solve the equation  , whose root is  , using one or more of the following iterative methods


(i)  


(ii)  


(iii)  


Problem 4aEdit

Which of the three methods can be used?

Solution 4aEdit

Methods {ii} and {iii} are appropriate fixed point iterations for  


{i} is not a fixed point iterationEdit

To be a suitable fixed point iteration, the range of each iteration must be within the domain of the next iteration. In the case of {i},   can return values in  , but can only take x-values in  .

{ii} and {iii} are fixed point iterationsEdit

Let   and  


It is clear that

 

and

 


Also notice that given domain  


  for some  

where  


and


  for some  

where  


That is, f,g are both contractions.

Problem 4bEdit

Which method should be used?

Solution 4bEdit

For the interval (0,1), {iii} is a better fixed point iteration than {ii} since its Lipschitz constant is smaller.

Problem 4cEdit

Give an even better iterative formula.

Solution 4cEdit

Newton's method gives an iterative formula that has quadratic convergence, compared to {iii}'s linear convergence.

Problem 5Edit

Consider the boundary value problem


 


Discretize the problem with a finite element method using continuous, piecewise linear functions on an equidistant grid. Quadrature is to be done with the trapezoid rule. Write the method in the form


 


where   denoted by the vector of unknown nodal values of the approximation solutions,   is an   matrix whose elements are independent of the discretization parameter  , and   is a nonlinear vector-valued function.

Solution 5Edit

Finding the weak formEdit

Let  .

Multiplying by a test function   and integrating by parts we obtain

 

Then the Variational formulation is: Find   such that

  for all  

Define piecewise linear basis functionsEdit

Let's consider a partition of the interval  ,


 .


As our finite element space, we take


 .


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


 


Therefore,


 


Thus the discrete formulation reads: Find   such that


 .


Since   is a basis for  , we have


 .


Then, we obtain the following equivalent discrete problem: Find   such that


  .

Rewrite problem in matrix formEdit

The equivalent discrete problem for  


 


can be rewritten in matrix form as follows:


 


The first integral can be computed as follows:


 


The second integral can be approximated using the trapezoidal rule i.e.


 


Notice that the boundary conditions impose that  .

Problem 6Edit

Determine the local order of accuracy and the stability properties of the two-step scheme


 


as an approximation for the ODE  . What is its convergence rate?

Solution 6Edit

Local Order of AccuracyEdit

Note that  . Also, denote the uniform step size   as h. Hence,


 


 


Therefore, the given equation may be written as


 


Expand Left Hand Side Using Taylor ExpansionEdit

Expanding about  , we get


 

Expand Right Hand Side Using Taylor ExpansionEdit

Also expanding about   gives


 

Compare Terms to Determine OrderEdit

Taking the difference of the left and right hand side Taylor expansions show that the two step equation is of order two since the terms match up to order 2.


 


Notice that the order 3 term on the left hand side differs from the order 3 term on the right hand side. ( )

Stability ConditionEdit

Our two-step equation is stable if the roots of the equation


 


Satisfy  , and if  , then it must be a simple root.


Since   yields the roots 1 and 2, the two-step equation is not stable.

ConvergenceEdit

A multi-step method is convergent if and only if it is stable and consistent. Our two-step equation is not stable, hence not guaranteed to converge.