Jump to content

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

From Wikibooks, open books for an open world

Problem 4a

[edit | edit source]

Describe Newton's method for finding a root of a smooth function


Solution 4a

[edit | edit source]

Newton's method:

Problem 4b

[edit | edit source]

Assume that is a smooth function, satisfies



and has a root . Draw a geometric picture illustrating the convergence of the method and give an analytic proof that Newton's method converges to for any initial guess

Solution 4b

[edit | edit source]

From the picture, notice that if , then after one step will be greater than . This is because from hypothesis, the function is always increasing and concave up.


Then without loss of generality assume .


Subtracting from both sides of Newton's method gives an expression for the relationship between consecutive errors.



Expanding around using Taylor expansion gives



where


Substituting this expression into (*), we have



Since and is always increasing (from hypothesis), is a positive number less than 1. Therefore the error decreases as increases which implies the method always converges.

Problem 5

[edit | edit source]

The goal of this problem is to solve the boundary value problem



in a suitable finite element space.

Problem 5a

[edit | edit source]

For , let . Define a suitable dimensional subspace in associated with the points . Let be any basis in . Explain how you can determine the coefficients in the representation element solution



by solving a linear system. Prove that there exists a unique solution

Solution 5a

[edit | edit source]

Define Suitable Subspace

[edit | edit source]


which has a basis the hat functions defined as follows:


How to Determine Coefficients

[edit | edit source]

The discrete weak variational form is given as such:


Find such that for all



Since we have a basis , we have a system of equations (that can be expressed in matrix form):


For


Existence of Unique Solution

[edit | edit source]

The existence of a unique solution follows from Lax-Milgram.


Note the following:


  • bilinear form continuous (bounded) e.g.



  • bilinear form coercive e.g.



Poincare Inequality:



Problem 5b

[edit | edit source]

Show that



defines an inner product on and thus a notion of orthogonality in

Solution 5b

[edit | edit source]




Problem 5c

[edit | edit source]

Let be the basis of the one-dimensional space . Find an orthogonal basis in that contains the basis function . Sketch the basis functions. Indicate how you would construct a basis of that contains the basis of

Solution 5c

[edit | edit source]



Define a new hat function on each new pair of adjoining subintervals. The hat functions should have all have the same height as the previous basis's hat functions.

Problem 5d

[edit | edit source]

What is the structure of the linear system in (a) for this special basis?


Solution 5d

[edit | edit source]

For our system in (a), this system yields a diagonal matrix.

Problem 6

[edit | edit source]

For solving the equation , consider the scheme



where and


Problem 6a

[edit | edit source]

Show that this scheme is fourth-order accurate.

Solution 6a

[edit | edit source]

Problem 6b

[edit | edit source]

For stability analysis, one takes . State what it means for to belong to the region of absolute stability for this scheme, and show that the region of absolute stability contains the entire negative real axis.

Solution 6b

[edit | edit source]



Letting and rearranging terms gives



If is a negative real number, then