The straight line of Level 3 is too stiff for data that curves. A polynomial of degree d, w0 + w1·x + w2·x² + ... + wd·x^d, can bend, and it is still a linear model: a dot product of the weights with the features [1, x, x², ..., x^d].
Write fit_poly(xs, ys, degree) that returns the list of weights [w0, w1, ..., w_degree] (floats) that minimises the total squared error Σ (w0 + w1·xs[i] + ... + w_degree·xs[i]^degree - ys[i])².
The setup provides make_wave(n, seed), which returns (xs, ys): n noisy observations of sin(3x) for x between -1 and 1. Some tests use it.
Examples
Input: xs = [0, 1, 2], ys = [1, 3, 5], degree = 1
Output: [1.0, 2.0]
Explanation: the three points lie on the line y = 1 + 2x.
Input: xs = [-1, 0, 1, 2], ys = [2, 1, 2, 5], degree = 2
Output: [1.0, 0.0, 1.0]
Input: xs = [1, 2, 3, 4], ys = [2, 4, 4, 5], degree = 0
Output: [3.75]
Explanation: the best constant is the mean.
Constraints
0 <= degree <= 6,len(xs) > degree, andxscontains more thandegreedistinct values, so the answer is unique-10 <= xs[i] <= 10,len(xs) <= 500- floats are compared with a tolerance of
1e-6
Goals
- Turn one input into the features 1, x, x², ..., x^d, so a curve becomes a linear model
- Find the least-squares weights of a linear model with several features by solving a linear system
- Implement elimination with pivoting and back substitution