NAG Library Routine Document
F01LEF computes an factorization of a real tridiagonal matrix, using Gaussian elimination with partial pivoting.
||N, IPIV(N), IFAIL
||A(N), LAMBDA, B(N), C(N), TOL, D(N)
is a real
tridiagonal matrix, is factorized as
is a permutation matrix,
is a unit lower triangular matrix with at most one nonzero subdiagonal element per column, and
is an upper triangular matrix with at most two nonzero superdiagonal elements per column.
The factorization is obtained by Gaussian elimination with partial pivoting and implicit row scaling.
An indication of whether or not the matrix
is nearly singular is returned in the
th element of the array IPIV
. If it is important that
is nonsingular, as is usually the case when solving a system of tridiagonal equations, then it is strongly recommended that
is inspected on return from F01LEF. (See the parameter IPIV
and Section 8
for further details.)
is included in the routine so that F01LEF may be used, in conjunction with F04LEF
, to obtain eigenvectors of
by inverse iteration.
Wilkinson J H (1965) The Algebraic Eigenvalue Problem Oxford University Press, Oxford
Wilkinson J H and Reinsch C (1971) Handbook for Automatic Computation II, Linear Algebra Springer–Verlag
- 1: N – INTEGERInput
On entry: , the order of the matrix .
- 2: A(N) – REAL (KIND=nag_wp) arrayInput/Output
On entry: the diagonal elements of .
On exit: the diagonal elements of the upper triangular matrix .
- 3: LAMBDA – REAL (KIND=nag_wp)Input
On entry: the scalar . F01LEF factorizes .
- 4: B(N) – REAL (KIND=nag_wp) arrayInput/Output
On entry: the superdiagonal elements of , stored in to ; is not used.
On exit: the elements of the first superdiagonal of , stored in to .
- 5: C(N) – REAL (KIND=nag_wp) arrayInput/Output
On entry: the subdiagonal elements of , stored in to ; is not used.
On exit: the subdiagonal elements of , stored in to .
- 6: TOL – REAL (KIND=nag_wp)Input
: a relative tolerance used to indicate whether or not the matrix (
) is nearly singular. TOL
should normally be chosen as approximately the largest relative error in the elements of
. For example, if the elements of
are correct to about
significant figures, then TOL
should be set to about
. See Section 8
for further details on how TOL
is used. If TOL
is supplied as less than
is the machine precision
, then the value
is used in place of TOL
- 7: D(N) – REAL (KIND=nag_wp) arrayOutput
On exit: the elements of the second superdiagonal of , stored in to ; and are not used.
- 8: IPIV(N) – INTEGER arrayOutput
: details of the permutation matrix
. If an interchange occurred at the
th step of the elimination, then
. If a diagonal element of
is small, indicating that
is nearly singular, then the element
is returned as positive. Otherwise
is returned as
. See Section 8
for further details. If the application is such that it is important that
is not nearly singular, then it is strongly recommended that
is inspected on return.
- 9: IFAIL – INTEGERInput/Output
must be set to
. If you are unfamiliar with this parameter you should refer to Section 3.3
in the Essential Introduction for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
is recommended. If the output of error messages is undesirable, then the value
is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is
. When the value is used it is essential to test the value of IFAIL on exit.
unless the routine detects an error or a warning has been flagged (see Section 6
6 Error Indicators and Warnings
If on entry
, explanatory error messages are output on the current error message unit (as defined by X04AAF
Errors or warnings detected by the routine:
The computed factorization will satisfy the equation
is the machine precision
The time taken by F01LEF is approximately proportional to .
The factorization of a tridiagonal matrix proceeds in steps, each step eliminating one subdiagonal element of the tridiagonal matrix. In order to avoid small pivot elements and to prevent growth in the size of the elements of , rows and () will, if necessary, be interchanged at the th step prior to the elimination.
returns the smallest integer,
, for which
denotes the sum of the absolute values of the
th row of the matrix (
). If no such
is returned as zero. If such a
is small and hence (
) is singular or nearly singular.
This routine may be followed by F04LEF
to solve systems of tridiagonal equations. If you wish to solve single systems of tridiagonal equations you should be aware of F07CAF (DGTSV)
, which solves tridiagonal systems with a single call. F07CAF (DGTSV)
requires less storage and will generally be faster than the combination of F01LEF and F04LEF
, but no test for near singularity is included in F07CAF (DGTSV)
and so it should only be used when the equations are known to be nonsingular.
This example factorizes the tridiagonal matrix
and then to solve the equations
by a call to F04LEF
. The example program sets
and, of course, sets
9.1 Program Text
Program Text (f01lefe.f90)
9.2 Program Data
Program Data (f01lefe.d)
9.3 Program Results
Program Results (f01lefe.r)