Proceedings of the 14th International Conference

on Computational and Mathematical Methods
in Science and Engineering, CMMSE 2014
3–7July, 2014.

Use of the vectorial Newton’s method for solving
nonlinear scalar equations
Higinio Ramos1 and J. Vigo-Aguiar2

Escuela Polit´ecnica Superior de Zamora, University of Salamanca. Spain


Departamento de Matem´
atica Aplicada, University of Salamanca. Spain

In this paper we propose to solve a scalar equation by means of an associated system
of two equations. In this way the solutions of the system lying on the identity line
provide solutions of the given equation. In most cases, the associated system can not
be solved exactly. Solving this system with the vectorial Newton’s method results more
efficient than the application of the scalar Newton’s method to the simpler equation.
Some examples are given to illustrate the performance of the proposed strategy.
Key words: nonlinear equations, Newton’s method, 2-cycles, approximate solutions
MSC 2000: 65H05



Finding the roots of a nonlinear equation f (x) = 0 is a classical and important problem in
science and engineering. There are very few functions for which the roots can be expressed
explicitly in closed form. Thus, the solutions must be obtained approximately, relying on
numerical techniques based on iterative processes [1]. Given an initial guess for the root, x0 ,
successive approximations are obtained by means of an iteration function (IF) Φ : X −→ X
xn+1 = Φ(xn ) ,

n = 0, 1, 2 . . .

which will often converge to a root α of the equation, provided that some convergence
criterion is satisfied.


ISBN: 978-84-616-9216-3

