Hybrid Steffensen’s Method for Solving Nonlinear Equation

Hamideh Eskandari

Department of Mathematics, Payame Noor University, Tehran, Iran.

DOI: 10.4236/am.2022.139046                

Abstract

In this paper, we are going to present a class of nonlinear equation solving methods. Steffensen’s method is a simple method for solving a nonlinear equation. By using Steffensen’s method and by combining this method with it, we obtain a new method. It can be said that this method, due to not using the function derivative, would be a good method for solving the nonlinear equation compared to Newton’s method. Finally, we will see that Newton’s method and Steffensen’s hybrid method both have a two-order convergence.

Keywords

Convergence, Simple Root, Newton’s Method, Steffensen’s Method, Nonlinear Equation, Iteration Method, Steffensen’s Hybrid Method

1. Introduction

In most fields of engineering, basic sciences, economics, management, etc., there are important problems, one of which is solving the nonlinear equation and finding the root of the nonlinear equation $f\left(x\right)=0$, which is one of the oldest problems in different and still scientists in different fields do a lot of research in this field.

If a number such as $\alpha$ in $f\left(\alpha \right)=0$ the case applies to the $\alpha$ root of the equation $f\left(x\right)=0$ or zero function $f\left(x\right)$. It is easy to find zero function for a linear function or quadratic function, but if the function is not a first or second degree algebraic function or a nonalgebraic function, it is not easy to find a zero function and we have to find the approximate zero from numerical methods or iteration methods.

2. Simple Methods

There are many methods to find the root of the nonlinear equation $f\left(x\right)=0$ in numerical analysis and computing books. [1] [2] [3] [4] [5] One of the easiest methods is simple iteration method or fixed point method. In this method, we assume that the function $f\left(x\right)$ in the interval $\left[a,b\right]$ has a unique root $\alpha$ and we write the equation $f\left(x\right)=0$ by manipulation $x=g\left(x\right)$. Therefore, it can be concluded according to $\alpha$ from $f\left(\alpha \right)=0$ that $\alpha =g\left(\alpha \right)$. So, the root $\alpha$ is both equation $f\left(x\right)=0$ and $x=g\left(x\right)$. We call the fixed point of function g.

Now we have an approximation of $\alpha$ the name $x_0$ and create the iteration sequence $\left\{x_n\right\}$ for $x_{n+1}=g\left(x_n\right)$ the form $n=0,1,2,3,\cdots$. Under the appropriate conditions for the function g as stated below, this iteration sequence will converge to the fixed point of function g or function f. We call the iteration formula $x_{n+1}=g\left(x_n\right)$ for $n=0,1,2,3,\cdots$ the formula a simple iteration method.

Determining the characteristics of the function g and the initial value $x_0$ for which the iteration sequence $\left\{x_n\right\}$ converges requires the following theories, proving them in calculus and numerical mathematics.

Theorem 1

If there is a function g in $\left[a,b\right]$ on $\left[a,b\right]$ and there is a positive constant number L that $\left|g^{\prime }\left(x\right)\right|\le L<1$, then the equation $x=g\left(x\right)$ has only one root that belongs to the interval $\left[a,b\right]$.

Theorem 2

With the conditions of the theorem 1 for each $x_0$ in $\left[a,b\right]$ sequence $\left\{x_n\right\}$ with condition $x_{n+1}=g\left(x_n\right)$ converges only with the answer $x=g\left(x\right)$.

Theorem 3

If the sequence $\left\{x_n\right\}$ obtained by the simple iteration method from the equation $x=g\left(x\right)$ is connected to the root $\alpha$ convergent and g has a derivative of order k, $g^{\prime }\left(\alpha \right)=g^{″}\left(\alpha \right)=\cdots =g^{\left(k-1\right)}\left(\alpha \right)=0$ and $g^{\left(k\right)}\left(\alpha \right)\ne 0$ then the order of convergence of the sequence $\left\{x_n\right\}$ is equal to k.

Stop Criteria

We use the following conditions to stop the calculation of x_ns.

If $\epsilon$ is a very small positive number

1) We calculate x_ns until the time when $\left|f\left(x_n\right)\right|<\epsilon$, means as soon as $\left|f\left(x_n\right)\right|<\epsilon$ we stop the operation and where we accept $x_n$ as an approximation of $\alpha$.

2) If we stop the operation $\left|x_n-x_{n-1}\right|<\epsilon$ and accept $x_n$ as an approximation of the root.

3. Preliminary Results

One of the fastest methods, as well as the method that can be seen in most calculation books, is Newton’s method [1]. This method is an iterative method and in it is assumed that a function like $f:R\to R$ is a smooth nonlinear function with a simple root $x^{*}$, that is, it is assumed that $f\left(x^{*}\right)=0$ has a first order derivative $f^{\prime }\left(x^{*}\right)\ne 0$. Starting from a starting point $x_0\in R$ which is a relatively close estimate of the desired root, we obtain $n=0,1,2,\cdots$ values per $x_n$ using the iteration formula

