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_update (f04me)

## Purpose

nag_linsys_real_toeplitz_yule_update (f04me) updates the solution to the Yule–Walker equations for a real symmetric positive definite Toeplitz system.

## Syntax

[x, v, ifail] = f04me(t, x, v, 'n', n)
[x, v, ifail] = nag_linsys_real_toeplitz_yule_update(t, x, v, 'n', n)

## Description

nag_linsys_real_toeplitz_yule_update (f04me) solves the equations
 $Tnxn=-tn,$
where ${T}_{n}$ is the $n$ by $n$ symmetric positive definite Toeplitz matrix
 $Tn= τ0 τ1 τ2 … τn-1 τ1 τ0 τ1 … τn-2 τ2 τ1 τ0 … τn-3 . . . . τn-1 τn-2 τn-3 … τ0$
and ${t}_{n}$ is the vector
 $tnT =τ1τ2…τn,$
given the solution of the equations
 $Tn- 1xn- 1=-tn- 1.$
The function will normally be used to successively solve the equations
 $Tkxk=-tk, k=1,2,…,n.$
If it is desired to solve the equations for a single value of $n$, then function nag_linsys_real_toeplitz_yule (f04fe) may be called. This function uses the method of Durbin (see Durbin (1960) and Golub and Van Loan (1996)).

## 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{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}_{n}$.
Constraint: ${\mathbf{t}}\left(0\right)>0.0$. Note that if this is not true, then the Toeplitz matrix cannot be positive definite.
2:     $\mathrm{x}\left(:\right)$ – double array
The dimension of the array x must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$
With ${\mathbf{n}}>1$ the ($n-1$) elements of the solution vector ${x}_{n-1}$ as returned by a previous call to nag_linsys_real_toeplitz_yule_update (f04me). The element ${\mathbf{x}}\left({\mathbf{n}}\right)$ need not be specified.
Constraint: $\left|{\mathbf{x}}\left({\mathbf{n}}-1\right)\right|<1.0$. Note that this is the partial (auto)correlation coefficient, or reflection coefficient, for the $\left(n-1\right)$th step. If the constraint does not hold, then ${T}_{n}$ cannot be positive definite.
3:     $\mathrm{v}$ – double scalar
With ${\mathbf{n}}>1$ the mean square prediction error for the ($n-1$)th step, as returned by a previous call to nag_linsys_real_toeplitz_yule_update (f04me).

### Optional Input Parameters

1:     $\mathrm{n}$int64int32nag_int scalar
Default: the dimension of the array x.
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(:\right)$ – double array
The dimension of the array x will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$
The solution vector ${x}_{n}$. The element ${\mathbf{x}}\left({\mathbf{n}}\right)$ returns the partial (auto)correlation coefficient, or reflection coefficient, for the $n$th step. If $\left|{\mathbf{x}}\left({\mathbf{n}}\right)\right|\ge 1.0$, then the matrix ${T}_{n+1}$ will not be positive definite to working accuracy.
2:     $\mathrm{v}$ – double scalar
The mean square prediction error, or predictor error variance ratio, ${\nu }_{n}$, for the $n$th step. (See Further Comments and the Introduction to Chapter G13.)
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

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$, or ${\mathbf{n}}>1$ and $\left|{\mathbf{x}}\left({\mathbf{n}}-1\right)\right|\ge 1.0$.
W  ${\mathbf{ifail}}=1$
The Toeplitz matrix ${T}_{n+1}$ is not positive definite to working accuracy. If, on exit, ${\mathbf{x}}\left({\mathbf{n}}\right)$ is close to unity, then the principal minor was probably close to being singular, and the sequence ${\tau }_{0},{\tau }_{1},\dots ,{\tau }_{{\mathbf{n}}}$ may be a valid sequence nevertheless. x returns the solution of the equations
 $Tnxn=-tn,$
and v returns ${v}_{n}$, but it may not be positive.
${\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=Tnxn+tn,$
where ${‖r‖}_{1}$ is approximately bounded by
 $r1≤cε ∏i=1n1+pi-1 ,$
$c$ being a modest function of $n$, $\epsilon$ being the machine precision and ${p}_{k}$ being the $k$th element of ${x}_{k}$. This bound is almost certainly pessimistic, but it has not yet been established whether or not the method of Durbin is backward stable. For further information on stability issues see Bunch (1985), Bunch (1987), Cybenko (1980) and Golub and Van Loan (1996). The following bounds on ${‖{T}_{n}^{-1}‖}_{1}$ hold:
 $max1vn-1,1∏i=1 n-11-pi ≤Tn-11≤∏i=1 n-1 1+pi 1-pi ,$
where ${v}_{n}$ is the mean square prediction error for the $n$th step. (See Cybenko (1980).) Note that ${v}_{n}<{v}_{n-1}$. The norm of ${T}_{n}^{-1}$ may also be estimated using function nag_linsys_real_gen_norm_rcomm (f04yd).

The number of floating-point operations used by this function is approximately $4n$.
The mean square prediction errors, ${v}_{i}$, is defined as
 $vi=τ0+ ti-1T xi-1/τ0.$
Note that ${v}_{i}=\left(1-{p}_{i}^{2}\right){v}_{i-1}$.

## Example

This example finds the solution of the Yule–Walker equations ${T}_{k}{x}_{k}=-{t}_{k}$, $k=1,2,3,4$ where
 $T4= 4 3 2 1 3 4 3 2 2 3 4 3 1 2 3 4 and t4= 3 2 1 0 .$
```function f04me_example

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

t = [4; 3; 2; 1; 0];
v = 0;
x=[0];
fprintf('  order   MSP error   solution\n');
for k=1:4
[x, v, ifail] = f04me(t(1:k+1), x, v);
fprintf('%6d%11.4f    ', k, v);
fprintf('%8.4f',transpose(x));
fprintf('\n');
if k < 4
x = [x; 0]; % Extend x by one element
end
end

```
```f04me example results

order   MSP error   solution
1     0.4375     -0.7500
2     0.4286     -0.8571  0.1429
3     0.4167     -0.8333  0.0000  0.1667
4     0.4000     -0.8000  0.0000 -0.0000  0.2000
```

Chapter Contents
Chapter Introduction
NAG Toolbox

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