is repelling if |Φ0 (x0 )| > 1. All points on the orbit of x0 have the same period. Newton’s method is probably the best known and most reliable and most used algorithm [4]. . that is. the order of convergence is often determined by using the Schr¨ oeder-Traub’s theorem [5] which states that being Φ an IF with Φ(r) continuous in a neighborhood of α. Given an IF Φ. . . We will offer a brief outline of the geometric approach. if x0 is a periodic point of period n ≥ 1 then x0 is also fixed by Φ◦kn for any positive integer k. and A is the asymptotic error constant of the method defined by Φ. The point x0 is called the seed of the orbit.)) where Φ is applied k times. . Φ(x0 ) . For such a method. and the corresponding orbit has only n different points. or a n-cycle. The basic idea behind Newton’s method relies in approximating f (x) with the best linear approximation passing for an initial guess x0 which is near the root α. where Φ◦k (x) denotes the k-fold composition of Φ with itself applied to x0 . the error |en+1 | = |xn+1 − α| is proportional to |en |p = |xn − α|p as n → ∞. Φ◦k (x0 ) = Φ(Φ(. A point x0 is called eventually fixed or eventually periodic if x0 itself is not fixed or periodic.[2]. Φ◦k (x0 ). A fixed point x0 of Φ is attracting if |Φ0 (x0 )| < 1. Φ(r) (α) 6= 0 . . f : R → R. If Φ◦n (x0 ) = 0 and Φ◦j (x0 ) 6= 0 for 0 < j < n then x0 is called a point with period n. 2 The Newton-Raphson method We will consider that the function f (x) whose root need to be calculated is a scalar real one. Among the iteration methods. . Similarly. In practice. Φ0 (α) = . A point x0 is a fixed or equilibrium point of Φ if Φ(x0 ) = x0 . . but some point on orb(x0 ) is fixed or periodic. . . There are many ways to obtain the Newton’s method. .Newton vectorial versus Newton scalar for solving f (x) = 0. In this case the corresponding orbit is said to be a periodic orbit of period n. and is indifferent or neutral if |Φ0 (x0 )| = 1 . . Φ(x0 ). = Φ(r−1) (α) = 0 . If there exists a real number p ≥ 1 and a nonzero constant A > 0 such that lim n→∞ |Φ(xn ) − α| =A |xn − α|p then p is called the order of convergence. Note that the orbit of a fixed point x0 consists on the constant sequence {x0 }. . This best approximation is the c CMMSE ISBN: 978-84-616-9216-3 . the orbit of x0 ∈ X under Φ is defined as the set given by the sequence of points n o orb(x0 ) = x0 . then Φ is of order r if and only if Φ(α) = α . Note that if x0 is a periodic point of period n ≥ 1 then x0 is a fixed point of Φ◦n . .

For certain forms of equations. even for apparently simple functions. Newton’s method diverges. For low values of the derivative. Despite the existence of certain convergence theorems. the most dramatic situation occurs when Newton’s method exhibit chaotic behavior. generally it is not possible to say how close the initial estimates have to be in order to assured convergence. the Newton’s iteration offshoots away from the current point of iteration and may possibly converge to a root far away from the desired one. f 0 (x) It converges quadratically to simple zeros and linearly to multiple zeros. 4. Finally. p. the Newton’s iteration function is given by Nf (x) = x − f (x) . Provided f 0 (x0 ) 6= 0 the intersection of this line with the horizontal axis results in x1 = x0 − f (x0 ) . c CMMSE ISBN: 978-84-616-9216-3 . 3. In fact. The convergence of Newton’s method can be slow near roots of multiplicity greater than one. provided a good approximation is at hand. This is the situation if the initial guess is in an orbit of period n or is eventually periodic of period n. f (x0 )). for which the iteration function is Nf (x) = 2x. An important result to consider here is the following theorem whose proof may be found in [6]. the orbit of this point may not always converge successfully. 6. In some cases. 2. Nevertheless. 167. The dynamics of the Newton’s IF may be very complicated. Some pathological situations in the application of Newton’s method follow: 1. for multiple roots the Newton’s method looses its quadratic convergence. J. In this way. which results in a divergent sequence whatever the initial guess x0 6= 0 is. the iterations oscillate.Higinio Ramos. f 0 (x0 ) This process can be continued with the new approximation xl to get x2 . and so on. A typical example of this √ situation is the function f (x) = 3 x. It may fail also to converge to the desired root in case the initial point is far from this root. in which there are orbits that wander from here to there aimlessly. Vigo-Aguiar tangent line to the graph of f (x) at (x0 . 5. We expect that the sequence obtained through the IF will converge to the desired root of f (x). Newton’s method may fail miserably if at any stage of computation the derivative of the function f (x) is either zero or very small. depending on the function under consideration and the initial point selected.

3 From a scalar equation to a vectorial system Let us consider a particularization of a result in [7] p. Proposition 1. [3]. x2 } is a 2-cycle • x = y = α. Any solution of the system {Nf (x) = y. Ten O is a 2-cycle of the Newton’s IF Nf if and only if x = x1 . x2 } ∈ R with x1 6= x2 . Although at first sight it may appear that solving a system would be more complicated than solving a scalar equation. and let O = {x1 . Nf (y) = x} . which means that α is a root of f (x) = 0. y). we may consider to solve what we call the associated system given by {Nf (x) = y. the solution of the above system using the Newton’s method is given by h i X(k+1) = X(k) − F0 (X(k) ) −1 F0 (X(k) ) where F0 (X(k) ) is the Jacobian matrix. for solving the equation f (x) = 0. we will show different examples where it is not so. Let be f (x) : R → R a differentiable function and Nf (x) the corresponding Newton’s IF. y = x2 with x1 6= x2 . y = x2 is a solution of the system {Nf (x) = y. f2 (x. y) = (f1 (x. which also may be used for solving systems of equations [2]. f2 (x. in which is based the proposed strategy for obtaining the roots of the equation f (x) = 0. Nf (y) = x} is of one of the following types • x = x1 . the strategy is the same as that used by Newton’s method in solving a single nonlinear equation: to linearize each of the equations. For solving a system {f1 (x. The following result shows that under local conditions solving the associated system leads to the solution of the equation f (x) = 0. Nf (y) = x}. y)T . in some cases in algebraic way. If we may ensure by some means that the IF Nf has no periodic orbits of period 2. then to get a solution of the system will be equivalent to get a solution of the escalar equation f (x) = 0. Thus. y))T with X = (x. but in general we will consider the Newton’s method. Using the notation F(x. To obtain the computational solution an initial approximation vector X(0) = (x(0) . which means that the set {x1 . Moreover. y) = 0. Let be f (x) : R → R a differentiable function. y) = 0} using Newton’s method. 117. y (0) ) must be provided. α is a root of f (x) of multiplicity k if and only if α is a fixed point of the IF Nf . From the above proposition and Theorem1 it is easy to get the following main result. Proposition 2. The associated system may be solve by different procedures. c CMMSE ISBN: 978-84-616-9216-3 . Theorem 1 (Newton’s fixed point theorem).Newton vectorial versus Newton scalar for solving f (x) = 0. such a fixed point is always attracting.

f (b) > 0 . Nf (y) = x} with Nf the Newton’s IF of f (x). f 0 (x) 6= 0 . b] 3. f 00 (x) is either ≥ 0 or ≤ 0 for all x ∈ [a. Condition i) merely states that f (a) and f (b) have different signs. it suffices to prove the theorem in the case I). Nf (y) = x} in [a. By virtue of condition ii) there is only one solution. b]. Let us see that this is the unique solution. f (b) > 0 . which we will call α. It is obvious that the set of solutions of the system {Nf (x) = y. y = yk . Thus. f (b) < 0 . b). There are four different situations covered by the theorem: I) f (a) < 0 . We assert that either xk = α or yk = α. If the following conditions are satisfied 1.Higinio Ramos. f 00 (x) ≤ 0 III) f (a) > 0 . For cases i) and ii) we have that f (xk ) < 0. b] is not empty as x = y = α is a solution. f (a)f (b) < 0 2. Let the function f (x) be defined and twice continuously differentiable on the closed finite interval [a. and hence that the equation f (x) = 0 has at least one root in (a. Condition iii) states that the graph of f (x) is either concave from above or concave from below. f 00 (x) ≤ 0 but all cases may be reduced to one of them by using appropriate transformations (see [8]. p. x ∈ [a. In this case the graph of f (x) looks as given in Figure 1. b] then there is a unique solution of the system {Nf (x) = y. In other case we would have three possibilities i) xk ≤ yk < α ii) xk < α < yk iii) α < xk ≤ yk Let us see that these cases result in contradictions. If a solution apart from x = y = α exists. J. f 00 (x) ≥ 0 IV) f (a) > 0 . 79). being x = y = α where f (α) = 0. f 00 (x) ≥ 0 II) f (a) < 0 . Vigo-Aguiar Proposition 3. Expanding f (x) in Taylor series about yk and taking x = α it results that f (α) = f (yk ) + f 0 (yk )(α − yk ) + c CMMSE 1 00 f (ζk )(α − yk )2 ≥ f (xk ) + f 0 (xk )(α − xk ) 2 ISBN: 978-84-616-9216-3 . we may assume without loss of generality that xk ≤ yk. Proof. say x = xk . f (b) < 0 .

0 f (yk ) f (α) ISBN: 978-84-616-9216-3 . Hence. if yk = α then we have x k = yk − c CMMSE f (yk ) f (α) =α− 0 = α. f 0 (xk ) > 0 and thus it results that α < xk − yk = x k − f (xk ) < xk f 0 (xk ) which contradicts the hypothesis xk ≤ yk . a Α b Figure 1: or 0 ≥ f (xk ) + f 0 (xk )(α − xk ) from which we have that f (xk ) = yk f 0 (xk ) which is a contradiction with the hypothesis that xk < α.Newton vectorial versus Newton scalar for solving f (x) = 0. 0 f (xk ) f (α) and xk = yk = α as stated. Thus. For case iii) we have that f (xk ) > 0. If xk = α then it follows that yk = x k − f (xk ) f (α) =α− 0 = α. cases i) and ii) are not possible. either xk = α or yk = α. Similarly.

4. J. For any initial guess x0 6= 0 the iteration with this function results in a divergent 6x2 −1 sequence. c CMMSE ISBN: 978-84-616-9216-3 .704885352466915992721311334 Table 1: List of functions and the corresponding roots to be approximated. the associated system {Nf1 (x) = y. which is the root of f1 (x) = 0. Thus the proof of the proposition is complete. For x 6= 0 the Newton’s IF results in Nf1 (x) = 2(3x3 +x) . On the other hand.15 cos(50x) 0.1 Example 1 The function f1 (x) has only the root α = 0.627818561918557849123154131 f4 (x) = x3 + log(x) + 0. =x . We have considered the command FindRoot in the Mathematica program. 4 Application examples In order to test the efficiency of the strategy proposed here we are going to evaluate the number of iterations required to reach a specified level of convergence for different problems.717519716444759257246717966 1. In Table 1 appear the functions considered together with the roots we want to approximate. y0 )T = (−2. 6x2 − 1 6y 2 − 1 Solving this system using the command Solve in the Mathematica program we obtain that the unique real solution is x = y = 0. Solving the above system using the Newton’s method with initial guess (x0 . 2)T we obtain after 9 iterations the approximate solution with the required precision. Vigo-Aguiar which results in xk = yk = α. and the Newton’s method is not capable to get an approximation to the solution.Higinio Ramos. Nf1 (y) = x} reads ( )   2 3x3 + x 2 3y 3 + y = y. taking the options Method->"Newton" and WorkingPrecision->30. Function √ 2 f1 (x) = 3 x e−x Root 0 6 f2 (x) = ex +7x−30 − 1  2 20 f3 (x) = ex + x − 20 1. This proves that the IF Nf1 (x) does not have any 2-cycle.

