Can someone explain how to get flops for full Newton method?

Question

So we are considering the full Newton method for nonlinear equations. The algorithm includes:

for k=0,1...until converges(suppose n)
compute -F(x_k)
compute Jacobian matrix of F(x_k)
solve Jacobian matrix*k=-F(x_k)
update x_k+1=x_k+k

I am given that the LU factorization is $n^3/3+O(n^2)$ (for some reason not $O(n^3)$. There are $n^2$ flops in Jacobian matrix. My question is the total number of flops then: $n^2+n^3/3+O(n^2)$?

Answer 1

You are using $n$ as both the size of the matrix and the number of iterations. To me, this does not make sense.

The number of iterations definitely depends on how close the initial approximation is to the actual result.

You are correct in that the number of flops per iteration is $n^3/3+O(n^2)$ for "solve Jacobian matrix*k=-F(x_k)" and the number of flops for the other steps is at least $O(n^2)$ and may be more depending on the complexity of computing F(x_k) and its Jacobian.

If $m$ is the number of iterations, which can not be computed in advance, the total number of flops would be $mn^3/3+O(mn^2)$.

I don't think that you can say anything more.