Solve a linear Toeplitz system
MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.
MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.
linalg::toeplitzSolve(t, y) returns the solution of
the linear Toeplitz system with i =
1, …, n.
linalg::toeplitzSolve(t, y) with
t = [tk,
…, t0, …, t- k] and
y = [y1,
…, yn] solves
the n×n Toeplitz
with 2 k + 1 bands.
linalg::toeplitzSolve implements the Levinson
algorithm. It uses O(n2) elementary
operations to solve the Toeplitz system. The memory requirements are O(n).
For dense Toeplitz systems, it is faster than the general solver
solve and the linear
Note that the Levinson algorithm requires that all principal minors
linalg::toeplitzSolve does not manage
to find the solution due to this limitation, or if the system is very
sparse with k smaller
we recommend to generate the corresponding Toeplitz matrix via
compute the solution via
respectively. Cf. Example 2
linalg::toeplitzSolve can solve Toeplitz
systems over arbitrary coefficient rings. Just make sure that both
the Toeplitz entries t as
well as the components of the 'right hand side' y are
elements of the desired coefficient ring. Cf. Example 3.
The Toeplitz entries t and the right hand side y of the linear system are entered as row vectors:
t := matrix([4, 2, 1, 3, 5]): y := matrix([y1, y2, y3]):
The solution of the Toeplitz system is returned as a vector of the same type as the input vector y:
x := linalg::toeplitzSolve(t, y): x, domtype(x)
If the input vector is a list, the output is a list, too:
x := linalg::toeplitzSolve(t, [y1, y2, y3]): x, domtype(x)
delete t, y, x:
The Levinson algorithm cannot solve the following Toeplitz system because the first principal minor of the Toeplitz matrix (the central element of the Toeplitz entries) vanishes:
linalg::toeplitzSolve([1, 0, 1], [y1, y2, y3, y4])
This does not necessarily imply that the Toeplitz system is
not solvable. We generate the corresponding Toeplitz matrix and use
a generic linear solver such as
T := linalg::toeplitz(4, 4, [1, 0, 1])
linalg::matlinsolve(T, matrix([y1, y2, y3, y4]))
We solve a Toeplitz system over the field ℤ7 (the
integers modulo 7) represented by the domain
R := Dom::IntegerMod(7): t := [R(5), R(3), R(2), R(5), R(1)]: y := [R(1), R(2), R(3)]: linalg::toeplitzSolve(t, y)
delete R, t, y:
A vector or a list with 2 k +
1 elements. (A vector is a (2 k +
1)×1 or a 1
×(2 k + 1) matrix
A vector or a list with n elements
Vector or list with n elements
of the same domain type as the elements of
returned if the algorithm does not succeed in finding a solution.