Generals 1998 7

From PlasmaWiki

[edit] Computational Quickie

We can solve working backwards from the bottom. The last row of the matrix only multiplies one element:

a_nnx_n = y_n

This can be inverted by division:

x_n = y_n / a_nn

The next line up only involves this and one other element:

a_{n − 1,n − 1}x_{n − 1} + a_{n − 1,n}x_n = y_{n − 1}

Solving for x_{n − 1}, the only unknown:

We can see that this process can be repeated for every element:

So using this and x_n = y_n / a_nn, we have a solution for all x. This requires N divisions, N − 1 multiplications, and N − 1 subtractions, for a total of 3N − 2 operations.