hide long namesshow long names
hide short namesshow short names
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_yule (f04fe)

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

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:     n int64int32nag_int scalar
The order of the Toeplitz matrix T.
Constraint: n0. When n=0, then an immediate return is effected.
2:     t0:n – double array
t0 must contain the value τ0 of the diagonal elements of T, and the remaining n elements of t must contain the elements of the vector t.
Constraint: t0>0.0. Note that if this is not true, then the Toeplitz matrix cannot be positive definite.
3:     wantp – logical scalar
Must be set to true if the partial (auto)correlation coefficients are required, and must be set to false otherwise.
4:     wantv – logical scalar
Must be set to true if the mean square prediction errors are required, and must be set to false otherwise.

Optional Input Parameters

None.

Output Parameters

1:     xn – double array
The solution vector x.
2:     p: – double array
The dimension of the array p will be max1,n if wantp=true and 1 otherwise
With wantp as true, the ith element of p contains the partial (auto)correlation coefficient, or reflection coefficient, pi for the ith step. (See Further Comments and Chapter G13.) If wantp is false, then p is not referenced. Note that in any case, xn=pn.
3:     v: – double array
The dimension of the array v will be max1,n if wantv=true and 1 otherwise
With wantv as true, the ith element of v contains the mean square prediction error, or predictor error variance ratio, vi, for the ith step. (See Further Comments and Chapter G13.) If wantv is false, then v is not referenced.
4:     vlast – double scalar
The value of vn, the mean square prediction error for the final step.
5:     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_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.

   ifail=-1
On entry,n<0,
ort00.0.
W  ifail>0
The principal minor of order (ifail+1) of the Toeplitz matrix is not positive definite to working accuracy. If, on exit, xifail is close to unity, then the principal minor was close to being singular, and the sequence τ0,τ1,,τifail may be a valid sequence nevertheless. The first ifail elements of x return the solution of the equations
Tifailx=-τ1,τ2,,τifailT,  
where Tifail 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 vifail. In particular if ifail=n, then the solution of the equations Tx=-t is returned in x, but τn is such that Tn+1 would not be positive definite to working accuracy.
   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=Tx+t,  
where r1 is approximately bounded by
r1cε i=1n1+pi-1 ,  
c being a modest function of n and ε 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 pn 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 t-11 hold:
max 1 vn-1 , 1 i=1 n-1 1-pi T-11 i=1 n-1 1+pi 1-pi .  
Note:  vn<vn-1. The norm of T-1 may also be estimated using function nag_linsys_real_gen_norm_rcomm (f04yd).

Further Comments

The number of floating-point operations used by nag_linsys_real_toeplitz_yule (f04fe) is approximately 2n2, independent of the values of wantp and wantv.
The mean square prediction error, vi, is defined as
vi=τ0+τ1τ2τi-1yi-1/τ0,  
where yi is the solution of the equations
Tiyi=-τ1τ2τiT  
and the partial correlation coefficient, pi, is defined as the ith element of yi. Note that vi=1-pi2vi-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


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