Newton's Method
Newton's method for nonlinear equations is based on a linear approximation
so the Newton step is found simply by setting ,
Near a root of the equations, Newton's method has -quadratic convergence, similar to Newton's method for minimization. Newton's method is used as the default method for FindRoot.
Newton's method can be used with either line search or trust region step control. When it works, the line search control is typically faster, but the trust region approach is usually more robust.
In[1]:= |
Note that each of the line searches started along the line . This is a particular property of the Newton step for this particular problem.
When this step is added to the point , it is easy to see why the steps go to the line
. This is a particular feature of this problem, which is not typical for most functions. Because the trust region approach does not try the Newton step unless it lies within the region bound, this feature does not show up so strongly when the trust region step control is used.
When the structure of the Jacobian matrix is sparse, the Wolfram Language will use SparseArray objects both to compute the Jacobian and to handle the necessary numerical linear algebra.
When solving nonlinear equations is used as a part of a more general numerical procedure, such as solving differential equations with implicit methods, often starting values are quite good, and complete convergence is not absolutely necessary. Often the most expensive part of computing a Newton step is finding the Jacobian and computing a matrix factorization. However, when close enough to a root, it is possible to leave the Jacobian frozen for a few steps (though this does certainly affect the convergence rate). You can do this in the Wolfram Language using the method option "UpdateJacobian", which gives the number of steps to go before updating the Jacobian. The default is "UpdateJacobian"->1, so the Jacobian is updated every step.
Of course for a simple one-dimensional root, updating the Jacobian is trivial in cost, so holding the update is only of use here to demonstrate the idea.
option name | default value | |
"UpdateJacobian" | 1 | number of steps to take before updating the Jacobian |
"StepControl" | "LineSearch" | method for step control, can be "LineSearch", "TrustRegion", or None (which is not recommended) |
Method options for Method->"Newton" in FindRoot.