tridiagonal matrix with a corner entry from upper diagonal

Question

I am trying a construct a matlab code such that it will solve an almost tridiagonal matrix. The input I want to put in is the main diagonal (a), the upper diagonal (b) and the lower diagonal and the RHS vector (r). The matrix I want to solve looks like this:

         | a(1)  b(1)                                 |
         | c(1)  a(2)  b(2)                           |
         |       c(2)  a(3)  b(3)                     |
         |              .     .     .                 |
         |                    .     .     .           |
         |                          .     .    b(n-1) |
         | b(n)                        c(n)     a(n)  |

I can construct a code that works for the tridiagonal, but that corner entry got me, especially when it is supposed to come from the original input c.

This is what I got so far:

function y = tridiagonal ( c, a, b, r )

n = length ( a );

for i = 1 : n-1
    b(i) = b(i) / a(i);
    a(i+1) = a(i+1) - c(i) * b(i);
end


r(1) = r(1) / a(1);
for i = 2 : n
    r(i) = ( r(i) - c(i-1) * r(i-1) ) / a(i);
end

for i = n-1 : -1 : 1
    r(i) = r(i) - r(i+1) * b(i);
end



if ( nargout == 0 )
    disp ( r )
else
    y = r;

end

Thanks for any input!

Answer 1

A slightly longer comment:

First, you apply a standard tridiagonal LU on the leading $(n−1)\times(n−1)$ submatrix. Then note that eliminating the entry $b(n)$ using the first row introduces a nonzero entry at the position $(n,2)$, which is eliminated using the second row introducing a nonzero at $(n,3)$ etc. It is of course still $O(n)$ but needs a bit more work in the last row.

Schematically, you can write the matrix, say, $A$, like this: $$\tag{1} A:=\pmatrix{T&b_{n-1}e_{n-1}\\c^*&a_n}, $$ where $e_{n-1}$ is the last column of the $(n-1)\times(n-1)$ identity. Let $T=L_TU_T$ be an LU factorization of the tridiagonal submatrix $T$ (assume unit diagonal of $L$) and let's look for the LU of $A$ in the form $$\tag{2} A=LU, \quad L=\pmatrix{L_T&0\\l^*&1}, \quad U=\pmatrix{U_T&u\\0&\mu}. $$ Using (1) and (2), we have $$ L_Tu=b_{n-1}e_{n-1}, \quad U_T^*l=c, \quad a_n=\mu+l^*u. $$ Since $L_T$ is unit lower triangular, $u=b_{n-1}e_{n-1}$. The vector $l$ requires solving a system $U_T^*l=c$ using forward substitution. Note that its solution is generally a vector full of nonzeros if $b_n\neq 0$. Finally, we can compute $\mu=a_n-l^*u$. The only thing of interest to compute $\mu$ is the last entry of $l^*$, which is given by $c_n/(U_T)_{n-1,n-1}$, so $\mu=a_n-b_{n-1}c_n/(U_T)_{n-1,n-1}$.