decreases with increasing ), its convergence is guaranteed. While a convergent sequence must necessarily be of Cauchy type, the reverse statement is, in general, not true (although here it will be assumed to be). Second, the quantity has disappeared from the convergence criteria. In other words, once for some and beyond, we only know that the sequence has converged (in the practical sense) to some value , that henceforth will play the role of the numerical root within the prescribed tolerance.
Finally, the bisection code also provides the vector res containing the sequence of absolute quantities , usually called the residuals. Since this quantity should approach zero when converges to a root, the reader may wonder why should not be used as a measure for stopping the iterations. The reason is that the residual is not always a reliable measure (although it is often used in practice to decide convergence). We will address this question later in this chapter, when we introduce the concept of condition number of a root.
1.3 Newton's Method
Newton's method, also known as Newton–Raphson method,7 is probably the most important root‐finding algorithm of numerical mathematics. Its formulation naturally leads to a wide variety of other root‐finding algorithms and is easily adaptable to solving systems of nonlinear equations.8 To formulate this method we will assume that is differentiable and that the root is close to some initial guess. To get a better estimation of the root we assume that, close to , the function can be approximated by its tangent line at the point plotted in gray below. In other words, we locally approximate by its first order Taylor expansion at :
(1.6)
where is the value of the derivative of at . The motivation for approximating by is simple: if is a reasonably good approximation of , then the solution of should be a reasonable good estimation of the solution of . Let be the solution of satisfying
(1.7)
The resulting abscissa where intercepts the ‐axis is the new (hopefully more accurate) estimation of the root. The process can be repeated approximating by its Taylor expansion at (straight gray line below the curve) in order to obtain an even better estimation satisfying
(1.8)
and so on, leading to the iterative formula:
Newton's Iteration:
(1.9)
A simple implementation of Newton's method can be found in the next code, whose structure essentially differs from the one seen in the bisection in two main aspects. First, the code needs an initial guess as starting point, instead of an interval. Second, in addition to the string name corresponding to the M‐file function fun, the code also needs the one associated with in the argument dfun. Providing the M‐file for the exact derivative entails both analytical differentiation and its subsequent programming, both being error‐prone tasks. While this is the correct procedure, it is sometimes advisable to let the computer do the job by approximating the value of by the ratio
decreases with increasing 