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

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

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:     t: – double array
The dimension of the array t must be at least max1,n
ti+1 must contain the value τi, for i=0,1,,n-1.
Constraint: t1>0.0. Note that if this is not true, then the Toeplitz matrix cannot be positive definite.
2:     b: – double array
The dimension of the array b must be at least max1,n
The right-hand side vector b.
3:     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:     n int64int32nag_int scalar
Default: the dimension of the arrays t, b.
The order of the Toeplitz matrix T.
Constraint: n0. When n=0, then an immediate return is effected.

Output Parameters

1:     xn – double array
The solution vector x.
2:     p: – double array
The dimension of the array p will be max1,n-1 if wantp=true and 1 otherwise
With wantp as true, the ith element of p contains the reflection coefficient, pi, for the ith step, for i=1,2,,n-1. (See Further Comments.) If wantp is false, then p is not referenced.
3:     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_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.

   ifail=-1
On entry,n<0,
ort00.0.
W  ifail>0
The principal minor of order ifail of the Toeplitz matrix is not positive definite to working accuracy. The first (ifail-1) elements of x return the solution of the equations
Tifail-1x=b1,b2,,bifail-1T,  
where Tk is the kth principal minor of T.
   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-b ,  
where r is approximately bounded by
r cεCT ,  
c being a modest function of n, ε being the machine precision and CT 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 4n2.
If yi is the solution of the equations
Tiyi=-τ1τ2τiT,  
then the partial correlation coefficient pi is defined as the ith element of yi.

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