the approximation of the root by using the scalar Newton’s method applied to f2 (x) and the vectorial one applied to the associated system: initial guesses. from any initial guess x0 >> α1 the convergence of the iterative sequence produced by Nf2 (x) will be very slow. The Newton’s IF is 6 e−x −7x+30 − 1 Nf2 (x) = x + 6x5 + 7 and is located under the diagonal y = x and for x → ∞ tends asymptotically to this diagonal. In Table 2 appear the data corresponding to 2 3.0 1.0 2.2 Example 2 The function f2 (x) has two roots. and if x0 > α1 the tangent line is very steep and then Newton’s sequence will approach very slowly towards the root. computational time (in seconds) and number of iterations. Thus.0 -2 1 -1 2 1.0 Figure 2: Graphs of the functions f2 (x) (left) and Nf2 (x) (right). as may be seen in Figure 2. The Newton’s method works acceptably only if the initial guess is very close to the root. 4. α1 .5 3.0 f2 HxL Nf2 HxL 2. Looking at the graph of the function f2 (x) in Figure 2 we see that if x0 < α1 the tangent line is almost horizontal and the next iteration will be far away from the root. c CMMSE ISBN: 978-84-616-9216-3 . We are interested in the positive root.5 1 2.5 2.5 -1 -2 1. except if the initial guess is very close to the root.Newton vectorial versus Newton scalar for solving f (x) = 0. It can also be seen from Table 2 that a less number of iterations are required to reach the root with the proposed method than those required with Newton’s method. and the negative one could be approximated similarly.

