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

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

Problem 4[edit]

One wants to solve the equation , whose root is , using one or more of the following iterative methods


(i)


(ii)


(iii)


Problem 4a[edit]

Which of the three methods can be used?

Solution 4a[edit]

Methods {ii} and {iii} are appropriate fixed point iterations for


{i} is not a fixed point iteration[edit]

To be a suitable fixed point iteration, the range of each iteration must be within the domain of the next iteration. In the case of {i}, can return values in , but can only take x-values in .

{ii} and {iii} are fixed point iterations[edit]

Let and


It is clear that

and


Also notice that given domain


for some

where


and


for some

where


That is, f,g are both contractions.

Problem 4b[edit]

Which method should be used?

Solution 4b[edit]

For the interval (0,1), {iii} is a better fixed point iteration than {ii} since its Lipschitz constant is smaller.

Problem 4c[edit]

Give an even better iterative formula.

Solution 4c[edit]

Newton's method gives an iterative formula that has quadratic convergence, compared to {iii}'s linear convergence.

Problem 5[edit]

Consider the boundary value problem



Discretize the problem with a finite element method using continuous, piecewise linear functions on an equidistant grid. Quadrature is to be done with the trapezoid rule. Write the method in the form



where denoted by the vector of unknown nodal values of the approximation solutions, is an matrix whose elements are independent of the discretization parameter , and is a nonlinear vector-valued function.

Solution 5[edit]

Finding the weak form[edit]

Let .

Multiplying by a test function and integrating by parts we obtain

Then the Variational formulation is: Find such that

for all

Define piecewise linear basis functions[edit]

Let's consider a partition of the interval ,


.


As our finite element space, we take


.


For our basis of , we use the hat functions , i.e., for



Therefore,



Thus the discrete formulation reads: Find such that


.


Since is a basis for , we have


.


Then, we obtain the following equivalent discrete problem: Find such that


.

Rewrite problem in matrix form[edit]

The equivalent discrete problem for



can be rewritten in matrix form as follows:



The first integral can be computed as follows:



The second integral can be approximated using the trapezoidal rule i.e.



Notice that the boundary conditions impose that .

Problem 6[edit]

Determine the local order of accuracy and the stability properties of the two-step scheme



as an approximation for the ODE . What is its convergence rate?

Solution 6[edit]

Local Order of Accuracy[edit]

Note that . Also, denote the uniform step size as h. Hence,




Therefore, the given equation may be written as



Expand Left Hand Side Using Taylor Expansion[edit]

Expanding about , we get


Expand Right Hand Side Using Taylor Expansion[edit]

Also expanding about gives


Compare Terms to Determine Order[edit]

Taking the difference of the left and right hand side Taylor expansions show that the two step equation is of order two since the terms match up to order 2.



Notice that the order 3 term on the left hand side differs from the order 3 term on the right hand side. ()

Stability Condition[edit]

Our two-step equation is stable if the roots of the equation



Satisfy , and if , then it must be a simple root.


Since yields the roots 1 and 2, the two-step equation is not stable.

Convergence[edit]

A multi-step method is convergent if and only if it is stable and consistent. Our two-step equation is not stable, hence not guaranteed to converge.