Module 2 -- Interpolation

1. Newton's forward and backward interpolation

🔢 Sample Dataset (Equally Spaced x-values)

✅ This is based on $f(x)=x^3$, which makes checking your results easy.

• Newton’s Forward Interpolation to estimate $f(2.4)$
• Newton’s Backward Interpolation to estimate $f(4.6)$

Step 1: Build the difference table

and the step size $h=1$, since the gap between the $x$ values = 1.

Step 2: Find $p$

For forward interpolation, we choose :

So, for $f(2.4)$, $x=2.4$, and $x_0$ is the first entry in the table, $1$.

$\therefore p=1.4$.

For backward interpolation, we choose:

for $f(4.6)$, $x=4.6$ and $x_n$ is the last entry in the table, $5$.

$\therefore p=-0.4$

Step 3: Forward and Backward Interpolation

Forward Interpolation formula:

So,

Backward Interpolation formula

So,

If you apply both the values of $2.4$ and $4.6$ to $f(x)=x^3$ , you can verify that the answers are correct.

2. Lagrange Interpolation and Newton's Divided Difference Interpolation

The formula

Given a set of n+1 data points:

$(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)$,

the Lagrange interpolation polynomial $P(x)$ is given by:

where the Lagrange basis polynomial $L_j(x)$ is defined as:

Let's practice an example to clear this up.

📊 New Dataset (Unequally spaced x-values):

Find $f(5)$ using Lagrange Interpolation.

Or better yet we can write the dataset like this:

which can be considered pairs of the following format:

Step 1: Create the Lagrange Polynomials

• Hide $x_0$. Then the polynomial should be like this.

In the denominator write the same terms but replace $x$ with the hidden value, in this case, $x_0$, then multiply the entire fraction by the corresponding $f(x)$ value

• Hide $x_1$

• Hide $x_2$

• Hide $x_3$

For $x=5$,

We put $5$ in place of $x$ and add up all the Lagrange polynomials.

So,

Using Newton's Divided Difference Interpolation

So again we have the dataset.

Step 1: Build the difference table

Then use this formula:

So,

Module 3 -- Numerical Integration

1. Trapezoidal Rule

• Formula:

All terms except the first and last one are multiplied by 2.

Approximate the value of:

with 4 sub-intervals

Step 1: Find step size $h$

$n=4$ subintervals, $b=2$, $a=1$

Step 2: Calculate $x_i$ values

Step 3: Evaluate the values for $f(x_i)$

1. $f(1)=\ln (1)=0$
2. $f(1.25)=ln(1.25)=0.2231$
3. $f(1.5)=\ln (1.5)=0.4054$
4. $f(1.75)=\ln (1.75)=0.5596$
5. $f(2)=ln(2)=0.693$

Step 4: Apply Trapezoidal rule.

2. Simpson's $\frac{1}{3}rd$ rule

• Formula:

All terms besides the first and last ones are multiplied by constants. Odd terms are multiplied by 4, even terms are multiplied by 2.

Approximate the value of:

till $n=6$ subintervals

Step 1: Find $h$

Step 2: Calculate $x_i$ values

Step 3: Calculate $f(x_i)$ values

• $f(0)=1$
• $f(1)=0.5$
• $f(12)=0.00689$
• $f(18)=0.00307$
• $f(24)=0.00173$
• $f(30)=0.00110$
• $f(36)=0.00077$

Step 4: Apply formula

Module 5 -- Solutions to a non-linear algebraic equation

1. The Bisection Method

Algorithm

1. Initial Bracket: Choose $a$ and $b$ so that $f(a)\cdot f(b)<0$.
2. Midpoint: Compute the midpoint $c=\frac{a+b}{2}$​.
3. Test Sign:
   • If $f(c)=0$ (or is close enough to zero), then $c$ is the root.
   • If $f(a)\cdot f(c)<0$, set $b=c$; otherwise, set $a=c$.
4. Repeat: Continue the process until the interval $[a,b]$ is sufficiently small or until the error is less than a predetermined tolerance (or till c stops changing).

• Given Equation:

Let's go with the classic combination of 1,-1

$f(1)=-2$
$f(-1)=-4$

Their product is not less than zero, so we need another separate interval.

Let's try (1, 2)

$f(2)=4$

And, $f(1)\times f(2)=-8$

So, we have a valid interval as $a=1$, $b=2$

So we find the midpoint $c=\frac{1+2}{2}=1.5$

and $f(1.5)=-0.125$

So far, we have had:

Let's continue this till the value of $c$ stops changing, which would probably take 10-15 iterations.

$f(c)\times f(a)>0$ , set a = c

After 17 iterations, the midpoint $c$ has stopped changing till 4 decimal places and $f(c)$ is really close to zero, which is good enough, so the most precise real root for this equation is $1.521355567$.

