BSc (Hons) in Software Engineering

FND 210130 - Mathematics III for SE

Numerical Methods

<copyright notice – copyrighted to LNBTI>

ACKNOWLEDGEMENT

Presented by: Ms. Vishmila Kannangara

Reviewed by: Ms. Bhashini Wijewickrama

2
RESOURCES

➢ Course page of the course

➢ References books
• "Numerical Methods for Engineers" by Steven C. Chapra and Raymond P. Canale
• "An Introduction to Numerical Analysis" by Kendall E. Atkinson
• "Applied Numerical Methods with MATLAB for Engineers and Scientists" by Steven C. Chapra
• "Numerical Methods: Design, Analysis, and Computer Implementation of Algorithms" by Anne Greenbaum and
Timothy P. Chartier

➢ Online resources for the section

• [Link]
• [Link]
• [Link]

3
INTENDED LEARNING OUTCOMES (ILO)

By the end of this section, students should be able to:

✓ Understand the principles and applications of numerical
methods.
✓ Solve equations using techniques like bisection, Newton-
Raphson, and numerical integration.
✓ Analyze the accuracy and efficiency of different numerical
methods.
✓ Appreciate the role of numerical methods in real-world
problem-solving.

4
Agenda
• Introduction to Linear & Non-linear Equations.
• Solution of Nonlinear Equations
Bisection method
Newton’s method
• Interpolation Theory
Lagrange Interpolation
Divided Differences
• Numerical Differentiation and Integration
Three-point, five-point formula
Trapezoid Rule
Simpson Method
• Solution of Systems of Linear Equation
Gaussian Elimination method
L-U Factorization method

5
 Linear Equations
Vs
Non – linear Equations

6
Linear Equations Vs Non – linear Equations

7
Examples for Linear Equations

Example

Edges

8
Examples for Non – Linear Equations
Example

Edges

9
Solution of Nonlinear
Equations

10
Introduction
• Nonlinear equations are equations in which the unknown variable
appears with an exponent other than one, or in a non-linear function.
• Solving these equations can be challenging, and numerical methods
provide approximate solutions to these problems.
• In this note, we discuss two fundamental numerical methods for finding
roots of nonlinear equations:

Bisection Method
Newton’s Method
Fixed point iteration Method
Secant Method
Regular - Falsi Method

11
Roots of a Function
• Given any function f(x), find 𝑥 ∗ such that 𝑓(𝑥 ∗ ) = 0.
• The 𝑥 ∗ is called a root of the equation 𝑓(𝑥) = 0.

• Geometrically, a root of the equation is the value of 𝑥 at which

the graph of 𝑦 = 𝑓(𝑥) intersects the x – axis.

12
Intermediate Value Theorem

• If 𝑓(𝑥) is a continuous on a closed interval [𝑎, 𝑏] and

𝑓(𝑎). 𝑓(𝑏) < 0,then there is a value 𝑥 ∗ ∈ [𝑎, 𝑏] such that
𝑓(𝑥 ∗ ) = 0.

13
Example

• Show f(x) = x3 + 4x2-10 = 0 has a root in [1,2].

• Solution:

• 𝑓(1) = −5
• 𝑓(2) = 14
• 𝑓(1). 𝑓(2) < 0
• So, according to the IVT ,this continuous function has a root in
[1,2].

14
Stopping Criteria

15
1. Bisection Method
• The Bisection Method is a simple and robust technique for
finding the roots of a nonlinear equation.
• It is particularly useful when the function is continuous, and you
can find two points where the function changes sign.

16
Example 1

• Find the root of 𝑓(𝑥) = 𝑥 2 − 3 = 0. Use tolerance as 0.01

and start with the interval [1, 2].

17
Solution

• 𝑓(𝑥) = 𝑥 2 − 3 , [1, 2].

• By IVT,
• 𝑓 1 = −2
• 𝑓(2) = 1
• 𝑓 1 . 𝑓 2 = −2.1 = −2
• So, according to the IVT ,this continuous function has a root in
[1,2].

