clearlypk > and pk pk ik holdso that in fact pk is an orthogonal matrix we can solve the linear system an xn an in ( time recursivelyas follows assume that we have somehow solved for the upper block ak xk ak and now we wish to solve for the ( ( block#ak pk ak ak ak+ xk+ ak+ = > pk ak+ thereforea ak+ > pk ak ak pk ak - since - pk pk ak the second equation above simplifies to - - ak ak pk ak xk pk xk substituting xk pk xk into ak+ > pk and solving for yieldsaak+ > pk xk > xk finallywith the value of computed abovewe have xk pk xk xk+ levinsondurbin this gives the following levinson-durbin recursive algorithm for solving an xn an algorithm levinson-durbin recursion for solving an xn an inputfirst row [ an- [ > - of matrix an outputsolution xn - an for do bk > xk [xk, xk, - xk, ] (ak+ > )/bk xk xk+ return xn in the algorithm abovewe have identified xk [xk, xk, xk, ]the advantage of the levinson-durbin algorithm is that its running cost is ( )instead of the usual ( using the {xk bk computed in algorithm we construct the following lower triangular matrix recursivelysetting and lk lk+ ( (pk xk )