Root Finding Methods

Root finding methods are essential numerical techniques used to find solutions (roots) of
equations of the form 𝑓(𝑥) = 0. These methods are particularly important in engineering,
physics, and applied mathematics, where many problems can be modeled as equations needing
solutions.

Algebracic and Transcedental Equations

 𝑓(𝑥) = 0 is called an algebraic equation if the corresponding 𝑓(𝑥) is a polynomial

An example is 7𝑥 2 + 𝑥 − 8 = 0

 𝑓(𝑥) = 0 is called transcendental equation if the corresponding 𝑓(𝑥) contains

trigonometric, or exponential or logarithmic functions.

Examples of transcendental equations are

𝑠𝑖𝑛𝑥 − 𝑥 = 0, 𝑡𝑎𝑛𝑥 − 𝑥 = 0 𝑎𝑛𝑑 7𝑥 3 + log(3𝑥 − 6) + 3𝑒 𝑥 𝑐𝑜𝑠𝑥 + 𝑡𝑎𝑛𝑥 = 0

 Graphical methods are intuitive approaches to finding roots of equations where the
function intersects the x-axis. These methods involve plotting the function and visually
identifying the points where it crosses the x-axis, indicating the roots.

Key Features of Graphical Methods

1. Visual Representation: Graphical methods provide a clear visual insight into the
behavior of a function, making it easier to identify roots and understand how the function
behaves over an interval.
2. Easy to Use: These methods are straightforward and do not require complex calculations,
making them accessible for preliminary analysis.
3. Estimation of Roots: While graphical methods can help estimate the location of roots,
they typically do not provide precise values. Further numerical methods may be required
for accuracy.

Steps for Graphical Root Finding

1. Define the Function: Start with a function 𝑓(𝑥) whose roots you want to find.
2. Choose an Interval: Determine a suitable interval [𝑎, 𝑏] within which to search for roots.
This interval should ideally contain at least one root.
3. Plot the Function: Create a graph of the function 𝑓(𝑥) over the selected interval. This
can be done using graphing software, calculators, or manually.
4. Identify Intersections: Look for points where the graph intersects the x-axis. Each
intersection point corresponds to a root of the equation 𝑓(𝑥) = 0.
 5. Refine Estimates: If necessary, refine the estimates of the roots by zooming in on the
intersection points or by using numerical methods like the Bisection Method or Newton-
Raphson for greater precision.

Example of Graphical Root Finding

Function: 𝑓(𝑥) = 𝑥 2 − 4

1. Define the Function: We want to find the roots of 𝑓(𝑥) = 𝑥 2 − 4.

2. Choose an Interval: We can choose the interval [−3,3].
3. Plot the Function: The graph of 𝑓(𝑥) is a parabola opening upwards with its vertex at
the origin.
o Plot Points:
 𝑓(−3) = (−3)2 − 4 = 5
 𝑓(−2) = 0
 𝑓(−1) = −3
 𝑓(0) = −4
 𝑓(1) = −3
 𝑓(2) = 0
 𝑓(3) = 32 − 4 = 5
4. Identify Intersections: From the graph, we see that 𝑓(𝑥) intersects the x-axis at 𝑥 = −2
and 𝑥 = 2, indicating that these are the roots of the equation.
5. Refine Estimates: To confirm and refine these roots, numerical methods can be applied
in the vicinity of the estimated roots. For example, using the Bisection Method between
−2 and −1.5 could provide a more accurate value for the root at 𝑥 = −2.

Advantages of Graphical Methods

 Intuitive Understanding: Visualizing the function helps in understanding the nature of

the roots.
 Identifying Multiple Roots: Graphs can reveal the presence of multiple roots or complex
behavior in a function.
 Error Checking: Graphical methods can help validate the results obtained from
numerical methods.

Disadvantages of Graphical Methods

 Lack of Precision: Graphical methods provide only approximate values; numerical

methods are needed for accuracy.
 Limited to Simple Functions: Complex functions may be difficult to analyze visually,
and intersections may not be clear.

Conclusion

Graphical methods are a valuable tool for root finding, offering an intuitive way to visualize and
estimate the roots of equations. While they are not a substitute for precise numerical methods,
they serve as an excellent preliminary approach to understanding the behavior of functions and
identifying potential roots before applying more rigorous techniques.

Bracketing Methods and Initial Guesses

Importance of Initial Guesses

Initial guesses are crucial in bracketing methods as they determine the starting interval for the
search for roots. Here are key aspects:

 Identifying Intervals: A good initial guess should ideally capture a sign change in the
function, ensuring that a root exists between the two points.
 Convergence Speed: The choice of interval can affect the convergence speed of the
method. Poor initial guesses may lead to slow convergence or fail to find a root.
 Multiple Roots: If a function has multiple roots, the initial guess can determine which
root is found. A careful selection of intervals based on the function's behavior can help
isolate desired roots.

Conclusion

Bracketing methods, including the Bisection Method and the False Position Method, are
effective techniques for finding roots of continuous functions. The choice of initial guesses
significantly impacts the efficiency and success of these methods. Understanding how to select
appropriate intervals can lead to faster convergence and more accurate solutions in numerical
analysis. These methods are widely used in engineering, physics, and mathematics for solving
real-world problems.

Here’s an overview of the fundamental root finding methods.

1. Bisection Method

Overview

The bisection method is a simple and robust technique that works by repeatedly dividing an
interval in half.

Process

 Identify two points 𝑎 and 𝑏 such that 𝑓(𝑎) and 𝑓(𝑏) have opposite signs (i.e., 𝑓(𝑎) ×
𝑓(𝑏) < 0).
 Compute the midpoint = 𝑎 + 𝑏/2.
 Determine the sign of 𝑓(𝑐) :

o If 𝑓(𝑐) = 0, 𝑐 is the root.

o If 𝑓(𝑎) and 𝑓(𝑐) have opposite signs, set 𝑏 = 𝑐.
o Otherwise, set 𝑎 = 𝑐.
  Repeat until the desired accuracy is achieved.

Pros and Cons

 Pros: Guaranteed to converge if the initial interval is chosen correctly; simple to implement.
 Cons: Slower convergence compared to other methods (linear convergence).

False Position Method

Definition

The False Position Method, also known as the Regula Falsi Method, is a numerical technique for
finding roots of a continuous function. It is similar to the Bisection Method but uses a linear
interpolation to find a better approximation of the root. The method iteratively narrows down the
interval that contains the root by replacing one of the endpoints with a point where the function
crosses the x-axis.

Characteristics

 Convergence: The method generally converges faster than the Bisection Method,
especially when the function is nonlinear.
 Robustness: It can handle a wider variety of functions effectively, but it may still stall if
the root is very close to one of the endpoints.
 Simplicity: The method is straightforward to implement and understand.

Steps of the False Position Method

1. Choose two initial points 𝑎 and 𝑏 such that 𝑓(𝑎) and 𝑓(𝑏) have opposite signs.
2. Calculate the point ccc where the line connecting (𝑎, 𝑓(𝑎)) and (𝑏, 𝑓(𝑏)) crosses the x-
axis:

𝑓(𝑏) ⋅ (𝑎 − 𝑏)
𝑐=𝑏−
𝑓(𝑎) − 𝑓(𝑏)

