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_linsys_real_toeplitz_yule (f04fe)

## Purpose

nag_linsys_real_toeplitz_yule (f04fe) solves the Yule–Walker equations for a real symmetric positive definite Toeplitz system.

## Syntax

[x, p, v, vlast, ifail] = f04fe(n, t, wantp, wantv)
[x, p, v, vlast, ifail] = nag_linsys_real_toeplitz_yule(n, t, wantp, wantv)

## Description

nag_linsys_real_toeplitz_yule (f04fe) solves the equations
 $Tx=-t,$
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 $t$ is the vector
 $tT=τ1,τ2…τn.$
The function uses the method of Durbin (see Durbin (1960) and Golub and Van Loan (1996)). Optionally the mean square prediction errors and/or the partial correlation coefficients for each step can 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
Durbin J (1960) The fitting of time series models Rev. Inst. Internat. Stat. 28 233
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{n}$int64int32nag_int scalar
The order of the Toeplitz matrix $T$.
Constraint: ${\mathbf{n}}\ge 0$. When ${\mathbf{n}}=0$, then an immediate return is effected.
2:     $\mathrm{t}\left(0:{\mathbf{n}}\right)$ – double array
${\mathbf{t}}\left(0\right)$ must contain the value ${\tau }_{0}$ of the diagonal elements of $T$, and the remaining n elements of t must contain the elements of the vector $t$.
Constraint: ${\mathbf{t}}\left(0\right)>0.0$. Note that if this is not true, then the Toeplitz matrix cannot be positive definite.
3:     $\mathrm{wantp}$ – logical scalar
Must be set to true if the partial (auto)correlation coefficients are required, and must be set to false otherwise.
4:     $\mathrm{wantv}$ – logical scalar
Must be set to true if the mean square prediction errors are required, and must be set to false otherwise.

None.

### 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}}\right)$ if ${\mathbf{wantp}}=\mathit{true}$ and $1$ otherwise
With wantp as true, the $i$th element of p contains the partial (auto)correlation coefficient, or reflection coefficient, ${p}_{i}$ for the $i$th step. (See Further Comments and Chapter G13.) If wantp is false, then p is not referenced. Note that in any case, ${x}_{n}={p}_{n}$.
3:     $\mathrm{v}\left(:\right)$ – double array
The dimension of the array v will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$ if ${\mathbf{wantv}}=\mathit{true}$ and $1$ otherwise
With wantv as true, the $i$th element of v contains the mean square prediction error, or predictor error variance ratio, ${v}_{i}$, for the $i$th step. (See Further Comments and Chapter G13.) If wantv is false, then v is not referenced.
4:     $\mathrm{vlast}$ – double scalar
The value of ${v}_{n}$, the mean square prediction error for the final step.
5:     $\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_yule (f04fe) 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 (${\mathbf{ifail}}+1$) of the Toeplitz matrix is not positive definite to working accuracy. If, on exit, ${x}_{{\mathbf{ifail}}}$ is close to unity, then the principal minor was close to being singular, and the sequence ${\tau }_{0},{\tau }_{1},\dots ,{\tau }_{{\mathbf{ifail}}}$ may be a valid sequence nevertheless. The first ifail elements of x return the solution of the equations
 $Tifailx=-τ1,τ2,…,τifailT,$
where ${T}_{{\mathbf{ifail}}}$ is the ifailth principal minor of $T$. Similarly, if wantp and/or wantv are true, then p and/or v return the first ifail elements of p and v respectively and vlast returns ${v}_{{\mathbf{ifail}}}$. In particular if ${\mathbf{ifail}}={\mathbf{n}}$, then the solution of the equations $Tx=-t$ is returned in x, but ${\tau }_{{\mathbf{n}}}$ is such that ${T}_{{\mathbf{n}}+1}$ would not be positive definite to working accuracy.
${\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 solution of the equations certainly satisfies
 $r=Tx+t,$
where ${‖r‖}_{1}$ is approximately bounded by
 $r1≤cε ∏i=1n1+pi-1 ,$
$c$ being a modest function of $n$ and $\epsilon$ being the machine precision. This bound is almost certainly pessimistic, but it has not yet been established whether or not the method of Durbin is backward stable. If $\left|{p}_{n}\right|$ is close to one, then the Toeplitz matrix is probably ill-conditioned and hence only just positive definite. For further information on stability issues see Bunch (1985), Bunch (1987), Cybenko (1980) and Golub and Van Loan (1996). The following bounds on ${‖{{\mathbf{t}}}^{-1}‖}_{1}$ hold:
 $max 1 vn-1 , 1 ∏ i=1 n-1 1-pi ≤ T-11 ≤ ∏ i=1 n-1 1+pi 1-pi .$
Note:  ${v}_{n}<{v}_{n-1}$. The norm of ${T}^{-1}$ may also be estimated using function nag_linsys_real_gen_norm_rcomm (f04yd).

The number of floating-point operations used by nag_linsys_real_toeplitz_yule (f04fe) is approximately $2{n}^{2}$, independent of the values of wantp and wantv.
The mean square prediction error, ${v}_{i}$, is defined as
 $vi=τ0+τ1τ2…τi-1yi-1/τ0,$
where ${y}_{i}$ is the solution of the equations
 $Tiyi=-τ1τ2…τiT$
and the partial correlation coefficient, ${p}_{i}$, is defined as the $i$th element of ${y}_{i}$. Note that ${v}_{i}=\left(1-{p}_{i}^{2}\right){v}_{i-1}$.

## Example

This example finds the solution of the Yule–Walker equations $Tx=-t$, where
 $T= 4 3 2 1 3 4 3 2 2 3 4 3 1 2 3 4 and t= 3 2 1 0 .$
```function f04fe_example

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

% Solve Yule-Walker equations for symmetric definite Toeplitz system
n = int64(4);
t = [4     3     2     1     0];

wantp = true;
wantv = true;
[x, p, v, vlast, ifail] = ...
f04fe(n, t, wantp, wantv);

disp('Solution vector');
disp(x');
disp('Reflection coefficients');
disp(p');
disp('Mean square prediction errors');
disp(v');

```
```f04fe example results

Solution vector
-0.8000    0.0000   -0.0000    0.2000

Reflection coefficients
-0.7500    0.1429    0.1667    0.2000

Mean square prediction errors
0.4375    0.4286    0.4167    0.4000

```