Development and Analysis of New Iterative Schemes for Solving Nonlinear Equations
Chapter One
Aim and objectives
The aim of the study is to develop and analyse new iterative schemes for solving nonlinear equations.
The objectives of the study are
- To review iterative schemes between 1998 and 2012 which have been developed from Adomian decomposition method, Homotopy perturbation method and variants of Newton-Raphson’s method for solving nonlinear
- To develop new schemes that could compete with previous schemes and probably have further
- To compare the new schemes with the existing known iterative
CHAPTER TWO
LITERATURE REVIEW
Introduction
A numerical method for determining zeroes of a functional equation, f ( x) = 0 is generally an iterative method that will converge to zero of the function, f (x) . It is simply a method which
produces an approximate rather than exact solution. As one would presume, each algorithm has its advantages and disadvantages and therefore selecting the right algorithm for a given problem is never easy. Various methods for solving one variable nonlinear equations are presented in the literature. Probably the easiest numerical method for solving a nonlinear equation is the Newton (Newton-Raphson) method as already stated in chapter 1. This method have local convergent and will converge to complex zeros only if the initial guess is complex. However, it can be suitably modified to compute zeros of complex polynomials and transcendental equations. When Newton’s method does converge, the convergence is quadratic, ie the order of convergence is two.
The Newton-Raphson algorithm is derived from Taylor series expansion of nonlinear equation. The higher order terms (second order and higher order derivatives of the series) are neglected assuming that the initial guess for the iterative process is closer to the solution. Hence the equation for Newton- Raphson method is one of the reduced forms of Taylor series expansion. The Newton-Raphson method is an iterative process for solving other non-linear equations. In the iterative process, the first order derivative of the non-linear equation is calculated at an initial guess of the variables for the first iteration. The change in variables is then calculated by solving linear equations that contain the first order derivative and input vector. The change in variable is used to update the variables in each iteration. The updated variables are used in successive iteration, Ortega and Rheinboldt (1970) and are given as follows:
x = x
f(xn )
which is the Newton-Raphson method, where
x is the new iterate and
n+1
n f ¢(x )
n+1
xn is the previous one.
Generalizations of Newton’s method
Several researchers generalized this method and offered methods which suggest convergence with higher orders in comparison with Newton’s method. The following works are variants of Newton-Raphson method.
Jisheng et al. (2006) presented a new modification of Newton’s method for solving non-linear equations. Analysis of convergence showed that the new method is cubically convergent. Per iteration, the new method requires two evaluations of the function and one evaluation of its first derivative. Thus, the new method is preferable if the computational costs of the first derivative are equal or more than those of the function itself. Its practical utility was demonstrated by numerical examples. Jisheng et al. scheme is as follows:
CHAPTER THREE
CONSTRUCTION OF THE NEW SCHEMES
Introduction
In this section we construct two new methods for solving nonlinear algebraic and transcendental equations, f (x) = 0.
As mentioned earlier, there is no general methods for finding solutions of nonlinear equations. Researchers are continuously trying to develop easy methods to accurately and efficiently solve problems of nonlinear equations. The new schemes we have developed give results faster than the Adomian’s decomposition method and equally or faster than other methods derived from Adomian’s and other methods. The convergences of the new schemes are proved to be of cubic order. Several examples are presented and the new schemes are used in solving the examples. The examples are also solved with other existing methods, namely Abbasbany’s, Adomian decomposition method, Basto et al. and Newton-Raphson method, which showed the accuracy and fast convergence of these new schemes. With the assumption that
f ¢ » 1, the schemes obviously are free of
f ¢
second derivative and this reduces the computational cost. This assumption is in particular true for the function
e x and some functions such as
x3 + 4x 2 + 8x + 8 at x = – 2 ,
x3 – 6x – 4
at x = -0.732
and 3x – ln x – 16
at x = -0.434 , see appendix. Of course there are other situations where the assumption is far away from being true.
The schemes start with an initial guess and then generate a sequence of approximations which improve the solution of a problem at each step.
The present work
Suppose we consider the nonlinear equation f (x) = 0 , such that a is a root of the equation and f is a continuous function on an interval containing a. For the new scheme 1, we start
from Taylor’s series around x and truncate the series after the third term, while for the new scheme 2, we truncate after the fourth term of the series. Assuming that the initial guess for the iterative process is closer to the solution, then we apply ADM. The ADM involves breaking the given equation into linear and nonlinear parts. The linear operator representing the linear portion of the equation is inverted and the inverse operator is then applied to the nonlinear part. The nonlinear part is decomposed into a series of Adomian polynomials. This method gives a solution in the form of a series whose terms are determined by a recursive relationship using these Adomian polynomials. To explain clearly the Adomian approach, consider the equation
Fy = f
where F is a nonlinear differential operator involving both y and f are functions of t . Rewriting the equation we get
CHAPTER FOUR
ANALYSIS OF RESULTS
Introduction
We present some numerical examples to illustrate the efficiency and the accuracy of the new developed iterative methods for solving problems of nonlinear algebraic equations. To demonstrate the performance of the new methods, we solved thirty examples of different nature. As mentioned earlier, the methods used for comparison with the new developed iterative methods are Newton-Raphson method, Abbasbanby, Basto et al. and Adomian method. The iterative methods for this class of equations will require knowledge of initial guess for desired roots of equations. Adomian method was used to find the initial point x0 . The comparison was carried out in terms of the number of iterations obtained from the different methods used, using one way analysis of variance (ANOVA). In each case, the comparison was done only for those methods which converge for the particular numerical example. Note also that methods such as the Karthikeyan (2010) method did not converge for most of the 30 problems and so it was not used in the comparison. Similarly, other methods were not used in the comparison for one reason or another. In all cases, tolerance level for the error was taken as e = 10–7for a method to converge.
CHAPTER FIVE
SUMMARY, CONCLUSION AND RECOMMENDATIONS
Summary
Determining the zeroes of nonlinear function is not always direct. It generally takes the form of constructing one or several sequences {xn } of complex (or pure real) numbers supposed to
converge to a zero of the function. Iterative method developed should give approximations to all roots of a functional equation, Traub (1964). Many iterative methods developed will converge only if the starting value x0 is sufficiently close to a zero of the equation. These are said to be locally convergent. Iterative methods that do not require a sufficiently close starting value are globally convergent. Generally, iterative methods with high order of convergence, converges more rapidly than that with a lower order. In this study, we have developed two new iterative methods which converge locally and whose order of convergence is three. The study is summarised below.
In this study we present two new iterative schemes for solving nonlinear equations of the form
f (x) = 0. We started by discussing on the motivation for the study as well as the actual problem studied. We also discussed aims and objectives of the study. Basic definition and theorems which will be helpful throughout our study were then presented. In the literature we discussed the basic concept of iterative methods regarding roots of nonlinear equations. Various methods which were developed by several researchers such as the Newton-Raphson method and it variants, Adomian approach and some of the iterative methods developed based on the Adomian method, as far back from 1998 to the most recent of 2012 were also presented. Our two new schemes for solving nonlinear equations were then presented. Later 30 different examples of different nature were presented and the two new schemes applied on the examples to determine the number of iterations to reach solutions by the schemes.
Some existing iterative methods namely Adomian method, Abbasbandy, Basto et al. and Newton-Raphson’s method were also applied to solve these examples and record the number of iterations. We then carried out one way analysis of variance test (ANOVA) to make comparison between our schemes and the other iterative methods used.
Conclusion
The number of iterations to get a solution using the two new schemes for the 30 examples is generally accommodating. It was noted that the two new schemes perform equally or better than some of the good existing methods in solving both algebraic and transcendental equations. The results from ANOVA show that there is significant difference between the numbers of iterations obtained for the different methods. The results show that Newton- Raphson method and New scheme 1 have more advantage with a maximum of seven iterations each, while new scheme 2 has nine. Basto et al. and Abbasbany have equal number of thirteen iterations each. The Adomian has sixteen iterations. This shows clearly that the new schemes 1 and 2 perform equally better and as efficiently as the best existing methods.
Recommendations
At the end of this study we come up with the following recommendations:
Further studies with more examples should be carried out to make definite conclusions on the results
As we used the approximation f¢
f ¢ 1, further studies could be carried out using other ratios
f ¢ » c f ¢
(where c is any constant) to obtain other schemes which could be good as well.
- Further studies could be carried out on the two new schemes developed to see whether they could be applied in solving complex
References
- Abbas bandy. S. (2003). Improving Newton–Raphson method for nonlinear equations by modified Adomian decomposition method Applied Mathematics and Computations 145 887–893.
- Abbasbandy. S. (2005). Extended Newtons method for a system of nonlinear equations by modified Adomian decomposition method. Applied Mathematics and Computations 170 648 – 656.
- Adomian, G. (1984). A global method for solutions of complex systems. Math Model, 5, 521-568.
- Adomian. G and Rach. R, (1985), On Solution of Algebraic Equations By the Decomposition Method, Journal of Mathematical Analysis and Applications 105, 141-166
- Adomian, G. (1986). Nonlinear Stochastic Operator Equations, Academic Press, Orlando, Florida.
- Adomian, G. (1988). A review of the Decomposition Method in Applied Mathematics. J. Math. Anal. Appl., 135, 501-544.
- Awawdeh, F (2010) On new iterative method for solving systems of nonlinear equations. Numerical Algorithms 54 (3), 395-409
- Basto. M., Semiao. V., Calheiros, F. L. (2006). A new iterative method to compute nonlinear equations. Applied Mathematics and Computations 173 468 – 483.
- Biazar, J., Babolian, E. and Islam, R. (2004). Solution of the system of ordinary differential equations by Adomian decomposition method. Applied Mathematics and Computations 147 713 –719
- Boyd, S., Xiao, L. and Mutapcic, A. (2003). Notes on Decomposition Methods, Stanford University, Stanford.
- Burden, R. L. and Faires, J. D. (2011). Numerical Analysis, Ninth Edition Brooks/Cole, California.
- Chi, C. and Feng, G. (2008). Few Numerical Methods for Solving Nonlinear Equations International Mathematical Forum, 3 (29), 1437 – 1443.
- Chun, C. (2005). Iterative methods improving Newton’s method by decomposition method. Applied Mathematics and Computations 50 1559 –1568.
- Darvishi, M.T. and Barati, A. (2006). Super cubic iterative methods to solve systems of nonlinear equations, Appl. Math. Comput. 10 1016.
- Feng, J. (2009). A New Two- Step method for Solving Nonlinear Equations, International Journal of Nonlinear Science 8 (1) 40-44.
- Gupta. C. Malik, A. K, Kumar, V, (2009), Advanced Mathematics, New Age International Limited 4835/24, Ansari Road, Daryaganj, New Delhi.
