hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_matop_real_gen_tridiag_lu (f01le)

Purpose

nag_matop_real_gen_tridiag_lu (f01le) computes an LULU factorization of a real tridiagonal matrix, using Gaussian elimination with partial pivoting.

Syntax

[a, b, c, d, ipiv, ifail] = f01le(a, lambda, b, c, tol, 'n', n)
[a, b, c, d, ipiv, ifail] = nag_matop_real_gen_tridiag_lu(a, lambda, b, c, tol, 'n', n)

Description

The matrix TλIT-λI, where TT is a real nn by nn tridiagonal matrix, is factorized as
TλI = PLU,
T-λI=PLU,
where PP is a permutation matrix, LL is a unit lower triangular matrix with at most one nonzero subdiagonal element per column, and UU 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 TλIT-λI is nearly singular is returned in the nnth element of the array ipiv. If it is important that TλIT-λI is nonsingular, as is usually the case when solving a system of tridiagonal equations, then it is strongly recommended that ipiv(n)ipivn is inspected on return from nag_matop_real_gen_tridiag_lu (f01le). (See the parameter ipiv and Section [Further Comments] for further details.)
The parameter λλ is included in the function so that nag_matop_real_gen_tridiag_lu (f01le) may be used, in conjunction with nag_linsys_real_tridiag_fac_solve (f04le), to obtain eigenvectors of TT by inverse iteration.

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

Parameters

Compulsory Input Parameters

1:     a(n) – double array
n, the dimension of the array, must satisfy the constraint n1n1.
The diagonal elements of TT.
2:     lambda – double scalar
The scalar λλ. nag_matop_real_gen_tridiag_lu (f01le) factorizes TλIT-λI.
3:     b(n) – double array
n, the dimension of the array, must satisfy the constraint n1n1.
The superdiagonal elements of TT, stored in b(2)b2 to b(n)bn; b(1)b1 is not used.
4:     c(n) – double array
n, the dimension of the array, must satisfy the constraint n1n1.
The subdiagonal elements of TT, stored in c(2)c2 to c(n)cn; c(1)c1 is not used.
5:     tol – double scalar
A relative tolerance used to indicate whether or not the matrix (TλIT-λI) is nearly singular. tol should normally be chosen as approximately the largest relative error in the elements of TT. For example, if the elements of TT are correct to about 44 significant figures, then tol should be set to about 5 × 1045×10-4. See Section [Further Comments] for further details on how tol is used. If tol is supplied as less than εε, where εε is the machine precision, then the value εε is used in place of tol.

Optional Input Parameters

1:     n – int64int32nag_int scalar
Default: The dimension of the arrays a, b, c. (An error is raised if these dimensions are not equal.)
nn, the order of the matrix TT.
Constraint: n1n1.

Input Parameters Omitted from the MATLAB Interface

None.

Output Parameters

1:     a(n) – double array
The diagonal elements of the upper triangular matrix UU.
2:     b(n) – double array
The elements of the first superdiagonal of UU, stored in b(2)b2 to b(n)bn.
3:     c(n) – double array
The subdiagonal elements of LL, stored in c(2)c2 to c(n)cn.
4:     d(n) – double array
The elements of the second superdiagonal of UU, stored in d(3)d3 to d(n)dn; d(1)d1 and d(2)d2 are not used.
5:     ipiv(n) – int64int32nag_int array
Details of the permutation matrix PP. If an interchange occurred at the kkth step of the elimination, then ipiv(k) = 1ipivk=1, otherwise ipiv(k) = 0ipivk=0. If a diagonal element of UU is small, indicating that (TλI)(T-λI) is nearly singular, then the element ipiv(n)ipivn is returned as positive. Otherwise ipiv(n)ipivn is returned as 00. See Section [Further Comments] for further details. If the application is such that it is important that (TλI)(T-λI) is not nearly singular, then it is strongly recommended that ipiv(n)ipivn is inspected on return.
6:     ifail – int64int32nag_int scalar
ifail = 0ifail=0 unless the function detects an error (see [Error Indicators and Warnings]).

Error Indicators and Warnings

Errors or warnings detected by the function:
  ifail = 1ifail=1
On entry,n < 1n<1.

Accuracy

The computed factorization will satisfy the equation
PLU = (TλI) + E,
PLU=(T-λI)+E,
where
E1 9 × maxij (|lij|,|lij|2) ε TλI1
E1 9×maxij (|lij|,|lij|2) ε T-λ I1
where εε is the machine precision.

Further Comments

The time taken by nag_matop_real_gen_tridiag_lu (f01le) is approximately proportional to nn.
The factorization of a tridiagonal matrix proceeds in (n1)(n-1) 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 LL, rows kk and (k + 1k+1) will, if necessary, be interchanged at the kkth step prior to the elimination.
The element ipiv(n)ipivn returns the smallest integer, jj, for which
|ujj|(TλI)j1 × tol,
|ujj|(T-λI)j1×tol,
where (TλI)j1(T-λI)j1 denotes the sum of the absolute values of the jjth row of the matrix (TλIT-λI). If no such jj exists, then ipiv(n)ipivn is returned as zero. If such a jj exists, then |ujj||ujj| is small and hence (TλIT-λI) is singular or nearly singular.
This function may be followed by nag_linsys_real_tridiag_fac_solve (f04le) to solve systems of tridiagonal equations. If you wish to solve single systems of tridiagonal equations you should be aware of nag_lapack_dgtsv (f07ca), which solves tridiagonal systems with a single call. nag_lapack_dgtsv (f07ca) requires less storage and will generally be faster than the combination of nag_matop_real_gen_tridiag_lu (f01le) and nag_linsys_real_tridiag_fac_solve (f04le), but no test for near singularity is included in nag_lapack_dgtsv (f07ca) and so it should only be used when the equations are known to be nonsingular.

Example

function nag_matop_real_gen_tridiag_lu_example
a = [3;
     2.3;
     -5;
     -0.9;
     7.1];
lambda = 0;
b = [0;
     2.1;
     -1;
     1.9;
     8];
c = [0;
     3.4;
     3.6;
     7;
     -6];
tol = 5e-05;
[aOut, bOut, cOut, d, ipiv, ifail] = nag_matop_real_gen_tridiag_lu(a, lambda, b, c, tol)
 

aOut =

    3.0000
    3.6000
    7.0000
   -6.0000
    1.1508


bOut =

         0
    2.1000
   -5.0000
   -0.9000
    7.1000


cOut =

         0
    1.1333
   -0.0222
   -0.1587
    0.0168


d =

         0
         0
         0
    1.9000
    8.0000


ipiv =

                    0
                    1
                    1
                    1
                    0


ifail =

                    0


function f01le_example
a = [3;
     2.3;
     -5;
     -0.9;
     7.1];
lambda = 0;
b = [0;
     2.1;
     -1;
     1.9;
     8];
c = [0;
     3.4;
     3.6;
     7;
     -6];
tol = 5e-05;
[aOut, bOut, cOut, d, ipiv, ifail] = f01le(a, lambda, b, c, tol)
 

aOut =

    3.0000
    3.6000
    7.0000
   -6.0000
    1.1508


bOut =

         0
    2.1000
   -5.0000
   -0.9000
    7.1000


cOut =

         0
    1.1333
   -0.0222
   -0.1587
    0.0168


d =

         0
         0
         0
    1.9000
    8.0000


ipiv =

                    0
                    1
                    1
                    1
                    0


ifail =

                    0



PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013