# 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)$. – VoB Nov 17 '18 at 21:54
• $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. – Kirill Nov 17 '18 at 21:58