列文森递归

列文森递归或列文森-杜宾递归是线性代数中的一个程序，用于递归地计算涉及托普利茨矩阵的方程的解。该算法的运行时间为Θ(n2)，这比高斯-乔丹消除法有很大的改进，后者的运行时间为Θ(n3)。与这些相比，列文森递归往往在计算上更快，但对四舍五入误差等计算不准确的情况更敏感。Toeplitz矩阵的Bareiss算法运行速度与Levinson递归差不多，但它使用O空间，而Levinson递归只使用O空间。不过，Bareiss算法在数值上是稳定的，而Levinson递归充其量只是弱稳定的。较新的算法，称为渐进式快速或有时超快速的Toeplitz算法，可以在Θ内解决各种p。列文森递归仍然很受欢迎，原因有几个；其一，相比之下，它比较容易理解；其二，对于小的n，它可以比超快算法更快。

矩阵方程的形式为Levinson-Durbin算法可用于任何此类方程，只要M是一个已知的Toeplitz矩阵，其主对角线不为零。这里在本文中，êi是一个完全由零组成的向量，除了它的第1位，即持有1的数值。它的长度将隐含地由周围的环境决定。术语N指的是上述矩阵的宽度--M是一个N×N矩阵。最后，在本文中，上标指的是一个归纳指数，而下标则表示指数。

该算法分两步进行。在xxx步，建立两组向量，称为前向和后向。前向向量用于帮助得到后向向量集；然后可以立即丢弃。后向向量对于第二步是必要的，在第二步中它们被用来建立所需的解决方案。当M是一个对称矩阵时，会出现一个重要的简化；然后两个向量通过bni=fnn+1-i的关系，也就是说，它们是彼此的行反转。在这种特殊情况下，这可以节省一些额外的计算。

即使矩阵不是对称的，那么第n个前向和后向量也可以从长度为n-1的向量中找到，方法如下。首先，前向量可以用一个零来扩展，得到。在从Tn-1到Tn的过程中，当一个零被用来扩展前向量时，矩阵中额外增加的列不会扰乱解决方案。