1. Introduction

Solutions of equations by numerical iteration are of interest to many science and engineering problems. For this purpose, several methods have evolved over time. The traditional Newton method which requires evaluation of one function and its derivative at each step of the iteration has an order of convergence of two in many cases. Several methods developed later on over the years are largely based on modification of the Newton method and have been shown to give increasingly higher order convergence.

Methods with demonstrated higher order convergence, mostly based on Newton iteration, have been documented in the literature. Starting from a third order convergencemethod, the method developed by S. Weeraksoon and T.G. Fernando[1] that requires evaluation of one function and two first derivatives is a notable example. On the other hand, the method developed by Ostrowsky[2] has a fourth order convergence and requires evaluation of two functional values and one value of a derivative. A number of sixth order methods have also been developed that generally require evaluation of four functions in each step of the iteration, (Grau and D´ıaz-Barrero[3], Sharma and Guha[4], Chun and Ham[5]).

The method developed by Kou, et al[6] has a seventh order convergence and requires evaluation of two functional values and two values of a derivative. The method developed by Bi, et al[7] has eighth order convergence and requires a total of four functional evaluations. Hu et al[8] developed a method that has Ninth order convergence that requires evaluation of four functional values per iteration.

The Two point Newton Method developed earlier by the author[9] using a two-point modification of the traditional Newton method has been shown to give a super-quadratic convergence of order about 2.414. The method is based on application of Newton iteration formula by taking as the independent variable the cotangent of the angle between the line connecting the two successive points of iteration with the vertical and as the dependent variable the given function y = f(x). The resulting iteration formula for a root estimation is shown to be the weighted sum of the estimates of the two previous iterations with a weighing factor that penalizes the iteration point having undesirable characteristics such as a near zero derivative. For example, near the point where the derivative of the function is zero, the weighing factor for that particular point will be close to zero. This condition effectively moves the iteration away from the undesirable point having zero derivative.

The method offers a particular advantage for cases where the traditional Newton method and its variants of higher order convergence may not converge at all. In terms of computational effort, the proposed method requires only evaluation of the value of a function and its derivative at each step of the iteration except for the first iteration step in which two functional evaluations are required for the first two starting points.

The Third Order Two Point Newton Method proposed in this paper is a modification of the earlier Two Point Newton method. The modificationstep consists ofestimation of the x-and y values as well as the first derivative for an intermediate point that lies between the two successive points of iteration. The method, as will be shown later, requires evaluation of the function and its derivative for each step of the iteration except the first iteration step which requires evaluation of a function and thederivative for the first two starting points. The proposed procedure as such offers a higher computation efficiency requiring evaluation of two functions per iteration only while attaining a third order convergence.

2. Methodology

The two-point Newton method developed earlier by the author[9] takes the form:

(1)

Where

- x_k-1, x_k and x_k+1 = the estimate of the root at the k-1^th, k^thand k+1^th iterations respectively.

- y_k-1, y_k = the functional values corresponding to the values of x_k-1 and xk respectively.

- y'_k = the first derivative of the function y at the kth iteration.

The modified cubically convergent Two-Point Newton method proposed in this paper is based on a two-step extension of the earlier method but with the same number of functional evaluations as the earlier method. The step for the proposed method is outlined below.

First Equation 1 above is applied to locate the intermediate point x_i (refer to Figure 1 below).

Figure 1. The graph of y=f(x) showing iteration points x0, x1, xi and x2

(2)

The estimate for the derivative dy/dx at the intermediate point is made using the linear extrapolation of the derivatives at x₀ and x₁.

(3)

The estimate for the functional value at the intermediate point yi is made from the derivatives at the points x₁ and point x_i using the Trapezoidal rule. (Refer to Figure 2 below).

Area of the Trapezoid A is calculated as: (Figure 2 above):

Figure 2. Estimate for the intermediate y value using trapezoidal rule

Further yi can be expressed as:

(4)

Inserting the expression for area A given above;

Substituting the expression for y'_igiven in Equation 3 above results in:

Further simplification leads to:

(5)

Finally the estimate for x₂ is made by applying the Two Point Newton formula once again:

(6)

In terms of the iteration steps, k-1, k and k+1, Equation 6 above is generalized as:

(7)

Computation steps

The computational procedure for each step of the iteration consists of evaluation of equations 8,9,10 and 11 that are shown below. It is to be noted that, for x_k-1 the most recent value obtained from the previous intermediate iteration , i.e., x_(k-1)i will be used instead of x_k-1 which represents a point further away from the root than the point x_(k-1)i .

(8)

(9)

(10)

(11)

3. Proof of Third Order Convergence

