Jump to content

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

From Wikibooks, open books for an open world

Problem 4

[edit | edit source]

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


(i)


(ii)


(iii)


Problem 4a

[edit | edit source]

Which of the three methods can be used?

Solution 4a

[edit | edit source]

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


{i} is not a fixed point iteration

[edit | edit source]

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

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

Which method should be used?

Solution 4b

[edit | edit source]

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

Problem 4c

[edit | edit source]

Give an even better iterative formula.

Solution 4c

[edit | edit source]

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

Problem 5

[edit | edit source]

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

Finding the weak form

[edit | edit source]

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

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

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

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

Local Order of Accuracy

[edit | edit source]

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

Expanding about , we get


Expand Right Hand Side Using Taylor Expansion

[edit | edit source]

Also expanding about gives


Compare Terms to Determine Order

[edit | edit source]

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

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

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.