3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$. $\endgroup$ – VoB Nov 17 '18 at 21:54
  • $\begingroup$ sorry, just edited my comment. I mean, why does Newton's method have that complexity? $\endgroup$ – VoB Nov 17 '18 at 21:57
  • $\begingroup$ $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. $\endgroup$ – Kirill Nov 17 '18 at 21:58
  • $\begingroup$ Ok, that's clear. One last question: if I do not want to use the LU decomposition, what is the compexity of Newton's method? I'd say $C \cdot O(N^2)$, since I need to solve linear systems until the method achieve convergence $\endgroup$ – VoB Nov 17 '18 at 22:02
  • $\begingroup$ Or am I completely wrong? $\endgroup$ – VoB Nov 17 '18 at 23:13

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.