$x_{n+1}=x_n-\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)}$ (1)

This iteration formula is known as Newton iteration formula. This method is a special case of simple iteration method.

We use the previous theorems to discuss the convergence of Newton’s method. We write the equation of $f\left(x\right)=0$ in the form of $x=x-\frac{f\left(x\right)}{f^{\prime }\left(x\right)}$, that is

$g\left(x\right)=x-\frac{f\left(x\right)}{f^{\prime }\left(x\right)}$ (2)

and the formula for iteration Newton’s method will be in the form of $x_{n+1}=g\left(x_n\right)$, that is mean $x_{n+1}=x_n-\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)}$.

To discuss the convergence of Newton’s method, we need to examine the convergence conditions of the simple iteration method for the $g\left(x\right)$ defined in (2). For this purpose, we calculate $g^{\prime }\left(x\right)$ and assume that the f function has a continuous second order derivative. So we have

$g^{\prime }\left(x\right)=\frac{f^{″}\left(x\right)f\left(x\right)}{{\left(f^{\prime }\left(x\right)\right)}^2}$ (3)

If $\alpha$ is a simple root, it is $f\left(\alpha \right)=0$ and $f^{\prime }\left(\alpha \right)\ne 0$, and therefore it is $g^{\prime }\left(\alpha \right)=0$.

And also $g^{″}\left(\alpha \right)=\frac{f^{″}\left(\alpha \right)}{f^{\prime }\left(\alpha \right)}$ is obtained, which is easily the result of $g^{″}\left(\alpha \right)\ne 0$, and therefore Newton’s method has convergence of the second order.

One of the problems with Newton’s method is the necessity of existence of $f^{\prime }\left(x\right)$ and its calculation at points $x_n$ and the fact that it is always $f^{\prime }\left(x_n\right)\ne 0$. Sometimes the function f does not have a derivative, as a result of which it will not be possible to use Newton formula, or the $f^{\prime }\left(x\right)$ form and its calculation are complicated.

To solve these problems and avoid calculating the first order derivative, you can use Steffensen’s method [1] [2] [4] [6].

In this method, for the first order derivative of the function $f\left(x\right)$ at the point x with step length h, we use the three main approximation formulas, i.e. the forward difference formula

$f^{\prime }\left(x\right)\approx \frac{f\left(x+h\right)-f\left(x\right)}{h}$ (4)

or the backward difference formula

$f^{\prime }\left(x\right)\approx \frac{f\left(x\right)-f\left(x-h\right)}{h}$ (5)

or the central difference formula of

$f^{\prime }\left(x\right)\approx \frac{f\left(x+h\right)-f\left(x-h\right)}{2h}$ (6)

If we use the first order derivative of the $f\left(x\right)$ function at the point $x_n$ with step length $h=f\left(x_n\right)$ in the forward difference formula (4), we have

$f^{\prime }\left(x_n\right)\approx \frac{f\left(x_n+f\left(x_n\right)\right)-f\left(x_n\right)}{f(\; x\; n\; )}$

By inserting in Newton iteration formula (1), we arrive at Steffensen iteration formula

$x_{n+1}=x_n-\frac{{\left(f\left(x_n\right)\right)}^2}{f\left(x_n+f\left(x_n\right)\right)-f\left(x_n\right)}$ (7)

If we use the first derivative of the function $f\left(x\right)$ at the point $x_n$ with step length $h=f\left(x_n\right)$ in the backward difference formula (5), we have

$f^{\prime }\left(x_n\right)\approx \frac{f\left(x_n\right)-f\left(x_n-f\left(x_n\right)\right)}{f(\; x\; n\; )}$

By inserting in Newton iteration formula (1) we have

$x_{n+1}=x_n-\frac{{\left(f\left(x_n\right)\right)}^2}{f\left(x_n\right)-f\left(x_n-f\left(x_n\right)\right)}$ (8)

If we use the first order derivative of the function $f\left(x\right)$ at the point $x_n$ with step length $h=f\left(x_n\right)$ in the central difference formula (6), we have

$f^{\prime }\left(x_n\right)\approx \frac{f\left(x_n+f\left(x_n\right)\right)-f\left(x_n-f\left(x_n\right)\right)}{2f(\; x\; n\; )}$

By inserting in Newton iteration formula (1) we have

$x_{n+1}=x_n-\frac{2{\left(f\left(x_n\right)\right)}^2}{f\left(x_n+f\left(x_n\right)\right)-f\left(x_n-f\left(x_n\right)\right)}$ (9)

Each of the iteration formulas (7), (8) and (9) has convergence higher than two. [1] [2] [4] [6] That this subject has been proven in many articles and books.

We want to combine the iteration formula (7) and (8). We do this by using the w parameter. We introduce the w parameter in this method. If $0\le w\le 1$ is a real constant number to write the convex combination of these two iteration formulas, we act like this. We know that

