NUMERICAL METHOD CHAPTE 2- basics of error estimation.pptx

NUMERICAL METHOD CHAPTER 2 Numerical solution of non linear equation

1. Addis Ababa Science and Technology University College of Engineering Environmental Engineering (4 th Year) Course: Numerical Analysis for Environmental Engineering (EnEg-4103) Prerequisite: Math and Programming BY SHELEMA. A 2025

2. Chapter 2 : Numerical solutions for nonlinear and transcendental equations Bisection method Regula-Falsi Method Secant method Newton-Raphson method Fixed point iteration

3. Introduction Numerical solutions for nonlinear and transcendental equations, which cannot be solved algebraically, are found using iterative methods like the Bisection, Newton-Raphson, and Secant methods. These methods begin with an initial estimate or interval and refine it through repeated calculations until the solution converges to a desired level of accuracy. An equation which contains polynomials, trigonometric functions, logarithmic functions, exponential functions etc., is called a Transcendental equation. For example, A transcendental equation may have one root or no root or infinite number of roots depending on the form of f (x).

4. Introduction Direct methods give the exact values of all the roots in a finite number of steps. There are no direct methods for solving higher degree algebraic equations or transcendental equations. Such equations can be solved by Numerical methods. Numerical methods are based on the idea of successive approximations. In these methods, we start with one or two initial approximations to the root and obtain a sequence of approximations x0, x1, … xk which in the limit as k approaches to infinity converge to the exact root x = a.

5. Introduction Most numerical methods use iterative procedures to find an approximate root of an equation 𝑓 ( 𝑥 ) = 0. They require an initial guess of the root as starting value and each subsequent iteration leads closer to the actual root. In these methods, we first find an interval in which the root lies. If a and b are two numbers such that f (a) and f (b) have opposite signs, then a root of f (x) = 0 lies in between a and b. We take a or b or any valve in between a or b as first approximation x1. This is further improved by numerical methods. Here we discuss few important Numerical methods to find a root of f (x) = 0.

6. Numerical solutions for nonlinear and transcendental equations Bisection method Regula-Falsi Method Secant method Newton-Raphson method Fixed point iteration

7. Bisection method The bisection method is a reliable and simple technique for finding the numerical solution (a root) of a nonlinear or transcendental equation by repeatedly narrowing an interval until the desired accuracy is met. Bisection method is a simple iteration method to solve an equation. This method is also known as half-interval method . This is a very simple method. Identify two points x = a and x = b such that f (a) and f (b) are having opposite signs. Let f (a) be negative and f (b) be positive. Then there will be a root of f (x) = 0 in between a and b.

8. Bisection method How it works: Finds an interval ([a,b]) where the function changes sign, meaning a root is within this interval. It repeatedly halves the interval until the desired root is found. It operates on the Intermediate Value Theorem, starting with an interval [a, b] where the function f(x) has opposite signs at the endpoints (f(a) and f(b) have different signs). In each iteration, the interval is bisected by finding the midpoint c = (a + b) / 2, and the interval is then updated to [a, c] or [c, b] depending on the sign of f(c)

9. How it works:

10. EXAMPLE 2. 1 Find a real root of the equation f (x) = x 3 – x – 1 = 0, using Bisection method.

11. EXAMPLE 2.2 . Find a root of the equation x 3 - 5x +1 = 0 using the bisection method in 5 –stages

12. solution cont.

13. solution cont.

14. Example 2.3 class work ( bonus 1 mark) Find a root of the equation x3 - 4x - 9 = 0 using bisection method in four stages

15. solution

16. solution conti

17. Example 2.4 Apply bisection method to find a root of the equation f(x)= xe x- 1 correct to three decimal places .

18. solution cont Hence 0.56715 is the real root correct to three decimal place s

19. Example 2.5 class work bonus 1 mark Using bisection method find an approximate root of the equation f(x ) = xsin 𝑥 − 1 correct to two decimal places.

20. solution

21. solution cont

22. Example 2.6 Home work Apply bisection method to find a root of the equation x 4 + 2x 3 − x−1 = 0

23. solution

24. solution cont

25. False Position Method ( Regula –Falsi Method) Regula Falsi Method, also known as the False Position Method, is a iterative numerical technique used to find the roots of a non-linear or transcendental equation of the form f(x)=0. Based on the concept of bracketing, where two initial gusses, x0 and x1​, are chosen such that the function values at these points have opposite signs, indicating that a root lies between them When compared to other root finding algorithms, it has better convergence than bisection method, but slower convergence than Newton Raphson Method which has quadratic convergence. Where, a and b are the endpoints of the interval [a, b]. f(a) and f(b) are the function values at points a and b. c is the point where the linear interpolation intersects the x-axis.

