# Geometrically Constructed Families of Newton's Method for Unconstrained Optimization and Nonlinear Equations

Authors: Sanjeev Kumar; Vinay Kanwar; Sushil Kumar Tomar; Sukhjit Singh
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## Abstract

One-parameter families of Newton's iterative method for the solution of nonlinear equations and its extension to unconstrained optimization problems are presented in the paper. These methods are derived by implementing approximations through a straight line and through a parabolic curve in the vicinity of the root. The presented variants are found to yield better performance than Newton's method, in addition that they overcome its limitations.


---

## Body

## 1. Introduction

Newton’s method is one of the most fundamental tools in computational mathematics, operations research, optimization, and control theory. It has many applications in management science, industrial and financial research, chaos and fractals, dynamical systems, variational inequalities and equilibrium-type problems, stability analysis, data mining, and even to random operator equations. Its role in optimization theory cannot be overestimated as the method is the basis for the most effective procedures in linear and nonlinear programming. For a more detailed survey, one can refer to [1] and the references cited therein.Letf(x) be a sufficiently continuous differentiable function of a single variable x. One of the most basic problems in numerical analysis is to find the solution of frequently occurring nonlinear equation of the form(1.1)f(x)=0.
Let(1.2)y=f(x),
represent the graph of the function f(x).A large number of iterative methods have been developed for finding out the solution of single variable nonlinear equations as well for the solution of a system of nonlinear equations. One important reason for these methods is that none of them works for all types of problems. For a more detailed survey of these most important methods, many excellent textbooks are available in the literature [2–4].Newton’s method is probably the simplest, most flexible, best known, and most used numerical method. However, as it is well known, a major difficulty in the application of Newton’s method is the selection of initial guess which must be chosen sufficiently close to the true solution in order to guarantee the convergence. Finding a criterion for choosing initial guess is quite cumbersome and the method may fail miserably if at any stage of computation, the derivative of the functionf(x) is either zero or sufficiently small. Due to this reason, it exhibits poor convergence and falls in stability problems.Also for solving nonlinear, univariate, and unconstrained optimization problems, Newton’s method [1] is an important and basic method which converges quadratically. The idea behind Newton’s method is to approximate the objective function locally by a quadratic function which at x=xn agrees with the function f(x) up to second derivatives. Again, the condition f′′(x)≠0 in a neighborhood of the root is required for the success of Newton’s method.The purpose of this paper is to eliminate the defects of Newton’s method by the simple modification of iteration processes. Numerical results indicate that the proposed iterative formulae are effective and comparable to the well-known Newton’s method. Furthermore, the presented techniques have guaranteed convergence unlike Newton’s method and are as simple as this known technique.


## 2. Proposed Methods for Single-Variable Nonlinear Equations

In this section, we shall derive two families by applying approximation via a straight line and via a parabolic curve.(a) Approximation by a Straight Line.
Consider the equation of a straight line having slope equal topf(x0) and passing through the point (x0,0), in the form
(2.1)y=pf(x0)(x-x0),
where x0 is an initial guess to an exact root r of (1.1) and p∈ℜ, |p|<∞. Let
(2.2)x1=x0+h,|h|<1,
be the better approximation to the root. Assume that the straight line (2.1) intersects the graph of the function (1.2) at a point (x1,f(x0+h)). Now the straight line (2.1) while passing through the point (x1,f(x0+h)) takes the form
(2.3)f(x0+h)=hpf(x0).
Expanding the left-hand side by means of Taylor’s expansion about the point x=x0 and simplifying (retaining the terms up to O(h)), we get an iteration formula given by
(2.4)x1=x0-f(x0)f′(x0)-pf(x0).
The general formula for successive approximations is given by(2.5)xn+1=xn-f(xn)f′(xn)-pf(xn).
This is the one-parameter family of Newton’s method. This formula was independently derived earlier by Mamta et al. [5] and Kanwar and Tomar [6] by using different approaches. In order to obtain the quadratic convergence of the method, the sign of entity p should be chosen so that the denominator is the largest in magnitude. This formula is well defined, even if f′(x) is zero unlike Newton’s method.(b) Approximation by a Parabola
Consider a parabola in the form(2.6)y=p2f(x0)(x-x0)2.
Adopting the same procedure as done in the previous case (a), one can obtain the following iterative formula given by
(2.7)xn+1=xn-2f(xn)f′(xn)±f′2(xn)+4p2f2(xn).
In (2.7), the sign in the denominator should be chosen so that the denominator is the largest in magnitude. This is a parabolic version of Newton’s method [6] and does not fail if f′(xn)=0. Note that for p=0, the classical Newton’s formula can be recovered from the formulae (2.5) and (2.7).(c) Exponential Iteration Formulae.
Exploiting the main idea of Mamta et al. [5], Chen and Li [7] derived new classes of quadratically convergent exponential iterative methods. On the similar lines, we can also derive exponential iterative formulae for solving nonlinear equations.
If lettingxn+1=xnexp(-h/xn) be the better approximation to the exact root r, then from (2.5) and (2.7), we obtain the following exponential iteration formulae:
(2.8)xn+1=xnexp⁡(-f(xn)xn(f′(xn)-pf(xn))),xn+1=xnexp⁡⁡(-2f(xn)xn(f′(xn)±f′2(xn)+4p2f2(xn))),
respectively. Letting p=0 in these formulae, we obtain another exponential iterative formula given by
(2.9)xn+1=xnexp⁡(-f(xn)xnf′(xn)).
Note that by taking the first-order Taylor’s expansion of exp(-f(xn)/xnf′(xn)) in (2.9), Newton’s formula can be achieved. The idea can further be generalized (similar to Mir and Rafiq [8, 9]) to the case of multiple zeros of nonlinear equations.


