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

T

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: The diagonal elements of $T$ .
2: $lambda$ – double scalar: The scalar $λ$ . nag_matop_real_gen_tridiag_lu (f01le) factorizes $T - λ I$ .
3: $b (n)$ – double array: The superdiagonal elements of $T$ , stored in $b (2)$ to $b (n)$ ; $b (1)$ is not used.
4: $c (n)$ – double array: The subdiagonal elements of $T$ , stored in $c (2)$ to $c (n)$ ; $c (1)$ is not used.
5: $tol$ – double scalar: A relative tolerance used to indicate whether or not the matrix ( $T - λ I$ ) is nearly singular. tol should normally be chosen as approximately the largest relative error in the elements of $T$ . For example, if the elements of $T$ are correct to about $4$ significant figures, then tol should be set to about $5 \times 10^{- 4}$ . See 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.)
$n$ , the order of the matrix $T$ .

Constraint: $n \geq 1$ .

Output Parameters

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

Error Indicators and Warnings

Errors or warnings detected by the function:

$ifail = 1$

On entry,

n < 1

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.

$ifail = - 999$: Dynamic memory allocation failed.

Accuracy

The computed factorization will satisfy the equation

P L U = (T - λ I) + E,

where

{‖E‖}_{1} \leq 9 \times \max_{i \geq j} (|l_{i j}|, {|l_{i j}|}^{2}) ε {‖T - λ I‖}_{1}

where

ε

is the machine precision.

Further Comments

The time taken by nag_matop_real_gen_tridiag_lu (f01le) is approximately proportional to

n

The factorization of a tridiagonal matrix proceeds in

(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

L

, rows

k

and (

k + 1

) will, if necessary, be interchanged at the

k

th step prior to the elimination.

The element

ipiv (n)

returns the smallest integer,

j

, for which

|u_{j j}| \leq {‖{(T - λ I)}_{j}‖}_{1} \times tol,

where

{‖{(T - λ I)}_{j}‖}_{1}

denotes the sum of the absolute values of the

j

th row of the matrix (

T - λ I

). If no such

j

exists, then

ipiv (n)

is returned as zero. If such a

j

exists, then

|u_{j j}|

is small and hence (

T - λ 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

This example factorizes the tridiagonal matrix

T

where

T = (\begin{array}{r} 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 \end{array})

and then to solve the equations

T x = y

, where

y = (\begin{array}{r} 2.7 \\ - 0.5 \\ 2.6 \\ 0.6 \\ 2.7 \end{array})

by a call to nag_linsys_real_tridiag_fac_solve (f04le). The example program sets

tol = 5 \times 10^{- 5}

and, of course, sets

lambda = 0

Open in the MATLAB editor: f01le_example

function f01le_example


fprintf('f01le example results\n\n');


% Tridiagonal matrix T stored by diagonals
b =       [0     2.1    -1      1.9     8];
a =       [3     2.3    -5     -0.9     7.1];
c = [0     3.4   3.6     7     -6];

% LU factorize T
lambda = 0;
tol = 5e-05;
[D, U1, L, U2, ipiv, ifail] = f01le( ...
                                     a, lambda, b, c, tol);

fprintf('Details of factorization\n\n');
disp(' Main diagonal of U');
disp(D);
disp(' First super-diagonal of U');
disp(U1(2:end));
disp(' Second super-diagonal of U');
disp(U2(3:end)');
disp(' Multipliers');
disp(L(2:end));
disp(' Vector of interchanges');
disp(double(ipiv(1:end-1))');

% Solve Tx = y, where 
y = [2.7  -0.5   2.6   0.6   2.7 ];
% using factorized form of T
job = int64(1);

[x, ~, ifail] = f04le( ...
                       job, D, U1, L, U2, ipiv, y, tol);

disp('Solution vector:');
disp(x);

f01le example results

Details of factorization

 Main diagonal of U
    3.0000    3.6000    7.0000   -6.0000    1.1508

 First super-diagonal of U
    2.1000   -5.0000   -0.9000    7.1000

 Second super-diagonal of U
         0    1.9000    8.0000

 Multipliers
    1.1333   -0.0222   -0.1587    0.0168

 Vector of interchanges
     0     1     1     1

Solution vector:
   -4.0000    7.0000    3.0000   -4.0000   -3.0000

PDF version (NAG web site, 64-bit version, 64-bit version)

Chapter Contents

Chapter Introduction

NAG Toolbox