Newton’s (forward and backward) and interpolation, Lagrange’s Interpolation | Mathematics Optional Notes for UPSC PDF Download

 Page 1


Newton’ s F orward and Backward Interpolation
1 Introduction to Interpolation
Interpolation is the process of estimating unknown values of a function using a
set of known data points. It is widely used in fields such as engineering, com-
puter science, and mathematics to approximate values within a given r ange.
• Definition : Interpolation involves constructing a function (often a polyno-
mial) that passes through known data points to estimate values at unspec-
ified points.
• Purpose : T o find the value of y for an unknown x within the interval of
known dat a points.
• K ey Assumption : The data points are equally spaced, and the func tion can
be approximated b y a polynomial.
2 Newton’ s F orward Interpolation
Newton’ s F orward Interpolation is used to estimate the value of a function for
an x -value that is closer to the beginning of the given data table. It relies on
forward differences to construct a polynomial that approximates the function.
2.1 K ey F eatures
• Applicability : Best suited when the interpolation point is near the start of
the data set.
• F ormula : The forward interpolation formula is given b y:
y(x) = y
0
+ p?y
0
+
p(p-1)
2!
?
2
y
0
+
p(p-1)(p-2)
3!
?
3
y
0
+ ...
where:
– y
0
: The first y -value in the data table.
– ?y
0
: First forward difference.
– ?
2
y
0
: Second forward difference, and so on.
– p =
x-x
0
h
: Normalized distance, where h is the interval between con-
secutive x -values.
– h : The constant difference between successive x -values.
2.2 Example
T o illustr ate, consider finding the value of tan (0.12) using a table of tan(x) values
for x = 0.1,0.15,0.2,0.25,0.3 .
• Construct the forward difference table.
1
Page 2


Newton’ s F orward and Backward Interpolation
1 Introduction to Interpolation
Interpolation is the process of estimating unknown values of a function using a
set of known data points. It is widely used in fields such as engineering, com-
puter science, and mathematics to approximate values within a given r ange.
• Definition : Interpolation involves constructing a function (often a polyno-
mial) that passes through known data points to estimate values at unspec-
ified points.
• Purpose : T o find the value of y for an unknown x within the interval of
known dat a points.
• K ey Assumption : The data points are equally spaced, and the func tion can
be approximated b y a polynomial.
2 Newton’ s F orward Interpolation
Newton’ s F orward Interpolation is used to estimate the value of a function for
an x -value that is closer to the beginning of the given data table. It relies on
forward differences to construct a polynomial that approximates the function.
2.1 K ey F eatures
• Applicability : Best suited when the interpolation point is near the start of
the data set.
• F ormula : The forward interpolation formula is given b y:
y(x) = y
0
+ p?y
0
+
p(p-1)
2!
?
2
y
0
+
p(p-1)(p-2)
3!
?
3
y
0
+ ...
where:
– y
0
: The first y -value in the data table.
– ?y
0
: First forward difference.
– ?
2
y
0
: Second forward difference, and so on.
– p =
x-x
0
h
: Normalized distance, where h is the interval between con-
secutive x -values.
– h : The constant difference between successive x -values.
2.2 Example
T o illustr ate, consider finding the value of tan (0.12) using a table of tan(x) values
for x = 0.1,0.15,0.2,0.25,0.3 .
• Construct the forward difference table.
1
• Calculate p =
0.12-0.1
0.05
= 0.4 (assuming h = 0.05 ).
• Apply the forward interpolation formula using the differences up to the
desired order (e.g., four th order).
• The interpolated value of tan(0.12) is computed b y summing the terms.
3 Newton’ s Backward Interpolation
Newton’ s Backward Interpolation is used to estimate the value of a function
for an x -value that is closer to the end of the given data table. It uses backward
differences to construct the interpolating polynomial.
3.1 K ey F eatures
• Applicability : Best suited when the interpolation point is near the end of
the data set.
• F ormula : The backward interpolation formula is given b y:
y(x) = y
n
+ p?y
n
+
p(p+1)
2!
?
2
y
n
+
p(p+1)(p+2)
3!
?
3
y
n
+ ...
where:
– y
n
: The last y -value in the data table.
– ?y
n
: First backward difference.
– ?
2
y
n
: Second backward difference, and so on.
– p =
x-xn
h
: Normalized distance, where h is the interval between con-
secutive x -values.
3.2 Example
Consider estimating y(300) using a table of y -values for x = 50,100,150,200,250 .
• Construct the backward difference table.
• Calculate p =
300-250
50
= 1 (assuming h = 50 ).
• Apply the backward interpolation formula using the backward differences.
• The interpolated value of y(300) is computed b y summing the terms.
4 Constructing Difference T ables
Both forward and backward interpolation rely on difference tables to compute
the differences used in the formulas.
2
Page 3