## 3. Extension to Unconstrained Optimization Problems

In this section, we shall extend the formulae (2.5) and (2.7) to solve nonlinear, univariate and unconstrained optimization problems.Consider the nonlinear optimization problem: minimize{f(x),x∈ℜ,f:ℜ→ℜ}, where the function f(x) is nonlinear twice-differentiable function.(a) Extension of Formula (2.5).
Assume thatf(x) is sufficiently smooth function and has an extremum (maxima or minima) at a point x=α. From (2.3), consider the auxiliary function with parameter p as
(3.1)q(x)=f(x)-phf(xn).
It is possible to construct a quadratic function q(x) which agrees with f(x) up to second derivatives in the neighborhood of a point x=xn, that is,
(3.2)q(x)=f(xn)+f′(xn)(x-xn)+12f′′(xn)(x-xn)2-p(x-xn)f(xn).
We may calculate an estimate of f(x) at x=xn+1 by finding the point where the derivative of  q(x) vanishes [1, 10], that is, q′(xn+1)=0, we have
(3.3)f′(xn)+f′′(xn)(xn+1-xn)-pf′(xn)(xn+1-xn)=0.
This gives the following iterative formula given by
(3.4)xn+1=xn-f′(xn)f′′(xn)-pf′(xn).
This is a one-parameter family of Newton’s method for unconstrained optimization problem and do not fail even if f′′(xn)=0 unlike Newton’s method.(b) Extension of Formula (2.7).
Similarly, it is possible to construct a quadratic functionq(x) from (2.6) which agrees with f(x) up to second derivatives in the neighborhood of a point x=xn, that is,
(3.5)q(x)=f(xn)+(x-xn)f′(xn)+(x-xn)22f′′(xn)-p2(x-xn)2f(xn).
Taking into account that q′(xn+1)=0, we get
(3.6)xn+1=xn-2f′(xn)f′′(xn)±f′′2(xn)+4p2f′2(xn).
This is the modification over the formula (2.7) for unconstrained optimization problem which again does not fail even if f′′(xn)=0. In (3.4) and (3.6), the sign in the denominator should be chosen so that the denominator is largest in magnitude. If we let  p=0 in (3.4) and (3.6), we obtain Newton’s iteration formula for unconstrained optimization problem [1].
Adopting the same procedure as in exponential iteration formulae, we can also derive exponential quadratically convergent iterative formulae for unconstrained optimization. Recently, Kahya [10] also derived similar formulae, namely, (3.4) and (3.6) by using the different approach based on the ideas of Mamta et al. [5].


## 4. Convergence Analysis

