 # how i invert a matrix without inverting it ^^

0

## Introduction

In this article, we show you how to invert a matrix without going through the burdens of inversions, i.e. without doing operations, which is required by Gauss Jordan. Herein, a Newton method is adopted for matrix inversion.

The approach is via Newton’s method and instead of computing explicitly , we solve whose solution is obviously .

## Approach

Given matrix , define

(1) Note that the solution of the above problem is , since

(2) Using Newton, the updates to solve are

(3) But hence

(4) But is what we trying to estimate by iterations, and hence replace it by the most recent estimate of , namely (5) Defining a residual matrix

(6) and error matrix

(7) Let us compute using equation (6) then plugging equation (4) at (8) (9) Now

(10) Also, ## MATLAB implementation

So, Let’s start with building a function called NewtonInverse, which computes the inverse based on equation (5). This is simply attained as such

function[X] = NewtonInverse(A,N,Niter)

%% NewtonInverse: computes inverse of A
%input
%A     - matrix
%N     - matrix dimension
%Niter - maximum number of iterations

I = eye(N);
%the true inverse to compute the error.
A_trueinverse = inv(A);
%initial guess
X(:,:,1) = A'/(norm(A,1) * norm(A,inf));

%iterations
for n = 2:Niter
X(:,:,n) = X(:,:,n-1) + X(:,:,n-1)*(I - A*X(:,:,n-1));
error(n-1) = norm(X(:,:,n) - A_trueinverse,2);
end

For sake of completeness, we will see how the iterations converge and compare it with an inverse based off MATLAB’s LU decomposition (which is not iterative herein). So we shall add the following block

%Using LU decompostion
[L1,U] = lu(A);
A_inverse_LU = inv(U)*inv(L1);
error_LU = norm(A_inverse_LU - A_trueinverse,2);
figure
plot(log10(error),'k','Linewidth',2)
hold on
plot(log10(error_LU*ones(Niter,1)),'--*r','Linewidth',2)
xlabel('n iteration')
ylabel('error (log scale)')
legend('Using Newton','Matlabs LU decomposition')
grid on
grid minor

Now our function looks like this

function[X] = NewtonInverse(A,N,Niter)

%% NewtonInverse: computes inverse of A
%input
%A     - matrix
%N     - matrix dimension
%Niter - maximum number of iterations

I = eye(N);
%the true inverse to compute the error.
A_trueinverse = inv(A);
%initial guess
X(:,:,1) = A'/(norm(A,1) * norm(A,inf));

%iterations
for n = 2:Niter
X(:,:,n) = X(:,:,n-1) + X(:,:,n-1)*(I - A*X(:,:,n-1));
error(n-1) = norm(X(:,:,n) - A_trueinverse,2);
end
%Using LU decompostion
[L1,U] = lu(A);
A_inverse_LU = inv(U)*inv(L1);
error_LU = norm(A_inverse_LU - A_trueinverse,2);
figure
plot(log10(error),'k','Linewidth',2)
hold on
plot(log10(error_LU*ones(Niter,1)),'--*r','Linewidth',2)
xlabel('n iteration')
ylabel('error (log scale)')
legend('Using Newton','Matlabs LU decomposition')
grid on
grid minor



Our main function will then test the above by simply generating a random matrix and inputting it to the above function as

A = 50*randn(3,3);
N = 3;
Niter = 30;

[X] = NewtonInverse(A,N,Niter);