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_toeplitz_solve (f04ff)

## Purpose

nag_linsys_real_toeplitz_solve (f04ff) solves the equations $Tx=b$, where $T$ is a real symmetric positive definite Toeplitz matrix.

## Syntax

[x, p, ifail] = f04ff(t, b, wantp, 'n', n)
[x, p, ifail] = nag_linsys_real_toeplitz_solve(t, b, wantp, 'n', n)

## Description

nag_linsys_real_toeplitz_solve (f04ff) solves the equations
 $Tx=b,$
where $T$ is the $n$ by $n$ symmetric positive definite Toeplitz matrix
 $T= τ0 τ1 τ2 … τn-1 τ1 τ0 τ1 … τn-2 τ2 τ1 τ0 … τn-3 . . . . τn-1 τn-2 τn-3 … τ0$
and $b$ is an $n$-element vector.
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:     $\mathrm{t}\left(:\right)$ – double array
The dimension of the array t must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$
${\mathbf{t}}\left(\mathit{i}+1\right)$ must contain the value ${\tau }_{\mathit{i}}$, for $\mathit{i}=0,1,\dots ,{\mathbf{n}}-1$.
Constraint: ${\mathbf{t}}\left(1\right)>0.0$. Note that if this is not true, then the Toeplitz matrix cannot be positive definite.
2:     $\mathrm{b}\left(:\right)$ – double array
The dimension of the array b must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$
The right-hand side vector $b$.
3:     $\mathrm{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:     $\mathrm{n}$int64int32nag_int scalar
Default: the dimension of the arrays t, b.
The order of the Toeplitz matrix $T$.
Constraint: ${\mathbf{n}}\ge 0$. When ${\mathbf{n}}=0$, then an immediate return is effected.

### Output Parameters

1:     $\mathrm{x}\left({\mathbf{n}}\right)$ – double array
The solution vector $x$.
2:     $\mathrm{p}\left(:\right)$ – double array
The dimension of the array p will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}-1\right)$ if ${\mathbf{wantp}}=\mathit{true}$ and $1$ otherwise
With wantp as true, the $i$th element of p contains the reflection coefficient, ${p}_{\mathit{i}}$, for the $\mathit{i}$th step, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}-1$. (See Further Comments.) If wantp is false, then p is not referenced.
3:     $\mathrm{ifail}$int64int32nag_int scalar
${\mathbf{ifail}}={\mathbf{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.

${\mathbf{ifail}}=-1$
 On entry, ${\mathbf{n}}<0$, or ${\mathbf{t}}\left(0\right)\le 0.0$.
W  ${\mathbf{ifail}}>0$
The principal minor of order ifail of the Toeplitz matrix is not positive definite to working accuracy. The first (${\mathbf{ifail}}-1$) elements of x return the solution of the equations
 $Tifail-1x=b1,b2,…,bifail-1T,$
where ${T}_{k}$ is the $k$th principal minor of $T$.
${\mathbf{ifail}}=-99$
An unexpected error has been triggered by this routine. Please contact NAG.
${\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 solution of the equations certainly satisfies
 $r = Tx-b ,$
where $‖r‖$ is approximately bounded by
 $r ≤ cεCT ,$
$c$ being a modest function of $n$, $\epsilon$ being the machine precision and $C\left(T\right)$ 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 1 ∏ i=1 n-1 1 - pi2 , 1 ∏ i=1 n-1 1-pi ≤ T-11 ≤ ∏ i=1 n-1 1+pi 1-pi .$
(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}$.
If ${y}_{i}$ is the solution of the equations
 $Tiyi=-τ1τ2…τiT,$
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 $Tx=b$, where
 $T= 4 3 2 1 3 4 3 2 2 3 4 3 1 2 3 4 and b= 1 1 1 1 .$
```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

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015