<jupyter_start><jupyter_text>Polynomial InterpolationWe know that if we have a set of $n$ data points with coordinates $(x_1; y_1), (x_2; y_2), \dots, (x_n; y_n)$, we can try to figure out what function may have generated these points.Please note that **our assumptions about the data** will lead us to choosing one function over another. This means that our results are as good as our data and assumptions. Therefore, it's extremely important that we write down our assumptions (which sometimes can be difficult as we sometimes don't realize we're making them). It will be better for our readers if they know what those assumptions and models are.In this case, we'll state two assumptions:1. The points in our dataset are generated by a polynomial function2. The points are very precise, there is absolutely no error in them. This means that the function should pass **through every point**This method is called *polynomial interpolation* (*"polynomial"* captures assumption 1 and *"interpolation"* captures assumption 2).It can be proved (look at [Wikipedia](https://en.wikipedia.org/wiki/Polynomial_interpolation) for example) that if we have $n$ data points, there is only one polynomial of degree $n-1$ which passes through them. In "math speak": "the vector spaces of $n$ points and polynomials of degree $n-1$ are isomorphic (there exists a bijection mapping one to the other)".There are a lot of ways to do interpolation. We can also write the function ourselves if we want but this requires quite a lot more knowledge than we already covered in this course. So we'll use a function which does this for us. `numpy.polyfit()` is one such function. It accepts three main parameters (there are others as well, but they are optional): a list of $x$ coordinates, a list of $y$ coordinates, and a polynomial degree.Let's say we have these points:```pythonpoints = np.array([(0, 0), (1, 0.8), (2, 0.9), (3, 0.1), (4, -0.8), (5, -1.0)])```First, we need to "extract" the coordinates:```pythonx = points[:, 0]y = points[:, 1]```Then, we need to calculate the interpolating polynomial. For the degree, we'll set $n-1$:```pythoncoefficients = np.polyfit(x, y, len(points) - 1)poly = np.poly1d(coefficients)```After that, we need to plot the function. To do this, we'll create a range of $x$ values and evaluate the polynomial at each value:```pythonplot_x = np.linspace(np.min(x), np.max(x), 1000)plot_y = poly(plot_x)```Finally, we need to plot the result. We'll plot both the fitting polynomial curve (using `plt.plot()`) and the points (using `plt.scatter`). It's also nice to have different colors to make the line stand out from the points.```pythonplt.plot(plot_x, plot_y, c = "green")plt.scatter(x, y)plt.xlabel("x")plt.ylabel("y")plt.show()```Don't forget to label the axes!Your task now is to **wrap the code in a function**. It should accept a list of points, the polynomial degree, min and max value of $x$ used for plotting. **Be extremely careful to ensure that the function uses its parameters!**We'll use this function to try some other cases.<jupyter_code>import numpy as np
import numpy.polynomial.polynomial as p
import matplotlib.pyplot as plt

"""
Polynomial Interpolation - Interpolates a polynomial of the specified degree through the given points and plots it
points - a list of points (x, y) to plot
degree - the polynomial degree
min_x, max_x - range of x values used to plot the interpolating polynomial
"""
def interpolate_polynomial(points, degree, min_x, max_x):
    x = points[:, 0]
    y = points[:, 1]
    coefficients = np.polyfit(x, y, degree)
    polynomial = np.poly1d(coefficients)
    plot_x = np.linspace(min_x, max_x, 1000)
    plot_y = polynomial(plot_x)
    
    plt.plot(plot_x, plot_y, c = "green")
    plt.scatter(x, y)
    plt.xlabel("x")
    plt.ylabel("y")
    plt.show()

    pass
points = np.array([(0, 0), (1, 0.8), (2, 0.9), (3, 0.1), (4, -0.8), (5, -1.0)])
interpolate_polynomial(points, len(points) - 1, np.min(points[:, 0]), np.max(points[:, 0]))<jupyter_output><empty_output><jupyter_text>We see this is a very nice fit. This is expected, of course. Let's try to expand our view a little. Let's try to plot other values of $x$, further than the original ones. This is **extrapolation**.<jupyter_code>interpolate_polynomial(points, len(points) - 1, -5, 10)<jupyter_output><empty_output><jupyter_text>Hmmm... it seems our polynomial goes a little wild outside the original range. This is to show how **extrapolation can be quite dangerous**.Let's try a lower polynomial degree now. We used 4, how about 3, 2 and 1?**Note:** We can add titles to every plot so that we know what exactly we're doing. Te title may be passed as an additional parameter to our function.<jupyter_code>interpolate_polynomial(points, 3, np.min(points[:, 0]), np.max(points[:, 0]))
interpolate_polynomial(points, 2, np.min(points[:, 0]), np.max(points[:, 0]))
interpolate_polynomial(points, 1, np.min(points[:, 0]), np.max(points[:, 0]))<jupyter_output><empty_output><jupyter_text>We see the fitting curves (or line in the last case) struggle more and more and they don't pass through every point. This breaks our assumptions but it can be very useful.Okay, one more thing. How about increasing the degree? Let's try 5, 7 and 10. Python might complain a little, just ignore it, everything is fine... sort of :).<jupyter_code>interpolate_polynomial(points, 5, np.min(points[:, 0]), np.max(points[:, 0]))
interpolate_polynomial(points, 7, np.min(points[:, 0]), np.max(points[:, 0]))
interpolate_polynomial(points, 10, np.min(points[:, 0]), np.max(points[:, 0]))<jupyter_output><empty_output><jupyter_text>Those graphs look pretty much the same. But that's the point exactly. I'm being quite sneaky here. Let's try to expand our view once again and see what our results really look like.<jupyter_code>interpolate_polynomial(points, 5, -10, 10)
interpolate_polynomial(points, 7, -10, 10)
interpolate_polynomial(points, 10, -10, 10)<jupyter_output><empty_output><jupyter_text>Now we see there are very wild differences. Even though the first two plots look quite similar, look at the $y$ values - they're quite different.So, these are the dangers of interpolation. Use a too high degree, and you get "the polynomial wiggle". These are all meant to represent **the same** data points but they look insanely different. Here's one more comparison.<jupyter_code>interpolate_polynomial(points, len(points) - 1, -2, 7)
interpolate_polynomial(points, len(points) + 1, -2, 7)<jupyter_output><empty_output><jupyter_text>Now we can see what big difference even a small change in degree can make. This is why we have to choose our interpolating functions very carefully. Generally, a lower degree means a simpler function, which is to be preferred. See [Occam's razor](https://en.wikipedia.org/wiki/Occam%27s_razor).And also, **we need to be very careful about our assumptions**.<jupyter_code>points = np.array([(-5, 0.03846), (-4, 0.05882), (-3, 0.1), (-2, 0.2), (-1, 0.5), (0, 1), (1, 0.5), (2, 0.2), (3, 0.1), (4, 0.05882), (5, 0.03846)])
interpolate_polynomial(points, 10, np.min(points[:, 0]), np.max(points[:, 0]))<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup