Complexity of Newton iteration problem for a d-dimensional problem

Question

If we assume that we have $f:\mathbb{R}^{d} \rightarrow \mathbb{R}^{d}$ and we want to use the Newton iteration method to solve $f(x)=0_{\mathbb{R}^{d} }$. Is there any theorem regarding the complexity of this method for a problem with dimension $d$?

Answer 1

If the linear systems are solved by Gaussian elimination, then each step takes $O(d^3)$ time. The number of steps needed depends on the convergence rate. In the case of a simple root, this rate is quadratic.

Much of the time, we can do better than the algorithm suggested above. For instance you can use an iterative method to solve the linear systems approximately. In fact you can often solve the linear systems with rather low accuracy early in the computation, because those values are just going to get thrown away anyway. So one step can sometimes be quite cheap, maybe as low as $O(d^2)$ time. It won't be any lower than $O(d^2)$ time in the general situation, simply because there are $d^2$ derivatives and in the general case you need to approximate all of them.