Householder's Method

and

are vectors with the same norm, there exists an orthogonal symmetric matrix

such that

,
where

and

.

Since

is both orthogonal and symmetric, it follows that

Corollary ( Householder Matrix)

Let be an matrix, and any vector. If is an integer with , we can construct a vector and matrix so that

(1) [Graphics:Images/HouseholderMod_gr_20.gif] .

Householder Transformations

Suppose that is a symmetric matrix. Then a sequence of transformations of the form will reduce to a symmetric tridiagonal matrix. Let us visualize the process when . The first transformation is defined to be , where is constructed by applying the above Corollary with the vector being the first column of the matrix . The general form of is

[Graphics:Images/HouseholderMod_gr_32.gif]

where the letter stands for some element in . As a result, the transformation does not affect the element of :

(2) .

The element denoted is changed because of premultiplication by , and is changed because of postmultiplication by ; since is symmetric, we have . The changes to the elements denoted have been affected by both premultiplication and postmultiplication. Also, since is the first column of , equation (1) implies that .

The second Householder transformation is applied to the matrix defined in (2) and is denoted , where is constructed by applying the Corollary with the vector being the second column of the matrix . The form of is

[Graphics:Images/HouseholderMod_gr_55.gif]

where stands for some element in . The identity block in the upper-left corner ensures that the partial tridiagonalization achieved in the first step will not be altered by the second transformation . The outcome of this transformation is

(3) [Graphics:Images/HouseholderMod_gr_60.gif] .

The elements and were affected by premultiplication and postmultiplication by . Additional changes have been introduced to the other elements by the transformation. The third Householder transformation, , is applied to the matrix defined in (3) where the Corollary is used with being the third column of . The form of is

[Graphics:Images/HouseholderMod_gr_70.gif]

Again, the identity block ensures that does not affect the elements of , which lie in the upper corner, and we obtain

.

Thus it has taken three transformations to reduce to tridiagonal form.

In general, for efficiency, the transformation is not performed in matrix form. The next result shows that it is more efficiently carried out via some clever vector manipulations.

Theorem (Computation of One Householder Transformation)

If is a Householder matrix, the transformation is accomplished as follows. Let

Let and compute

and
,

then .

Reduction to Tridiagonal Form

Suppose that is a symmetric matrix. Start with

.

Construct the sequence of Householder matrices, so that

for ,

where has zeros below the subdiagonal in columns . Then is a symmetric tridiagonal matrix that is similar to . This process is called Householder's method.

Comments

Runge-Kutta-Fehlberg Method

One way to guarantee accuracy in the solution of an I.V.P. is to solve the problem twice using step sizes h and and compare answers at the mesh points corresponding to the larger step size. But this requires a significant amount of computation for the smaller step size and must be repeated if it is determined that the agreement is not good enough. The Runge-Kutta-Fehlberg method (denoted RKF45) is one way to try to resolve this problem. It has a procedure to determine if the proper step size h is being used. At each step, two different approximations for the solution are made and compared. If the two answers are in close agreement, the approximation is accepted. If the two answers do not agree to a specified accuracy, the step size is reduced. If the answers agree to more significant digits than required, the step size is increased. Each Runge-Kutta-Fehlberg step requires the use of the following six values: Then an approximation to the solution of the I.V.P.

Van Der Pol System

The van der Pol equation is an ordinary differential equation that can be derived from the Rayleigh differential equation by differentiating and setting . It is an equation describing self-sustaining oscillations in which energy is fed into small oscillations and removed from large oscillations. This equation arises in the study of circuits containing vacuum tubes and is given by If , the equation reduces to the equation of simple harmonic motion The van der Pol equation is , where is a constant. When the equation reduces to , and has the familiar solution . Usually the term in equation (1) should be regarded as friction or resistance, and this is the case when the coefficient is positive. However, if the coefficient is negative then we have the case of "negative resistance." In the age of "vacuum tube" radios, the " tetrode vacuum tube " (cathode, grid, plate), was used for a power amplifie

Powell's Method

The essence of Powell's method is to add two steps to the process described in the preceding paragraph. The vector represents, in some sense, the average direction moved over the n intermediate steps in an iteration. Thus the point is determined to be the point at which the minimum of the function f occurs along the vector . As before, f is a function of one variable along this vector and the minimization could be accomplished with an application of the golden ratio or Fibonacci searches. Finally, since the vector was such a good direction, it replaces one of the direction vectors for the next iteration. The iteration is then repeated using the new set of direction vectors to generate a sequence of points . In one step of the iteration instead of a zig-zag path the iteration follows a "dog-leg" path. The process is outlined below. Let be an initial guess at the location of the minimum of the function . Let for be the

Fibonacci Method

An approach for finding the minimum of in a given interval is to evaluate the function many times and search for a local minimum. To reduce the number of function evaluations it is important to have a good strategy for determining where is to be evaluated. Two efficient bracketing methods are the golden ratio and Fibonacci searches. To use either bracketing method for finding the minimum of , a special condition must be met to ensure that there is a proper minimum in the given interval. The function is unimodal on , if there exists a unique number such that is decreasing on , and is increasing on . In the golden ratio search two function evaluations are made at the first iteration and then only one function evaluation is made for each subsequent iteration. The value of remains constant on each subinterval and the search is terminated at the subinterval, provided that or where are the predefined tolerances. The Fibo

Numerical Analysis

Search This Blog