# Fourth order methods for finding multiple as well as distinct zeros of non-linear equations.

1. Introduction

Finding the roots of a single variable non-linear equations efficiently, is a very interesting and old problem in numerical analysis and has many applications in engineering and other applied sciences.

We consider equation of the form

f(x) = 0, (1.1)

where f(x) is single variable non-linear function. Many one-step iterative methods for solving non-linear equations for distinct zeros have been developed using various techniques, see (1 - 7). Recently, Ujevic (10) has suggested two- step method for solving non-linear equations for distinct zeros.

Motivated by the research going on in this direction, we present and analyze six two-step iterative methods for finding multiple as well as distinct zeros of non-linear equations. We prove that the methods for multiple zeros as well as the methods for distinct zeros have fourth order convergence. The methods calculate the multiple as well as the distinct zeros with high accuracy. The numerical tests show their better performance in case of algebraic as well as non-algebraic equations First, we generalize the method due to Mamta et al. (7) to the case of multiple zero finding of non-linear equations and combine it with modified J. Chen and W. Li method for multiple zero finding of non-linear equations(2), (9) and classical Newton's method for multiple zeros of non-linear equations. Our results can be considered as generalization, improvement and refinement of the previously known results in the literature.

2. Two-step Iterative Methods for Multiple and Distinct Zeros of Non-linear Equations

We suggest the following generalization to Mamta et al. method to the case of multiple zero finding of non-linear equations:

Consider the Mamta et al. method (7):

[x.sub.n+1] = [x.sub.n] - h([x.sub.n]),

where

h([x.sub.n]) = f([x.sub.n])/f'([x.sub.n]) + pf([x.sub.n])' (2.1)

p is chosen here as positive or negative sign so as to make the denominator largest in magnitude. We observe that

f([x.sub.n])/f'([x.sub.n]) = h([x.sub.n])/1-ph([x.sub.n]).

The modified Mamta et al. method for multiple zeros can be written as

[x.sub.[n + 1]] = [x.sub.n] - [alpha][[h([x.sub.n])]/[1 - ph([x.sub.n])]], (2.2)

where [alpha] is the multiplicity of the root and h([x.sub.n]) is provided by (2.1). The relation (2.2) can further be written as:

[x.sub.[n + 1]] = [x.sub.n](1 - [alpha][h([x.sub.n])]/[[x.sub.n](1 - ph([x.sub.n]))])[equivalent][x.sub.n]exp[gamma]( - [alpha][h([x.sub.n])]/[[x.sub.n](1 - ph([x.sub.n]))]). (2.3)

Combining the method (2.3) with modified Chen Li method for multiple zeros (9), namely