18
Solution
𝑰𝒇 𝒇 𝒂 . 𝒇 𝒄 < 𝟎 𝒕𝒉𝒆𝒏 𝒄𝒉𝒂𝒏𝒈𝒆 𝒃 . 𝒃 = 𝒄
𝑓(𝑥) = 𝑥2 −3 𝑰𝒇 𝒇 𝒂 . 𝒇 𝒄 > 𝟎 𝒕𝒉𝒆𝒏 𝒄𝒉𝒂𝒏𝒈𝒆 𝒂 . 𝒂 = 𝒄

𝒂 𝒃 𝒇(𝒂) 𝒇 (𝒃) 𝒄 = (𝒂 + 𝒃)/𝟐 𝒇(𝒄) 𝒇(𝒂). 𝒇(𝒄) 𝑼𝒑𝒅𝒂𝒕𝒆

1 2 -2 1 1.5 -0.75 >0 𝒂=𝒄

1.5 2.0 -0.75 1 1.75 0.062 <0 𝒃 = 𝒄

1.5 1.75 -0.75 0.625 1.625 -0.359 >0 𝒂=𝒄

1.625 1.75 -0.3594 0.625 1.6875 -0.1523 >0 𝒂=𝒄

1.6875 1.75 -0.1523 0.625 1.7188 -0.0457 >0 𝒂=𝒄

1.7188 1.75 -0.0457 0.625 1.7344 0.0081 <0 𝒃 = 𝒄

|𝑓(1.7344)| = |0.0081| < 0.01. Therefore choose 1.7344 to be the approximation of the root.

19
Example 2

• For the function 𝑓(𝑥) = 10 − 𝑥 2 , find the best approximation

of the root given the tolerance 0.01 with the interval [-2,5].

20
Solution

21
Convergence Analysis

22
Example

• Find the number of iterations of 𝑓(𝑥) with an initial interval of

[−2,5] and a tolerance of 𝜖 = 0.01.

23
Solution

24
Stopping Criteria

• |𝒄𝒏+𝟏 - 𝒄𝒏 | < tolerance

25
Example

• Consider the function, 𝑓(𝑥) = 𝑒 𝑥 - 3𝑥 2 .

(i) Check whether there is a root for this function in the interval
[0,1].
(ii) Find the number of iterations that should be used to obtain the
root given the tolerance 0.01 using bisection method.
(iii) Find the root using bisection method.

26
Solution

𝒇(𝒙) = 𝒆𝒙 - 𝟑𝒙𝟐 @ [0,1]

(i)
• 𝑓(0) = 1
• 𝑓(1) = −0.2817
• 𝐴𝑠 𝑓(0). 𝑓(1) < 0

• According to the 𝑰𝒏𝒕𝒆𝒓𝒎𝒆𝒅𝒊𝒂𝒕𝒆 𝑽𝒂𝒍𝒖𝒆 𝑻𝒉𝒆𝒐𝒓𝒆𝒎, this continuous

function has a root in [0,1].

27
Solution

28
Solution

(iii) 𝑎1 = 0 𝑏1 = 1
𝑐1 = 0.5
• f(𝑐1 ) = 0.898721 > 0.001

• f(𝑎1 ).f(𝑐1 ) = 1 × 0.898721 > 0

• 𝑎2 = 0.5 𝑏2 = 1

29
Solution

|𝒄𝒏+𝟏 - 𝒄𝒏 | < tolerance

| 𝒄𝟕 - 𝒄𝟔 | = |0.91406 – 0.92187|
= 0.00781 < 0.01 (tolerance)

Therefore, the root of the function = 0.91406

30
Example

• Show the real root of the equation 𝑓 (𝑥) = 𝑥 3 − 𝑥 − 1 using

bisection method at the interval [1,2]. The tolerance is 0.01.

31
Solution