3. Evaluate 𝑓(𝑐) :
o If 𝑓(𝑐) = 0, then 𝑐 is the root.
o If 𝑓(𝑎) ⋅ 𝑓(𝑐) < 0, set 𝑏 = 𝑐.
o If 𝑓(𝑐) ⋅ 𝑓(𝑏) < 0, set 𝑎 = 𝑐.
4. Repeat until the desired accuracy is achieved.

Example: Use the false position method find approximate solutions of

𝑥 3 + 𝑥 − 1 = 0 on [0, 1] accurate 10−2 ?

 The bisection and regula-falsi method is developed based on the principle, the
intermediate value theorem for continuous functions
Open Methods in Root Finding

Definition

Open methods are numerical techniques used to find roots of equations, relying on iterative
procedures that do not require the bracketing of the root. Unlike closed methods (e.g., Bisection
Method), open methods do not necessarily start with two points that enclose a root. Instead, they
use one or more initial approximations and iteratively refine these guesses.

Characteristics

 Fewer Initial Points: Open methods typically require only one (or sometimes two) initial
guesses.
 Faster Convergence: Many open methods can converge more quickly than closed
methods, especially near the root.
 Dependence on Function Behavior: The success and speed of convergence can be
heavily influenced by the function's characteristics and the choice of initial guesses.

Common Open Methods

1. Newton-Raphson Method
o Description: This method is an iterative technique that uses the function and its
derivative (tangents) to find successively better approximations of the root. The
formula for updating the approximation is:

𝑓(𝑥 )
𝑥𝑛+1 = 𝑥𝑛 − 𝑓′(𝑥𝑛 ) , 𝑛 = 0,1,2 , … , 𝑚𝑎𝑥. 𝑖𝑡𝑒
𝑛

 Repeat until |𝑥𝑛+1 − 𝑥𝑛 | is less than a specified tolerance (𝜀).

o Convergence: Quadratic convergence near the root, but can diverge if the initial guess is
not close enough to the root or if 𝑓′ is zero.

Example: Consider the function:

𝑓(𝑥) = 𝑥 3 − 2𝑥 − 5 lead to divergence

Choose an Initial Guess, let’s start with 𝑥0 = 3 (lead to a series of oscillations or slow
convergence) & 𝑥0 = 1 (lead to increasingly larger values, moving away from the root.)

2. Secant Method
o Description: This method approximates the derivative using two initial points and
uses the formula:

𝑓(𝑥𝑛 )(𝑥𝑛 −𝑥𝑛−1 )

𝑥𝑛+1 = 𝑥𝑛 − ,𝑛 = 1, 2 , … 𝑚𝑎𝑥. 𝑖𝑡𝑒
𝑓(𝑥𝑛 )−𝑓(𝑥𝑛−1 )

 Repeat until convergence

 oConvergence: Superlinear convergence, but it requires two initial guesses and
may not converge if the initial points are poorly chosen.
3. Fixed-Point Iteration
o Description: This method (where the equation 𝑓(𝑥) = 0 is arranged ) rearranges the
root-finding problem (𝑓(𝑥) = 0) into the form

𝑥 = 𝑔(𝑥) and iterates using:

𝑥𝑛+1 = 𝑔(𝑥𝑛 ) or 𝑥𝑛 = 𝑔(𝑥𝑛−1 ) 𝑛 = 1, 2, 3, … , 𝑚𝑎𝑥. 𝑖𝑡𝑒

 Repeat until convergence

o Convergence: Convergence depends on the choice of 𝑔(𝑥) and the initial guess;
may converge slowly or diverge.

Advantages of Open Methods

 Efficiency: Often converge faster than closed methods, especially for well-behaved
functions.
 Simplicity: Some methods, like fixed-point iteration, can be easier to implement.
 Flexibility: Can be applied to a wide range of functions without the need for bracketing.

Limitations

 Divergence Risk: Open methods can diverge if the initial guess is far from the root or if
the function behaves poorly.
 No Guarantee of Root: Unlike closed methods, there is no assurance that a root will be
found.
 Requires Derivative Information: The Newton-Raphson method requires the
derivative, which may not always be easy to compute.

Applications

 Engineering and Physics: Used for solving nonlinear equations in various engineering
problems.
 Computer Science: Applied in algorithms for optimization and machine learning.
 Finance: Often employed in models that require root-finding for equations related to
interest rates, pricing, etc.

Conclusion

Open methods for root finding are powerful numerical techniques that leverage iterative
processes to refine approximations of roots. Methods such as Newton-Raphson and Secant
provide rapid convergence under suitable conditions, making them widely useful in scientific
and engineering applications. However, careful selection of initial guesses and consideration of
the function's behavior are essential to ensure success.
Brent’s Method

Brent’s Method is

 a powerful root-finding algorithm that combines the robustness of bracketing methods

(like the Bisection Method) with the speed of open methods (like the Secant Method). It
is particularly effective for finding roots of functions that are continuous and
differentiable. or
 a highly effective and versatile root-finding algorithm that combines the strengths of both
bracketing and open methods. Its guaranteed convergence and adaptability make it a preferred
choice for many numerical analysis applications, especially when dealing with continuous
functions. Understanding and applying Brent’s Method can lead to efficient solutions in
engineering, physics, and mathematical modeling. Brent’s Method is widely used due to its
efficiency and reliability.

Roots of Polynomials

Definition

The roots of a polynomial are the values of the variable (typically 𝑥) that satisfy the equation
𝑃(𝑥) = 0, where P(x) is a polynomial function. These roots can be real or complex numbers, and
they play a crucial role in various fields of mathematics, science, and engineering.

General Form of a Polynomial

A polynomial of degree 𝑛 can be expressed in the standard form as:

𝑃(𝑥) = 𝑎𝑛 𝑥 𝑛 + 𝑎𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎1 𝑥 + 𝑎0

where:

 𝑎𝑛 , 𝑎𝑛−1 , … , 𝑎1 , 𝑎0 are coefficients (with 𝑎𝑛 ≠ 0),

 𝑛 is a non-negative integer (the degree of the polynomial),
 𝑥 is the variable.

Types of Roots

1. Real Roots: These are the points where the polynomial intersects the x-axis. A
polynomial of degree 𝑛 can have up to 𝑛 real roots.
2. Complex Roots: These occur in conjugate pairs when the coefficients of the polynomial
are real. For example, if 𝑎 + 𝑏𝑖 is a root, then 𝑎 − 𝑏𝑖 must also be a root.
3. Multiple Roots: A root is considered multiple if it satisfies the polynomial equation more
than once. For instance, in (𝑥 − 2)2 = 0, the root 𝑥 = 2 has a multiplicity of 2.

Finding Roots of Polynomials

Analytical Methods

1. Factoring: For lower degree polynomials (especially quadratics), roots can often be
found by factoring.
o Example: 𝑥 2 − 5𝑥 + 6 = 0 can be factored as (𝑥 − 2)(𝑥 − 3) = 0, giving roots
𝑥 = 2 and 𝑥 = 3.
2. Quadratic Formula: For a quadratic polynomial 𝑎𝑥 2 + 𝑏𝑥 + 𝑐 = 0, the roots can be
−𝑏±√𝑏 2 −4𝑎𝑐
found using: 𝑥 = 2𝑎
3. Synthetic Division: This method is used to divide polynomials and can help in finding
roots by simplifying higher-degree polynomials.

