# Computational complexity of Newton's method

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 $$t\geq 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.
• I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$.
• $N^2$ is the time to solve a linear system, $N^3$ is the time to compute an LU factorization. So counting only the time spent doing linear algebra (not function or Jacobian evaluations), that's the time complexity of Newton's method. Nov 17, 2018 at 21:58
• More precisely $O(N^2)$ is the time to solve $LU x = b$. Apr 19, 2021 at 22:41