The iteration process follows the following sequence:

Examination of the columns of x values shown above reveals that the intermediate x values of the iteration x_i1, x_i2, x_i3, etc., are bounded both to the left and to the right with the same sequence of x values of the iteration, i.e., x₁, x₂, x₃, etc. Therefore, the intermediate points also converge to the same root towards which the x values converge. They also converge to the root with the same rate of convergence as the x values.

Using Taylor series expansion of the functions y and its derivative about the root r gives the following expression:

Where the C_m values are given by:

In the above expression, r is the desired root of the equation and y^m+1(r) is the m+1^th derivative of the function y evaluated at the root x = r.

Denoting the error terms e_k = x_k-r; e_k-1 = x_k-1-r, etc.;

It is now possible to write the expression for the intermediate point of iteration, x_i, i.e.

(12)

In terms of the error terms e_k, e_k-1, etc., equation 12 above can be rewritten as;

(13)

Substituting the Taylor series forms for the variables y, y_(k-1)iandy'_kin Equation 13 above and using the commands available in MATLAB symbolic manipulation platform MUPAD resulted in the following simplified expression for e_ki. Note that terms containing fourth order errors involving e_k and e _{(k-1) i} have been discarded.

(14)

Similar manipulation of the error terms using MATLAB for e_k+1 also gives the following expression:

(15)

Defining positive real terms S_k and S_k-1 so that;

From Equation 14 above;

(16)

Also from Equation 15 above;

Solving for e_k once again;

(17)

Equating the constants of the expressions for e_k in Equations 16 and 17 gives;

Rearranging further;

Equating expressions containing the e_k term in Equations 16 and 17 gives;

For the above expression to be true, the exponent term should be equal to zero, i.e.

Since α= 0 is not valid solution for a convergent iteration, α = 3 is taken as the feasible solution.

Therefore, the iteration process given in Equations 8, 9, 10 and 11 has a third order (cubic) convergence.

4. Computational Efficiency

The computational efficiency is usually estimated through the formula[10]:

(18)

Where α= the order convergence of the method and C = the number of functional evaluations required at each step of the iteration. Table 1 below gives a comparison of the computational efficiency of the proposed method with some of the existing methods for computing roots of various orders.

It is clear that, compared with all the methods listed below in Table 1 that have convergence order less than or equal to eight, the proposed method has a higher computational efficiency. Its efficiency is equal to that of a Ninth order method requiring four functional evaluations. This comparison serves to highlight the computational efficiency of the proposed Third Order - Two Point Newton method which requires only two functional evaluations for all the steps of the iteration except the first one.

Table 1. Comparison of computational efficiency of the proposed method with some of existing methods

5. Application Examples

Equations used to test the efficiency of root finding methods have been used in this paper to evaluate the number of iterations required to reach to a specified level of convergence (Table 2). The stopping criterion used for the iteration process is given by:

(19)

The rate of convergenceα, towards the root x = r for each step of the iteration is evaluated using the formula:

(20)

Table 2 above shows a comparison of the proposed Third Order Two-Point Newton method with the traditional Newton method as well as the Two Point Newton method developed earlier[9] and which has a super-quadratic convergence of order 2.414. The equations tested include the ones used to test efficiency of root finding methods elsewhere. A third order (cubic) convergence with which the proposed method converges to the root is mostly evident with the α values being close to 3.0 or above for most of the test equations. It can also be seen from Table 2 that less number of iterations are required to reach to the desired root for the proposed method than the number of iterations required for Newtonmethod and for the original Two Point Newton method.

Table 2. Comparison of result of iterations of the Third Order Two-Point Newton method with Newton Method and the unmodified Two point Newton method

6. Conclusions

A numerical iterative procedure of root finding that uses a third order modification of the Two-Point Newton method has been presented in this paper. It is proved that the method has a third order (cubic) convergence. In terms of computational effort involved, the proposed method displays a higher computational efficiency requiring only two functional evaluations per iteration except for the first iteration step. Most of the higher order methods documented in the literature (third order and above) require evaluation of at least three functions to achieve the desired rate of convergence. This proposed method, on the other hand, achieves a third order convergence with two functional evaluations per iteration. The computational efficiency for the proposed method is comparable with a 9^th order method that requires four functional evaluations. The computational efficiency is also shown to be greater than 3^rd, 4^th and higher order methods that requirethree or more functional evaluations per iteration.

The stability of the proposed method against equations for which the traditional Newton method may fail to converge is still retained as in the unmodified Two Point Newton method proposed earlier[9]. This characteristic of stability makes the proposed method applicable to a wide range of equations.