26. . It is an improved version of the bisection method. An alternative way from halving the distance is to join the points by a straight line. The intersection of this line with the x-axis represents an improved estimate of the root. From the figure, the intersection of the straight line with the x-axis can be estimated as in the formula according to the two symmetrical triangles:

27. False Position Method ( Regula –Falsi Method) In the false position method we will find the root of the equation f (x) = 0 Consider two initial approximate values x0 and x1 near the required root so that f (x0) and f (x1) have different signs. This implies that a root lies between x0 and x1 The curve f (x) crosses x- axis only once at the Point x2 lying between the points x0 an 𝑑 x 1.

28. How this method works

29. Example 2.7 find the root of the fuction using solution

30. Example 2.8 Find the root of f(x) = e x - 4x = 0 using False position method, correct to three decimal places.

31. solution

32. solution continued

33. Newton- Raphson Method:- Newton-Raphson method named after Isaac Newton and Joseph Raphson is a powerful technique for solving equations numerically. The Newton- Raphson method is a powerful and elegant method to find the root of an equation. This method is generally used to improve the results obtained by the previous methods. Methods such as the bisection method and the false position method of finding roots of a nonlinear equation require bracketing of the root by two guesses.

34. Newton- Raphson Method: In the Newton-Raphson method, the root is not bracketed. In fact, only one initial guess of the root is needed to get the iterative process started to find the root of an equation. The method hence falls in the category of open methods. Convergence in open methods is not guaranteed, but it does so much faster than the bracketing methods if the method does converge.

35. . The Newton-Raphson method is based on the principle that if the initial guess of the root of f(x) = 0 is at xi, then if one draws the tangent to the curve at (xi. f(xi), the point xi+1where the tangent crosses the x -axis is an improved estimate of the root (Figure below) One can then use xi+1 as the next point to draw the tangent line to the function f(x) and find out where that tangent line crosses the x-axis. Continuing this process brings us closer and closer to the root of the equation.

36. Steps of Newton- Raphson Method:- step 1 step2 step 3 Evaluate

37. step4

38. Example Use Newton-Raphson method to find a root of the equation x 3 − 5x + 3 = 0 correct to three decimal places. use initial approximation between [0,1] let it xo 0.8

39. solution cont

40. Example Use Newton-Raphson method to find a root of the equation xsin 𝑥 +cos 𝑥 = 0 correct to three decimal places. use pi as xo

41. solution cont

42. Class work Find the real root of the equation:x 3 + 2 𝑥 − 5 = 0, by applying (NRM) for five iterations X0 = 2

43. solution

44. Example home work Iteration 1 The estimate of the root is .

45. solution cont

46. . . Iteration 2 The estimate of the root is

47. The absolute relative approximate error /Er/ at the end of Iteration 2 is . Iteration 3 The estimate of the root is

48. solution continoued

49. The Secant method: A major disadvantage of the Newton-Raphson algorithm requires the evaluation of two functions (the function and its derivative) pereach iteration. The secant method is a slight modification for the Newton-Raphson method. This method (secant method) requires the selection of two initial approximations x0 and x1, which may or may not bracket the desired root, but which are chosen reasonably close to the exact root. n = 1, 2, 3, . . . ,

50. The Secant method: N = 1 , 2 , 3 , . . . ,

51. Examle Finding a root of f(x)=x 3 -5x+1=0

52. solution cont.

53. Example Find a root of an equation f(x)=x 3 -x-1 using Secant method take xo=1 and x1=2 Solution

54. solution cont.

55. solution cont.

56. solution cont.

57. solution cont.

58. Summary in table

59. Class work 2 Find a root of an equation f(x)=2x 3 -2x-5 using Secant method take x0=1 and x1=2 use up to 5th iteration .

60. Fixed- point iteration reading assignment) The fixed-point iteration method is a numerical technique used to find the roots of an equation, f(x)=0, by rearranging it into the form x=g(x). The method starts with an initial guess, x0, and repeatedly applies the function g(x) to get a sequence of approximations, (x n+1=g(xn), until the values converge to a solution. With fixed-point iteration, the equation , is rearranged so that where

61. Fixed- point iteration (reading assignment)

62. home work Consider the nonlinear equation x 3 = 2x + 1 which has a root in the interval [1.5, 2.0] using fixed-point method with x0 = 1.5, take three different rearrangements for the equation.