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

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

Problem 4a[edit]

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


Solution 4a[edit]

Newton's method:

Problem 4b[edit]

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]

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]

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



in a suitable finite element space.

Problem 5a[edit]

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]

Define Suitable Subspace[edit]


which has a basis the hat functions defined as follows:


How to Determine Coefficients[edit]

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]

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]

Show that



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

Solution 5b[edit]




Problem 5c[edit]

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]



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]

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


Solution 5d[edit]

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

Problem 6[edit]

For solving the equation , consider the scheme



where and


Problem 6a[edit]

Show that this scheme is fourth-order accurate.

Solution 6a[edit]

Problem 6b[edit]

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]



Letting and rearranging terms gives



If is a negative real number, then