レビンソン再帰

行列方程式は次の形式に従います

${\displaystyle \mathbf {M} \,{\vec {x}}={\vec {y}}.}$

Mが非ゼロの主対角成分を持つ既知のトープレッツ行列である限り、レビンソン・ダービンアルゴリズムはこのような任意の方程式に適用できます。${\displaystyle {\vec {y}}}$は既知のベクトルであり、${\displaystyle {\vec {x}}}$は、まだ決定されていない未知の数値ベクトルx _iです。

この記事では、ê _iは i 番目の位置を除いてすべてゼロで構成されるベクトルであり、i番目の位置には値 1 が格納されます。その長さは周囲のコンテキストによって暗黙的に決定されます。用語Nは上記の行列の幅を指します。MはN × N行列です。最後に、この記事では、上付き文字は帰納的インデックスを指し、下付き文字はインデックスを示します。たとえば (定義)、この記事では、行列T ⁿは、 Mの左上のn × nブロックをコピーしたn × n行列です 。つまり、T ⁿ _ij = M _ijです。

T ⁿはトープレッツ行列でもあるので、次のように書くことができる。

${\displaystyle \mathbf {T} ^{n}={\begin{bmatrix}t_{0}&t_{-1}&t_{-2}&\dots &t_{-n+1}\\t_{1}&t_{0}&t_{-1}&\dots &t_{-n+2}\\t_{2}&t_{1}&t_{0}&\dots &t_{-n+3}\\\vdots &\vdots &\vdots &\ddots &\vdots \\t_{n-1}&t_{n-2}&t_{n-3}&\dots &t_{0}\end{bmatrix}}.}$

このアルゴリズムは2つのステップで進行します。最初のステップでは、順方向ベクトルと逆方向ベクトルと呼ばれる2組のベクトルが確立されます。順方向ベクトルは逆方向ベクトルのセットを取得するために使用され、その後すぐに破棄できます。逆方向ベクトルは2番目のステップで必要となり、そこで目的の解を構築するために使用されます。

レビンソン・ダービン再帰では、n番目の「前方ベクトル」が定義され、$\displaystyle {\vec {f}}^{n}}$長さnのベクトルとして、以下の条件を満たす。

${\displaystyle \mathbf {T} ^{n}{\vec {f}}^{n}={\hat {e}}_{1}.}$

n番目の「逆ベクトル」${\displaystyle {\vec {b}}^{n}}$も同様に定義されます。これは、次の条件を満たす長さnのベクトルです。

${\displaystyle \mathbf {T} ^{n}{\vec {b}}^{n}={\hat {e}}_{n}.}$

Mが対称行列の場合、重要な簡略化が実現できます。この場合、2つのベクトルはb ⁿ _i = f ⁿ _{n +1− i}の関係にあり、つまり互いに行を反転させたものとなります。この特殊なケースでは、余分な計算を削減できます。

行列が対称でない場合でも、n番目の順方向ベクトルと逆方向ベクトルは、長さn  − 1のベクトルから 次のように求めることができます。まず、順方向ベクトルにゼロを追加して、次の式を得ます。

${\displaystyle \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}}.}$

T ^{n −1から}T ⁿへ移行する際、ゼロを使用して前方ベクトルを拡張する場合、行列に追加された列は解に影響を与えません。しかし、行列に追加された行は解に影響を与え、最後の位置に不要な誤差項ε _fを生み出します。上記の式は、その値を次のように表します。

${\displaystyle \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}.}$

このエラーはすぐに返され、新しい順方向ベクトルから削除されますが、まず、逆方向ベクトルも同様の（ただし逆方向の）方法で拡張する必要があります。逆方向ベクトルについては、

${\displaystyle \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}}.}$

これまでと同様に、行列に追加された列はこの新しい逆ベクトルに影響を与えませんが、追加された行は影響を与えます。ここで、値を持つ別の不要なエラーε _bが発生します。

