Editing Levinson recursion (section)

=== Obtaining the backward vectors ===
Even if the matrix is not symmetric, then the ''n''<sup>th</sup> forward and backward vector may be found from the vectors of length ''n''&nbsp;−&nbsp;1 as follows. First, the forward vector may be extended with a zero to obtain:

:<math>\mathbf T^n \begin{bmatrix} \vec f^{n-1} \\ 0 \\ \end{bmatrix} =
  \begin{bmatrix}
    \        & \               & \     & t_{-n+1}   \\
    \        & \mathbf T^{n-1} & \     & t_{-n+2} \\
    \        & \               & \     & \vdots   \\
    t_{n-1}  & t_{n-2}         & \dots & t_0      \\
  \end{bmatrix}
  \begin{bmatrix}  \            \\
                   \vec f^{n-1} \\
                   \            \\
                   0            \\
                   \            \\
  \end{bmatrix} = 
  \begin{bmatrix}  1            \\
                   0            \\
                   \vdots       \\
                   0            \\
                   \varepsilon_f^n
  \end{bmatrix}. </math>

In going from '''''T''<sup>''n''−1</sup>''' to '''''T<sup>n</sup>''''', the extra ''column'' added to the matrix does not perturb the solution when a zero is used to extend the forward vector. However, the extra ''row'' added to the matrix ''has'' perturbed the solution; and it has created an unwanted error term ''ε''<sub>''f''</sub> which occurs in the last place. The above equation gives it the value of:

: <math> \varepsilon_f^n \ = \  \sum_{i=1}^{n-1} \ M_{ni} \  f_{i}^{n-1} \ = \ \sum_{i=1}^{n-1} \  t_{n-i} \ f_{i}^{n-1}. </math>

This error will be returned to shortly and eliminated from the new forward vector; but first, the backwards vector must be extended in a similar (albeit reversed) fashion. For the backwards vector,

:<math> \mathbf T^n \begin{bmatrix} 0 \\ \vec b^{n-1} \\ \end{bmatrix} =
\begin{bmatrix}
    t_0     & \dots & t_{-n+2}         & t_{-n+1} \\
    \vdots  & \     & \               & \       \\
    t_{n-2} & \     & \mathbf T^{n-1} & \       \\
    t_{n-1} & \     & \               &
  \end{bmatrix}
  \begin{bmatrix}  \            \\
                   0            \\
                   \            \\
                   \vec b^{n-1} \\
                   \            \\
  \end{bmatrix} = 
  \begin{bmatrix}  \varepsilon_b^n  \\
                   0             \\
                   \vdots        \\
                   0             \\
                   1
  \end{bmatrix}. </math>

As before, the extra column added to the matrix does not perturb this new backwards vector; but the extra row does. Here we have another unwanted error ''ε''<sub>''b''</sub> with value:

:<math> \varepsilon_b^n \ = \ \sum_{i=2}^n \  M_{1i} \ b_{i-1}^{n-1} \ = \ \sum_{i=1}^{n-1} \  t_{-i} \ b_i^{n-1}. \ </math>

These two error terms can be used to form higher-order forward and backward vectors described as follows. Using the linearity of matrices, the following identity holds for all <math>(\alpha,\beta)</math>:

:<math>\mathbf T \left( \alpha
  \begin{bmatrix}
                   \vec f \\
                   \            \\
                   0            \\
  \end{bmatrix} + \beta
  \begin{bmatrix}
                   0            \\
                   \            \\
                   \vec b
  \end{bmatrix} \right ) = \alpha
  \begin{bmatrix}  1        \\
                   0        \\
                   \vdots   \\
                   0        \\
                   \varepsilon_f \\
  \end{bmatrix} + \beta
  \begin{bmatrix}  \varepsilon_b  \\
                   0             \\
                   \vdots        \\
                   0             \\
                   1
  \end{bmatrix}.</math>

If ''α'' and ''β'' are chosen so that the right hand side yields ''ê''<sub>1</sub> or ''ê''<sub>''n''</sub>, then the quantity in the parentheses will fulfill the definition of the ''n''<sup>th</sup> forward or backward vector, respectively. With those alpha and beta chosen, the vector sum in the parentheses is simple and yields the desired result.

To find these coefficients, <math>\alpha^n_{f}</math>, <math>\beta^n_{f}</math> are such that :
:<math>
\vec f^n = \alpha^n_{f} \begin{bmatrix} \vec f^{n-1}\\
0
\end{bmatrix}
+\beta^n_{f}\begin{bmatrix}0\\
\vec b^{n-1}
\end{bmatrix}
</math>
and respectively  <math>\alpha^n_{b}</math>, <math>\beta^n_{b}</math> are such that :
:<math>\vec b^n = \alpha^n_{b}
\begin{bmatrix}
\vec f^{n-1}\\
0
\end{bmatrix}
+\beta^n_{b}\begin{bmatrix}
0\\
\vec b^{n-1}
\end{bmatrix}.
</math>
By multiplying both previous equations by <math>{\mathbf T}^n</math> one gets the following equation:
: <math>
\begin{bmatrix} 1 & \varepsilon^n_b \\
0 & 0 \\
\vdots & \vdots \\
0 & 0 \\
\varepsilon^n_f & 1
\end{bmatrix} \begin{bmatrix} \alpha^n_f & \alpha^n_b \\ \beta^n_f & \beta^n_b \end{bmatrix}
= \begin{bmatrix}
1 & 0 \\
0 & 0 \\
\vdots & \vdots \\
0 & 0 \\
0 & 1
\end{bmatrix}.</math>

Now, all the zeroes in the middle of the two vectors above being disregarded and collapsed, only the following equation is left:

: <math> \begin{bmatrix} 1 & \varepsilon^n_b \\ \varepsilon^n_f & 1 \end{bmatrix} \begin{bmatrix} \alpha^n_f & \alpha^n_b \\ \beta^n_f & \beta^n_b \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}.</math>

With these solved for (by using the Cramer 2×2 matrix inverse formula), the new forward and backward vectors are:

: <math>\vec f^n = {1 \over { 1 - \varepsilon_b^n \varepsilon_f^n }}          \begin{bmatrix} \vec f^{n-1} \\ 0 \end{bmatrix}
                 - { \varepsilon_f^n \over { 1 - \varepsilon_b^n \varepsilon_f^n }}\begin{bmatrix} 0 \\ \vec b^{n-1} \end{bmatrix}</math>

: <math>\vec b^n =  { 1 \over { 1 - \varepsilon_b^n \varepsilon_f^n }}         \begin{bmatrix} 0 \\ \vec b^{n-1} \end{bmatrix}
                 - { \varepsilon_b^n \over { 1 - \varepsilon_b^n \varepsilon_f^n }}\begin{bmatrix} \vec f^{n-1} \\ 0 \end{bmatrix}.</math>

Performing these vector summations, then, gives the ''n''<sup>th</sup> forward and backward vectors from the prior ones. All that remains is to find the first of these vectors, and then some quick sums and multiplications give the remaining ones. The first forward and backward vectors are simply:

: <math>\vec f^1 = \vec b^1 = \left[ {1 \over M_{11}} \right] = \left[ {1 \over t_0} \right].</math>