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_linsys_real_tridiag_fac_solve (f04le)

Purpose

nag_linsys_real_tridiag_fac_solve (f04le) solves a system of tridiagonal equations following the factorization by nag_matop_real_gen_tridiag_lu (f01le). This function is intended for applications such as inverse iteration as well as straightforward linear equation applications.

Syntax

[y, tol, ifail] = f04le(job, a, b, c, d, ipiv, y, tol, 'n', n)
[y, tol, ifail] = nag_linsys_real_tridiag_fac_solve(job, a, b, c, d, ipiv, y, tol, 'n', n)

Description

Following the factorization of the nn by nn tridiagonal matrix (TλI)(T-λI) as
TλI = PLU
T-λI=PLU
by nag_matop_real_gen_tridiag_lu (f01le), nag_linsys_real_tridiag_fac_solve (f04le) may be used to solve any of the equations
(TλI)x = y,   (TλI)Tx = y,   Ux = y
(T-λ I)x=y,   (T-λ I)Tx=y,   Ux=y
for xx, 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 UU, this option being intended for use in applications such as 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:     job – int64int32nag_int scalar
Must specify the equations to be solved.
job = 1job=1
The equations (TλI)x = y(T-λI)x=y are to be solved, but diagonal elements of UU are not to be perturbed.
job = 1job=-1
The equations (TλI)x = y(T-λI)x=y are to be solved and, if overflow would otherwise occur, diagonal elements of UU are to be perturbed. See parameter tol.
job = 2job=2
The equations (TλI)Tx = y(T-λI)Tx=y are to be solved, but diagonal elements of UU are not to be perturbed.
job = 2job=-2
The equations (TλI)Tx = y(T-λI)Tx=y are to be solved and, if overflow would otherwise occur, diagonal elements of UU are to be perturbed. See parameter tol.
job = 3job=3
The equations Ux = yUx=y are to be solved, but diagonal elements of UU are not to be perturbed.
job = 3job=-3
The equations Ux = yUx=y are to be solved and, if overflow would otherwise occur, diagonal elements of UU are to be perturbed. See parameter tol.
2:     a(n) – double array
n, the dimension of the array, must satisfy the constraint n1n1.
The diagonal elements of UU as returned by nag_linsys_real_tridiag_fac_solve (f04le).
3:     b(n) – double array
n, the dimension of the array, must satisfy the constraint n1n1.
The elements of the first superdiagonal of UU as returned by nag_linsys_real_tridiag_fac_solve (f04le).
4:     c(n) – double array
n, the dimension of the array, must satisfy the constraint n1n1.
The subdiagonal elements of LL as returned by nag_linsys_real_tridiag_fac_solve (f04le).
5:     d(n) – double array
n, the dimension of the array, must satisfy the constraint n1n1.
The elements of the second superdiagonal of UU as returned by nag_linsys_real_tridiag_fac_solve (f04le).
6:     ipiv(n) – int64int32nag_int array
n, the dimension of the array, must satisfy the constraint n1n1.
Details of the matrix PP as returned by nag_matop_real_gen_tridiag_lu (f01le).
7:     y(n) – double array
n, the dimension of the array, must satisfy the constraint n1n1.
The right-hand side vector yy.
8:     tol – double scalar
The minimum perturbation to be made to very small diagonal elements of UU. tol is only referenced when job is negative. tol should normally be chosen as about εUεU, where εε is the machine precision, but if tol is supplied as non-positive, then it is reset to εmax|uij|εmax|uij|.

Optional Input Parameters

1:     n – int64int32nag_int scalar
Default: The dimension of the arrays a, b, c, d, ipiv, y. (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:     y(n) – double array
y stores the solution vector xx.
2:     tol – double scalar
If on entry tol is non-positive, it is reset as just described. Otherwise tol is unchanged.
3:     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,
orjob = 0job=0,
orjob < 3job<-3 or job > 3job>3.
  ifail > 1ifail>1
Overflow would occur when computing the (ifail1ifail-1)th element of the solution vector xx. This can only occur when job is supplied as positive and either means that a diagonal element of UU is very small or that elements of the right-hand side vector yy are very large.

Accuracy

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

Further Comments

The time taken by nag_linsys_real_tridiag_fac_solve (f04le) is approximately proportional to nn.
If you have single systems of tridiagonal equations to solve you are advised that nag_lapack_dgtsv (f07ca) requires less storage and will normally be faster than the combination of nag_matop_real_gen_tridiag_lu (f01le) and nag_linsys_real_tridiag_fac_solve (f04le), but nag_lapack_dgtsv (f07ca) does not incorporate a test for near singularity.

Example

function nag_linsys_real_tridiag_fac_solve_example
job = int64(1);
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;
ipiv = [int64(0);1;1;1;0];
y = [2.7;
     -0.5;
     2.6;
     0.6;
     2.7];
tol = 5e-05;
[a, b, c, d, ipiv, ifail] = nag_matop_real_gen_tridiag_lu(a, lambda, b, c, tol);
[yOut, tolOut, ifail] = nag_linsys_real_tridiag_fac_solve(job, a, b, c, d, ipiv, y, tol)
 

yOut =

   -4.0000
    7.0000
    3.0000
   -4.0000
   -3.0000


tolOut =

   5.0000e-05


ifail =

                    0


function f04le_example
job = int64(1);
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;
ipiv = [int64(0);1;1;1;0];
y = [2.7;
     -0.5;
     2.6;
     0.6;
     2.7];
tol = 5e-05;
[a, b, c, d, ipiv, ifail] = f01le(a, lambda, b, c, tol);
[yOut, tolOut, ifail] = f04le(job, a, b, c, d, ipiv, y, tol)
 

yOut =

   -4.0000
    7.0000
    3.0000
   -4.0000
   -3.0000


tolOut =

   5.0000e-05


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