# NAG FL Interfacef04lef (real_​tridiag_​fac_​solve)

## ▸▿ Contents

Settings help

FL Name Style:

FL Specification Language:

## 1Purpose

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.

## 2Specification

Fortran Interface
 Subroutine f04lef ( job, n, a, b, c, d, ipiv, y, tol,
 Integer, Intent (In) :: job, n, ipiv(n) Integer, Intent (Inout) :: ifail Real (Kind=nag_wp), Intent (In) :: a(n), b(n), c(n), d(n) Real (Kind=nag_wp), Intent (Inout) :: y(n), tol
#include <nag.h>
 void f04lef_ (const Integer *job, const Integer *n, const double a[], const double b[], const double c[], const double d[], const Integer ipiv[], double y[], double *tol, Integer *ifail)
The routine may be called by the names f04lef or nagf_linsys_real_tridiag_fac_solve.

## 3Description

Following the factorization of the $n×n$ tridiagonal matrix $\left(T-\lambda I\right)$ as
 $T-λI=PLU$
by f01lef, f04lef may be used to solve any of the equations
 $(T-λI)x=y, (T-λI)Tx=y, Ux=y$
for $x$, the choice of equation being controlled by the argument 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.
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

## 5Arguments

1: $\mathbf{job}$Integer Input
On entry: must specify the equations to be solved.
${\mathbf{job}}=1$
The equations $\left(T-\lambda I\right)x=y$ are to be solved, but diagonal elements of $U$ are not to be perturbed.
${\mathbf{job}}=-1$
The equations $\left(T-\lambda I\right)x=y$ are to be solved and, if overflow would otherwise occur, diagonal elements of $U$ are to be perturbed. See argument tol.
${\mathbf{job}}=2$
The equations ${\left(T-\lambda I\right)}^{\mathrm{T}}x=y$ are to be solved, but diagonal elements of $U$ are not to be perturbed.
${\mathbf{job}}=-2$
The equations ${\left(T-\lambda I\right)}^{\mathrm{T}}x=y$ are to be solved and, if overflow would otherwise occur, diagonal elements of $U$ are to be perturbed. See argument tol.
${\mathbf{job}}=3$
The equations $Ux=y$ are to be solved, but diagonal elements of $U$ are not to be perturbed.
${\mathbf{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 argument tol.
2: $\mathbf{n}$Integer Input
On entry: $n$, the order of the matrix $T$.
Constraint: ${\mathbf{n}}\ge 1$.
3: $\mathbf{a}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Input
On entry: the diagonal elements of $U$ as returned by f04lef.
4: $\mathbf{b}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Input
On entry: the elements of the first superdiagonal of $U$ as returned by f04lef.
5: $\mathbf{c}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Input
On entry: the subdiagonal elements of $L$ as returned by f04lef.
6: $\mathbf{d}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Input
On entry: the elements of the second superdiagonal of $U$ as returned by f04lef.
7: $\mathbf{ipiv}\left({\mathbf{n}}\right)$Integer array Input
On entry: details of the matrix $P$ as returned by f01lef.
8: $\mathbf{y}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Input/Output
On entry: the right-hand side vector $y$.
On exit: y is overwritten by the solution vector $x$.
9: $\mathbf{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 $\epsilon ‖U‖$, where $\epsilon$ is the machine precision, but if tol is supplied as non-positive, it is reset to $\epsilon \mathrm{max}|{u}_{ij}|$.
On exit: if on entry tol is non-positive, it is reset as just described. Otherwise tol is unchanged.
10: $\mathbf{ifail}$Integer Input/Output
On entry: ifail must be set to $0$, $-1$ or $1$ to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $-1$ means that an error message is printed while a value of $1$ means that it is not.
If halting is not appropriate, the value $-1$ or $1$ is recommended. If message printing is undesirable, then the value $1$ is recommended. Otherwise, the value $0$ is recommended. When the value $-\mathbf{1}$ or $\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

## 6Error Indicators and Warnings

If on entry ${\mathbf{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:
${\mathbf{ifail}}=1$
On entry, ${\mathbf{job}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{job}}\ne 0$ and ${\mathbf{job}}\ge -3$ and ${\mathbf{job}}\le 3$.
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 1$.
${\mathbf{ifail}}>1$
Overflow would occur computing the element $I$ in the solution. $I=⟨\mathit{\text{value}}⟩$.
${\mathbf{ifail}}=-99$
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

## 7Accuracy

The computed solution of the equations $\left(T-\lambda I\right)x=y$, say $\overline{x}$, will satisfy an equation of the form
 $(T-λI+E)x¯=y,$
where $E$ can be expected to satisfy a bound of the form
 $‖E‖≤αε‖T-λI‖,$
$\alpha$ being a modest constant and $\epsilon$ being the machine precision. The computed solution of the equations ${\left(T-\lambda I\right)}^{\mathrm{T}}x=y$ and $Ux=y$ will satisfy similar results. The above result implies that the relative error in $\overline{x}$ satisfies
 $‖x¯-x‖ ‖x¯‖ ≤c(T-λI)αε,$
where $c\left(T-\lambda I\right)$ is the condition number of $\left(T-\lambda I\right)$ with respect to inversion. Thus if $\left(T-\lambda I\right)$ is nearly singular, $\overline{x}$ can be expected to have a large relative error. Note that f01lef incorporates a test for near singularity.

## 8Parallelism and Performance

f04lef is not threaded in any implementation.

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 requires less storage and will normally be faster than the combination of f01lef and f04lef, but f07caf does not incorporate a test for near singularity.

## 10Example

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 ${T}^{\mathrm{T}}x=y$.

### 10.1Program Text

Program Text (f04lefe.f90)

### 10.2Program Data

Program Data (f04lefe.d)

### 10.3Program Results

Program Results (f04lefe.r)