${\displaystyle \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}.\ }$

これら2つの誤差項は、以下のように記述される高次の順方向ベクトルと逆方向ベクトルを形成するために使用できます。行列の線形性を使用すると、すべてのに対して次の恒等式が成り立ちます。${\displaystyle (\alpha ,\beta )}$:

${\displaystyle \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}}.}$

αとβを、右辺がê ₁またはê _nとなるように選択すると、括弧内の値はそれぞれn番目の順方向ベクトルまたは逆方向ベクトルの定義を満たします。このようにαとβを選択すると、括弧内のベクトル和は単純になり、目的の結果が得られます。

これらの係数を見つけるには、${\displaystyle \alpha _{f}^{n}}$、${\displaystyle \beta _{f}^{n}}$次のようなものである ：

${\displaystyle {\vec {f}}^{n}=\alpha _{f}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{f}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}}$

それぞれ ${\displaystyle \alpha _{b}^{n}}$、${\displaystyle \beta _{b}^{n}}$次のようなものである ：

${\displaystyle {\vec {b}}^{n}=\alpha _{b}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{b}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}.}$

前述の2つの式にそれぞれを掛けると${\displaystyle {\mathbf {T} }^{n}}$次のような方程式が得られる。

${\displaystyle {\begin{bmatrix}1&\varepsilon _{b}^{n}\\0&0\\\vdots &\vdots \\0&0\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&0\\\vdots &\vdots \\0&0\\0&1\end{bmatrix}}.}$

さて、上記の2つのベクトルの中央にあるすべてのゼロを無視して統合すると、次の式だけが残ります。

${\displaystyle {\begin{bmatrix}1&\varepsilon _{b}^{n}\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}.}$

これらを（クレイマーの2×2行列逆行列公式を用いて）解くと、新しい前方ベクトルと後方ベクトルは次のようになります。

${\displaystyle {\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}}}$

${\displaystyle {\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}}.}$

これらのベクトル和を実行すると、前のベクトルからn番目の順方向ベクトルと逆方向ベクトルが得られます。あとは、これらのベクトルのうち最初のベクトルを見つけるだけで、簡単な和と乗算で残りのベクトルが得られます。最初の順方向ベクトルと逆方向ベクトルは次のようになります。

${\displaystyle {\vec {f}}^{1}={\vec {b}}^{1}=\left[{1 \over M_{11}}\right]=\left[{1 \over t_{0}}\right].}$

上記の手順により、 MのN個の逆ベクトルが得られます。そこから、より任意の方程式は次のようになります。

${\displaystyle {\vec {y}}=\mathbf {M} \ {\vec {x}}.}$

解は、逆ベクトルが構築されたのと同じ再帰的な方法で構築できます。したがって、${\displaystyle {\vec {x}}}$中間体のシーケンスに一般化する必要がある${\displaystyle {\vec {x}}^{n}}$、したがって${\displaystyle {\vec {x}}^{N}={\vec {x}}}$。

次に、以下の点に着目して再帰的に解を構築します。

${\displaystyle \mathbf {T} ^{n-1}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\end{bmatrix}}.}$

次に、再びゼロを追加し、必要に応じて誤差定数を定義します。

${\displaystyle \mathbf {T} ^{n}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\\varepsilon _{x}^{n-1}\end{bmatrix}}.}$

次に、n番目の逆ベクトルを使用して誤差項を除去し、それを目的の式に置き換えることができます。手順は次のとおりです。

${\displaystyle \mathbf {T} ^{n}\left({\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\\\end{bmatrix}}+(y_{n}-\varepsilon _{x}^{n-1})\ {\vec {b}}^{n}\right)={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\y_{n}\end{bmatrix}}.}$

この方法をn = Nまで拡張すると、解が得られます。${\displaystyle {\vec {x}}}$。

実際には、これらの手順は他の手順と並行して行われることが多いが、これらは一貫性のある単位を形成しており、独立した手順として扱うに値する。