# 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)$$?

## 1 Answer

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.

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.

• 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
• sorry, just edited my comment. I mean, why does Newton's method have that complexity? – VoB Nov 17 '18 at 21:57
• $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