# Algorithm for Back substitution of LU Decompositions

As part of a larger solution, I've established that I've implemented something incorrectly regarding solving the system

$Uz=y$

Where U is the upper triangular submatrix resultant from an LU=A decomposition.

What I have is; (assuming zero based indexing)

$z_{n-1}=y_{n-1}/U_{n-1,n-1}$

$for\ i=n-2;i>=0;i--$

$\ \ t=0$

$\ \ for\ j=i+1; j<n; j++$

$\ \ \ \ t-=U_{i,j}y_j$

$\ \ z_i=(y_i-t)/=U_{i,i}$

This is coming from my reading of Goulb and Van Loan but I could be making a mistake.

In a nutshell, all the z values except for z[0] are correct.

Notes; the LU decomposition used is lower unitary i.e diag L are all 1,

For anyone interested in the larger problem be my guest, but as far as I can see this is the last thing wrong.

-

The way you've currently written it, it looks as if you're subtracting entities from t, and then subtracting it from y(i) (i.e., adding that total to t) before the division. I'd have done something like the following:

z(n-1)=y(n-1)/U(n-1, n-1);
for (i=n-2;i>=0;i--) {
t=y(i);
for (j=i+1;j<n;j++) t -= U(i, j)*y(j)
z(i)=t/U(i, i);
}


As a check for your code:

$$\begin{pmatrix}1&2&3\\0&4&5\\0&0&6\end{pmatrix}\begin{pmatrix}1\\1\\1\end{pmatrix}=\begin{pmatrix}6\\9\\6\end{pmatrix}$$

-