Advantage in fixing the Jacobian for several steps (Modified Newton's method)

Question

Consider a modification to Newton's method for which we fix the Jacobian for $k$ steps. ($x \in \mathbb{R}^m$) $$x_{rk+j+1} = x_{rk+j} - J(x_{rk})^{-1}f(x_{rk+j})\\ j = 0,1,\dots,k-1$$

I have read in my text (Atkinson's Numerical Analysis) that this system is more efficient (though slower in convergence) than the original Newton's method:

the linear system of $m$ unknowns would require $\frac{2}{3}m^3$ calculations for $j = 0$, but for $j = 1, \dots, k-1$, would only require $2m^2$ operations.

At first I assumed that this is because we only need to solve the inverse of the Jacobian once and then simply multiply for the rest of the steps, but then my instructor told me that basically, we never find the inverse and only solve for the unknowns. I think this means that there is another way of looking at the problem. Is there another way to think about how this reduces computation?

Answer 1

Newton's method is frequently stated as $$ x_{k+1} = x_{k} - Df(x_k)^{-1} f(x_k)$$ where $Df(x) \in \mathbb{R}^{n \times n}$ is the Jacobian of $f$ at the point $x$. In practice, we use the equivalent equation $$ x_{k+1} = x_{k} - z_k,$$ where $z_k$ is the solution of the linear system $$ Df(x_k) z_k = f(x_k).$$ If we know the LU factorization of $Df(x_k)$, then we can compute $z_k$ using $O(n^2)$ arithmetic operations. The cost of computing an LU factorization from scratch is $O(n^3)$ which is why recycling is even considered.

---

We only compute the inverse if it is explicitly required by the application. Any rounding errors in the construction of the inverse can be magnified if we use the inverse to compute the solution of a linear system.

Answer 2

There are two points to mention:

1. As already said above, if you calculate the Jacobi matrix once and you use it in more subsequent iterations, before you recalculate the Jacobi matrix again. It is obviously cheaper and it can be sufficient -- you can still improve your solution iterate even with the slightly outdated Jacobi matrix (then you move more to the secant (Picard) method, which has only linear convergence order near equilibrium). However, I personally prefer to use the actual Jacobi matrix at each iteration step, because in this case you have the most robust method, which is more important than the fact, that the method is faster.

2. Maybe more important is the following fact: if you calculate a post-critical behavior of a beam for example (a 'snap-through' problem, see the attached picture), the problem formulation yields a singular Jacobi matrix in the middle, where it cannot be inverted. The solution to this problem is easy: at the point, where you become a singular Jacobi matrix, you use the Jacobi matrix from the last iteration, where the Jacobi matrix was regular, which allows you to pass through a critical region. Beyond this region you calculate Newton's iterations normally again. This approach is called the modified Newton's method and it is an easy way how to increase robustness of Newton's method.