PDF version (NAG web site
, 64-bit version, 64-bit version)
NAG Toolbox: nag_linsys_real_toeplitz_update (f04mf)
Purpose
nag_linsys_real_toeplitz_update (f04mf) updates the solution of the equations , where is a real symmetric positive definite Toeplitz matrix.
Syntax
Description
nag_linsys_real_toeplitz_update (f04mf) solves the equations
where
is the
by
symmetric positive definite Toeplitz matrix
and
is the
-element vector
, given the solution of the equations
This function will normally be used to successively solve the equations
If it is desired to solve the equations for a single value of
, then function
nag_linsys_real_toeplitz_solve (f04ff) may be called. This function uses the method of Levinson (see
Levinson (1947) 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
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:
– double array
-
The dimension of the array
t
must be at least
must contain the value , for .
Constraint:
. Note that if this is not true, then the Toeplitz matrix cannot be positive definite.
- 2:
– double array
-
The dimension of the array
b
must be at least
The right-hand side vector .
- 3:
– double array
-
The dimension of the array
x
must be at least
With the () elements of the solution vector as returned by a previous call to nag_linsys_real_toeplitz_update (f04mf). The element need not be specified.
- 4:
– double array
-
The dimension of the array
work
must be at least
With
the elements of
work should be as returned from a previous call to
nag_linsys_real_toeplitz_update (f04mf) with (
) as the argument
n.
Optional Input Parameters
- 1:
– int64int32nag_int scalar
-
Default:
the dimension of the arrays
t,
b,
x.
The order of the Toeplitz matrix .
Constraint:
. When , then an immediate return is effected.
Output Parameters
- 1:
– double array
-
The dimension of the array
x will be
The solution vector .
- 2:
– double scalar
-
The reflection coefficient
. (See
Further Comments.)
- 3:
– double array
-
The dimension of the array
work will be
The first (
) elements of
work contain the solution to the Yule–Walker equations
where
.
- 4:
– int64int32nag_int scalar
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.
-
-
- W
-
The Toeplitz matrix
is not positive definite to working accuracy. If, on exit,
p is close to unity, then
was probably close to being singular.
-
An unexpected error has been triggered by this routine. Please
contact
NAG.
-
Your licence key may have expired or may not have been installed correctly.
-
Dynamic memory allocation failed.
Accuracy
The computed solution of the equations certainly satisfies
where
is approximately bounded by
being a modest function of
,
being the
machine precision and
being the condition number of
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
is ill-conditioned. The following bound on
holds:
(See
Golub and Van Loan (1996).) The norm of
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 this function is approximately .
If
is the solution of the equations
then the reflection coefficient
is defined as the
th element of
.
Example
This example finds the solution of the equations
,
, where
Open in the MATLAB editor:
f04mf_example
function f04mf_example
fprintf('f04mf example results\n\n');
t = [4; 3; 2; 1];
b = [1; 1; 1; 1];
x = [0];
work = zeros(9,1);
fprintf(' order refl. coeff solution\n');
for k=1:4
[x, p, work, ifail] = f04mf( ...
t(1:k), b(1:k), x, work);
if k > 1
fprintf('%6d%11.4f ', k, p);
else
fprintf('%6d%11.4s ', k, ' ');
end
fprintf('%8.4f',transpose(x));
fprintf('\n');
if k < 4
x = [x; 0];
end
end
f04mf example results
order refl. coeff solution
1 0.2500
2 -0.7500 0.1429 0.1429
3 0.1429 0.1667 0.0000 0.1667
4 0.1667 0.2000 0.0000 -0.0000 0.2000
PDF version (NAG web site
, 64-bit version, 64-bit version)
© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015