Geometrically Constructed Families of Newton′s Method for Unconstrained Optimization and Nonlinear Equations
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.
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.
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 function f(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 to pf(x0) and passing through the point (x0, 0), in the form
The general formula for successive approximations is given by
(b) Approximation by a Parabola Consider a parabola in the form
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 letting xn+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:
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 that f(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
(b) Extension of Formula (2.7). Similarly, it is possible to construct a quadratic function q(x) from (2.6) which agrees with f(x) up to second derivatives in the neighborhood of a point x = xn, that is,
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. Let f : 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:
Proof. Since x = α 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
Theorem 4.2. Let f : 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:
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.
| No. | Examples | [a, b] | Initial guesses | Root (r) |
|---|---|---|---|---|
| (1) | xe−x − 0.1 = 0 | [0,2] | 0.8 | 0.111832559108734 |
| (2) | sinx = 0 | 1.0 | ||
| [−1,1.6] | 1.51 | 0.000000000000000 | ||
| 1.52 | ||||
| (3) | e−x − sinx = 0 | [5,7] | 5.0 | 6.285049438476562 |
| (4) | [2,3.5] | 2.0 | 3.000000000000000 | |
| 2.8 | ||||
| (5) | (x−1)6 − 1 = 0 | [1,3] | 1.0 | |
| 1.5 | 2.000000000000000 | |||
| 2.5 |
| No. | Examples | Initial guesses | Optimum point (β) |
|---|---|---|---|
| (1) | x3 − 6x2 + 9x − 8 | 2 | 3 |
| 3.5 | |||
| (2) | 32 | 40.777259826660156 | |
| 45 | |||
| (3) | (x−2)2 + cos (x) | 1 | 2.3542480166260 |
| 3 | |||
| (4) | ex − 3x2 | −1 | 0.204481452703476 |
| 1 | |||
| (5) | 0.5 | 0.860541462898254 | |
| 2.0 |
In 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 Table 1, 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.
Acknowledgment
The authors would like to thank the reviewers and the academic editor for many valuable comments and suggestions.
