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

Problem 4aEdit

Given a smooth function  , state the secant method for the approximate solution of nonlinear equation in  


 

Solution 4aEdit

 

Problem 4bEdit

State the order of convergence for this method, and explain how to derive it.

Solution 4bEdit

If   is bounded and   is close to  , then the secant method has convergence order   (the Golden ratio).

A partial proof of this can be found here

Problem 4cEdit

Are there situations in which the order of convergence is higher? Explain your answers.

Solution 4cEdit

Problem 5Edit

Consider the initial value problem


 


Problem 5aEdit

Write the ODE in integral form and explain how to use the trapezoidal quadrature rule to derive the trapezoidal method with uniform time step  :


 

Solution 5aEdit

 

Problem 5bEdit

Define the concept of absolute stability. That is, consider applying the method to the case   with real  . Show that the region of absolute stability contains the entire negative real axis of the complex   plane.

Solution 5bEdit

Letting  , we have


 


If we let  , and rearrange the equation we have


 


We require  . This is true if   is a negative real number.

Problem 5cEdit

Suppose that   where   is a symmetric matrix and  . Examine the properties of   which guarantee that the method is absolutely stable (Hint: study the eigenvalues of  ).

Solution 5Edit

We now want instead

 


i.e.


 


or (since   is symmetric)


 


or (since multiplying by orthogonal matrices does not affect the norm)


 


or (by definition)


 


If   is negative definite (all its eigenvalues are negative), the above inequality holds.

Problem 6Edit

Consider the following two-point boundary value problem in  


 

Problem 6aEdit

Give a variation formulation of (1), i.e, express it it as

 


Define the function space  , the bilinear form  , and the linear functional   and state the relation between   and  . Show that the solution   is unique.

Solution 6aEdit

Variational FormEdit

Derive the variational form by multiplying by test function   and integrating from 0 to 1. Use integration by parts and substitute initial conditions to then have:


Find   such that for all  


 


Relationship between (1) and (2)Edit

(2) is an equivalent formulation of (1) but it does not involve second derivatives.


Existence of Unique SolutionEdit

By the Lax-Milgram theorem, we have the existence of a unique solution.


  • bilinear form continuous/bounded:  


  • bilinear form coercive:  


  • functional bounded:  


 

Problem 6bEdit

Write the finite element method with piecewise linear elements over a uniform partition   with meshsize  . If   is the vector of nodal values of the finite element solution, find the stiffness matrix   and right hand side   such that  . Show that   is symmetric and positive definite. Show that solution   is unique

Solution 6bEdit

Define hat functions   as basis of the discrete space. Note that   and   have only half the support as the other basis functions. Using this basis we have


 


Observe that   is symmetric. It is positive definite by Gergoshin's theorem. The solution   is unique since   is diagonally dominant.

Problem 6cEdit

Consider two partitions   and   of  , with   a refinement of  . Let   and   be the corresponding piecewise linear finite element spaces. Show that   is a subspace of  

Solution 6cEdit

If   then it is also in   since   is a refinement of  . In other words, since   is piecewise linear over each intervals, it is also piecewise linear over a refinement of its interval.

Problem 6dEdit

Let   and   be the finite element solutions. Show the orthogonality equality.


 

Solution 6Edit

From orthogonality of error, we have


  for all  


Specifically,


 


Then