Numerical Methods

When analytical methods are not feasible, numerical methods are employed to approximate
roots, especially for higher-degree polynomials.

1. Newton-Raphson Method: An iterative method that uses derivatives to converge to a

root.
2. Bisection Method: A bracketing method that repeatedly bisects an interval to narrow
down the root.
3. Müller’s Method: A root-finding algorithm that generalizes the secant method to find
roots of polynomials.
4. Bairstow's Method: Specifically designed for finding both real and complex roots of
polynomials.

Applications of Polynomial Roots

 Engineering: Roots are used in stability analysis, control theory, and signal processing.
 Physics: Roots appear in solving equations of motion, energy levels in quantum
mechanics, and wave equations.
 Economics: Used in modeling and optimization problems, especially in regression
analysis.
 Computer Science: Algorithms for polynomial root-finding are used in graphics, data
fitting, and computational geometry.

Special Cases

 Cubic and Quartic Equations: There are specific formulas for finding roots of cubic
and quartic polynomials, although they are more complex than the quadratic formula.
 Fundamental Theorem of Algebra: States that every non-constant polynomial has at
least one complex root. This implies that a polynomial of degree nnn has exactly nnn
roots (counting multiplicity and considering complex roots).

Conclusion
The roots of polynomials are fundamental to understanding and solving polynomial equations.
They have significant implications across various scientific and mathematical disciplines, and
methods for finding these roots range from analytical to numerical approaches, depending on the
complexity of the polynomial.

Chapter 3

Linear Algebraic Equations (Numerical solution for System of Linear Equations)

Definition

A linear algebraic equation is an equation of the form: 𝐴𝑥 = 𝑏

where:

 𝐴 is a matrix (coefficients),
 𝑥 is a vector of variables,
 𝑏 is a vector of constants.

The goal is to find the vector 𝑥 that satisfies this equation.

Categories of Methods for Solving Linear Algebraic Equations

Linear algebraic equations can be solved using two primary categories of methods:

Direct Methods and Iterative Methods.

1. Direct Methods

Direct methods provide an exact solution in a finite number of steps. They are generally
preferred when the problem size is manageable, and precision is critical.

Common direct methods include:

a. Gaussian Elimination

 Description: This method transforms the matrix 𝐴 into an upper triangular form using
row operations. Once in this form, back substitution is used to find the solution vector 𝑥.
 Steps:
1. Eliminate variables to form an upper triangular matrix.
2. Use back substitution to solve for the variables.

b. LU Decomposition
  Description: This method decomposes the matrix 𝐴 into a product of a lower triangular
matrix 𝐿 and an upper triangular matrix 𝑈. This allows for easier solving of multiple
equations with the same coefficient matrix.
 Steps:
1. Decompose 𝐴 into 𝐿𝑈.
2. Solve 𝐿𝑦 = 𝑏 for 𝑦. Provided that 𝑦 is column vector
3. Solve 𝑈𝑥 = 𝑦 for 𝑥.

 Use : 𝑢𝑖𝑖 = 1 ( Court method) and 𝑙𝑖𝑖 = 1 ( Doolittle method)

Example: The currents I1, I2, and I3 occurring in a closed circuit having three mesh
points is given by:

−I1 + 3I2 = 5
3I1 + I2 + 2I3 = 3
−11I2 − 7I3 = −15

Use the LU decomposition method to determine the currents I1, I2, and I3

Solution: To solve the system of equations using the 𝐿𝑈 decomposition method, we first need to
express the system in matrix form 𝐴𝑋 = 𝐵, where:

Step 1: Write the System in Matrix Form

The given equations are:

1. −I1+3I2+0I3=5
2. 3I1+I2+2I3=3
3. 0I1−11I2−7I3=−15

−1 3 0 𝐼1 5
We can express this as: 𝐴 = ( 3 1 𝐼
2 ) 𝑋 = ( 2) 𝐵 = ( 3 )
0 −11 −7 𝐼3 −15

Step 2: LU Decomposition

We need to decompose the matrix 𝐴 into lower triangular matrix 𝐿 and upper triangular matrix
𝑈.

Let's perform the 𝐿𝑈 decomposition step-by-step.

1. Start with 𝑈 = 𝐴 and 𝐿 = 𝐼 (identity matrix).

−1 3 0 1 0 0
𝑈=( 3 1 2 ) 𝐿 = (0 1 0)
0 −11 −7 0 0 1
 2. Eliminate the first column below the pivot in 𝑈.

 For row 2: 𝑳𝟐𝟏 = 𝟑/−1 = −3

 Update row 2 of 𝑈:

𝑼𝟐𝟏 = 𝑼𝟐𝟏 − 𝑳𝟐𝟏 ⋅ 𝑼𝟏𝟏 ⇒ 𝑼𝟐 = (𝟑 𝟏 𝟐) + 𝟑 ⋅ (−𝟏 𝟑 𝟎) = (0 10 2)

 For row 3: 𝐿31 = 0 (no change needed).

Now, 𝐿 and 𝑈 look like this:

1 0 0 −1 3 0
𝐿 = (−3 1 0) 𝑈 = ( 0 10 2)
0 0 1 0 −11 −7

3. Now eliminate the second column below the pivot in 𝑈:

 For row 3: 𝑳𝟑𝟐 = −𝟏𝟏/10 = −1.1

 Update row 3 of 𝑈:

𝑼𝟑𝟐 = 𝑼𝟑𝟐 − 𝑳𝟑𝟐 ⋅ 𝑼𝟐𝟐 ⇒ 𝑼𝟑 = (𝟎 − 𝟏𝟏 − 𝟕) + 𝟏. 𝟏 ⋅ (𝟎 𝟏𝟎 𝟐) = (𝟎 𝟎 − 𝟓. 𝟖)

1 0 0 −1 3 0
Now the matrices are: 𝐿 = (−3 1 0) 𝑈 = ( 0 10 2 )
0 −11 1 0 0 −5.8

Step 3: Solve for 𝒀 in 𝑳𝒀 = 𝑩

Now we can solve the equation 𝐿𝑌 = 𝐵:

1. 𝑌1 = 5
2. −3𝑌1 + 𝑌2 = 3 → 𝑌2 = 3 + 3𝑥5 = 18
3. −1.1𝑌2 + 𝑌3 = −15 → 𝒀𝟑 = −𝟏𝟓 + 𝟏. 𝟏 ⋅ 𝟏𝟖 = −15 + 19.8 = 4.8

5
Thus, 𝑌 = ( 18 )
4.8

Step 4: Solve for 𝑿 in 𝑼𝑿 = 𝒀

Now we solve 𝑈𝑋 = 𝑌:

1. From the third equation: −5.8𝐼3 = 4.8 → 𝑰𝟑 = 𝟒. 𝟖/−5.8 ≈ −0.8276

2. From the second equation: 10𝐼2 + 2𝐼3 = 18 →

𝑰𝟐 = (𝟏𝟖 − 𝟐𝑰𝟑)/𝟏𝟎 = (𝟏8 − 2(−0.8276))/10 ≈ 19.6552/10 ≈ 1.9655

 3. From the first equation: −𝑰𝟏 + 𝟑𝑰𝟐 = 𝟓 → 𝑰𝟏 = 𝟑𝑰𝟐 − 𝟓 ≈ 𝟑(1.9655) − 5 ≈