Newton’ s F orward and Backward Interpolation
1 Introduction to Interpolation
Interpolation is the process of estimating unknown values of a function using a
set of known data points. It is widely used in fields such as engineering, com-
puter science, and mathematics to approximate values within a given r ange.
• Definition : Interpolation involves constructing a function (often a polyno-
mial) that passes through known data points to estimate values at unspec-
ified points.
• Purpose : T o find the value of y for an unknown x within the interval of
known dat a points.
• K ey Assumption : The data points are equally spaced, and the func tion can
be approximated b y a polynomial.
2 Newton’ s F orward Interpolation
Newton’ s F orward Interpolation is used to estimate the value of a function for
an x -value that is closer to the beginning of the given data table. It relies on
forward differences to construct a polynomial that approximates the function.
2.1 K ey F eatures
• Applicability : Best suited when the interpolation point is near the start of
the data set.
• F ormula : The forward interpolation formula is given b y:
y(x) = y
0
+ p?y
0
+
p(p-1)
2!
?
2
y
0
+
p(p-1)(p-2)
3!
?
3
y
0
+ ...
where:
– y
0
: The first y -value in the data table.
– ?y
0
: First forward difference.
– ?
2
y
0
: Second forward difference, and so on.
– p =
x-x
0
h
: Normalized distance, where h is the interval between con-
secutive x -values.
– h : The constant difference between successive x -values.
2.2 Example
T o illustr ate, consider finding the value of tan (0.12) using a table of tan(x) values
for x = 0.1,0.15,0.2,0.25,0.3 .
• Construct the forward difference table.
1
• Calculate p =
0.12-0.1
0.05
= 0.4 (assuming h = 0.05 ).
• Apply the forward interpolation formula using the differences up to the
desired order (e.g., four th order).
• The interpolated value of tan(0.12) is computed b y summing the terms.
3 Newton’ s Backward Interpolation
Newton’ s Backward Interpolation is used to estimate the value of a function
for an x -value that is closer to the end of the given data table. It uses backward
differences to construct the interpolating polynomial.
3.1 K ey F eatures
• Applicability : Best suited when the interpolation point is near the end of
the data set.
• F ormula : The backward interpolation formula is given b y:
y(x) = y
n
+ p?y
n
+
p(p+1)
2!
?
2
y
n
+
p(p+1)(p+2)
3!
?
3
y
n
+ ...
where:
– y
n
: The last y -value in the data table.
– ?y
n
: First backward difference.
– ?
2
y
n
: Second backward difference, and so on.
– p =
x-xn
h
: Normalized distance, where h is the interval between con-
secutive x -values.
3.2 Example
Consider estimating y(300) using a table of y -values for x = 50,100,150,200,250 .
• Construct the backward difference table.
• Calculate p =
300-250
50
= 1 (assuming h = 50 ).
• Apply the backward interpolation formula using the backward differences.
• The interpolated value of y(300) is computed b y summing the terms.
4 Constructing Difference T ables
Both forward and backward interpolation rely on difference tables to compute
the differences used in the formulas.
2
4.1 F orward Difference T able
• First Differ ence : ?y
i
= y
i+1
- y
i
• Second Differ ence : ?
2
y
i
= ?y
i+1
-?y
i
• Higher-Order Differences : Computed similarly b y taking differences of
the previo us differences.
4.2 Backward Difference T able
• First Differ ence :?y
i
= y
i
- y
i-1
• Second Diff erence :?
2
y
i
=?y
i
-?y
i-1
• Higher-Order Differences : Computed b y taking differences of the previ-
ous back ward differences.
5 A dvantages and Disadvantages
5.1 A dvantages
• A ccur acy : Provides accur ate estimates for points within the r ange of known
data.
• Simplicity : Easy to implement using difference tables and polynomial for-
mulas.
• V ersatility : Applicable in various fields, including computer gr aphics, data
analysis, an d scientific computations.
5.2 Disadvantages
• Limited Range : Less accur ate for extr apolation (values outside the data
r ange).
• Error Propagation : Higher-order differences ma y introduce errors if the
data is noisy .
• Middle Range Limitation : Neither forward nor backward interpolation is
ideal for point s in the middle of the data table.
6 Applications in Computer Science
Interpolation techniques, including Newton’ s methods, have significant applica-
tions in computer science:
• Computer Gr aphics : Used to smooth curves and surfaces for rendering.
• Data Analy sis : Helps estimate missing data points in datasets.
• Numerical Simulations : F acilitates the approximation of functions in sim-
ulations.
3
Page 4


