Interpolation Calculator

def linear_interpolate(x1, y1, x2, y2, x):
    """Linear interpolation between two points."""
    if x2 == x1:
        raise ValueError("x1 and x2 must be different")
    return y1 + (x - x1) * (y2 - y1) / (x2 - x1)

def lagrange_interpolate(points, x):
    """Lagrange polynomial interpolation.
    points: list of (x, y) tuples.
    Returns the estimated y value at x.
    """
    n = len(points)
    result = 0.0
    for i in range(n):
        xi, yi = points[i]
        basis = 1.0
        for j in range(n):
            if i != j:
                xj, _ = points[j]
                basis *= (x - xj) / (xi - xj)
        result += yi * basis
    return result

def newton_divided_diff(points):
    """Newton's divided differences table."""
    n = len(points)
    coef = [y for _, y in points]
    xs = [x for x, _ in points]
    for j in range(1, n):
        for i in range(n - 1, j - 1, -1):
            coef[i] = (coef[i] - coef[i - 1]) / (xs[i] - xs[i - j])
    return coef

# Examples
print(linear_interpolate(0, 0, 10, 100, 5))  # 50.0

pts = [(1, 1), (2, 4), (3, 9), (4, 16)]  # y = x²
print(f"Lagrange at x=2.5: {lagrange_interpolate(pts, 2.5):.4f}")  # 6.25