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

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


Problem 4[edit]

Consider the problem of solving a nonlinear system of ODE



by an implicit method. The -th step consists of solving for the unknown a non-linear algebraic system of the form



where is known, and is the stepsize. Let

Problem 4a[edit]

Write as a fixed point iteration and find conditions in and that local convergence for this iteration

ononon

Solution 4a[edit]

Fixed point iteration[edit]

Equation is conveniently in fixed point iteration form.



Notice that the right hand side is only a function of since are fixed when solving for the fixed point where


Also note that is the fixed point iteration index.

Conditions for local convergence[edit]

The fixed point iteration will converge when the norm of the Jacobian of is less than 1 i.e.



Since , we equivalently have the condition


Problem 4b[edit]

Write the Newton iteration for and give conditions on and that guarantee local convergence for this iteration. State precise additional assumptions on that guarantee quadratic convergence

Solution 4b[edit]

Newton iteration[edit]

The Newton iteration solves and the iteration is given by



Let

Conditions for local convergence[edit]

If exists, i.e. is invertible or equivalently non-singular, then local convergence is guaranteed.


Note that


Conditions for quadratic convergence[edit]

If is Lipschitz, then we have quadratic convergence and is twice continuously differentiable in a neighborhood of the root

Problem 5[edit]


This problem is about choosing between a specific single-step and a specific multi-step methods for solving ODE:


Problem 5a[edit]

Write the trapezoid method, define its local truncation error and estimate it.

Solution 5a[edit]

Trapezoid method (Implicit, Adams-Moulton)[edit]

Define Local Truncation Error[edit]

The local truncation error is given as follows:

Find Local Truncation Error Using Taylor Expansion[edit]

Note that . The uniform step size is . Hence,



Therefore, the given equation may be written as


Expand Left Hand Side[edit]

Expanding about , we get


Expand Right Hand side[edit]

Also expanding about gives

Calculate local truncation error[edit]

Since the order 3 terms of do not agree (), the error is of order .

Problem 5b[edit]

Show that the truncation error for the following multistep method is of the same order as in (a):

Solution 5b[edit]

We need to show that


Again, note that


So this method is also consistency order 2.

Problem 5c[edit]

What could be said about the global convergence rate for these two methods? Justify your conclusions for both methods.

Solution 5c[edit]

The trapezoid is stable because its satisfies the root condition. (The root of the characteristic equation is 1 and has a simple root)


The second method is not stable because the characteristic equation has a double root of 1.


Both the trapezoid method and second method are consistent with order


Note that convergence occurs if and only the method is both stable and consistent.


Therefore, the trapezoid method converges in general but the second method does not. mkmkmkmlmklml

Problem 6[edit]

Consider the boundary value problem

where is constant. Let be a uniform meshsize .

Let

be the corresponding finite element space, and let be the corresponding finite element solution of (2). Note that is a projection operator, the Ritz projector, onto the finite dimensional space with respect to the element scalar product induced by problem (2).


Problem 6a[edit]

Let be the -seminorm, namely for all . Find the constant in terms of the parameter such that



Hint: recall the Poincare inequality for all where denotes the -norm

Solution 6a[edit]

Weak Form[edit]

Integrating by parts gives, for all



Specifically,


Discretized Form (Finite Element Formulation)[edit]

Similarly, the finite element formulation is find such that for all



Specifically,


Equate Both Sides and Apply Inequalities[edit]


Hence we have,


Problem 6b[edit]


If is the Lagrange interpolant of , then prove . Deduce



Solution 6b[edit]

Prove equality[edit]

We have for all



Specifically, for all



The discrete form of the energy scalar product is for all



Subtracting equation (2) from equation (1), we have



Let . Note that by hypothesis . Then,



By ellipticity,



which implies



i.e.


Deduce inequality[edit]

Hence we have



Arguing as we did in part (a), we have


Problem 6c[edit]

Use (b) to derive the error estimate



and bound the right hand side by suitable power of . Make explicit the required regularity of

Solution 6c[edit]

Show inequality[edit]

Bound Right Hand Side[edit]

For , Newton's polynomial interpolation error gives for some


Therefore the error on the entire interval is given by



which implies



needs to be twice differentiable.