Newton’ s F orward and Backward Interpolation
1 Introduction to Interpolation
Interpolation is the process of estimating unknown values of a function using a
set of known data points. It is widely used in fields such as engineering, com-
puter science, and mathematics to approximate values within a given r ange.
• Definition : Interpolation involves constructing a function (often a polyno-
mial) that passes through known data points to estimate values at unspec-
ified points.
• Purpose : T o find the value of y for an unknown x within the interval of
known dat a points.
• K ey Assumption : The data points are equally spaced, and the func tion can
be approximated b y a polynomial.
2 Newton’ s F orward Interpolation
Newton’ s F orward Interpolation is used to estimate the value of a function for
an x -value that is closer to the beginning of the given data table. It relies on
forward differences to construct a polynomial that approximates the function.
2.1 K ey F eatures
• Applicability : Best suited when the interpolation point is near the start of
the data set.
• F ormula : The forward interpolation formula is given b y:
y(x) = y
0
+ p?y
0
+
p(p-1)
2!
?
2
y
0
+
p(p-1)(p-2)
3!
?
3
y
0
+ ...
where:
– y
0
: The first y -value in the data table.
– ?y
0
: First forward difference.
– ?
2
y
0
: Second forward difference, and so on.
– p =
x-x
0
h
: Normalized distance, where h is the interval between con-
secutive x -values.
– h : The constant difference between successive x -values.
2.2 Example
T o illustr ate, consider finding the value of tan (0.12) using a table of tan(x) values
for x = 0.1,0.15,0.2,0.25,0.3 .
• Construct the forward difference table.
1
• Calculate p =
0.12-0.1
0.05
= 0.4 (assuming h = 0.05 ).
• Apply the forward interpolation formula using the differences up to the
desired order (e.g., four th order).
• The interpolated value of tan(0.12) is computed b y summing the terms.
3 Newton’ s Backward Interpolation
Newton’ s Backward Interpolation is used to estimate the value of a function
for an x -value that is closer to the end of the given data table. It uses backward
differences to construct the interpolating polynomial.
3.1 K ey F eatures
• Applicability : Best suited when the interpolation point is near the end of
the data set.
• F ormula : The backward interpolation formula is given b y:
y(x) = y
n
+ p?y
n
+
p(p+1)
2!
?
2
y
n
+
p(p+1)(p+2)
3!
?
3
y
n
+ ...
where:
– y
n
: The last y -value in the data table.
– ?y
n
: First backward difference.
– ?
2
y
n
: Second backward difference, and so on.
– p =
x-xn
h
: Normalized distance, where h is the interval between con-
secutive x -values.
3.2 Example
Consider estimating y(300) using a table of y -values for x = 50,100,150,200,250 .
• Construct the backward difference table.
• Calculate p =
300-250
50
= 1 (assuming h = 50 ).
• Apply the backward interpolation formula using the backward differences.
• The interpolated value of y(300) is computed b y summing the terms.
4 Constructing Difference T ables
Both forward and backward interpolation rely on difference tables to compute
the differences used in the formulas.
2
4.1 F orward Difference T able
• First Differ ence : ?y
i
= y
i+1
- y
i
• Second Differ ence : ?
2
y
i
= ?y
i+1
-?y
i
• Higher-Order Differences : Computed similarly b y taking differences of
the previo us differences.
4.2 Backward Difference T able
• First Differ ence :?y
i
= y
i
- y
i-1
• Second Diff erence :?
2
y
i
=?y
i
-?y
i-1
• Higher-Order Differences : Computed b y taking differences of the previ-
ous back ward differences.
5 A dvantages and Disadvantages
5.1 A dvantages
• A ccur acy : Provides accur ate estimates for points within the r ange of known
data.
• Simplicity : Easy to implement using difference tables and polynomial for-
mulas.
• V ersatility : Applicable in various fields, including computer gr aphics, data
analysis, an d scientific computations.
5.2 Disadvantages
• Limited Range : Less accur ate for extr apolation (values outside the data
r ange).
• Error Propagation : Higher-order differences ma y introduce errors if the
data is noisy .
• Middle Range Limitation : Neither forward nor backward interpolation is
ideal for point s in the middle of the data table.
6 Applications in Computer Science
Interpolation techniques, including Newton’ s methods, have significant applica-
tions in computer science:
• Computer Gr aphics : Used to smooth curves and surfaces for rendering.
• Data Analy sis : Helps estimate missing data points in datasets.
• Numerical Simulations : F acilitates the approximation of functions in sim-
ulations.
3
• Image Processing : Applied in image interpolation for resizing or recon-
structing im ages.
7 Caveats and Best Pr actices
• Choosing t he Right Method :
– Use forward interpolation for points near the beginning of the data
table.
– Use backward interpolation for points near the end of the data table.
– F or points in the middle, consider alternative methods lik e Lagr ange
interpolation.
• Data Spacing : Both methods assume equally spaced data points. F or un-
equally spaced points, use Newton’ s divided difference or Lagr ange inter-
polation.
• Error Consider ation : Higher-order polynomials ma y lead to oscillations
(Runge’ s pheno menon). Choose the polynomial degree carefully .
• Numerical Stability : Ensure the difference table is computed accur ately
to avoid error propa gation.
8 Conclusion
Newton’ s F orward and Backward Interpolation methods are powerful tools
for estimating function values between known data points. B y lever aging for-
ward and backward differences, these methods provide efficient and accur ate
approximations for equally spaced data. With applications in computer science,
engineering, and numerical analysis, these techniques remain essential for solv-
ing real-world problems. F or further details, refer to resources on numerical
methods or explore implementations in progr amming languages lik e MA TLAB
or C.
4