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

T_{n} x_{n} = - t_{n},

where

T_{n}

is the

n

n

symmetric positive definite Toeplitz matrix

T_{n} = (\begin{array}{l} τ_{0} & τ_{1} & τ_{2} & \dots & τ_{n - 1} \\ τ_{1} & τ_{0} & τ_{1} & \dots & τ_{n - 2} \\ τ_{2} & τ_{1} & τ_{0} & \dots & τ_{n - 3} \\ . & . & . & . \\ τ_{n - 1} & τ_{n - 2} & τ_{n - 3} & \dots & τ_{0} \end{array})

and

t_{n}

is the vector

t_{n}^{T} = (τ_{1} τ_{2} \dots τ_{n}),

given the solution of the equations

T_{n - 1} x_{n - 1} = - t_{n - 1} .

The function will normally be used to successively solve the equations

T_{k} x_{k} = - t_{k}, k = 1, 2, \dots, 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: $t (0 : n)$ – double array: $t (0)$ 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_{n}$ .

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

With $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 $x (n)$ need not be specified.

Constraint: $|x (n - 1)| < 1.0$ . Note that this is the partial (auto)correlation coefficient, or reflection coefficient, for the $(n - 1)$ th step. If the constraint does not hold, then $T_{n}$ cannot be positive definite.
3: $v$ – double scalar: With $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: $n$ – int64int32nag_int scalar: Default: the dimension of the array x.
The order of the Toeplitz matrix $T$ .

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

Output Parameters

1: $x (:)$ – double array: The dimension of the array x will be $\max (1, n)$

The solution vector $x_{n}$ . The element $x (n)$ returns the partial (auto)correlation coefficient, or reflection coefficient, for the $n$ th step. If $|x (n)| \geq 1.0$ , then the matrix $T_{n + 1}$ will not be positive definite to working accuracy.
2: $v$ – double scalar: The mean square prediction error, or predictor error variance ratio, $ν_{n}$ , for the $n$ th step. (See Further Comments and the Introduction to Chapter G13.)
3: $ifail$ – int64int32nag_int scalar: $ifail = 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.

$ifail = - 1$

On entry,	$n < 0$ ,
or	$t (0) \leq 0.0$ ,
or	$n > 1$ and $\|x (n - 1)\| \geq 1.0$ .

W $ifail = 1$

The Toeplitz matrix

T_{n + 1}

is not positive definite to working accuracy. If, on exit,

x (n)

is close to unity, then the principal minor was probably close to being singular, and the sequence

τ_{0}, τ_{1}, \dots, τ_{n}

may be a valid sequence nevertheless. x returns the solution of the equations

T_{n} x_{n} = - t_{n},

and v returns

v_{n}

, but it may not be positive.

$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_{n} x_{n} + t_{n},

where

{‖r‖}_{1}

is approximately bounded by

{‖r‖}_{1} \leq c ε (\prod_{i = 1}^{n} (1 + |p_{i}|) - 1),

c

being a modest function of

n

ε

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:

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

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).

Further Comments

The number of floating-point operations used by this function is approximately

4 n

The mean square prediction errors,

v_{i}

, is defined as

v_{i} = (τ_{0} + t_{i - 1}^{T} x_{i - 1}) / τ_{0} .

Note that

v_{i} = (1 - p_{i}^{2}) 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

T_{4} = (\begin{array}{l} 4 & 3 & 2 & 1 \\ 3 & 4 & 3 & 2 \\ 2 & 3 & 4 & 3 \\ 1 & 2 & 3 & 4 \end{array}) and t_{4} = (\begin{array}{l} 3 \\ 2 \\ 1 \\ 0 \end{array}) .

Open in the MATLAB editor: f04me_example

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

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

Chapter Contents

Chapter Introduction

NAG Toolbox