Here, we shall present the mathematical proof for the order of convergence of iterative formulae (3.4) and (3.6), respectively.Theorem 4.1.
Letf:I→ℜ be a sufficiently differentiable function defined on I, and let x=α∈I be an optimum point of f(x). Assume that the initial guess x=xn is sufficiently close to α and f′′(xn)-pf′(xn)≠0 in I. Then the iteration scheme defined by formula (3.4) is quadratically convergent and satisfies the following error equation:
(4.1)en+1=(3A3-p)en2+O(en3),
where en=xn-α and
(4.2)Ak=(1k!)fk(α)f′′(α),k=3,4,….Proof.
Sincex=α is an optimum point of f(x), that is, f′(α)=0 and f′′(α)≠0. Expanding f′(xn) and f′′(xn) about x=α by Taylor’s expansion, we obtain
(4.3)f′(xn)=f′′(α)⌊en+3A3en2+O(en3)⌋,
and
(4.4)f′′(xn)=f′′(α)⌊1+6A3en+O(en2)⌋.
Furthermore,
(4.5)f′(xn)f′′(xn)-pf′(xn)=en-(3A3-p)en2+O(en3).
Using (4.5) in (3.4), we get
(4.6)en+1=(3A3-p)en2+O(en3).
This proves the quadratic convergence of the formula (3.4).Theorem 4.2.
Letf:I→ℜ be a sufficiently differentiable function defined on I, and let x=α∈I be an optimum point of f(x). Assume that initial guess x=xn is sufficiently close to α in I. Then the iteration scheme defined by formula (3.6) is quadratically convergent and satisfies the following error equation:
(4.7)en+1=3A3en2+O(en3).Proof.
Using (4.3) and (4.4), we have
(4.8)2f′(xn)f′′(xn)±(f′′2(xn)+4p2f′2(xn))=en-3A3en2+O(en3).
Using (4.8) in (3.6), we get
(4.9)en+1=3A3en2+O(en3).
It is interesting to note that this error equation is the same as that of Newton’s method. This completes the proof of the theorem.


## 5. Numerical Examples

Here we consider some examples to compare the number of iterations needed in the traditional Newton’s method and its modifications, namely, (2.5), (2.7), (3.4), and (3.6) respectively, for solving nonlinear equation (Table 1 and Table 2) as well as unconstrained optimization problems (Table 3 and Table 4). Here, for simplicity, the formulae are tested for |p|=1. Computations have been performed using C++ in double-precision arithmetic.Table 1
Test problem (nonlinear equations).
No.Examples[a,b]Initial guessesRoot(r)(1)xe-x-0.1=0[0,2]0.80.111832559108734(2)sinx=01.0[-1,1.6]1.510.0000000000000001.52(3)e-x-sinx=0[5,7]5.06.285049438476562(4)ex2+7x-30-1=0[2,3.5]2.03.0000000000000002.8(5)(x-1)6-1=0[1,3]1.01.52.0000000000000002.5Table 2
Comparison table for nonlinear equations.
ExamplesNMMethod (2.5)Method (2.7)(1)955Fails55(2)Converges to undesired root(-5π)75Converges to undesired root(-6π)75(3)Converges to undesired root (9.424696922302246)64353(4)Divergent22111111Fails11(5)1477676Table 3
Unconstrained optimization problems.
No.ExamplesInitial guessesOptimum point(β)(1)x3-6x2+9x-8233.5(2)3774.522x+2.27x-181.5293240.77725982666015645(3)(x-2)2+cos(x)12.35424801662603(4)ex-3x2−10.2044814527034761(5)10.2x+6.2x3,x>00.50.8605414628982542.0Table 4
Comparison table for unconstrained optimization problems.
ExamplesNMMethod (3.4)Method (3.6)Optimum value(1)Fails11−8454(2)415133.5997653499586024108(3)464−0.580237420585759354(4)4651.1014507066670358454(5)55515.804002928482971465In the following problems, we are to find the root of equations in the given interval[a,b].


## 6. Discussion and Conclusions

This study presents several iterative formulae of second order for solving scalar nonlinear equations and unconstrained optimization problems. The numerical examples considered in Table1, Table 2, Table 3, and Table 4 above show that in many cases our methods are efficient alternative to Newton’s method which may converge slowly or even fail. These are the simple extensions of Newton’s formula and have well-known geometric derivations. These methods remove the severe conditions f′(x)≠0 or f′′(x)≠0 of Newton’s method for the case of nonlinear equations or for the case of nonlinear unconstrained optimization problems, respectively. The behaviors of Newton’s method and the proposed modifications can be compared by their correction factors. For example, Newton’s correction factor f(xn)/f′(xn) is now modified by f(xn)/(f′(xn)-pf(xn)), where the parameter p is chosen such that the corresponding function values f′(xn) and pf(xn) have opposite signs. However, for p=0 and if derivatives of the function f(xn) are singular or almost singular, Newton’s method will either fail or diverge. Therefore, these modifications have two remarkable advantages over Newton’s method, namely, (i) if p≠0, the modified denominator of proposed modifications is well defined and never zero, provided xn is not accepted as an approximation to the required root or optima, respectively, and hence, they are well defined even if f′(x)=0 or f′′(xn)=0 happens; (ii) the absolute value of the modified denominator of modified techniques is always greater than the denominator of Newton’s method, that is, |f′(xn)|, provided xn is not accepted as an approximation to the required root or optima, respectively. This means that the proposed methods are numerically more stable unlike Newton’s method. Finally numerical experiments demonstrate that the parabolic methods outperform Newton’s method and the one-parameter family of Newton’s method.



---

*Source: 972537-2011-08-07.xml*