Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

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 $LU$ 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-\lambda I$, where $T$ is a real $n$ by $n$ tridiagonal matrix, is factorized as
 $T-λI=PLU,$
where $P$ is a permutation matrix, $L$ is a unit lower triangular matrix with at most one nonzero subdiagonal element per column, and $U$ 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-\lambda I$ is nearly singular is returned in the $n$th element of the array ipiv. If it is important that $T-\lambda I$ is nonsingular, as is usually the case when solving a system of tridiagonal equations, then it is strongly recommended that ${\mathbf{ipiv}}\left(n\right)$ is inspected on return from nag_matop_real_gen_tridiag_lu (f01le). (See the argument ipiv and Further Comments for further details.)
The argument $\lambda$ 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:     $\mathrm{a}\left({\mathbf{n}}\right)$ – double array
The diagonal elements of $T$.
2:     $\mathrm{lambda}$ – double scalar
The scalar $\lambda$. nag_matop_real_gen_tridiag_lu (f01le) factorizes $T-\lambda I$.
3:     $\mathrm{b}\left({\mathbf{n}}\right)$ – double array
The superdiagonal elements of $T$, stored in ${\mathbf{b}}\left(2\right)$ to ${\mathbf{b}}\left(n\right)$; ${\mathbf{b}}\left(1\right)$ is not used.
4:     $\mathrm{c}\left({\mathbf{n}}\right)$ – double array
The subdiagonal elements of $T$, stored in ${\mathbf{c}}\left(2\right)$ to ${\mathbf{c}}\left(n\right)$; ${\mathbf{c}}\left(1\right)$ is not used.
5:     $\mathrm{tol}$ – double scalar
A relative tolerance used to indicate whether or not the matrix ($T-\lambda 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×{10}^{-4}$. See Further Comments for further details on how tol is used. If tol is supplied as less than $\epsilon$, where $\epsilon$ is the machine precision, then the value $\epsilon$ is used in place of tol.

### Optional Input Parameters

1:     $\mathrm{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: ${\mathbf{n}}\ge 1$.

### Output Parameters

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

## Error Indicators and Warnings

Errors or warnings detected by the function:
${\mathbf{ifail}}=1$
 On entry, ${\mathbf{n}}<1$.
${\mathbf{ifail}}=-99$
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.

## Accuracy

The computed factorization will satisfy the equation
 $PLU=T-λI+E,$
where
 $E1≤ 9×maxi≥j lij,lij2 ε T-λ I1$
where $\epsilon$ is the machine precision.

The time taken by nag_matop_real_gen_tridiag_lu (f01le) is approximately proportional to $n$.
The factorization of a tridiagonal matrix proceeds in $\left(n-1\right)$ 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 ${\mathbf{ipiv}}\left(n\right)$ returns the smallest integer, $j$, for which
 $ujj≤T-λIj1×tol,$
where ${‖{\left(T-\lambda I\right)}_{j}‖}_{1}$ denotes the sum of the absolute values of the $j$th row of the matrix ($T-\lambda I$). If no such $j$ exists, then ${\mathbf{ipiv}}\left(n\right)$ is returned as zero. If such a $j$ exists, then $\left|{u}_{jj}\right|$ is small and hence ($T-\lambda 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= 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 then to solve the equations $Tx=y$, where
 $y= 2.7 -0.5 2.6 0.6 2.7$
by a call to nag_linsys_real_tridiag_fac_solve (f04le). The example program sets ${\mathbf{tol}}=5×{10}^{-5}$ and, of course, sets ${\mathbf{lambda}}=0$.
```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

```