Let be a nonlinear smooth function. To determine a (local) minimum of one can use a descent method of the form
where is a suitable parameter obtained by backtracking and is a descent direction i.e. it satisfies
Write the steepest descent method (or gradient) method and show that there exist such that the resulting method satisfies (2)
Steepest Descent Method
Choose such that minimizes i.e.
Directional Derivative Negative
To satisfy (2), the directional derivative should be negative i.e.
Write the Newton method and examine whether or not there exist which yield (2). Establish conditions on the Hessian of which guarantee the existence of .
Directional Derivative Negative
To have descent, we want the directional derivative to be negative i.e.
Therefore is positive definite and therefore is positive definite.
If we replace the Hessian by the matrix , where and is the identity matrix, we obtain a quasi-Newton method. Find a condition on which leads to (2).
We now want to be positive definite.
Let , be the eigenvalues of .
Then , are eigenvalues of .
Since we want to be positive definite, we equivalently have for
Consider the following nonlinear autonomous initial value problem in with .
Write the ODE in integral form and use the mid-point quadrature rule to derive the mid-point method with uniform time-step :
Define truncation error . Assuming that , show an estimate for the error . What is the order of the method? (Hint: use that is Lipschitz continuous.
where is the Lipschitz constant of . Rearranging terms we get
Then is given by
Prove that for this method. (Hint: expand first and around and next expand Also expand around .)
The midpoint method may be rewritten as follows:
Expanding each term around yields .
Consider the following boundary two-point boundary value problem in with
Write the finite element method with piecewise linear elements over a uniform partition of with meshsize . If is the vector of nodal values of the finite element solution, find the (stiffness) matrix and right-hand side such that . Is symmetric? Is positive definite?
Weak Variational Formulation
Multiplying the given equation by a test function and integrating from 0 to 1 gives the equivalent weak variational formulation:
Find such that for all the following holds
Discrete Variational Formulation
Then we have the discrete variational formulation which is an approximation to the weak variational formulation.
Find such that for all
Define basis for V_h
Let be the linear "hat" functions which defines a basis for .
Then calculation yields the following: (draw pictures)
Discrete Variational Formulation in Matrix Form
Since is a basis for ,
Also, the discrete variational formulation may be expressed as
which in matrix form is
is not symmetric. is positive definite if
Find a relation between the three parameters for to be an matrix, i.e. to have if and
The first,second, and last rows all yield the same inequality for to be an -matrix:
Consider the upwind modification of the ODE
Show that the resulting matrix is an M-matrix without restrictions on and .
Substituting for yields the following matrix :
All off diagonal entries are . Diagonal entries are
The first row meets the last condition since
The second row through (n-1) rows meets the last condition since
The last row meets the last condition since