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

Problem 4aEdit

Show that the two-step method

 

is of order 2 but does not satisfy the root condition.

Solution 4aEdit

Method of Order 2Edit

Method   finds an approximation for   such that  .


Let   be the  th point of evaluation where   is the starting point and   is the step size.

Taylor Expansion of y' about a_0Edit

 


Substituting into the second term on the right hand side of   and simplifying yields


 

Taylor Expansion of y about a_0Edit

Since  , we also take Taylor Expansion of   about  


 


Substituting and simplifying yields,

 

Take Difference of Taylor ExpansionsEdit

Hence   shows that (1) is a method of order 2.

Does Not Satisfy Root ConditionEdit

The Characteristic equation of (1) is

 

Giving the roots

 
 

  clearly does not satisfy  

Problem 4bEdit

Give an example to show that the method (1) need not converge when solving  .

Solution 4bEdit

Let  . Then  . We have the difference equation


 


which has general solution (use the roots)


 


If  , then   as  


 


 


Hence,  . Therefore if  , then  .

Problem 5Edit

Consider the boundary value problem


 

Problem 5aEdit

Prove that   has at most one solution

Solution 5aEdit

Let   and   be solutions. Let  .


By subtracting the two equations and their conditions we have


 


Multiplying by test function   and integrating by parts from 0 to 1, we want to find   such that for all  


 


Let  . Then, we have


 


Since  ,  , and   are all  ,  . Hence  .

Problem 5bEdit

Discretize the problem. Take a uniform partition of  


 


Use the three point difference formula for   and the simplest difference formula for the boundary condition at  . Write the resulting system as a matrix vector equation   where  


Solution 5bEdit

The three point difference formula for   is given by

 

Equations for i=2,...,n-2Edit

Substituting into   with our difference formula we have in matrix formulation


 

Equation for i=1Edit

We can eliminate the   variable by using the approximation


 


which implies


 


Using this relationship and the three difference formula, we have


 

Equations for i=n-1Edit

Since  , we can eliminate the   variable by substituting into the n-1 equation.

 

Problem 5cEdit

Prove that the equation found in   has a unique solution


Solution 5cEdit

Since the matrix   is diagonally dominant, the system   has unique solution.

Problem 5dEdit

Transform the problem   into an equivalent problem with homogeneous boundary conditions.

Solution 5dEdit

Let  ,a solution of the boundary value problem, be represented as the sum of solutions to two different boundary value problems i.e.


  where


 


 


 


Suppose  . Then


  and   which implies   and hence


 


Substituting into  , we then have


 


which implies


 


Since  , we have  


Therefore an equivalent boundary value problem with homegenous boundary conditions is given by


 

Problem 5eEdit

Obtain the variational formulation of the problem formulated in  . Specify the Sobolev space   involved. Prove that this problem has a unique solution, which we denote by  .

Solution 5eEdit

Variational Formulation and Sobolev spaceEdit

Using the problem's notation, we want to find   such that for all  , we have


 


The above comes from integrating by parts and applying the boundary conditions.

Unique SolutionEdit

To show that   is unique, we show that the hypothesis of the Lax-Milgram Theorem are met.

a(v,w) bounded and continuousEdit

 

a(v,v) coerciveEdit

 

F(v) boundedEdit

 

Problem 5fEdit

Consider the approximation of   by piecewise linear finite elements. Define precisely the piecewise linear finite element subspace (use the partition (3)). Show that the finite element problem has a unique solution.

Problem 5gEdit

Show that   and indicate how the constant   depends on the derivatives of  .

Solution 5Edit

Problem 6Edit

Let   be a nonlinear function with zero  :


 ,  .


Consider the iteration

 ,  .


Problem 6aEdit

Prove (4) is locally convergent.

Solution 6aEdit

  is a fixed point iteration. By the contraction mapping theorem, if   is a contraction in some neighborhood of   then the iteration converges at least linearly.


We have to show there exists   such that  .


By the mean value theorem we have that  , that is   for some   in our neighborhood of  .


In particular,  , implying that   is a contraction and that the iterative method converges at least linearly.


Calculating the JacobianEdit

 


 


 


 



 

Problem 6bEdit

Show that the convergence is at least quadratic.

Solution 6bEdit

 


where   satisfies   when  .


Then, we obtain  .

Problem 6cEdit

Write the Newton iteration and compare it with (4)

Solution 6cEdit

The Newton iteration looks like this:

 


 


Where B is the inverse of the Jacobian of f.


 


That is,   in the Newton Iteration gives (4).