Describe Newton's method for finding a root of a smooth function
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
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
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.
The goal of this problem is to solve the boundary value problem
in a suitable finite element space.
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
Define Suitable Subspace
which has a basis the hat functions defined as follows:
How to Determine Coefficients
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):
Existence of Unique Solution
The existence of a unique solution follows from Lax-Milgram.
Note the following:
- bilinear form continuous (bounded) e.g.
- bilinear form coercive e.g.
defines an inner product on and thus a notion of orthogonality in
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
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.
What is the structure of the linear system in (a) for this special basis?
For our system in (a), this system yields a diagonal matrix.
For solving the equation , consider the scheme
Show that this scheme is fourth-order accurate.
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.
Letting and rearranging terms gives
If is a negative real number, then