Development and analysis of new iterative schemes for solving nonlinear equations

Thesis Overview

<p> GENERAL INTRODUCTION<br>1.1 Introduction<br>Solving nonlinear equations is an important part of numerical analysis. In recent years,<br>interests have grown considerably in developing effective iterative methods (IM) for<br>computing solutions for large systems in science and engineering. The development of faster<br>and more robust IM and preconditions which can be efficiently mapped to a variety of<br>problems is of fundamental importance in that it will be of great assistance to scientists and<br>engineers throughout many disciplines. In numerical analysis this approach is in contrast<br>to direct methods which attempt to solve the problem by a finite sequence of operations.<br>Numerical analysis assumes this task, and with it the limitations of practical calculations.<br>Numerical answers are usually tentative and, at best, known to be accurate only to within<br>certain bounds. IM are often useful even for linear problems involving a large number of<br>variables, where direct methods would be prohibitively expensive. Intuitively iterative<br>methods keep on improving upon subsequent iterations. With iteration methods, the<br>operational cost can often be reduced.<br>In this thesis, we study iterative methods for solving nonlinear equations, f x  0, where<br>f x is any continuously differentiable real valued function. The iterative methods we try to<br>develop for this class of equations will require knowledge of initial guess for desired roots of<br>the equation.<br>2<br>Traub (1964), Numerical methods for solving nonlinear equations are divided into two<br>categories; the interval methods and the initial point methods.. Bisection method is an<br>example of interval methods. The initial point methods use one or more initial points as the<br>starting values to find the approximate solution using recurrence relation. In this study, we<br>concentrate mainly on one point initial methods. The major disadvantage of these methods<br>however, is that their convergences are not guaranteed and the choice of initial guess requires<br>some insight. These methods are however, usually faster than the interval methods. Secant<br>method and Newton method are examples of initial point methods. There are several methods<br>for solving nonlinear equations and here we introduce a few of them.<br>Newton or Newton-Raphson method is the most widely used method for finding roots of an<br>equation. According to Traub (1964), it begins with an initial approximation, 0 x and<br>generates a sequence of successive iterates  <br>k k0 x converging quadratically to simple roots.<br>In Secant Method, which is a variant of Newton-Raphson’s method it use finite difference to<br>approximate the derivative of the function y = f (x) close to the root by the line (secant) and<br>requires two initial points   1 1 , n n x f and   n n x , f , where   n n f  f x .Taking the point of<br>intersection of this line with the x-axis as the subsequent iterate. We get<br>, 1,2<br>1<br>1<br>1 <br><br><br><br><br><br> f n<br>f f<br>x x x n<br>n n<br>n n<br>n where xn1 and xn are two consecutive iterates. Since a secant<br>line is defined using two points on the graph of f (x), as opposed to a tangent line that requires<br>information at only one point on the graph, we need two initial approximations 0 x and 1 x .<br>Traub (1964), the method has a super linear convergence.<br>3<br>The Bisection Method tries to decrease the size of the interval in which a solution exist. If<br>the function f xsatisfies     &lt; 0, 0 0 f a f b then the equation starts with one sign at 0 a and<br>ends with the opposite sign at 0 b , and if  0   0  = 0 f a f b , then either 0 a or 0 b or both are roots<br>of f(x) = 0. This method consists of finding midpoint 0 a and 0 b . If   1 2 0 0<br>m  1 a  b is the<br>midpoint of this interval, then the root will lie either in the interval   0 1 a ,m or in the interval<br>  1 0 m ,b provided that   0 1 f m  . If   0 1 f m  , then 1 m is the required root. Repeating this<br>procedure, we obtain the bisection method<br> , 0,1,<br>2<br>1<br>1      m a b a n n n n n .<br>Where     1 , 1  an an mn if f an f mn1  &lt; 0 (1.1)<br>and<br>    bn1 mn1,bn  if f mn 1 f bn  &lt; 0 <br>We take the midpoint of the last interval as an approximation to the root. Traub (1964), if f (x)<br>is continuous in the interval [a, b] which contains the root, the method converges.<br>Hafiz and Bahgat (2012), several iterative methods have been developed to solve nonlinear<br>algebraic equations and the system of nonlinear equations. These methods have been<br>improved using Taylor polynomials, homotopy perturbation method and Adomian<br>decomposition methods.<br>4<br>The homotopy perturbation method (HPM) was developed for solving nonlinear systems, He<br>(1999). HPM linearizes any given problem (converting it to a series of linear equations). The<br>method gives a rapid convergence of the solution and only a few iterations lead to accurate<br>result. In contrast to the traditional perturbation methods, this method does not require a small<br>parameter in an equation. In this method, a homotopy with an imbedding parameter p ∈ [0, 1]<br>is constructed, and the imbedding parameter is considered as a “small parameter”. Li (2009),<br>when p=0, the system of equation usually reduces to a sufficiently simplified form, which<br>normally admits a rather simple solution. As p increases to 1, the system under goes a<br>sequence of deformations, the solution of each is close to that at the previous stage of<br>deformation. When p=1, the system takes the original form of the equation and the final stage<br>of deformation gives the desired solution.<br>Adomian (1984), developed a new method known as the Adomian decomposition method<br>(ADM) for solving functional equations of any kind: ordinary differential equations (ODEs),<br>algebraic, partial differential equations (PDEs), integral equations, etc. The ADM breaks any<br>given problem into linear and nonlinear parts. The linear operator representing the linear<br>portion of the equation is inverted and the inverse operator is then applied to both sides of the<br>equation, before applying the initial or boundary conditions. The term that contains the<br>independent variable alone is taken as the initial approximation. The unknown function is<br>then decomposed into a series whose components are to be determined. The components are<br>determined in terms of polynomials called Adomian polynomials whose successive terms are<br>determined using a recurrent relation.<br>5<br>Traub (1964), classified one-point iterative methods into,<br>(i) One-point methods without memory<br>(ii) One-point methods with memory<br>If the value of the root is ascertained by using new data only at one point and no previous data<br>is used, then it is called one-point iterative method without memory. An example of one-point<br>iterative methods without memory is the Newton-Raphson method. Hence, if n1 x is estimated<br>by new data at n x and no previous data is used, we have   n n x  x 1 , then  is called onepoint<br>iteration function without memory.<br>If the value of the root is ascertained by using new data at one point and by using the previous<br>data at either one or more than one points, then the iterative method is called one-point<br>method with memory. Secant method is an example of one point iterative method with<br>memory. If n1 x is estimated by new data at n x and the previous data at n n m x x   , , 1  , we have<br>  n n n n m x x x x     , , , 1  1  and is called one-point iteration function with memory.<br>1.2 Motivation for this study<br>Many methods and algorithms have been developed to solve problems of nonlinear algebraic<br>equations over the years. Despite these efforts, no single algorithm is capable of solving any<br>and all nonlinear problems. Depending on the system and the degree of nonlinearity, one<br>solution scheme may be preferred over another. To keep up with recent computational<br>challenges in the field of numerical analysis, it is imperative to develop new schemes that are<br>capable of taking advantage of the latest advances in numerical analysis. This is what<br>6<br>motivates us to undertake this study. Advances such as Adomian decomposition method,<br>Basto et al. method.<br>1.3 Problem studied in the thesis<br>In our present work, we have tried to develop two new iterative schemes which are based on<br>Taylor’s series and Adomian method. The first scheme truncates the Taylor’s series after the<br>third term while the second scheme truncates the series after the fourth term. Moreover in<br>both schemes, it is assumed that  <br>  ï‚» 1.<br>ï‚¢<br>ï‚¢<br>f x<br>f x<br>1.4 Aim and objectives<br>The aim of the study is to develop and analyse new iterative schemes for solving nonlinear<br>equations.<br>The objectives of the study are<br>(i) To review iterative schemes between 1998 and 2012 which have been<br>developed from Adomian decomposition method, Homotopy perturbation method<br>and variants of Newton-Raphson’s method for solving nonlinear equations.<br>(ii) To develop new schemes that could compete with previous schemes and<br>probably have further advantages.<br>(iii)To compare the new schemes with the existing known iterative schemes.<br>7<br>1.5 Limitation of the study<br>This work is limited to initial point methods and specifically, only to one point iterative<br>methods. Moreover, for those problems whose second derivatives are far away from the first<br>derivatives, the assumption  <br>  ï‚» 1<br>ï‚¢<br>ï‚¢<br>f x<br>f x is a limitation.<br>1.6 Definitions of term<br>(i) Let n x  x be the truncation error in the nth iterate where x is the required<br>root. If there exists a number p 1 and a constant c  0 such that<br>c<br>x x<br>x x<br>p<br>n<br>n<br>n<br><br><br><br><br><br><br><br>1 lim ,<br>then p is called the order of convergence of the method, Burden and Faires (2011) .<br>Note that;<br>If p 1, we say that   n x is linearly convergent.<br>If p &gt;1, we have super linear convergence.<br>If p  2 , we have quadratic convergence.<br>8<br>1.7 Theorems used in the study<br>We now state the following theorems without proofs, which will be used in this study. The<br>proofs can be found in any standard analysis text book such as Burden and Faires (2011).<br>Theorem 1.7.1: Mean value Theorem<br>If f C[a,b] (whereC[a,b] is the space of continuous functions on[a,b]) and f xis<br>differentiable ina,b, then there exists a point ca,bsuch that f b f a  b  af c.<br>Theorem 1.7.2: Fixed Point Theorem<br>If g C[a,b]and gx[a,b]for all x[a,b],then g has a fixed point in [a,b]. If in addition,<br>gxexists on a,b and a positive constant k &lt; 1exists with gx ï‚£ k , for all xa,b, then<br>the fixed point in [a,b] is unique.<br>Theorem 1.7.3: Rolle’s Theorem<br>Suppose f C[a,b] and f is differentiable on a,b. If f a f b, then a number c in<br>a,b exists with f c  0.<br>Theorem 1.7.4: Extreme Value Theorem<br>Suppose f C[a,b] and , [ , ] 1 2 c c  a b with       1 2 f c ï‚£ f x ï‚£ f c , for all x[a,b]. In<br>addition, if f is differentiable on a,b, then the numbers 1 c and 2 c occur either at the<br>endpoints of [a,b] or where f ï‚¢  0 .<br>9<br>Theorem1.7.5: Taylor’s Theorem<br>Suppose f Cn[a,b], (where Cn[a,b]is the space of n-times continuously differentiable<br>functions on[a,b]) and that f n1 exists on[a,b], with [ , ] 0 x  a b . Then for every x[a,b] ,<br>there exists a number  x between xo and x with<br>            x x  R x<br>n<br>f x f x f x x x f x x x f x n<br>n<br>n<br>    <br>ï‚¢<br>  ï‚¢   0<br>2 0<br>0<br>0<br>0 0 0 2! !<br><br>Where    <br>    1<br>0<br>1<br>1 !<br><br><br><br><br> n<br>n<br>n x x<br>n<br>R x f x<br><br>(called the remainder term or truncation error).<br>1.8 Outline of the thesis<br>The present thesis is structured as follows:<br>Chapter 1, which is the present chapter constitutes the general introduction, the aims and<br>objectives of the study and limitations of the study. It also contains some basic definitions and<br>theorems that are important to the study being done.<br>Chapter 2 is a review of previous work that is related to the work under study.<br>Chapter 3 is a description of the Adomian method and how it is used to develop the two new<br>iterative methods.<br>Chapter 4 contains analysis of numerical results to illustrate the effectiveness of the new<br>methods.<br>Chapter 5 contains summary, conclusion and recommendations. It also contains discussion of<br>potential areas for further work. <br></p>