Why solve J(X_k) ΔX_k = -F(X_k) instead of computing J⁻¹(X_k) directly

  • Context: Undergrad 
  • Thread starter Thread starter Ax_xiom
  • Start date Start date
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
5 replies · 2K views
Ax_xiom
Messages
82
Reaction score
4
So the formula used to solve non-linear equations using the Newton-Raphson method is this $$ X_{k+1} = X_k - J^{-1}(X_k)F(X_k) $$ and instead of finding ##J^{-1}(X_k)##, we solve for the change that will be applied to ##X_k## (##\Delta X_k##) using this relation $$J(X_k) \Delta X_k = -F(X_k)$$ and the next iteration will be this $$ X_{k+1} = X_k + \Delta X_k $$ My question is that wouldn't you need to solve for ##J^{-1}(X_k)## anyways when doing that? If so, why do we do that step in the first place?
 

Discussion

Physics news on Phys.org
We don't solve linear systems numerically by finding an inverse matrix; that is incredibly inefficient. Instead we use other methods, like Gaussian elimination or LU decomposition.
 
pasmith said:
We don't solve linear systems numerically by finding an inverse matrix; that is incredibly inefficient. Instead we use other methods, like Gaussian elimination or LU decomposition.
So what happens comptationally during the ##J(X_k) \Delta X_k = -F(X_k)## step? Do you express the problem as a series of linear equations and solve them?

Edit: I think that might be the case. I was under the impression that using Gaussian manipulation to solve a system of equations would give you the inverse matrix for free, but I don't think that is the case
 
Last edited:
If ##A## is invertible, then solving ##Ax = b## by Gaussian elimination where ##b## consists of zeros except for a 1 in the ##i##th row will give you the ##i##th column of ##A^{-1}##.
 
pasmith said:
If ##A## is invertible, then solving ##Ax = b## by Gaussian elimination where ##b## consists of zeros except for a 1 in the ##i##th row will give you the ##i##th column of ##A^{-1}##.
I'm assuming that this is computationally inefficient and it's much faster to just solve directly.

This is good to know but I attempted to implement this in Excel, and I was only doing it with a 3x3 matrix so it was much easier to just use Excel's MINVERSE() and MMULT() functions
 
Ax_xiom said:
I'm assuming that this is computationally inefficient and it's much faster to just solve directly.

This is good to know but I attempted to implement this in Excel, and I was only doing it with a 3x3 matrix so it was much easier to just use Excel's MINVERSE() and MMULT() functions

That appears to be the only method Excel provides for solving ##Ax = b##. The documentation does not explain what method Excel uses to calculate a matrix inverse, but assuming it is based on the standard LAPACK library it is using LU factorisation with partial pivoting.