[x.sub.[n + 1]][equivalent][x.sub.n]exp[gamma]( - [alpha][f([x.sub.n])]/[[x.sub.n]f'([x.sub.n])]). (2.4)

we have therefore, the following two-step method for finding multiple zeros of non-linear equations:

[z.sub.n] = [x.sub.n]exp[gamma] (1 - [alpha][h([x.sub.n])]/[[x.sub.n](1 - ph([x.sub.n]))]), [x.sub.[n + 1]] = [z.sub.n]exp[gamma] ( - [alpha][h([x.sub.n])]/[[z.sub.n]f' ([z.sub.n])]). (2.5)

We propose the following three two-step algorithms for finding multiple zeros of non-linear equations:

Algorithm 1 (Chen-Li Mamta Method for Multiple Zeros(CLMM))

Step 1: For initial guess [x.sub.0], a tolerance [epsilon] > 0, and for iterations n, set k = 0.

Step 2: Calculate

[z.sub.k] = [x.sub.k]exp[gamma] ( - [alpha][f ([x.sub.k])]/[[x.sub.k]f' ([x.sub.k])]), [x.sub.[k + 1]] = [z.sub.k] exp [gamma] (1 - [[alpha]/[z.sub.k]][h([z.sub.k])]/[1 - ph([z.sub.k])]), (2.6)

where

h ([z.sub.k]) = [[f([z.sub.k])]/[f'([z.sub.k]) + pf([z.sub.k])]].

Step 3: If |x.sub.k+1] - [x.sub.k] < [epsilon] or k > n then stop.

Step 4: Set k [right arrow] k + 1 and go to Step 2.

Algorithm 2(Mamta Chen-Li Method for Multiple Zeros(MCLM))

Step 1: For initial guess [x.sub.o], a tolerance [epsilon] > 0, and for iterations n, set k = 0.

Step 2: Calculate

[z.sub.k] = [x.sub.k]exp[gamma] ( - [[alpha]/[x.sub.k]][h([x.sub.k])]/[1 - ph([x.sub.k])]),

where

h([x.sub.k]) = [[f([x.sub.k])]/[f'([x.sub.k]) + pf ([x.sub.k])]].[x.sub.[k + 1]] = [z.sub.k]exp[gamma], ( - [alpha][f([z.sub.k])]/[[x.sub.z]f'([z.sub.k])]). (2.7)

Step 3: If |x.sub.k+1] - [x.sub.k] < [epsilon] or k > n then stop.

Step 4: Set k [right arrow] k + 1 and go to Step 2.

Algorithm 3(Modified Mamta Newton Method for Multiple Zeros(MMNM))

Step 1: For initial guess [x.sub.0], a tolerance [epsilon] > 0, and for iterations n, set k = 0.

Step 2: Calculate

[z.sub.k] = [x.sub.k]exp[f( - [[alpha]/[x.sub.k]][h([x.sub.k])]/[1 - ph([x.sub.k])]),

where

h([x.sub.k]) = [[f ([x.sub.k])]/[f' ([x.sub.k]) + pf([x.sub.k])]][x.sub.[k + 1]] = [z.sub.k] - [alpha][[f([z.sub.k])]/[f'([z.sub.k])]]. (2.8)

Step 3: If |[x.sub.k+1] - [x.sub.k]| < [epsilon] or k > n then stop.

Step 4: Set k [right arrow] k + 1 and go to Step 2.

Taking [alpha] = 1, gives us the following three two-step algorithms for finding distinct zeros of non-linear equations:

Algorithm 4 (Chen-Li Mamta Method for Distinct Zeros(CLMD))

Step 1: For initial guess [x.sub.0], a tolerance [epsilon] > 0, and for iterations n, set k = 0.

Step 2: Calculate

[z.sub.k] = [x.sub.k] exp [gamma] ( - [f ([x.sub.k])]/[f' ([x.sub.k]) + pf([x.sub.k])]), [x.sub.[k + 1]] = [z.sub.k] exp [gamma] ( - [1/[z.sub.k]][h ([z.sub.k])]/[1 - ph([z.sub.k])]) (2.9)

Step 3: If |[x.sub.k+1] - [x.sub.k]| < [epsilon] or k > n then stop.

Step 4: Set k [right arrow] k + 1 and go to Step 2.

Algorithm 5(Mamta Chen-Li Method for Distinct Zeros(MCLD))

Step 1: For initial guess [x.sub.0], a tolerance [epsilon] > 0, and for iterations n, set k = 0.

Step 2: Calculate

[z.sub.k] = [x.sub.k] exp [gamma] ( - [1/[x.sub.k]] [h([x.sub.k])]/[1 - ph([x.sub.k])]), [x.sub.[k + 1]] = [z.sub.k] exp [gamma] ( - [f([z.sub.k])]/[[z.sub.k]f' ([z.sub.k])]). (2.10)

Step 3: If |[x.sub.k+1] - [x.sub.k]| < [epsilon] or k > n then stop.

Step 4: Set k [right arrow] k + 1 and go to Step 2.

Algorithm 6(Modified Mamta Newton Method for Distinct Zeros (MMND)

Step 1: For initial guess [x.sub.0], a tolerance [epsilon] > 0, and for iterations n, set k = 0.

Step 2: Calculate

[z.sub.k] = [x.sub.k] exp [gamma] ( - [1/[x.sub.k]][h ([x.sub.k])]/[1 - ph([x.sub.k])]), [x.sub.[k + 1]] = [z.sub.k] - [[f([z.sub.k])]/[f' ([z.sub.k])]]. (2.11)

Step 3: If |[x.sub.k+1] - [x.sub.k]| < [epsilon] or k > n then stop.

Step 4: Set k [right arrow] k + 1 and go to Step 2.

3. Convergence Analysis

In this section, we prove that algorithms 1, 2 and 3 as well as algorithms 4, 5 and 6 have convergence order four.

Theorem 1. Let [omega] be the root of sufficiently difierentiable function f: (a, b) [??] R [right arrow] R with multiplicity [alpha] If [x.sub.0] is sufficiently close to [omega], then the two-step method defined by Algorithm 1 has fourth order convergence. The error equation in this case is given by:

[e.sub.n+1] = 1/8[[alpha].sup.4][[omega].sup.3] ([[alpha].sup.4] + 6[[alpha].sup.3][omega][c.sub.2] + 12[[alpha].sup.2][[omega].sup.2][c.sub.2.sup.2] + 8[alpha][[omega].sup.3][c.sub.3.sup.2] - 8p[alpha][[omega].sup.3][c.sub.2.sup.2] - 8p[[alpha].sup.2][[omega].sup.2][c.sub.2] + 8p[[omega].sup.3][c.sub.2.sup.2] + 8p[alpha][[omega].sup.2][c.sub.2] - 2p[[alpha].sup.3][omega])[e.sub.n.sup.4] + O([e.sub.n.sup.5]),

where [e.sub.n] = [x.sub.n] - [omega] and [c.sub.j] = [f.sup.([alpha]+j-1)]([omega])/([alpha] + 1)([alpha] + 2) ... ([alpha] + j-1)[f.sup.([alpha])]([omega]), j = 2, 3, ...

Proof. The two-step method is given by

[z.sub.n] = [x.sub.n] exp [gamma] ( - [alpha] [f ([x.sub.n])]/[[x.sub.n]f' ([x.sub.n])]), (3.1)

[x.sub.[n + 1]] = [z.sub.n] exp [gamma] ( - [[alpha]/[z.sub.n]][h ([z.sub.n])]/[1 - ph([z.sub.n])]), h ([z.sub.k]) = [[f([z.sub.n])]/[f' ([z.sub.n]) + pf ([z.sub.n])]].(3.2)

where

Let [omega] be the root of multiplicity [alpha], i.e. f([omega]) = f'([omega]) = f"([omega]) = ... = [f.sup.([alpha]-1)]([omega]) = 0 and [f.sup.([alpha])]([omega]) [not equal to] 0.

By Taylor expansion of f([x.sub.n]) about [omega] we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [e.sub.n] = [x.sub.n] - [omega] and [c.sub.j] = [f.sup.([alpha]+j-1)]([omega])/([alpha] + 1)([alpha] + 2) ... ([alpha] + j-1)[f.sup.([alpha])]([omega]), j = 2, 3, ...

Similarly, we obtain

f' ([x.sub.n]) = [[[f.sup.([alpha])](omega)]/[([alpha] - 1)!]] [e.sub.n.sup.[[alpha] - 1]] [1 + [c.sub.2][[[alpha] + 1]/[alpha]] [e.sub.n] + [c.sub.3] [[[alpha] + 2]/[alpha]] [e.sub.n.sup.2] + O([e.sub.n.sup.3]). (3.4)

From(3.3) and (3.4), we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and thus we have

-[alpha] [[f([x.sub.n])]/[[x.sub.n]f' ([x.sub.n])]] = [[e.sub.n]/[alpha]] + [[c.sub.2]/[[alpha].sup.2]] [e.sub.n.sup.2] - [1/[[alpha].sup.3]] ([alpha][c.sub.2.sup.2] - 2[alpha][c.sub.3]) [e.sub.n.sup.3] + [1/[[alpha].sup.4]] (3[[alpha].sup.2] [c.sub.2] [c.sub.3] + 4[alpha] [c.sub.2] [c.sub.3] - 3[[alpha].sup.2] [c.sub.4] - [[alpha].sup.2][c.sub.2.sup.3] - 2[alpha] [c.sub.2.sup.3] - [c.sub.2.sup.3])[e.sub.n.sup.4] + O([e.sub.n.sup.5]), (3.6)

implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now by Taylor expansion of f([z.sub.n]) about [omega] we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Similarly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

?From (3.8) and (3.9), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Finally, by using (3.7) and (3.11) we have,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

that is,

[e.sub.n+1] = 1/8[[alpha].sup.4][[omega].sup.3] ([[alpha].sup.4] + 6[[alpha].sup.3][omega][c.sub.2] + 12[[alpha].sup.2][[omega].sup.2][c.sub.2.sup.2] + 8[alpha][[omega].sup.3][c.sub.3.sup.2] - 8p[alpha][[omega].sup.3][c.sub.2.sup.2] - 8p[[alpha].sup.2][[omega].sup.2][c.sub.2] + 8p[[omega].sup.3][c.sub.2.sup.2] + 8p[alpha][[omega].sup.2][c.sub.2] - 2p[[alpha].sup.3][omega])[e.sub.n.sup.4] + O([e.sub.n.sup.5]),

showing that the algorithm has fourth order convergence.

Remark 2. Similarly, convergence order four of the second and third algorithms can also be determined.

Remark 3. Note that in case [alpha] = 1, we have fourth order two-step method for finding distinct zeros of non-linear equations, given in the form of algorithm 4. Similar proofs follow for algorithms 5 and 6 to show that they also have fourth order convergence.

4. Numerical Tests

Here, we give some numerical examples to test and illustrate the performance of our new six two-step methods for finding multiple zeros as well as distinct zeros of non-linear equations. We name the classical one-step Newton method for multiple zeros as NMM. We consider here [epsilon] = 1.0E - 64 as given tolerance, n, the maximum number of iterations to be performed and |[x.sub.i+1] - [x.sub.i]| < [member of] as stopping criterion. The computations are performed using Maple 10.0.

The following examples are used for numerical testing:

Ex.1: [f.sub.1] = [(x - 1).sup.40] [(x - 2).sup.30] [(x - 3).sup.20] [(x - 4).sup.10] (11)

Ex.2: [f.sub.2] = [[x - (0.3 + 0.6i)].sup.100][[x - (0.1 + 0.7i)].sup.200][[x - (0.7 + 0.5)].sup.300][[x - (0.3 + 0.4i)].sup.10] (11)

Ex.3: [f.sub.3] = (x - 1) ([e.sup.x-1] - 1) (8)

Ex.4: [f.sub.4] = f (x) = ln (x) (2)

Ex.5: [f.sub.5] = f (x) = arctan (x) (2)
```Table 4.1

Ex 1:  Initial point  Exact root  Number of Iterations

[x.sub.0]    [x.sub.n]   MCLM  CLMM  MMNM  NMM

0.6           1        3     3     3    7
2.5           2        4     4     4    8
3.5           3        4     4     4    8
4.4           4        5     5     5    10

Table 4.1

Table 4.2

Ex 2:  Initial point   Exact root    Number of Iterations

[x.sub.0]     [x.sub.n]   MCLM   CLMM  MMNM  NMM

0.300 + 601i  0.3 + 0.6i    3       3     3    6
0.100 + 702i  0.1 + 0.7i    3       3     3    6
0.700 + 498i  0.7 + 0.5i    3       3     3    6
0.280 + 401i  0.3 + 0.4i    3       3     3    6

Table 4.3

Ex 3:   Initial point  Exact root      Number of Iterations

[x.sub.0]    [x.sub.n]     MCLM    CLMM  MMNM    NMM
1.5          1.0         4       4     3 *    7

* Maximam Accuracy 34 digits
```

We have tested our three methods, namely MCLM, CLMM, and MMNM for determining the multiple zeros of algebraic as well as non-algebraic equations on a sufficient number of examples to check their robustness and efficiency. We mention here, however, three examples. which are taken from (1), (8), (11). Numerical results are provided in Tables 4.1 to 4.3. We compare our methods among themselves and also with one-step Newton method for multiple zeros. From Table 4.1, we, observe that, in general, the ill conditioned roots 1,2,3 and 4 of polynomial of degree 100 are calculated in 3 to 5 iterations with 64 digits accuracy by our proposed methods, whereas, Newton's method takes double the number of iterations to reach the same accuracy. Table 4.2 describes the result for polynomial of degree 1000 with complex coefficients and complex roots with huge multiplicities. We obtained the roots on third iteration getting 64 digits accuracy by our methods, whereas Newton's method takes double the number of iterations to reach the same accuracy Table 4.3 gives the numerical results for multiple zeros of non-algebraic equations. In three to 4 iterations, we obtained the roots correct up to 64 digits accuracy, whereas, Newton's method takes double the number of iterations to reach the same accuracy.
```Table 4.4

Ex 4:  Initial point  Exact root       Number of Iterations

[x.sub.0]      [x.sub.n]   MCLD  CLMD  MMND  NM  Formula 9

6             1          1     1    1      D      7
4             1          1     1    1      D      4
2             1          1     1    1      8      5
6.3            1          1 *   1 *  1 **   D      D

* Maximam accuracy 58 digits and
** Maximam accuracy 61 digits

Table 4.5

Ex 5:  Initial point  Exact root        Number of Iterations

[x.sub.0]      [x.sub.n]   MCLD  CLMD  MMND  NM  Formula 9

2             1         4     4     4     6      7
1.8            1         4     4     4     6      6
1.4            1         4     3     4     5      5
2.4            1         4     4     4     D      D
```

Similarly, we compare our methods, namely MCLD, CLMD and MMND with the one-step methods, namely the best method(Formula(9))of Chen, and Newton method (2) for determining distinct zeros of non-linear equations. The numerical results are provided in Table 4.4. to 4.5 We observe that our proposed methods provide highly accurate results in less number of iterations, where as the method of Chen and Newton method diverge at some points as well.

5. Conclusion

We have established six new two-step iterative methods of order four for finding multiple and distinct zeros of algebraic as well as non-algebraic equations. In view of the numerical tests, it follows that our methods for multiple zeros are very effective in determining the highly multiple ill-conditioned zeros of real as well as complex polynomial equations with high accuracy. These are also very effective and efficient in determining multiple zeros of non-algebraic equations, which shows the robustness of the methods. Similarly our methods for distinct zeros provide highly accurate results in less number of iterations as compared to some well known existing methods.

References

(1) R. L. Burden and J. D. Faires, Numerical analysis, PWS publishing company, Boston USA, 2001.

(2) J. Chen and W. Li, On new exponential quadratically convergent iterative formulae, Appl. Math. Comput., 180 (2006), 242-246.

(3) C. Chun, Iterative methods Improving Newton's method by the decomposition method, Int. J. Comp. Math. Appl., 50(2005), 1559-1568.

(4) M. Frontini and E. Sormani, Some variants of Newton's method with third order convergence and multiple roots, J. Comput. Appl. Math., 156(2003), 345-354.

(5) M. Frontini and E. Sormani, Third order methods for quadrature formulae for solving system of non-linear equations, Appl. Math. Comput., 149(2004), 771-782.

(6) M. V. Kanwar, V. K. Kukreja, and S. Singh, On a class of quadratically convergent iteration formulae, Appl. Math. Comput., 166(3)(2004), 633- 637.

(7) Mamta, V. Kanwar, V. K. Kukreja, and S. Singh, On some third order iterative methods for solving non-linear equations, Appl. Math. Comput., 171(2005), 272-280.

(8) G. Wheatley, Applied Numerical Analysis, Pearson Education Inc.

(9) N. A. Mir and Naila Rafiq, Third-order and fourth-order iterative methods for determining multiple and distinct zeros of non-linear equations, Appl. Math. Comput., 190(2007), 432-440.

(10) N. Ujevic, A method for solving non-linear equations, App. Math. Comput., 174(2006), 416-426.

(11) Z. Zeng, Computing multiple roots of inexact polynomials, Mathematics of Computation, 74 (250)(2004), 869-903.

Department of Mathematics, COMSATS Institute of Information Technology, Plot No. 30, Sector H-8/1, Islamabad 44000, Pakistan

and

Centre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, Pakistan

Received February 17, 2009, Accepted May 19, 2009.

* 2000 Mathematics Subject Classification. Primary 34A34, 65H05.

[double dagger] E-mail: farooqgujar@gmail.com

[section] E-mail: mreza06r@gmail.com

[paragraph] E-mail: tahira.nawaz@gmail.com