Matlab Matrix Inversion

Question

I'm a grad student, and one of my professors does not like his students to use "black box" functions when we could "easily" code a function ourselves.

So I need to be able to write a function, in Matlab, that will generically be able to take the inverse of an input matrix (probably of size 100x100 to 500x500). The only other guidance I have is that: "You should use an iterative method, whereas your function inputs should be the matrix you would like to invert and a specified amount of tolerable error. You may use any error estimator you would like."

Looking around, I have found a lot of estimation techniques that allow us to directly solve for Ax=b as opposed to solving for A^-1 (think Gauss-Seidel Method). The only other hint I have is that it might be useful to deconstruct my input matrix into upper triangular, diagonal, and lower triangular elements, and then to somehow invert them all individually.

Obviously, I'm not expecting someone to give me a code. What I would like is if anyone has a good resource that would give me some kind of basic numerical matrix inversion technique that I could form into a Matlab code.

Answer 1

Gauss-Jordan Elimination (See http://mathworld.wolfram.com/Gauss-JordanElimination.html) might do the trick. This isn't a trivial implementation but I'm sure with some effort you could get it to work. Note the following is a very informal sketch of the algorithm:

• Start with [A I]

  [a11 a12 a13 : 1 0 0]

  [a21 a22 a23 : 0 1 0]

  [a31 a32 a33 : 0 0 1]

• Add a21/a11 * row1 to row2

[a11 a12 a13 : 1 0 0]

[ 0 XXX YYY : r s t]

[a31 a32 a33 : 0 0 1]

• Do the same thing to row three (ie. add a31/a11 * row1 to row3)

After the previous steps you will have zeros in the first column expect for you leading a11.

• Now, add a22/a32 * row2 to row3. This will change a32 to a zero. Repeat on all FOLLOWING rows.

• repeat previous step on all LARGER columns.

You will have to generalize this method to operate on matricies larger than 3x3 but the pattern should be simple. When you have finished steps 1-5, you will be left with an upper triangular matrix. Now, you start going backwards. You add a portion of row 3 to rows 1 and 2 to change their third columns to zero, then a portion of row 2 to row 1 to change row 1's column to a zero (once again, generalize this to work on X by X matricies.

When that is finished, you will be left with a diagonal matrix on the left. Multiply each row by a factor that will change it to the identity matrix.

The result on the right is your inverted matrix! You will have to find ways of incorporating acceptable error into this.