Csdrhrt

the classical Newton's method for non-linear systems of equations is $x_{k+1} =x_k-J_F(x_n)^{-1} F(x_n)$. In pratice, rather than compute the inverse of the Jacobian matrix, one solves the systems $J_F(x_k) (x_{k+1}-x_k)=-F(x_k)$, for the unknown $x_{k+1}-x_k$.

In my notes (about ODE) I found:

Newton's method requires the computation of the Jacobian matrix and its "inversion" at every step $k$. This could be too expensive ($mathcal{O}(N^3)$), where $N$ is the dimension of the matrix.

My doubt is how to get that computational complexity. Is it talking about the way to invert a matrix using LU decomposition, which I know to be $mathcal{O}(N^3)$ ?

Then it states:

A standard way to reduce computational complexity is to use always the same Jacobian matrix, compute its LU decomposition and use it to solve the linear systems. This is $mathcal{O}(N^2)$

Here I have still a question: the complexity of the computation of the LU decomposition of $J_F$ should be $mathcal{O}(frac{N^3}{3})$. While the computational complexity of the resolution of a triangular system is $mathcal{O}(frac{N^2}{2})$. Since there are two triangular systems, it amounts to $2 mathcal{O}(frac{N^2}{2})$.

Shouldn't it be, totally, $mathcal{O}(frac{N^3}{3})$ instead of $mathcal{O}(N^2)$?

If you take $m$ steps, and update the Jacobian every $t$ steps, the time complexity will be $O(m N^2 + (m/t)N^3)$. So the time taken per step is $O(N^2+N^3/t)$. You're reducing the amount of work you do by a factor of $1/t$, and it's $O(N^2)$ when $tgeq N$. But $t$ is determined adaptively by the behaviour of the loss function, so the point is just that you're saving some unknown, significant amount of time.

In the quote, "this" probably refers to the immediately preceding sentence, the complexity of solving an already-factored linear system, not to the time taken for the whole step like in the paragraph before it.