newton_polynomial_interpolation

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Filename: newton_polynomial_interpolation.py
# Version: 1.0.0
# Author: Jeoi Reqi

"""
Description:
    - This script demonstrates polynomial interpolation using Newton's divided differences method.
    - It allows users to input their own data points and visualizes the interpolating polynomial.

Requirements:
    - Python 3.x
    - NumPy
    - Matplotlib

Functions:
    - newtdd:
        Computes coefficients of interpolating polynomial using Newton's divided differences method.
    - nest:
        Evaluates the interpolating polynomial at a specific point.
    - newton_poly:
        Evaluates the Newton polynomial at specific points.
    - main:
        Main function to execute polynomial interpolation.

Usage:
    - Run the script and follow the prompts to input data points.

Expected Example Output:
    - The script will plot the interpolating polynomial along with the data points provided by the user.

Additional Notes:
    - Ensure NumPy and Matplotlib are installed in your Python environment.
"""

import numpy as np
import matplotlib.pyplot as plt

def newtdd(x_values, y_values, n):
    """
    Calculate coefficients of interpolating polynomial using Newton's divided differences method.

    Parameters:
        x_values (ndarray):
            Array of x-coordinates of data points.
        y_values (ndarray):
            Array of y-coordinates of data points.
        n (int):
            Number of data points.

    Returns:
        ndarray: Coefficients of the interpolating polynomial.
    """
    v = np.zeros((n, n))
    for j in range(n):
        v[j][0] = y_values[j]
    for i in range(1, n):
        for j in range(n - i):
            v[j][i] = (v[j+1][i-1] - v[j][i-1]) / (x_values[i+j] - x_values[j])
    return v[0]

def nest(c, x_values, t):
    """
    Evaluate the interpolating polynomial at a specific point.

    Parameters:
        c (ndarray):
            Coefficients of the interpolating polynomial.
        x_values (ndarray):
            Array of x-coordinates of data points.
        t (float):
            Point at which to evaluate the polynomial.

    Returns:
        float: Value of the polynomial at point t.
    """
    n = len(c)
    result = c[-1]
    for i in range(2, n+1):
        result = result * (t - x_values[n-i]) + c[n-i]
    return result

def newton_poly(coef, x_data, x):
    """
    Evaluate the Newton polynomial at x.

    Parameters:
        coef (ndarray):
            Coefficients of the interpolating polynomial.
        x_data (ndarray):
            Array of x-coordinates of data points.
        x (ndarray):
            Points at which to evaluate the polynomial.

    Returns:
        ndarray: Value of the polynomial at points x.
    """
    n = len(x_data) - 1
    p = coef[n]
    for k in range(1, n + 1):
        p = coef[n-k] + (x - x_data[n-k]) * p
    return p

def main():
    """
    Main function to execute polynomial interpolation.
    """
    print("Welcome to Polynomial Interpolation using Newton's divided differences method!")
    n = int(input("\nEnter the number of data points: "))
    x_values = np.zeros(n)
    y_values = np.zeros(n)
    print("\nEnter the data points:")
    for i in range(n):
        x_values[i] = float(input(f"Enter x{i+1}: "))
        y_values[i] = float(input(f"Enter y{i+1}: "))

    coefficients = newtdd(x_values, y_values, n)

    # Evaluate the interpolating polynomial at specific points
    x_new = np.linspace(min(x_values), max(x_values), 500)
    y_new = nest(coefficients, x_values, x_new)

    # Plot the results
    plt.plot(x_new, y_new, label='Interpolating Polynomial')
    plt.scatter(x_values, y_values, color='red', label='Data Points')
    plt.xlabel('x')
    plt.ylabel('y')
    plt.title('Newton Polynomial Interpolation')
    plt.legend()

    # Annotate each data point with its corresponding coordinates
    for i, (x, y) in enumerate(zip(x_values, y_values)):
        plt.text(x, y, f'({x}, {y})', fontsize=10, ha='right', va='bottom')

    plt.grid(True)
    plt.show()

if __name__ == "__main__":
    main()