Why Go Numerical?
“I much prefer the sharpest criticism of a single intelligent man to the thoughtless approval of the masses”- Johannes Kepler
Hii! Today’s blog will be different as ill be talking differently than usual. If you have followed my blog regularly, you might have noticed I usually cover topics that apply numerical methods more than usual analytic solutions, so today, for you guys, I've decided ill go through the reason why, apart from the fact that me aspiring to be a numerical analyst.
What’s & Why’s
Numerical methods or computations are sets of techniques and tools one uses to solve a mathematical problem with the help of approximations. In many cases, real-world problems, we face some problems which are too complex or fail to give analytic solutions, or the process itself is too time consuming-it these cases, we use numerical solutions. Numerical solutions are nothing but iterative values.
Some of the most common numerical methods include:
- Interpolation: Interpolation is basically the technique where we estimate the value of a function at a point between two known points(our estimated value is a straight line between the two points).
- Differentiation: This method is used to approximate the derivative of a function at a point.
- Integration: This method is used to approximate the integral of a function over a given interval.
- Solving differential equations: This method is used to approximate the solution of a differential equation.
Today we will majorly focus on Interpolation.
Interpolation is a type of estimation, a method of constructing new data points within the range of a discrete set of known data points. It is often required to interpolate the value of that function for an intermediate value of an independent variable.
A polynomial is called an interpolating polynomial if the values of P(x) and its certain order derivatives coincide with those of f(x) and its same order derivatives at one or more tabular points,
Interpolation is mainly of two types:
- Linear Interpolation: This is the simplest type of interpolation. It uses the two known points to create a straight line, and the estimated value is the point on the line closest to the unknown point.
- Polynomial Interpolation:: This is a more complex type of interpolation. It uses a polynomial function to fit the known points, and then the estimated value is the value of the polynomial function at the unknown point.
Interpolation serves a great purpose in data analysis, curve fitting, and numerical integration.
Advantages: There are many advantages, but the most important are that:
- It's simple and efficient
- It helps us to estimate the value btw two unknown points
- helps to fill gaps-unknown data and smooth out noisy data.
Disadvantages: Despite all these advantages, it has its set of disadvantages. It often affects the accuracy due to its spacing-i.e spacing between the two points.
Interpolation Techniques: Among the various interpolation techniques- Lagrange and Newton interpolation techniques are the most powerful techniques.
Lagrange Interpolation:
Lagrange interpolation constructs a polynomial of degree n-1 (where n is the number of data points) that passes through each data point. It determines the coefficients of the polynomial so that it matches the function values at the given data points.
The Lagrange polynomials, denoted by Lᵢ(x), are the building blocks of the interpolation polynomial. Each Lᵢ(x) corresponds to a data point (xᵢ, yᵢ) and is defined as follows:
Lᵢ(x) = Π [ (x — xⱼ) / (xᵢ — xⱼ) ] for j ≠ i
These polynomials have the property that Lᵢ(xᵢ) = 1 and Lᵢ(xⱼ) = 0 for j ≠ i, which ensures that the interpolation polynomial passes through the data points correctly.
Interpolation Polynomial: The Lagrange interpolation polynomial P(x) is given by the sum of the products of the function values yᵢ and the corresponding Lagrange polynomials:
P(x) = Σ [ yᵢ * Lᵢ(x) ] for i = 0 to n-1
The uniqueness of Interpolation: Lagrange interpolation guarantees the uniqueness of the polynomial of degree at most n-1 that interpolates the data points. This means that for a given set of data points, only one Lagrange polynomial passes through all of them.
Lagrange interpolation is commonly used for data fitting, function approximation, and generating smooth curves from discrete data points. It is also employed in numerical methods, such as numerical integration and solving differential equations.
While Lagrange interpolation provides an accurate polynomial approximation for well-behaved functions, it can suffer from Runge’s phenomenon when interpolating using high-degree polynomials, leading to oscillations near the edges of the data range.
Newton’s Interpolation:
Newton interpolation is a numerical method to approximate a function using an interpolating polynomial that passes through a given set of data points. It is named after Sir Isaac Newton, who developed the method alongside Gottfried Wilhelm Leibniz in the 17th century. Newton interpolation is widely used in various fields, such as engineering, physics, computer graphics, and numerical analysis.
Divided Difference: The fundamental building block of Newton's interpolation is the concept of “divided difference.” Divided differences are coefficients that represent the slopes of the interpolating polynomial at the data points.
Newton’s Forward Difference Interpolation: In the forward difference interpolation, the divided differences are used to construct the interpolating polynomial in a progressive manner. Given a set of data points (xᵢ, yᵢ), where i = 0 to n-1, the first divided differences are calculated as:
Δyᵢ = yᵢ₊₁ — yᵢ, for i = 0 to n-2
The second divided differences are calculated as:
Δ²yᵢ = Δyᵢ₊₁ — Δyᵢ, for i = 0 to n-3
This process is continued until all divided differences are computed. The interpolating polynomial is then written as:
P(x) = y₀ + Σ [ Δⁱy₀ * Π (x — xⱼ) ] for i = 0 to n-1
Newton’s Backward Difference Interpolation: The divided differences are calculated reversely in the backward difference interpolation. The first divided differences are given by:
Δyᵢ = yᵢ — yᵢ₋₁, for i = 1 to n-1
The second divided differences are calculated as:
Δ²yᵢ = Δyᵢ — Δyᵢ₋₁, for i = 2 to n-1
The interpolating polynomial is then expressed as:
P(x) = yₙ₋₁ + Σ [ Δⁱyₙ₋₁ * Π (x — xⱼ) ] for i = 1 to n-1
The uniqueness of Interpolation: Similar to Lagrange interpolation, Newton interpolation also ensures the uniqueness of the interpolating polynomial of degree at most n-1 that passes through the data points. This means that for a given set of data points, only one Newton polynomial interpolates all of them.
Newton interpolation is commonly used for data fitting, function approximation, and generating smooth curves from discrete data points. It is particularly useful when additional data points are added incrementally.
- *Condition number is the ratio of relative change in output to changes in input, denoted by K(A)=||A^(-1)||*||A||
That’s it for today❤
Next week I’ll be back with more content, till then BBye!!
