Register to reply

[Numerical] Why is it better to solve Ax=b instead of calculating inv(A)

by nonequilibrium
Tags: inva, numerical, solve
Share this thread:
nonequilibrium
#1
May2-12, 04:49 PM
P: 1,412
Hello,

So I'm using a numerical method where I iteratively have to solve [itex]Ax_{i+1}=x_i[/itex] which can of course be done by calculating the inverse matrix, but something in the back of my mind is telling me that it is better to solve the equation using Gaussian elimination and substitution.

However, what is the reason for this? And is the difference relevant, or is merely a difference "in principle".
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
D H
#2
May2-12, 05:12 PM
Mentor
P: 15,066
There are lots of reasons not to use the inverse. Stability, accuracy, time. However, some of these reasons apply to a one-time solution of [itex]Ax=b[/itex]. Here you are apparently reusing the A matrix, iteratively solving [itex]Ax_{i+1} = x_i[/itex]. If you reuse A, timing considerations suggest you should compute the inverse of A instead of using Gaussian elimination.

There's an even better approach to using either of the techniques you mentioned. Compute the LU decomposition. It's cheaper to compute the LU decomposition than it is to use Gaussian elimination or the matrix inverse. LU backsubstitution is fast, faster than the matrix * vector computation, and the same stability and accuracy advantages that pertain to Gaussian elimination apply to LU decomposition.
nonequilibrium
#3
May2-12, 06:01 PM
P: 1,412
The iteration usually takes only three steps though, so maybe it is not evident that the inverse is optimal relative to solving it by Gaussian elimination?

Interesting what you say about the LU decomposition...

AlephZero
#4
May2-12, 08:49 PM
Engineering
Sci Advisor
HW Helper
Thanks
P: 6,957
[Numerical] Why is it better to solve Ax=b instead of calculating inv(A)

Calculating the inverse efficiently (i.e. by doing an LU decomposition and then solving N right hand sides each containng one 1 and the rest of the entries 0) is an overhead of about N solves. So if you are only doing 3 solves anyway, you will lose unless N is very small.

In addition to D.H's points, often A is sparse and the LU decomposition has a similar amount of sparsity, but the inverse matrix is almost always fully populated. In that situation, multiplying by the inverse can be orders of magnitude more expensive than solving using the sparse matrices, quite apart from the numerical conditoning issues and the amount of storage that may be required for the inverse matrix.

My "rule of thumb" here is that explicitly inverting a matrix numerically is NEVER the right thing to do, unless you can make a very good argument in favor of it. Even when it appears to be "no worse" than equation solving, straightforward equation solving (based on LU decomoposition for example) is usually not the only alternative.
nonequilibrium
#5
May3-12, 05:48 AM
P: 1,412
Thank you both for the good advice.


Register to reply

Related Discussions
M-files to solve numerical integration Engineering, Comp Sci, & Technology Homework 3
How do I solve this ODE with numerical methods? Differential Equations 5
Numerical method to solve ODE boundary problem Differential Equations 1
Mathematica:Please help me to solve numerical integration Math & Science Software 1
MATHEMATICA[solve numerical integration and find min value] Math & Science Software 3