$x_{n+1}=w{x}_{n+1}+\left(1-w\right)x_{n+1}$

Now, instead of each of the $x_{n+1}$, we place the iterations formulas (7) and (8).

$=w\left(x_n-\frac{2{\left(f\left(x_n\right)\right)}^2}{f\left(x_n+f\left(x_n\right)\right)-f\left(x_n\right)}\right)+\left(1-w\right)\left(x_n-\frac{2{\left(f\left(x_n\right)\right)}^2}{f\left(x_n\right)-f\left(x_n-f\left(x_n\right)\right)}\right)$

By simplifying we will have each

$=x_n-2{\left(f\left(x_n\right)\right)}^2\left(\frac{w}{f\left(x_n+f\left(x_n\right)\right)-f\left(x_n\right)}+\frac{1-w}{f\left(x_n\right)-f\left(x_n-f\left(x_n\right)\right)}\right)$

So, the formula for hybrid Steffensen iteration will be as follows

$x_{n+1}=x_n-2{\left(f\left(x_n\right)\right)}^2\left(\frac{w}{f\left(x_n+f\left(x_n\right)\right)-f\left(x_n\right)}+\frac{1-w}{f\left(x_n\right)-f\left(x_n-f\left(x_n\right)\right)}\right)$

Where w is parameter and $0\le w\le 1$.

If we change the value of w, we can get the zero of the nonlinear equation for different w and $0\le w\le 1$ with a relatively good approximation even compared to Newton’s method. It can be said that the new iteration formula, i.e., Steffensen’s hybrid method, has the same order of convergence as Steffensen’s method because it uses Steffensen’s method.

In order to see this issue better, we will give some examples in the next part. And we will see that the speed of convergence changes with the change of w for different functions.

4. Numerical Experiments

Here, in order to compare different w in this method, we bring some examples of non-linear equations and compare them (Table 1).

The result of this programming in Maple for these functions using Newton’s method is shown in the following table. In all these functions $\epsilon ={10}^{-1000}$ and $x_0=1.000000000$ are assumed. The different iterations of this method are listed in Table 2.

The result of this programming in Maple for these functions using Steffensen’s method is shown in the following table. In all these functions $\epsilon ={10}^{-1000}$ and $x_0=1.000000000$ are assumed. The different iterations of this method are listed in Table 3.

The result of this programming in Maple for these functions using Steffensen’s hybrid method is shown in the following table that we have obtained an approximate value for several values of w. In all these functions $\epsilon ={10}^{-1000}$ and $x_0=1.000000000$ are assumed. The different iterations of this method are listed in Tables 4-6 for w = 0.5, 0.25 and 0.85, respectively.

Table 1. Some examples of the function with its zero.

Table 2. Solution by using Newton’s method.

Table 3. Solution by using Steffensen’s method.

Table 4. Solution by using Steffensen’s hybrid method w = 0.5.

Table 5. Solution by using Steffensen’s hybrid method w = 0.25.

Table 6. Solution by using Steffensen’s hybrid method w = 0.85.

When we compare the number of repetitions with different w in Tables 4-6, we get interesting results. It can be seen that with this simple method it is possible to converge to a quick answer.

5. Conclusion

In this article, a class of solutions for a nonlinear equation was presented. Steffensen’s method is a simple method to solve the nonlinear equation. Using the w parameter, we obtained a class of answers. The method presented in this article called the Steffensen’s Hybrid Method, is a relatively good and fast method for solving nonlinear equations. One of its good features is that it does not use the derivative of the function in this method, and perhaps it can be said that this method is superior to Newton’s method, that by changing w, better results can be obtained and the solution method can converge faster.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Kincaid, D. and Cheney, W. (1996) Numerical Analysis. 2nd Edition, Brooks/Cole, Pacific Grove.
[2]	Jaiswal, J.P. (2013) A New Third-Order Derivative Free Method for Solving Nonlinear Equations. Universal Journal of Applied Mathematics, 1, 131-135. https://doi.org/10.13189/ujam.2013.010215
[3]	Eskandari, H. (2010) Solution of Equation by Using Difference Formulas. Proceedings of the 15th WSEAS International Conference on Applied mathematics. Athens, 29-31 December 2010, 17-19.
[4]	Sharma J. (2005) A Composite Third Order Newton–Steffensen Method for Solving Nonlinear Equations. Applied Mathematics and Computation, 169, 242-246. https://doi.org/10.1016/j.amc.2004.10.040
[5]	Hamideh, E. (2014) Generalized Difference Formula for a Nonlinear Equation. Applied and Computational Mathematics, 3, 30-136. https://doi.org/10.11648/j.acm.20140304.14
[6]	Tahereh, E. (2014) A New Sixth-Order Steffensen-Type Iterative Method for Solving Nonlinear Equations. International Journal of Analysis, 2014, Article ID: 685796. https://doi.org/10.1155/2014/685796