5.8965 − 5 ≈ 0.8965

Final Values

Thus, the currents are approximately:

 I1≈0.897
 I2≈1.966
 I3≈−0.828

Conclusion

The currents in the circuit are:

 I1≈0.897
 I2≈1.966
 I3≈−0.828

d. Matrix Inversion

 Description: If 𝐴 is invertible, the solution can be found directly using the inverse of 𝐴:
𝑥 = 𝐴−1 𝑏
 Caveat: This method is computationally expensive and not recommended for large
systems due to numerical stability concerns.

2. Iterative Methods

Iterative methods are used when direct methods are impractical, particularly for large or sparse
systems. These methods provide an approximate solution and refine it iteratively.

Common iterative methods include:

a. Jacobi Method

 Description: This method updates each variable using the most recent values from the
previous iteration. It is particularly suitable for diagonal-dominant matrices.

−𝑎11 𝐼1 + 𝑎12 𝐼2 + 𝑎13 𝐼3 = 𝑏1

𝑎12 𝐼1 + 𝑎22 𝐼2 + 𝑎23 𝐼3 = 𝑏2
−𝑎31 𝐼1 + 𝑎32 𝐼2 − 𝑎33 𝐼3 = 𝑏3
  Steps:
1. Rearrange the equations to isolate one variable.

𝑏1 − (𝑎12 𝐼2 + 𝑎13 𝐼3 )
𝐼1 =
−𝑎11
𝑏2 − (𝑎12 𝐼1 + 𝑎23 𝐼3 )
𝐼2 =
𝑎22
𝑏3 − (−𝑎31 𝐼1 + 𝑎32 𝐼2 )
𝐼3 =
− 𝑎33

Initial guess 𝐼1 = 𝐼2 = 𝐼3 = 0

2. Iterate until convergence: 𝑘 = 0, 1, 2, … . 𝑖 = 0, 1, 2, … . 𝑗 = 0, 1, 2, …

1
𝐼𝑖 (𝑘+1) = (𝑏𝑖 − ∑ 𝑎𝑖𝑗 𝐼𝑗 (𝑘) )
𝑎𝑖𝑖
𝑗≠𝑖

b. Gauss-Seidel Method ( Modification of the Jacobi method)

 Description: Similar to the Jacobi method, but it uses the latest updated values
immediately. This often leads to faster convergence.
 Steps:
1. Update each variable in the sequence as soon as it is calculated:

1
𝑥𝑖 (𝑘+1) = (𝑏 − ∑ 𝑎𝑖𝑗 𝑥𝑗 (𝑘+1) − ∑ 𝑎𝑖𝑗 𝑥𝑗 (𝑘) )
𝑎𝑖𝑖 𝑖
𝑗<𝑖 𝑗>𝑖

The choice between direct and iterative methods for solving linear algebraic equations depends
on factors such as the size of the system, the properties of the matrix, and the desired level of
precision.

 Direct Methods are suitable for smaller systems and provide exact solutions but may not
be practical for larger systems due to computational intensity.
 Iterative Methods are often more efficient for large or sparse systems but require careful
consideration of convergence criteria and initial guesses.

Understanding both categories allows for a more informed approach to solving linear algebraic
equations in various applications across mathematics, engineering, and the sciences.

Example. Use Gauss Jacobi and Seidel method , to solve the system
−𝐼1 + 3𝐼2 = 5
3𝐼1 + 𝐼2 + 2𝐼3 = 3
−11𝐼2 − 7𝐼3 = −15
 Solution. Step1: for 𝐼1 = 𝐼2 = 𝐼3 = 0
𝑏1 − (𝑎12 𝐼2 + 𝑎13 𝐼3 ) 5 − 3𝐼2
𝐼1 = = = −5
−𝑎11 −1
𝑏2 − (𝑎12 𝐼1 + 𝑎23 𝐼3 ) 3 − 3𝐼1 − 2𝐼3
𝐼2 = = = 3
𝑎22 1
𝑏3 − (−𝑎31 𝐼1 + 𝑎32 𝐼2 ) −15 + 11𝐼2
𝐼3 = = = 2.14
− 𝑎33 −7

Step2.: for 𝐼1 = −5, 𝐼2 = 3 , 𝐼3 = 2.14

5 − 3(3)
𝐼1 = =4
−1
3 − 3(−5) − 2(2.14)
𝐼2 = = 13.72
1
−15 + 11(3)
𝐼3 = = −2.57
−7

Sept3: for 𝐼1 = 4, 𝐼2 = 13.72, 𝐼3 = −2.57

5 − 3(13.72)
𝐼1 = =
−1
3 − 3(4) − 2(−2.57)
𝐼2 = =
1
−15 + 11(1372)
𝐼3 = =
−7

Chapter 4
Interpolation & Curve Fitting
In this chapter we are concerned with the problem of fitting an equation or a curve to data involving
paired values.
 An approximate non-mathematical relationship between the two variables, can be
established by a diagram called scatter diagram.
 The exact mathematical relationship between the two variables is given by simple algebraic
expression called curve fitting.
 Though there are infinite variety of curves in mathematics, the curves used for the purpose of curve
fitting are relatively limited in type.
The straight line is the simplest and one of the most important curves used.
THE STRAIGHT LINE
The equation 𝑦 = 𝑎 + 𝑏𝑥 − − − − (1) is an equation of the first degree in 𝑥 and 𝑦.
It represents a straight line.
The difference 𝑦𝑖 – (𝑎 + 𝑏𝑥𝑖 ) − − − − −(2) is zero if and only if the point (𝑥𝑖 , 𝑦𝑖 ) lies on the line
given by (1).
Usually fitting a straight line means finding the values of the parameters 𝑎 and 𝑏 of the straight line
given by (1), as well as actually constructing the line itself.
 The Graphic methods and the Method of least squares are two useful methods for fitting a
straight line.
The Graphical Method
This method can be used whenever the given formula can be plotted as a straight line either directly
or after suitable transformation.
The straight line drawn after a careful visual estimate of its position has been made with the aid of a ruler.
The co-ordinates of any two points on the line, not too near together are then measures and substituted in
equation (1). The resulting equations in 𝑎 and 𝑏 are then solved for their parameters. Graphical method,
whatever its theoretical attractions, suffers from the disadvantage that it is difficult to apply in practice
except for the straight line. This method will give fairly good results when finely divided co-ordinate
paper is used, but in general it is not recommended.

Least Squares Regression

Least Squares Regression is a statistical method used to determine the best-fitting line through a
set of data points. It minimizes the sum of the squares of the vertical distances (residuals)
between the observed values and the values predicted by the linear model.

The method of least squares assumes that the best fitting line in the curve for which the sum of
the squares of the vertical distances of the points (𝑥𝑖 , 𝑦𝑖 ) from the line is minimum.

Key Concepts

 Dependent Variable (𝒀): The outcome or response variable you want to predict.
 Independent Variable (𝑿): The predictor variable used to make predictions about 𝑌.
 Residuals: The differences between the observed values and the predicted values.
 Best-Fit Line: The line that minimizes the sum of the squares of the residuals.
The Least Squares Criterion

