F04LEF (PDF version)
F04 Chapter Contents
F04 Chapter Introduction
NAG Library Manual

NAG Library Routine Document

F04LEF

Note:  before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

+ Contents

    1  Purpose
    7  Accuracy

1  Purpose

F04LEF solves a system of tridiagonal equations following the factorization by F01LEF. This routine is intended for applications such as inverse iteration as well as straightforward linear equation applications.

2  Specification

SUBROUTINE F04LEF ( JOB, N, A, B, C, D, IPIV, Y, TOL, IFAIL)
INTEGER  JOB, N, IPIV(N), IFAIL
REAL (KIND=nag_wp)  A(N), B(N), C(N), D(N), Y(N), TOL

3  Description

Following the factorization of the n by n tridiagonal matrix T-λI as
T-λI=PLU
by F01LEF, F04LEF may be used to solve any of the equations
T-λ Ix=y,   T-λ ITx=y,   Ux=y
for x, the choice of equation being controlled by the parameter JOB. In each case there is an option to perturb zero or very small diagonal elements of U, this option being intended for use in applications such as inverse iteration.

4  References

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

5  Parameters

1:     JOB – INTEGERInput
On entry: must specify the equations to be solved.
JOB=1
The equations T-λIx=y are to be solved, but diagonal elements of U are not to be perturbed.
JOB=-1
The equations T-λIx=y are to be solved and, if overflow would otherwise occur, diagonal elements of U are to be perturbed. See parameter TOL.
JOB=2
The equations T-λITx=y are to be solved, but diagonal elements of U are not to be perturbed.
JOB=-2
The equations T-λITx=y are to be solved and, if overflow would otherwise occur, diagonal elements of U are to be perturbed. See parameter TOL.
JOB=3
The equations Ux=y are to be solved, but diagonal elements of U are not to be perturbed.
JOB=-3
The equations Ux=y are to be solved and, if overflow would otherwise occur, diagonal elements of U are to be perturbed. See parameter TOL.
2:     N – INTEGERInput
On entry: n, the order of the matrix T.
Constraint: N1.
3:     A(N) – REAL (KIND=nag_wp) arrayInput
On entry: the diagonal elements of U as returned by F04LEF.
4:     B(N) – REAL (KIND=nag_wp) arrayInput
On entry: the elements of the first superdiagonal of U as returned by F04LEF.
5:     C(N) – REAL (KIND=nag_wp) arrayInput
On entry: the subdiagonal elements of L as returned by F04LEF.
6:     D(N) – REAL (KIND=nag_wp) arrayInput
On entry: the elements of the second superdiagonal of U as returned by F04LEF.
7:     IPIV(N) – INTEGER arrayInput
On entry: details of the matrix P as returned by F01LEF.
8:     Y(N) – REAL (KIND=nag_wp) arrayInput/Output
On entry: the right-hand side vector y.
On exit: Y is overwritten by the solution vector x.
9:     TOL – REAL (KIND=nag_wp)Input/Output
On entry: the minimum perturbation to be made to very small diagonal elements of U. TOL is only referenced when JOB is negative. TOL should normally be chosen as about εU, where ε is the machine precision, but if TOL is supplied as non-positive, then it is reset to εmaxuij.
On exit: if on entry TOL is non-positive, it is reset as just described. Otherwise TOL is unchanged.
10:   IFAIL – INTEGERInput/Output
On entry: IFAIL must be set to 0, -1​ or ​1. 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 -1​ or ​1 is recommended. If the output of error messages is undesirable, then the value 1 is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is 0. When the value -1​ or ​1 is used it is essential to test the value of IFAIL on exit.
On exit: IFAIL=0 unless the routine detects an error or a warning has been flagged (see Section 6).

6  Error Indicators and Warnings

If on entry IFAIL=0 or -1, explanatory error messages are output on the current error message unit (as defined by X04AAF).
Errors or warnings detected by the routine:
IFAIL=1
On entry,N<1,
orJOB=0,
orJOB<-3 or JOB>3.
IFAIL>1
Overflow would occur when computing the (IFAIL-1)th element of the solution vector x. This can only occur when JOB is supplied as positive and either means that a diagonal element of U is very small or that elements of the right-hand side vector y are very large.

7  Accuracy

The computed solution of the equations T-λIx=y, say x-, will satisfy an equation of the form
T-λI+Ex-=y,
where E can be expected to satisfy a bound of the form
EαεT-λI,
α being a modest constant and ε being the machine precision. The computed solution of the equations T-λITx=y and Ux=y will satisfy similar results. The above result implies that the relative error in x- satisfies
x--x x- cT-λIαε,
where cT-λI is the condition number of T-λI with respect to inversion. Thus if T-λI is nearly singular, x- can be expected to have a large relative error. Note that F01LEF incorporates a test for near singularity.

8  Further Comments

The time taken by F04LEF is approximately proportional to n.
If you have single systems of tridiagonal equations to solve you are advised that F07CAF (DGTSV) requires less storage and will normally be faster than the combination of F01LEF and F04LEF, but F07CAF (DGTSV) does not incorporate a test for near singularity.

9  Example

This example solves the two sets of tridiagonal equations
Tx=y  and  TTx=y
where
T= 3.0 2.1 0 0 0 3.4 2.3 -1.0 0 0 0 3.6 -5.0 1.9 0 0 0 7.0 -0.9 8.0 0 0 0 -6.0 7.1   and   y = 2.7 -0.5 2.6 0.6 2.7 .
The example program first calls F01LEF to factorize T and then two calls are made to F04LEF, one to solve Tx=y and the second to solve TTx=y.

9.1  Program Text

Program Text (f04lefe.f90)

9.2  Program Data

Program Data (f04lefe.d)

9.3  Program Results

Program Results (f04lefe.r)


F04LEF (PDF version)
F04 Chapter Contents
F04 Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2012