2. The Regula-Falsi Method

Algorithm

We start off similar to how we do in the Bisection Method

1. Initial Bracket: As with bisection, choose $a$ and $b$ so that $f(a)\cdot f(b)<0$, that is, $a$ and $b$ should have opposite signs.
2. Interpolation: Compute the new estimate using the formula:

3. Test sign:
   • If $f(c)=0$ (or is close enough to zero), then $c$ is the root.
   • Otherwise, if $f(a)\cdot f(c)<0$, set $b=c$, else set $a=c$

This method should get the root faster than the bisection method.

For the same equation:

We know already know the intervals, 1 and 2.

and $f(a)=-2$, $f(b)=4$

Compute $c$.

$f(c)=f(1.33)=-0.977$

$f(c)\times f(a)=1.954,>0$

We see that $c$'s first 4 decimal places are now consistent, and $f(c)$ is very close to zero, which is good enough.

So the most precise real root is $1.52137969$.

3. Newton-Raphson Method

1. Initial Guess: Start with an initial guess $x_0$​.

2. Iteration: Compute the next approximation using:

   $$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}\$\$$$

Taking the same equation again,

And the derivative of this function is:

Let's keep the initial guesses:

$f(1)=-2$, $f(2)=4$

Now we choose $x_0$ as the value whose $f(x_0)$ is closest to zero.

A general rule of thumb is to take the midpoint between the two initial guesses if one of the guesses' $f(x)$ value is close to zero.

So, $x_0=\frac{1+2}{2}=1.5$

So, $f(1.5)=0.875$

and $f^{\prime }(1.5)=5.75$

Let's continue this till $n=5$

So, $x_1$:

For $x_2$:

For $x_3$:

For $x_4$:

For $x_5$:

Again we see that the value repeats till 5 decimal places, so we stop the process here.

The most precise real root is: $1.521379707$.

Module 6 -- Solutions to an ODE.

1. Euler's Method

Formula

If you know $y(t_n)$ and want to compute $y(t_{n+1})$ with a step $h$:

Note that we only calculate the derivative of $f(t_n,y_n)$ if $f$ is an explicit equation. If it's an ODE we just use the function directly.

And it requires very small step sizes.

Given ODE:

and $y(0)=1$

Given step size: $h=0.1$

• Find $y(0.1)$ and $y(0.2)$

So, we make a table like this:

• At $n=0$

where $x_n$ keeps on adding itself by $h$.

So, we found $f(0.1)=1.1$

Let's continue till $n=2$

So,

And $f(0.2)=1.22$

2. Runge-Kutta 2nd Order (RK2)

This method is used for 2nd order differential equations.

This is based upon Euler's method by modifying it.

(obtained by using Euler's method)

then, we use this to get :

For the same ODE:

with step size $h=0.1$

So,

For $y_1$ :

(from Euler's method).

Now:

$x_1=x_0+h=0.1$

So, $f(0.1)=1.11$

Now,

(from euler's method)

So, $f(0.2)=1.2415$

Notice the precision difference?

It gets even more precise in RK4.

Runge-Kutta 4th Order (RK4)

Builds on RK2:

We calculate these 4 stuff first.

And finally :

To not overly confuse you, let's just stick to the previously used:

with step size $h=0.1$

and $f(0)=1$

So, $x_0=0$ and $y_0=1$.

So,:

Next,

Next,

Finally

which is now much more precise than RK2.

Now for $x=0.2$

Next,

Next,

Finally,

which even more precise than RK2.

4. Predictor-Corrector's method

1. Heun's Method.

We’ll look at Heun’s method, a simpler Predictor-Corrector pair (especially good for exams):

It's a 2-step process and a bit similar to RK2.

Step 1: Predictor (Euler's estimate):

Step 2: Corrector (Average slope):

Yeah, it's exactly the same as RK2.

Finite Difference method.

FDM converts differential equations into algebraic equations by replacing derivatives with finite differences.

We commonly solve second-order ODEs like:

We do that using the following formula:

This gives us a system of linear equations which we can solve using methods like Gauss elimination or LU factorization.

The number of values we can find out depends on the internal points — the ones between the boundary conditions.

For example:

with step size $h=0.25$ and a chosen interval [0, 1]

So, the number of points we can have:

Only 4 points.

And we have the boundary values known.

Unknown values:

• $y(x_1)$
• $y(x_2)$
• $y(x_3)$

and $h^2=0.0625$

So, for $x_1,i=1$

• $$y_0-2y_1+y_2=-2y_1+y_2$$

and $$-h^2 \ \times \ x_i \ = \ -(0.00625 \ \times \ 0.25)$$

So we get an equation :

• For $x_2,i=2$

• For $x_3,i=3$

Now if we solve these three equations we can get all the intermediate values.

That can be done using any of the matrix equation solving methods.