- #1

mathmari

Gold Member

MHB

- 5,049

- 7

Let A be a regular ($n\times n$)-Matrix, for which the Gauss algorithm is possible.

If we choose as the right side $b$ the unit vectors $$e^{(1)}=(1, 0, \ldots , 0)^T, \ldots , e^{(n)}=(0, \ldots , 0, 1 )^T$$ and calculate the corresponding solutions $x^{(1)}, \ldots , x^{(n)}$ then the inverse matrix is $A^{-1}=[x^{(1)}, \ldots , x^{(n)}]$.

We can calculate the inverse with $n^3+O(n^2)$ operations. (1 operation = 1 multiplication or division)

If we calculate the solutions $x^{(1)}, \ldots , x^{(n)}$ with the using the LU-decomposition we get $\frac{4}{3}n^3+O(n^2)$ operations, or not?

It is because we apply the the Gauss algorithm which requires $\frac{1}{3}n^3+O(n^2)$ operations, right?

How do we get $n^3+O(n^2)$ ?

Do we have to use an other algorithm here?