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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Problem 4a[edit | edit source]

Show that the two-step method

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

Solution 4a[edit | edit source]

Method of Order 2[edit | edit source]

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_0[edit | edit source]


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


Taylor Expansion of y about a_0[edit | edit source]

Since , we also take Taylor Expansion of about



Substituting and simplifying yields,

Take Difference of Taylor Expansions[edit | edit source]

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

Does Not Satisfy Root Condition[edit | edit source]

The Characteristic equation of (1) is

Giving the roots

clearly does not satisfy

Problem 4b[edit | edit source]

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

Solution 4b[edit | edit source]

Let . Then . We have the difference equation



which has general solution (use the roots)



If , then as




Hence, . Therefore if , then .

Problem 5[edit | edit source]

Consider the boundary value problem


Problem 5a[edit | edit source]

Prove that has at most one solution

Solution 5a[edit | edit source]

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 5b[edit | edit source]

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 5b[edit | edit source]

The three point difference formula for is given by

Equations for i=2,...,n-2[edit | edit source]

Substituting into with our difference formula we have in matrix formulation


Equation for i=1[edit | edit source]

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-1[edit | edit source]

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

Problem 5c[edit | edit source]

Prove that the equation found in has a unique solution


Solution 5c[edit | edit source]

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

Problem 5d[edit | edit source]

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

Solution 5d[edit | edit source]

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 hemogenous boundary conditions is given by


Problem 5e[edit | edit source]

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 5e[edit | edit source]

Variational Formulation and Sobolev space[edit | edit source]

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 Solution[edit | edit source]

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

a(v,w) bounded and continuous[edit | edit source]

a(v,v) coercive[edit | edit source]

F(v) bounded[edit | edit source]

Problem 5f[edit | edit source]

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 5g[edit | edit source]

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

Solution 5[edit | edit source]

Problem 6[edit | edit source]

Let be a nonlinear function with zero :


, .


Consider the iteration

, .


Problem 6a[edit | edit source]

Prove (4) is locally convergent.

Solution 6a[edit | edit source]

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 Jacobian[edit | edit source]






Problem 6b[edit | edit source]

Show that the convergence is at least quadratic.

Solution 6b[edit | edit source]


where satisfies when .


Then, we obtain .

Problem 6c[edit | edit source]

Write the Newton iteration and compare it with (4)

Solution 6c[edit | edit source]

The Newton iteration looks like this:



Where B is the inverse of the Jacobian of f.



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