627818561918557849123154131 .0) 0. 4.062 38 Table 2: Data corresponding to the function f2 (x). The Newton’s iteration function is 2 ex + x − 20  Nf3 (x)x − 20 2ex2 x + 1 which tends asymptotically to the graph of y = x for x → ∞.016 36 (0. 2.6 0. J.0. In Table 3 appear the data corresponding to the approximation of the root by using the scalar Newton’s method applied to f3 (x) and the c CMMSE ISBN: 978-84-616-9216-3 .0) 0. Vigo-Aguiar Newton Scalar x0 /(x0 . 10. The negative zero could be approximated similarly. being f3 (x) > 0 out of these roots.0) 0. +y =x 6x5 + 7 6y 5 + 7 near the roots.Higinio Ramos. meaning that these are the two roots of the equation f2 (x) = 0 (α1 = 1. y0 ) Time Iter 4 1. which appear in Figure 3.0.3 Example 3 The function f3 (x) has two roots. We see that there are only two intersection points between the curves. The behavior of the iterations is similar to that of the above problem.046 30 (0. 4. With the help of the program Mathematica we have plot the graphs of the implicit curves in the associated system ( ) 6 6 e−x −7x+30 − 1 e−y −7y+30 − 1 + x = y.5.015 15 1.015 56 1. α2 = −1. which are on the diagonal y = x.872516561317824507097057829). 6.0) 0.016 4104 2 0. We are interested in the positive one.5 Newton Vectorial Overflow (1. We note that in this case there are no cycles of period 2 either.0.046 31 (1.

00 -1.651.65 1.90 -1.80 1. even in a wide interval.85 -1. For this problem there are no 2-cycles.95 -1. Although the Newton’s method for systems needs to consider the jacobians.717519716444759257246717966. and the graphs of the implicit curves in the associated system intersect only on the two roots (α1 = 1.6. 4.80 1.601. vectorial one applied to the associated system.8] × [0.8]. 0. there are a lot of 2-cycles of the Newton’s IF Nf4 (x). Some of the 2-cycles are shown in Figure 5.704885352466915992721311334 .501.55 1.75 -1. Due to the oscillatory character of the function.751.754947637178101198447348684).551. 0.6. the other intersections correspond to different 2-cycles. there are so few iterations.80 1.80 Figure 3: Detailed graphs of the implicit curves in the associated system to f2 (x). α2 = −1.85 -1.70 1.95 -2. that the computational time is much less than the time needed for the escalar Newton’s method.00 -2. -1.Newton vectorial versus Newton scalar for solving f (x) = 0.90 1.4 Example 4 The final example corresponds to a function that has only one real root.50 1. near the roots.701. We observe that te proposed strategy is more efficient than solving f (x) = 0 with Newton’s method. There is only one intersection over the diagonal which corresponds to the unique root α = 0. In Figure 4 we can see the intersections of the graphs of the two implicit curves of the associated system on the rectangle [0.60 -1. c CMMSE ISBN: 978-84-616-9216-3 .

Addison-Wesley. Springer.W. 7 (2001) 31–36. Deuflhard.0) 0. Springer. V. y0 ) Time Iter 10 0. 2.0) 0. Devaney. [2] P.015 9 (0.0. F.015 11 Table 3: Data corresponding to the function f3 (x).ance and Adaptive Algorithms. K. New York.Higinio Ramos. Academic Press.218 588 1 0.015 11 (0. [7] S. Rheinboldt. Boston. 2011. Plaza. Argyros.5. 1997. Iterative Solution of Nonlinear Equations in Banach Spaces.0) 0. Traub. [4] C. C. NewYork. Chelsea Publishing Company. c CMMSE ISBN: 978-84-616-9216-3 . J. Newton Methods for Nonlinear Problems. New York. SIAM. Ser. T.828 2517 4 0. Vergara. 10.234 570 (1.312 836 2 0. M. References [1] J. Existence of attracting periodic orbits for the Newton’s method.0. 4. 1970. Philadelphia. 1992. Affine Invari. 2003. A: Math. 6. [3] I. Berlin. A First Course In Chaotic Dynamical Systems. [5] J. Convergence and Applications of Newton-type Iterations. 2008. Iterative Methods for the Solution of Equations.0. [6] R. Vigo-Aguiar Newton Scalar Newton Vectorial x0 /(x0 . Sci.0) 0.015 9 (1. Ortega. Kelley. Sci. Solving Nonlinear Equations with Newton’s Method.

near the root.65 0.Newton vectorial versus Newton scalar for solving f (x) = 0. Henrici.70 0.75 0. John Wiley and Sons.60 0.75 0. 0.65 0.80 Figure 4: Plot showing the intersections of the graphs of the implicit curves in the associated system to f4 (x). [8] P.70 0.60 0. New York. c CMMSE ISBN: 978-84-616-9216-3 . 1964. Elements of Numerical Analysis.80 0.

8 0.2 0. c CMMSE ISBN: 978-84-616-9216-3 .9 Figure 5: Graphical representation of different 2-cycles of the iteration function Nf4 (x) near the root.3 -0.2 0.6 0.2 -0.3 0.3 0.3 -0. Vigo-Aguiar 0.2 0.2 -0.9 0.2 -0.7 0. J.6 -0.6 0.1 0.Higinio Ramos.7 0.8 0.3 0.9 0.1 -0.8 0.1 0.1 -0.3 0.7 0.1 0.1 -0.