𝑓 (𝑥) = 𝑥 𝟑 − 𝑥 − 1
Step 1
𝑓 1 = −1
𝑓(2) = 5
𝐴𝑠 𝑓(1). 𝑓(2) < 0

According to the 𝑰𝒏𝒕𝒆𝒓𝒎𝒆𝒅𝒊𝒂𝒕𝒆 𝑽𝒂𝒍𝒖𝒆 𝑻𝒉𝒆𝒐𝒓𝒆𝒎, this continuous function has a

root in [1,2].

32
Solutions

• Step 2 : Finding the no: if iterations

log 2−1 −log(10−2 )

• n≥
log 2
log 1 +2log(10)
• n≥
log 2
0+2 2
• n≥ = = 6.6445 ≈7
log 2 0.3010

33
Solutions
• Step 3: 𝑓 (𝑥) = 𝑥 𝟑 − 𝑥 − 1
𝒂 𝒃 𝒇(𝒂) 𝒄 𝒇(𝒄) 𝒇(𝒂). 𝒇(𝒄) 𝑼𝒑𝒅𝒂𝒕𝒆

1 2 -1 1.5 0.875 <0 b=c

1 1.5 -1 1.25 -0.2968 >0 a=c

1.25 1.5 -0.2968 1.375 0.2246 <0 b=c

1.25 1.375 -0.2968 1.3125 -0.0515 >0 a=c

1.3125 1.375 -0.0515 1.34375 0.0826 <0 b=c

1.3125 1.34375 -0.0515 1.328125 0.0145 <0 b=c

1.3125 1.328125 -0.0515 1.3203 -0.01876 >0 a=c

|𝒄𝒏+𝟏 - 𝒄𝒏 | < tolerance

| 𝒄𝟕 - 𝒄𝟔 | = |0.3203 – 0.328125|
= 0.007825 < 0.01 (tolerance)

Therefore, the root of the function = 0.3203

34
Homework

• Show that the real root of the function 𝑓(𝑥) = 𝑥 3 − 3𝑥 − 6 lies

between 2 and 3.
• Then find the real root of the function by using bi-section
method where the tolerance is 0.01.

35
Bisection Method

36
2. Newton-Raphson Method (Newton’s Method)

• Newton's method, also known as the Newton-Raphson method, is an

iterative numerical technique used to find approximations to the roots (or
zeros) of a real-valued function.

• It's particularly useful when solving equations that are difficult to solve
analytically.

• This method is same as the method of bi-section.

• But in this method use one side of approximation value which lies aside of
the root.

37
Formula of the Newton’s Method

where:
• 𝑥𝑛 is the current approximation,
• 𝑥𝑛+1 ​ is the next approximation,
• 𝑓′(𝑥𝑛 ) is the derivative of 𝑓(𝑥𝑛 ).
38
Steps to Apply Newton's Method
• Initial Guess: Start with an initial guess 𝑥0 ​.
• Iteration: Apply the iterative formula to get a new approximation:

• Convergence Check: Check if the difference ∣ 𝒙𝒏+𝟏 - 𝒙𝒏 ∣ is

within a desired tolerance level.

▪ If yes, 𝒙𝒏+𝟏 is accepted as the root.

▪ If no, repeat step 2 with the new approximation 𝒙𝒏+𝟏 ​.
39
Example 1

• Find the root of the function 𝑓(𝑥) = 𝑥2 starting with 𝑥0 = 4.

40
Solution

As n → ∞ , 𝑥 n→ 0, Thus, the root of 𝑓(𝑥) = 0​.

41
Example 2

• Suppose we want to find the root of the function 𝑓 𝑥 = 𝑥 2 − 2

starting with 𝑥0 = 1.

42
Solution

43
Example 3

• Find a root to the equation 𝑓(𝑥) = 𝑒 𝑥 − 2𝑥 starting with 𝑥0 = 1.

44
Solution

45
Example 4

