Numerical Analysis Lecture 3 PDF

Numerical Analysis Lecture 3 Chapter 2 Solution of Non-Linear Equations Introduction Bisection Method Regula-Falsi Method Method of iteration Newton - Raphson Method Muller’s Method Graeffe’s Root Squaring Method Definition: The equation f (x) = 0 is called an algebraic, if it is purely a polyno...

Numerical Analysis Lecture 3 Chapter 2 Solution of Non-Linear Equations Introduction Bisection Method Regula-Falsi Method Method of iteration Newton - Raphson Method Muller’s Method Graeffe’s Root Squaring Method Definition: The equation f (x) = 0 is called an algebraic, if it is purely a polynomial in x; it is a transcendental if f (x) contains trigonometric, exponential or logarithmic functions For example, 3 2 x  5 x  6 x  3 0 is an algebraic equation, Whereas M E  e sin E and ax  log( x  3)  e sin x 0 2 x are transcendental equations. To find the solution of an equation f (x) = 0, we find those values of x for which f (x) = 0 is satisfied. Such values of x are called the roots of f (x) = 0. Thus a is a root of an equation f (x) = 0, if and only if, f (a) = 0.  Properties of an algebraic equation Every algebraic equation of n-th degree, where n is a positive integer, has n and only n roots. Complex roots occur in pairs. That is, if (a + ib) is a root of f (x) = 0, then (a – ib) is also a root of this equation. If x = a is a root of f (x) = 0, a polynomial of degree n, then (x – a) is a factor of f (x). On dividing f (x) by (x – a) we obtain a polynomial of degree (n – 1). Descartes rule of signs: The number of positive roots of an algebraic equation f (x) = 0 with real coefficients cannot exceed the number of changes in sign of the coefficients in the polynomial f (x) = 0. Similarly, the number of negative roots of f (x) = 0 cannot exceed the number of changes in the sign of the coefficients of f (-x) = 0. For example, consider an equation 3 2 x  3 x  4 x  5 0 As there are three changes in sign, so, the degree of the equation is three, and hence the given equation will have all the three positive roots. Intermediate value property: If f (x) is a real valued continuous function in the closed interval a  x b If f (a) and f (b) have opposite once; thatis f (x) = 0 has at least one root such that a  b Numerical methods for solving either a transcendental equation or an algebraic equation are classified into two groups: Direct methods, which require no knowledge of the initial approximation of a root of the equation f (x) = 0. Iterative methods, require first approximation to initiate iteration. How to get the first approximation? We can find the approximate value of the root of f (x) = 0 either by graphical method or by an analytical method Graphical method The equation f (x) = 0 can be rewritten as f1(x) = f2(x) and the first approximation to a root of f (x) = 0 can be taken as the abscissa of the point of intersection of the graphs of y = f1(x) and y = f2(x). For example, consider, f ( x )  x  sin x  1 0 It can be written as x – 1 = sin x. Now, we shall draw the graphs of y =(x -1) and y = sin x  Answer ! The approximate value of the root is found to be 1.9 Analytical method This method is based on ‘intermediate value property’. f ( x) 3 x  1  sin x 0 f (0)  1  180  f (1) 3  1  sin  1  3  1  0.84147 1.64299    Here f (0) and f (1) are of opposite signs. Therefore, using intermediate value property we infer that there is at least one root between x = 0 and x = 1. This method is often used to find the first approximation to a root of either transcendental equation or algebraic equation. Hence, in analytical method, we must always start with an initial interval (a, b), so that f (a) and f (b) have opposite signs. Bisection Method (Bolzano) Suppose, we wish to locate the root of an equation f (x) = 0 in an interval, say (x0, x1). Let f (x0) and f (x1) are of opposite signs, such that f (x0) f (x1) < 0. Then the graph of the function crosses the x-axis between x0 and x1, which guarantees the existence of at least one root in the interval (x0, x1). The desired root is approximately defined by the midpoint x0  x1 x2  2 If f (x2) = 0, then x2 is the desired root of f (x) = 0. However, if f (x2) 0 then the root may be between x0 and x2 or x2 and x1. Now, we define the next approximation by x0  x2 x3  2 provided f (x0) f (x2) < 0, then the root may be found between x0 and x2 or by x1  x2 x3  2 provided f (x1) f (x2) < 0, then the root lies between x1 and x2 etc. Thus, at each step, we either find the desired root to the required accuracy or narrow the range to half the previous interval. This process of halving the intervals is continued to determine a smaller and smaller interval within which the desired root lies. Continuation of this process eventually gives us the desired root. Example Solve x – 9x + 1 = 0 3 for the root between x = 2 and x = 4 by the bisection method. Solution Given f (x) = x3 – 9x + 1. Here f (2) = -9, f (4) = 29. Therefore, f (2) f (4) < 0 and hence the root lies between 2 and 4. Let x0 = 2, x1 = 4. Now, we define x0  x1 2  4 x2   3 2 2 as a first approximation to a root of f (x) = 0 and note that f (3) = 1, so that f (2) f (3) < 0. Thus the root lies between 2 and 3 We further define, x0  x2 2  3 x3   2.5 2 2 and note that f (x3) = f (2.5) < 0, so that f (2.5) f (3) < 0. Therefore, we define the mid-point, x3  x2 2.5  3 x4   2.75, etc. 2 2 Similarly, x5 = 2. 875 and x6 = 2.9375 and the process can be continued until the root is obtained to the desired accuracy. These results are presented in the table. n xn f ( xn ) 2 3 1.0 3 2.5 -5.875 4 2.75 -2.9531 5 2.875 -1.1113 6 2.9375 -0.0901 Numerical Analysis Lecture 3