The function uses the method of Levinson (see Levinson (1947) and Golub and Van Loan (1996)). Optionally, the reflection coefficients for each step may also be returned.

References

Bunch J R (1985) Stability of methods for solving Toeplitz systems of equations SIAM J. Sci. Statist. Comput. 6 349–364

Bunch J R (1987) The weak and strong stability of algorithms in numerical linear algebra Linear Algebra Appl. 88/89 49–66

Cybenko G (1980) The numerical stability of the Levinson–Durbin algorithm for Toeplitz systems of equations SIAM J. Sci. Statist. Comput. 1 303–319

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

Levinson N (1947) The Weiner RMS error criterion in filter design and prediction J. Math. Phys. 25 261–278

Parameters

Compulsory Input Parameters

1: $t (:)$ – double array: The dimension of the array t must be at least $\max (1, n)$

$t (i + 1)$ must contain the value $τ_{i}$ , for $i = 0, 1, \dots, n - 1$ .

Constraint: $t (1) > 0.0$ . Note that if this is not true, then the Toeplitz matrix cannot be positive definite.
2: $b (:)$ – double array: The dimension of the array b must be at least $\max (1, n)$

The right-hand side vector $b$ .
3: $wantp$ – logical scalar: Must be set to true if the reflection coefficients are required, and must be set to false otherwise.

Optional Input Parameters

1: $n$ – int64int32nag_int scalar: Default: the dimension of the arrays t, b.
The order of the Toeplitz matrix $T$ .

Constraint: $n \geq 0$ . When $n = 0$ , then an immediate return is effected.

Output Parameters

1: $x (n)$ – double array: The solution vector $x$ .
2: $p (:)$ – double array: The dimension of the array p will be $\max (1, n - 1)$ if $wantp = true$ and $1$ otherwise

With wantp as true, the $i$ th element of p contains the reflection coefficient, $p_{i}$ , for the $i$ th step, for $i = 1, 2, \dots, n - 1$ . (See Further Comments.) If wantp is false, then p is not referenced.
3: $ifail$ – int64int32nag_int scalar: $ifail = 0$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Note: nag_linsys_real_toeplitz_solve (f04ff) may return useful information for one or more of the following detected errors or warnings.

Errors or warnings detected by the function:

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

$ifail = - 1$

On entry,	$n < 0$ ,
or	$t (0) \leq 0.0$ .

W $ifail > 0$

The principal minor of order ifail of the Toeplitz matrix is not positive definite to working accuracy. The first (

ifail - 1

) elements of x return the solution of the equations

T_{ifail - 1} x = {(b_{1}, b_{2}, \dots, b_{ifail - 1})}^{T},

where

T_{k}

is the

k

th principal minor of

T

$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 solution of the equations certainly satisfies

r = T x - b,

where

‖r‖

is approximately bounded by

‖r‖ \leq c ε C (T),

c

being a modest function of

n

ε

being the machine precision and

C (T)

being the condition number of

T

with respect to inversion. This bound is almost certainly pessimistic, but it seems unlikely that the method of Levinson is backward stable, so caution should be exercised when

T

is ill-conditioned. The following bound on

T^{- 1}

holds:

\max (\frac{1}{\prod_{i = 1}^{n - 1} (1 - p_{i}^{2})}, \frac{1}{\prod_{i = 1}^{n - 1} (1 - p_{i})}) \leq {‖T^{- 1}‖}_{1} \leq \prod_{i = 1}^{n - 1} (\frac{1 + |p_{i}|}{1 - |p_{i}|}) .

(See Golub and Van Loan (1996).) The norm of

T^{- 1}

may also be estimated using function nag_linsys_real_gen_norm_rcomm (f04yd). For further information on stability issues see Bunch (1985), Bunch (1987), Cybenko (1980) and Golub and Van Loan (1996).

Further Comments

The number of floating-point operations used by nag_linsys_real_toeplitz_solve (f04ff) is approximately

4 n^{2}

y_{i}

is the solution of the equations

T_{i} y_{i} = - {(τ_{1} τ_{2} \dots τ_{i})}^{T},

then the partial correlation coefficient

p_{i}

is defined as the

i

th element of

y_{i}

Example

This example finds the solution of the equations

T x = b

, where

T = (\begin{array}{l} 4 & 3 & 2 & 1 \\ 3 & 4 & 3 & 2 \\ 2 & 3 & 4 & 3 \\ 1 & 2 & 3 & 4 \end{array}) and b = (\begin{array}{l} 1 \\ 1 \\ 1 \\ 1 \end{array}) .

Open in the MATLAB editor: f04ff_example

function f04ff_example


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

% Solve Tx = b for positive definite Toeplitz T
t = [4     3     2     1];
b = [1     1     1     1];

wantp = true;
[x, p, ifail] = f04ff(t, b, wantp);

disp('Solution vector');
disp(x');
disp('Reflection coefficients');
disp(p');

f04ff example results

Solution vector
    0.2000    0.0000   -0.0000    0.2000

Reflection coefficients
   -0.7500    0.1429    0.1667

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

Chapter Contents

Chapter Introduction

NAG Toolbox