• Show that the negative root of the function 𝑓(𝑥) = 𝑥3 − 4𝑥 + 9 lies

between -2 and -3. Then find the negative root of the function by
using Newton Raphson method.

46
Solution

47
Solution

48
Advantages and Limitations

• Advantages:
• Fast convergence if the initial guess is close to the root.
• Simple and easy to implement.

• Limitations:
• Requires the derivative of the function.
• Convergence is not guaranteed; it may diverge if the initial
guess is not close to the root.
• Can fail or give incorrect results if 𝑓′(𝑥) is zero or near zero.

49
Interpolation Theory
Interpolation
• In this session we are going through the method which is determining a
polynomial that the system behavior is given.
• As an example,

Can you predict when 𝒙 = 𝟐𝟓, 𝒚 =? Or 𝐰𝐡𝐞𝐧 𝒙 = 𝟏𝟎𝟎, 𝒚 =?

You cannot answer above question without interpolation. Following are
some interpolation methods,
Lagrange Interpolation
Divided Differences
51
1. Lagrange Interpolation

• We can see how system polynomial can be taken if the data is

given uniformly distributed, but now the problem is we cannot
find always similar distribution for x- coordinate.

• We can use Lagrange interpolation to take the behavior

polynomial for this distribution.

52
The Formula

53
Example 1

• Construct a polynomial having the value given by the table.

54
Solution

55
Example 2

• The rainfall for the town B for the month collected as follows.

• Find the rain fall for the day 10th of the month approximately
in 𝑚𝑙

56
Solution
• Step1: Construct the matrix.

57
Solutions

58
Solution

59
Solutions

60
Example 1

• Use above example for rain fall to find the 20𝑡ℎ day of month.

61
Solution

62
Solution

63
Homework

Try to use Lagrange interpolation.

Find the value of ln 21 and ln 13 by using Lagrange interpolation.

(hint: eliminate the ln sign.)

64
2. Divided Differences
• The divided differences method is a numerical procedure for interpolating a polynomial given a set
of points.
• The divided differences method constructs the interpolating polynomial in Newton form.
• Consider a table of values of x and corresponding values of a function f(x) at those points:

Also assume that Pn(x) is the n𝑡ℎ Lagrangian polynomial that corresponds with the function 𝑓 at these points.
The polynomial Pn(x) can be expressed using the divided differences of the function 𝑓 with respect to the 𝑥-values.

𝑷𝒏(𝒙) = 𝒂𝟎 + 𝒂𝟏(𝒙 − 𝒙𝟎) + 𝒂𝟐(𝒙 − 𝒙𝟎)(𝒙 − 𝒙𝟏) + ⋯ + 𝒂𝒏 (𝒙 − 𝒙𝟎) ⋯ (𝒙 − 𝒙 𝒏 − 𝟏)

𝑷𝒏(𝒙) = 𝒇[𝒙𝟎] + 𝒇[𝒙𝟎, 𝒙𝟏](𝒙 − 𝒙𝟎) + 𝒇[𝒙𝟎, 𝒙𝟏, 𝒙𝟐](𝒙 − 𝒙𝟎)(𝒙 − 𝒙𝟏) + ⋯ + 𝒇[𝒙𝟎, 𝒙𝟏, 𝒙𝟐, ⋯ , 𝒙𝒏](𝒙 − 𝒙𝟎)(𝒙 − 𝒙𝟏) ⋯ (𝒙 − 𝒙 𝒏 − 𝟏)

65
66
Example 1
• Find Solution using Newton's Divided Difference Interpolation
formula.

67
Solution
• Newton's divided difference table is

68
Solution
• The value of x at you want to find the f(x): x=301

Newton's divided difference interpolation formula is

Solution of divided difference interpolation method y(301) = 2.4785

69
Example 2

• Find Solution using Newton's Divided Difference

Interpolation formula.

70
Solution

71
Solution

Solution of divided difference interpolation method 𝑦(2.7) = 0.9941

72
THANK YOU!

73