The formula for the least squares criterion can be expressed as:

̂𝑖 )2
Minimize 𝑆 = ∑(𝑌𝑖 − 𝑌

where:

 𝑌𝑖 is the observed value.

 ̂𝑖 is the predicted value from the regression line.
𝑌

The best fitting line is that line for which the sum of the squares, 𝑆 is a minimum. We
find the values of 𝑎 and 𝑏 which make 𝑆 minimum as follows:

Differentiating 𝑆 partially with respect to 𝑎 and 𝑏 and equally these partially to zero, we
obtain. ∴
𝑛
𝜕𝑆
= ∑(−2)[𝑦𝑖 − (𝑎 + 𝑏𝑥𝑖 )] &
𝜕𝑎
𝑖=1

𝑛
𝜕𝑆
= ∑(−2)𝑥𝑖 [𝑦𝑖 − (𝑎 + 𝑏𝑥𝑖 )]
𝜕𝑏
𝑖=1

𝜕𝑆 𝜕𝑆
i.e. for 𝑆 to be minimum, we have =0 & =0
𝜕𝑎 𝜕𝑏

which yield the so-called system of normal equations (sne),

𝑛 𝑛

∑ 𝑦𝑖 = 𝑛𝑎 + 𝑏 ∑ 𝑥𝑖 &
𝑖=1 𝑖=1

𝑛 𝑛 𝑛

∑ 𝑥𝑖 𝑦𝑖 = 𝑎 ∑ 𝑥𝑖 + 𝑏 ∑ 𝑥𝑖 2
𝑖=1 𝑖=1 𝑖=1

Solving this system of equations we get

𝑛(∑𝑛𝑖=1 𝑥𝑖 2 )(∑𝑛𝑖=1 𝑦𝑖 ) − (∑𝑛𝑖=1 𝑥𝑖 )(∑𝑛𝑖=1 𝑥𝑖 𝑦𝑖 )

𝑎=
𝑛(∑𝑛𝑖=1 𝑥𝑖 2 ) − (∑𝑛𝑖=1 𝑥𝑖 )2

𝑛(∑𝑛𝑖=1 𝑥𝑖 𝑦𝑖 ) − (∑𝑛𝑖=1 𝑥𝑖 )(∑𝑛𝑖=1 𝑦𝑖 )

𝑏=
𝑛(∑𝑛𝑖=1 𝑥𝑖 ) − (∑𝑛𝑖=1 𝑥𝑖 )2

where 𝑛 is the number of points (𝑥𝑖 , 𝑦𝑖 ).

 FITTING A PARABOLA

When a set of points exhibits a parabolic trend, the fitting of a quadratic function

𝑦 = 𝑎 + 𝑏𝑥 + 𝑐𝑥 2 , to the data may be carried out by the method of least squares, which leads
to the three equations
𝑛 𝑛 𝑛

𝑛𝑎 + 𝑏 ∑ 𝑥𝑖 + 𝑐 ∑ 𝑥𝑖 2 = ∑ 𝑦𝑖
1 1 1

𝑛 𝑛 𝑛 𝑛
2 3
𝑎 ∑ 𝑥𝑖 + 𝑏 ∑ 𝑥𝑖 + 𝑐 ∑ 𝑥𝑖 = ∑ 𝑥𝑖 𝑦𝑖
1 1 1 1

𝑛 𝑛 𝑛 𝑛

𝑎 ∑ 𝑥𝑖 + 𝑏 ∑ 𝑥𝑖 + 𝑐 ∑ 𝑥𝑖 = ∑ 𝑥𝑖 2 𝑦𝑖
2 3 4

1 1 1 1

The above equations can be solved for 𝑎, 𝑏, 𝑐.

EXPONENTIAL FUNCTION 𝑦 = 𝑎𝑒 𝑏𝑥

Transforming the exponential equation 𝑦 = 𝑎𝑒 𝑏𝑥 by taking logarithms on both sides we get

𝑙𝑜𝑔 𝑦 = 𝑙𝑜𝑔 𝑎 + 𝑏𝑥 𝑙𝑜𝑔 𝑒.

If we replace 𝑙𝑜𝑔 𝑦 by 𝑦 and the constants 𝑙𝑜𝑔 𝑎 and 𝑏 𝑙𝑜𝑔 𝑒 by 𝑎′ and 𝑏′ respectively, we

Obtain 𝑌 = 𝑎′ + 𝑏𝑥′ , which defines a straight line.

Example

1. Find the least square line (The Regression Equation) 𝒚 = 𝒂 + 𝒃𝒙 for the data

𝑥𝑖 -2 -1 0 1 2
𝑦𝑖 1 2 3 3 4

Solution:

𝑥𝑖 𝑦𝑖 𝑥𝑖 2 𝑥𝑖 𝑦𝑖
-2 1 4 -2
-1 2 1 -2
0 3 0 0
 1 3 1 3
2 4 4 8
0 13 10 7

∴ In this case , 𝑛 = 5, ∑51 𝑥𝑖 = 0, ∑51 𝑦𝑖 = 13, ∑51 𝑥𝑖 2 = 10, & ∑51 𝑥𝑖 𝑦𝑖 = 7

The normal equations are ∑𝑛𝑖=1 𝑦𝑖 = 𝑛𝑎 + 𝑏 ∑𝑛𝑖=1 𝑥𝑖

𝑛 𝑛 𝑛

∑ 𝑥𝑖 𝑦𝑖 = 𝑎 ∑ 𝑥𝑖 + 𝑏 ∑ 𝑥𝑖 2
𝑖=1 𝑖=1 𝑖=1

Putting the values of 𝑛, ∑51 𝑥𝑖 , ∑51 𝑦𝑖 , ∑51 𝑥𝑖 2 , & ∑51 𝑥𝑖 𝑦𝑖 in the above equation we get 5a = 13, 10b =
7

Solving 𝑎 = 2.6, 𝑏 = 0.7

∴ The required line of fit is 𝑦 = 2.6 + (0.7)𝑥

2. Fit a second degree parabola to the following data

𝑥𝑖 0 1 2 3 4
𝑦𝑖 0 1.8 1.3 2.5 6.3

Solution The values of 𝑥 are, 0, 1, 2, 3, 4

The number of values is odd. Shifting the origin to the middle value 2 of 𝑥, and making the substitution

𝑢 = 𝑥 – 2, 𝑣 = 𝑦,

the curve of fit as 𝑣 = 𝑎 + 𝑏𝑢 + 𝑐𝑢2 , / 𝑦 = 𝑎 + 𝑏𝑥 + 𝑐𝑥 2

𝑥 𝑦 𝑥2 𝑥𝑦 𝑥2𝑦

0 1 0 0 0
1 1.8 1 1.8 1.8
2 1.3 4 2.6 5.2
3 2.5 9 7.5 22.5
4 6.3 16 25.2 100.8
Total 10 12.9 30 37.1 130.3

The normal equations are

𝑛 𝑛 𝑛
2
𝑛𝑎 + 𝑏 ∑ 𝑥𝑖 + 𝑐 ∑ 𝑥𝑖 = ∑ 𝑦𝑖
1 1 1
 𝑛 𝑛 𝑛 𝑛
2 3
𝑎 ∑ 𝑥𝑖 + 𝑏 ∑ 𝑥𝑖 + 𝑐 ∑ 𝑥𝑖 = ∑ 𝑥𝑖 𝑦𝑖
1 1 1 1

𝑛 𝑛 𝑛 𝑛

𝑎 ∑ 𝑥𝑖 2 + 𝑏 ∑ 𝑥𝑖 3 + 𝑐 ∑ 𝑥𝑖 4 = ∑ 𝑥𝑖 2 𝑦𝑖
1 1 1 1

Putting the values of 𝑛, ∑𝑥, ∑𝑦, ∑𝑥𝑦, . . ., etc.,

𝐶𝑈𝑅𝑉𝐸 𝐹𝐼𝑇𝑇𝐼𝑁𝐺
5𝑎 + 10𝑏 + 30𝑐 = 12.9
10𝑎 + 30𝑏 + 100𝑐 = 37.1
30𝑎 + 100𝑏 + 354𝑐 = 130.3
solving these normal equations we get 𝑎 = 1.42, 𝑏 = −1.07, 𝑐 = 0.550.

∴ The required curve of fit is the parabola 𝑦 = 1.42 – 1.07𝑥 + 0.55𝑥 2.

Chapter 3

Interpolation / INTERPOLATION WITH EQUAL INTERVALS

INTRODUCTION

The word interpolation denotes the method of computing the value of the function
𝑦 = 𝑓(𝑥) for any given value of the independent variable 𝑥 when a set of values
of 𝑦 = 𝑓(𝑥) for certain values of 𝑥 are given.

Definition : Interpoltation is the estimation of a most likely estimate in given conditions. It

is the technique of estimating a Past figure (Hiral).

According to Theile: “Interpolation is the art of reading between the lines of a table”.

According to W.M. Harper: “Interpolation consists in reading a value which lies between two

extreme points”

Let y = f(x) be a function which takes the values 𝑦0 , 𝑦1 , 𝑦2 , … , 𝑦𝑛 , corresponding to the values

𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 of the independent variable 𝑥.

If the form of the function 𝑦 = 𝑓(𝑥) is known we can very easily calculate the value of 𝑦 correspondig
to any value of 𝑥.

But in most of the practical problems, the exact form of the function is not known. In such cases the
function 𝑓(𝑥) is replaced by a simpler function say 𝜙(𝑥) which has the same values as 𝑓(𝑥) for
𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 . The function 𝜙(𝑥) is called an interpolating function.
MISSING VALUES

Let a function 𝑦 = 𝑓(𝑥) be given for equally spaced values 𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 of the argument and
𝑦0 , 𝑦1 , 𝑦2 , … , 𝑦𝑛 denote the corresponding values of the function.

If one or more values of 𝑦 = 𝑓(𝑥) are missing we can find the missing values by using the relation
between the operators 𝐸 and ∆.

NEWTON’S BINOMIAL EXPANSION FORMULA

Let 𝑦0 , 𝑦1 , 𝑦2 , … , 𝑦𝑛 denote the values of the function 𝑦 = 𝑓(𝑥) corresponding to the values 𝑥0 , 𝑥0 +
ℎ, 𝑥1 + ℎ, 𝑥2 + 2ℎ, … , 𝑥𝑛 + 𝑛ℎ of 𝑥 and let one of the values of 𝑦 be missing since 𝑛 values of the
functions are known. We have

Δ𝑛 𝑦0 = 0
(Ε − 1)𝑛 𝑦0 = 0

[𝑛𝑐0 Ε 𝑛 − 𝑛𝑐1 Ε 𝑛−1 + 𝑛𝑐2 Ε 𝑛−2 + 𝑛𝑐3 Ε 𝑛−3 + ⋯ +(−1)𝑛 ]𝑦0 = 0

𝑛(𝑛 − 1) 𝑛−2
Ε 𝑛 𝑦0 − 𝑛Ε 𝑛−1 𝑦0 + Ε 𝑦0 + ⋯ +(−1)𝑛 𝑦0 = 0
1𝑥2
𝑛(𝑛 − 1)
𝑦𝑛 − 𝑛𝑦𝑛−1 + 𝑦𝑛−2 + ⋯ +(−1)𝑛 𝑦0 = 0
1𝑥2
The above formula is called Newton’s binomial expansion formula and is useful in finding the

missing values without constructing the difference table.

Example . Find the missing entry in the following table

𝑥𝑖 0 1 2 3 4
𝑦𝑖 1 3 9 - 81

Solution : Given 𝑦0 = 1, 𝑦1 = 3, 𝑦2 = 9, … , 𝑦3 = ? , 𝑦4 = 81 four values of 𝑦 are given. Let 𝑦 be

polynomial of degree 3

∴ Δ4 𝑦0 = 0
(Ε − 1)4 𝑦0 = 0

(Ε 4 − 4Ε 3 + 6Ε 2 − 4Ε + 1)𝑦0 = 0

(Ε 4 𝑦0 − 4Ε 3 𝑦0 + 6Ε 2 𝑦0 − 4Ε𝑦0 + 1𝑦0 ) = 0
𝑦4 − 4𝑦3 + 6𝑦2 − 4𝑦1 + 1𝑦0 = 0
∴ 81 − 4𝑦3 + 6(9) − 4(3) + 1 = 0
𝑦3 = 31
LAGRANGE’S INTERPOLATION FORMULA
Let 𝑦 = 𝑓(𝑥) be a function which assumes the values 𝑓(𝑥0 ), 𝑓(𝑥1 ), 𝑓(𝑥2 ), … , 𝑓(𝑥𝑛 ) corresponding to

the values 𝑥 = 𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 , where the values of 𝑥 are not equispaced. Since (𝑛 + 1) values of

the function are given corresponding to the (𝑛 + 1) values of the independent variable 𝑥, we can

represent the function 𝑦 = 𝑓(𝑥) be a polynomial in 𝑥 of degree 𝑛.

𝑛

𝐟(𝐱) = ∑ 𝑓(𝑥𝑖 )𝐿𝑖 (𝑥)

𝑖=0
------------------------------(*)

Where
𝑛 𝑥 − 𝑥𝑗
𝐿𝑖 (𝑥) = ∏
𝑖≠𝑗,𝑗=0 𝑥𝑖 − 𝑥𝑗
.

The formula given by (*) is called Lagrange’s interpolation formula

Example . Using Lagrange’s interpolation formula find a polynomial which passes the points (0, – 12),
(1, 0), (3, 6), (4, 12). Find the value of 𝑦 corresponding to 𝑥 = 3.5 & 𝑥 = 4

Solution : We have 𝑥0 = 0, 𝑥1 = 1, 𝑥2 = 3, 𝑥3 = 4, 𝑦0 = 𝑓(𝑥0 ) = – 12, 𝑦1 = 𝑓(𝑥1 ) =

0, 𝑦2 = 𝑓(𝑥2 ) = 6, 𝑦3 = 𝑓(𝑥3 ) = 12.

Using Lagrange’s interpolation formula we can write

(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )(𝑥 − 𝑥3 ) (𝑥 − 𝑥0 )(𝑥 − 𝑥2 )(𝑥 − 𝑥3 )
𝑓(𝑥) = 𝑓(𝑥0 ) + 𝑓(𝑥1 )
(𝑥0 − 𝑥1 )(𝑥0 − 𝑥2 )(𝑥0 − 𝑥3 ) (𝑥1 − 𝑥0 )(𝑥1 − 𝑥2 )(𝑥1 − 𝑥3 )
(𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥3 ) (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )
+ 𝑓(𝑥2 ) + 𝑓(𝑥3 )
(𝑥2 − 𝑥0 )(𝑥2 − 𝑥1 )(𝑥2 − 𝑥3 ) (𝑥3 − 𝑥0 )(𝑥3 − 𝑥1 )(𝑥3 − 𝑥2 )
(𝑥 − 1)(𝑥 − 3)(𝑥 − 4) (𝑥 − 0)(𝑥 − 3)(𝑥 − 4) (𝑥 − 0)(𝑥 − 1)(𝑥 − 4)
𝑓(𝑥) = (−12) + (0) + (6)
(0 − 1)(0 − 3)(0 − 4) (1 − 0)(1 − 3)(1 − 4) (3 − 0)(3 − 1)(3 − 4)
(𝑥 − 0)(𝑥 − 1)(𝑥 − 3)
+ (12)
(4 − 0)(4 − 1)(4 − 3)
(𝑥 3 − 8𝑥 2 + 19𝑥 − 12) (𝑥 3 − 5𝑥 2 + 4𝑥) (𝑥 3 − 4𝑥 2 + 3𝑥)
𝑓(𝑥) = (12) + (6) + (12)
12 (−6) 12
∴ 𝑓(𝑥) = 𝑥 3 − 7𝑥 2 + 18𝑥 − 12 is the required polynomial.

NEWTON’S FORWARD INTERPOLATION FORMULA

Let 𝑦 = 𝑓(𝑥) be a function which takes the values 𝑦0 , 𝑦, 𝑦, … , 𝑦𝑛 , corresponding to the (𝑛 + 1) values

𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 , of the independent variable 𝑥. Let the values 𝑥 be equally spaced, i.e., 𝑥𝑟 = 𝑥0 +

𝑟ℎ, 𝑟 = 0, 1, 2, 3, … , 𝑛 where ℎ is the interval of differencing. Let 𝜙(𝑥) be a polynomial of the 𝑛𝑡ℎ
degree in 𝑥 taking the same values as 𝑦 corresponding to 𝑥 = 𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 , then, 𝜙(𝑥)
represents the continuous function 𝑦 = 𝑓(𝑥) such that 𝑓(𝑥𝑟 ) = 𝜙(𝑥𝑟 ) for 𝑟 = 0, 1, 2, … , 𝑛 and at all
other points 𝑓(𝑥) = 𝜙(𝑥) + 𝑅(𝑥) where 𝑅(𝑥) is called the error term (Remainder term) of the
interpolation formula. Ignoring the error term

let us assume 𝑓(𝑥) = 𝑎0 + 𝑎1 (𝑥 − 𝑥0 ) + 𝑎2 (𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) + ⋯ + 𝑎𝑛 (𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) … (𝑥 − 𝑥𝑛−1 )

the constants 𝑎0 , 𝑎1 , 𝑎2 , … , 𝑎𝑛 can be determine as follows. -------------------(2*)

Putting 𝑥 = 𝑥0 in (2*) we get 𝑓(𝑥0 ) = 𝑎0 ⇒ 𝑦 = 𝑎0

putting 𝑥 = 𝑥1 in (2*) we get 𝑓(𝑥1 ) = 𝑎0 + 𝑎1 (𝑥 − 𝑥0 ) = 𝑦0 + 𝑎1 ℎ ⇒ 𝑦1 = 𝑦0 + 𝑎1 ℎ

𝑦1 − 𝑦0 ∆𝑦0
⇒ 𝑎1 = ⇒ 𝑎1 =
ℎ ℎ
∆2 𝑦0
Putting 𝑥 = 𝑥2 in (2*) we get 𝑎2 =
2!ℎ 2

∆3 𝑦0 ∆4 𝑦0 ∆𝑛 𝑦0
Similarly by putting 𝑥 = 𝑥3 , 𝑥 = 𝑥4 . . . , 𝑥 = 𝑥𝑛 in (2*) we get 𝑎3 = 3!ℎ 3
, 𝑎4 = 4!ℎ 4
, …, 𝑎𝑛 = 𝑛!ℎ 𝑛

putting the values of 𝑎0 , 𝑎1 , 𝑎2 , … , 𝑎𝑛 in (2*) we get

∆𝑦 ∆2 𝑦 ∆3 𝑦
𝑓(𝑥) = 𝑦0 + 1!ℎ0 (𝑥 − 𝑥0 ) + 2!ℎ20 (𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) + 3!ℎ30 (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥3 ) + ⋯ +
∆𝑛 𝑦0
(𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) … (𝑥 − 𝑥𝑛−1 ) -----------------(3*)
𝑛!ℎ 𝑛
𝑥−𝑥0
Writing 𝑢 = , we get 𝑥 − 𝑥0 = 𝑢ℎ
ℎ

𝑥 − 𝑥1 = 𝑥 − 𝑥0 + 𝑥0 − 𝑥1 = (𝑥 − 𝑥0 ) − (𝑥1 − 𝑥0 ) = 𝑢ℎ − ℎ = (𝑢 − 1)ℎ
Similarly 𝑥 − 𝑥2 = 𝑢 − 2ℎ

𝑥 − 𝑥3 = 𝑢 − 3ℎ
---

𝑥 − 𝑥0 = (𝑢 − 𝑛 + 1)h
Equation (3*) can be written as
𝑢 𝑢(𝑢 − 1) 2 𝑢(𝑢 − 1)(𝑢 − 2) 3 𝑢(𝑢 − 1) … (𝑢 − 𝑛 + 1) 𝑛
𝑓(𝑥) = 𝑦0 + ∆𝑦0 + ∆ 𝑦0 + ∆ 𝑦0 + ⋯ + ∆ 𝑦0
1! 2! 3! 𝑛!
The above formula is called Newton’s forward interpolation formula (NFIF).

Note:

1. Newton forward interpolation formula is used to interpolate the values of 𝑦 near the beginning of a
set of tabular values.

2.𝑦0 may be taken as any point of the table, but the formula contains only those values of 𝑦 which come

after the value chosen as 𝑦0 .

Example . A second degree polynomial passes through the points (1, – 1), (2, – 1), (3, 1), (4, 5). Find the
polynomial.

Solution : We construct difference table with the given values of 𝑥 and 𝑦

𝑥 𝑦 ∆𝑦 ∆2 𝑦 ∆3 𝑦
1 −1
0
2 −1 2
2 0
3 1 2
4
4 5

We have 𝑥0 = 1, ℎ = 1, 𝑦0 = −1, ∆𝑦 = 0, ∆2 𝑦 = 2
𝑥 − 𝑥0
𝑢= = (𝑥 − 1)
ℎ
𝑢 𝑢(𝑢−1) 2 𝑢(𝑢−1)(𝑢−2) 3
From Newton’s forward interpolation we get 𝑦 = 𝑓(𝑥) = 𝑦0 + 1! ∆𝑦0 + 2!
∆ 𝑦0 + 3!
∆ 𝑦0

(𝑥 − 1) (𝑥 − 1)(𝑥 − 1 − 1) (𝑥 − 1)(𝑥 − 1 − 1)(𝑥 − 1 − 2)

𝑦 = 𝑓(𝑥) = −1 + .0 + .2 + .0
1! 2! 3!
∴ 𝑓(𝑥) = 𝑥 2 − 3𝑥 + 1

NEWTON–GREGORY BACKWARD INTERPOLATION FORMULA

Newton’s forward interpolation formula cannot be used for interpolating a value of 𝑦 near the end

of a table of values. For this purpose, we use another formula known as Newton–Gregory backward

interpolation formula. It can be derived as follows.

Let 𝑦 = 𝑓(𝑥) be a function which takes the values 𝑦0 , 𝑦, 𝑦, … , 𝑦𝑛 , corresponding to the (𝑛 + 1) values

𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 , of the independent variable 𝑥. Let the values of 𝑥 be equally spaced with ℎ as the
interval of differencing, i.e., Let 𝑥𝑟 = 𝑥0 + 𝑟ℎ, 𝑟 = 0, 1, 2, 3, … , 𝑛

let us assume

𝑓(𝑥) = 𝑎0 + 𝑎1 (𝑥 − 𝑥𝑛 ) + 𝑎2 (𝑥 − 𝑥𝑛 )(𝑥 − 𝑥𝑛−1 ) + ⋯ + 𝑎𝑛 (𝑥 − 𝑥𝑛 )(𝑥 − 𝑥𝑛−1 ) … (𝑥 − 𝑥1 ) ----(4*)

the constants 𝑎0 , 𝑎1 , 𝑎2 , … , 𝑎𝑛 can be determine as follows. -------------------(4*)

Putting 𝑥 = 𝑥𝑛 in (4*) we get 𝑓(𝑥𝑛 ) = 𝑎0 ⇒ 𝑦𝑛 = 𝑎0

putting 𝑥 = 𝑥𝑛−1 in (4*) we get

𝑓(𝑥𝑛−1 ) = 𝑎0 + 𝑎1 (𝑥𝑛−1 − 𝑥𝑛 ) = 𝑦𝑛 + 𝑎1 (−ℎ) ⇒ 𝑦𝑛−1 = 𝑦𝑛 − 𝑎1 ℎ

𝑦𝑛 − 𝑦𝑛−1 ∇𝑦𝑛
⇒ 𝑎1 = ⇒ 𝑎1 =
ℎ ℎ
 ∇2 𝑦𝑛
Putting 𝑥 = 𝑥𝑛−2 in (4*) we get 𝑎2 = 2!ℎ 2

Similarly by putting 𝑥 = 𝑥𝑛−3 , 𝑥 = 𝑥𝑛−4 . . . , 𝑥 = 𝑥1 in (2*) we get

∇3 𝑦𝑛 ∇4 𝑦𝑛 ∇𝑛 𝑦𝑛
𝑎3 = 3!ℎ 3
, 𝑎4 = 4!ℎ 4
, …, 𝑎𝑛 = 𝑛!ℎ 𝑛

putting the values of 𝑎0 , 𝑎1 , 𝑎2 , … , 𝑎𝑛 in (4*) we get

∇𝑦𝑛 ∇2 𝑦𝑛 ∇3 𝑦𝑛
𝑓(𝑥) = 𝑦𝑛 + (𝑥 − 𝑥𝑛 ) + (𝑥 − 𝑥𝑛 )(𝑥 − 𝑥𝑛−1 ) + (𝑥 − 𝑥𝑛 )(𝑥 − 𝑥𝑛−1 )(𝑥 − 𝑥𝑛−3 ) + ⋯ +
1!ℎ 2!ℎ 2 3!ℎ 3
∇𝑛 𝑦𝑛
(𝑥 − 𝑥𝑛 )(𝑥 − 𝑥𝑛−1 ) … (𝑥 − 𝑥1 ) -----------------(6*)
𝑛!ℎ 𝑛
𝑥−𝑥𝑛
Writing 𝑢 = ℎ
, we get 𝑥 − 𝑥𝑛 = 𝑢ℎ

𝑥 − 𝑥𝑛−1 = 𝑥 − 𝑥𝑛 + 𝑥𝑛 − 𝑥𝑛−1 = (𝑥 − 𝑥𝑛 ) + (𝑥𝑛 − 𝑥𝑛−1 ) = 𝑢ℎ + ℎ = (𝑢 + 1)ℎ

Similarly 𝑥 − 𝑥𝑛−2 = (𝑢 + 2)ℎ

𝑥 − 𝑥𝑛−3 = (𝑢 + 3)ℎ
---

𝑥 − 𝑥1 = (𝑢 − 𝑛 + 1)h
Equation (6*) can be written as
𝑢 𝑢(𝑢 + 1) 2 𝑢(𝑢 + 1)(𝑢 + 2) 3 𝑢(𝑢 + 1) … (𝑢 + 𝑛 − 1) 𝑛
𝑓(𝑥) = 𝑦𝑛 + ∇𝑦𝑛 + ∇ 𝑦𝑛 + ∇ 𝑦𝑛 + ⋯ + ∇ 𝑦𝑛
1! 2! 3! 𝑛!
The above formula is called Newton’s backward interpolation formula (NBIF).

Note:

1. Newton backward interpolation formula is used to interpolate the values of 𝑦 near the end of a set of
tabular values.

2.𝑦𝑛 may be taken as any point of the table, but the formula contains only those values of 𝑦 which come

after the value chosen as 𝑦𝑛 .

Example . Calculate the value of 𝑓 (4.5) for the table.

X 1 2 3 4 5
Y 1 8 27 64 125

Solution : 4.5 is near to the end of the table, we use Newton’s backward formula to find 𝑓(4.5).

We construct difference table with the given values of 𝑥 and 𝑦

𝑥 𝑦 ∇𝑦 ∇2 𝑦 ∇3 𝑦 ∇4 𝑦
1 1
7
 2 8 12
19 6
3 27 18 0
37 6
4 64 24
61
5 125

We have 𝑥4 = 5, ℎ = 1, 𝑦4 = 125, ∇𝑦4 = 7, ∇2 𝑦4 = 12, ∇3 𝑦4 = 6, ∇4 𝑦4 = 0 ,

𝑥 − 𝑥4
𝑢= = (𝑥 − 5) = (4.5 − 5) = −0.5
ℎ
From Newton’s Backward interpolation we get
𝑢 𝑢(𝑢+1) 2 𝑢(𝑢+1)(𝑢+2) 3 𝑢(𝑢+1)(𝑢+2)(𝑥+3) 4
𝑦 = 𝑓(𝑥) = 𝑦4 + ∇𝑦4 + ∇ 𝑦4 + ∇ 𝑦4 + ∇ 𝑦4
1! 2! 3! 4!

(𝑥 − 5) (𝑥 − 5)(𝑥 − 4) (𝑥 − 5)(𝑥 − 4)(𝑥 − 3)

𝑦 = 𝑓(𝑥) = 125 + .7 + . 12 + .6
1! 2! 3!
(−0.5) (−0.5)(0.5) (−0.5)(0.5)(1.5)
𝑦 = 𝑓(𝑥) = 125 + .7 + . 12 + .6
1! 2! 3!
∴ 𝑓(𝑥 = 4.5) = 119.625