NUMERICAL ANALYSIS USING SCILAB SOLVING …

1 nonlinear equations page 1/25 NUMERICAL ANALYSIS USING SCILAB : SOLVING nonlinear EQUATIONS In this tutorial we provide a collection of NUMERICAL methods for SOLVING nonlinear equations USING SCILAB . Level This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs Unported License. nonlinear equations page 2/25 Step 1: The purpose of this tutorial The purpose of this SCILAB tutorial is to provide a collection of NUMERICAL methods for finding the zeros of scalar nonlinear functions. The methods that we present are: Bisection; Secant; Newton-Raphson; Fixed point iteration method. These classical methods are typical topics of a NUMERICAL ANALYSIS course at university level. An introduction to NUMERICAL ANALYSIS USING SCILAB SOLVING nonlinear equations Step 2: Roadmap This tutorial is composed of two main parts: the first one (Steps 3-10) contains an introduction about the problem of SOLVING nonlinear equations, presents some solution strategies and introduces properties and issues of such problems and solutions.

2 The second part (Steps 11-23) is dedicated to the specific methods, equipped with many SCILAB examples. Descriptions Steps Introduction and solution strategies 3-6 Conditioning and convergence 7-10 Bisection method 11-12 Secant method 13-14 Newton method 15-18 Fixed point iteration method 19-22 Conclusions and remarks 23-25 nonlinear equations page 3/25 Step 3: Introduction Many problems that arise in different areas of engineering lead to the solution of scalar nonlinear equations of the form ( ) to find a zero of a nonlinear function. nonlinear equations can have none, one, two, or an infinite number of solutions. Some examples are presented on the right. Note: A special class of nonlinear equations is constituted by polynomials of the form ( ).

3 (Linear chirp function ( ( )) with infinite zeros) (Function ( ) ( ) with one zero) The code of the examples is available in the file nonlinear equations page 4/25 Step 4: Solution strategies Many solution methods exist and the correct choice depends on the type of function . For example, different methods are used whether is a polynomial or it is a continuous function whose derivatives are not available. Moreover, the problem can be stated in equivalent formulations. For example, the original formulation ( ) can be converted into a fixed point formulation of the form ( ) or into a minimization problem of the form ( ). It is important to note that even if these formulations are mathematically equivalent (their zeros are the same ones), the NUMERICAL methods used to approximate the solution do not have all the same behavior.

4 Hence, the NUMERICAL solution strategy should take into account the kind of problem we try to solve. Example of equivalent formulations: Original problem: ( ) Examples of fixed point formulation: or ( ) Example of minimization formulation: ( ) nonlinear equations page 5/25 Step 5: Graphical interpretation and separation of zeros The first step of many NUMERICAL methods for SOLVING nonlinear equations is to identify a starting point or an interval where to search a single zero: this is called separation of zeros . If no other information is available, this can be done by evaluating the function at several values and plotting the results ( ). SOLVING the problem ( ) is equivalent to find the solutions of the following system { ( ) , graphically, to determine, in a Cartesian plane, the intersections of the graph of the function ( ) with the -axis.}

5 In the case of fixed point formulation ( ) its graphical formulation is related to the system { ( ) the solutions are given by the intersections of the function ( ) with the bisector . (Separation of zeros of the original problem: ) (Fixed point equivalent formulation: ( )) The code of the example is available in the file nonlinear equations page 6/25 Step 6: Example of a bracketing strategy Bracketing is an automatic strategy for finding intervals containing a zero of a given function . An example of bracketing is given in the following lines of code; the idea is to identify the points in which the function changes sign: function xsol=fintsearch(f, xmin, xmax, neval) // Generate x vector x = linspace(xmin, xmax, neval)'; // Evaluate function y = f(x); // Check for zeros indz = find(abs(y)<=1000*%eps); y(indz) = 0; // Compute signs s = sign(y); // Find where f changes sign inds = find(diff(s)~=0); // Compute intervals xsol = [x(inds),x(inds+1)].}

6 Endfunction The code is also available in the file , while the example can be found in (Separation of zeros for the function ( ) ( )) nonlinear equations page 7/25 Step 7: Conditioning of a zero-finding problem The conditioning of a zero-finding problem is a measure of how it is sensitive to perturbations of the equation. Here we denote by a zero of the function ( ), ( ) . From the first figure on the right we can intuitively see that if the derivative | ( )| is large the problem is well-conditioned. In this case we can clearly identify the zero of , even if there are rounding errors. Conversely, if the derivative is small , the zero-finding problem is said to be ill-conditioned and there is no clear identification of the zero.

7 In this case, if rounding errors are present, the zero is spread up over a large interval of uncertainty. In summary, we can state the following: The conditioning number of the root finding problem is | ( )|; The problem is ill-conditioned if | ( )| is large, | ( )| is small. In the graphic on the right down we can see that the zero of ( ) can not be identified because of ill-conditioning. The code of the example is available in the file (Example of well- and il- conditioned root finding problem) (Given a very ill-conditioned problem, the unique zero cannot be identified) nonlinear equations page 8/25 Estimating the conditioning of the problem of finding a (single) zero of a (continuously differentiable) function ( ) means to provide an estimate of the relative error of a perturbed solution.

8 Finding the zero of a function ( ), ( ) , is equivalent (for continuously differentiable functions) to SOLVING the inverse problem ( ). If we consider a perturbed solution , ( ) or, equivalently, ( ), making an error on its evaluation, we have the following error: ( ) ( ) USING the following Taylor expansion ( ) ( ) ( ( )) ( ) and the elation obtained on the right ( ( )) ( ) the error can be written as ( ) ( ( )) ( ) ( ( )) ( ) Hence, the relative error can be stated as | | | ( )| | | The code of the example on the right is available in the file Original problem: Find such that ( ) ( ) Perturbed problem: Find such that ( ) ( ) Inverse function.

9 (Example of inverse function) The function and its inverse are related from the relation ( ( )) ( ( )) and the derivative of the inverse function satisfies the relation ( ( )) ( ) ( ( )) ( ) (where ( )) nonlinear equations page 9/25 Step 8: Convergence rates of iterative methods Typically, methods for approximating nonlinear equations are based on iterative strategies, starting from an initial guess solution , and computing a sequence of solutions that converge to the desired solution (where ( ) ), We define the rate of convergence of the sequence as | || | | || | for some constant and . is called the asymptotic error constant while is the error at the iteration.

10 If and the convergence is called linear. We require to ensure the convergence of the method indeed the error must be reduced at each iteration as explained by this relation: | | | | ( | |) | | | | Here we compare the n+1-th step error with the initial error. If the convergence is called superlinear. If the convergence is called quadratic. The following figure shows a typical convergence rate profile where we can identify three different regions: an exploration region: in this region there is an exploration of the solution space trying to find an initial guess solution (starting point) where convergence properties are guaranteed, and, moreover, there is no significant reduction of the error; a convergence region: the basin of attraction of the solution; a stagnation region: this last region is due to round-off errors of the floating point system that are unavoidable.