레빈슨 재귀 알고리즘

레빈슨 재귀 알고리즘(Levinson recursion, 또는 Levinson-Durbin recursion)은 선형 대수학에서 퇴플리츠 행렬이 관여하는 방정식에 대한 해를 재귀적으로 계산하는 절차이다.

이 알고리즘은 ${\displaystyle {\color {blue}{\Theta }}}$ ${\displaystyle (n^{2})}$의 시간복잡도에서 실행되며, ${\displaystyle {\color {blue}{\Theta }}}$ ${\displaystyle (n^{3})}$에서 실행되는 가우스-조르단 소거법 보다 더 강하게 개선된 절차이다.

같이 보기

• 퇴플리츠 행렬
• QR 분해

참고

• Trench, W. F. (1964). "An algorithm for the inversion of finite Toeplitz matrices." J. Soc. Indust. Appl. Math., v. 12, pp. 515–522.
• Musicus, B. R. (1988). "Levinson and Fast Choleski Algorithms for Toeplitz and Almost Toeplitz Matrices." RLE TR No. 538, MIT.