Counting the number of additions/subtractions for Gauss-Jordan Elimination
We have a matrix of the form
$$\Big[\;\;\;n\times n\;\;\;\Big|\;\;\;n\times m\;\;\;\Big].$$
Where the set up is basically solving $m$ linear systems of equations all
with the same coefficient matrix. I wan't to use Gauss-Jordan elimination
on it to diagonalize the left part (the $n\times n$ side), but its
diagonal does not necessarily have to have ones on its pivots.
I'm trying to figure out how many additions/subtractions this will take as
a function of $m$ and $n$.
As far as I can tell, to first make it upper-traingular, I will need make
the following number of additions/subtractions:
$$\sum_{k=1}^n(k-1)(m+k).$$
And then to diagonalize will require another $$(m+1)\sum_{k=1}^n(k-1).$$
Adding these two series together and then simplifying I obtain
$$mn(n+1)+\frac{1}{3}n^3+\frac{1}{2}n^2-\frac{5}{6}n.$$
The book says the solution should be
$$\frac{1}{2}n^3+(m-1)n^2+(\frac{1}{2}-m)n.$$
Can anyone point to where my flawed reasoning is? Thanks.
No comments:
Post a Comment