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.





Suppose  . Then

  and   which implies   and hence


Substituting into  , we then have


which implies


Since  , we have  

Therefore an equivalent boundary value problem with hemogenous 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).