Polynomial Fit Coefficients

Compute quadratic regression coefficients from a list of points using least squares.

least-squares linear-algebra polynomial regression normal-equations

Given a list of points as tuples (x, y), write a function `polyfit_coefficients(points: list[tuple[float, float]]) -> list[float]` that returns the coefficients of the degree-2 polynomial (quadratic) that best fits those points in the least-squares sense. The returned list should be the coefficients of the polynomial \[ c_0 + c_1 x + c_2 x^2 \] starting with the constant term. Use the normal equations approach to solve for the coefficients. The input will contain at least 3 points, and there will be no two points with the same x. The data will be such that the system has a unique solution. Round each coefficient to 6 decimal places before returning.

Constraints

- Input length n >= 3.
- All x values are distinct.
- The system is well-conditioned enough for a unique quadratic fit.
- Coordinates are real numbers.
- Complexity: O(n) time and O(1) extra space.

Example

```python
>>> polyfit_coefficients([(0, 1), (1, 2), (2, 3)])
[1.0, 1.0, 0.0]
>>> polyfit_coefficients([(-1, 1), (0, 0), (1, 1)])
[0.0, 0.0, 1.0]
>>> polyfit_coefficients([(0, 1), (1, 2), (2, 4)])
[1.0, 0.5, 0.5]
```

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Set up the normal equations A^T A c = A^T y where each row of A is [1, x, x^2].

Compute the sums: n, sum(x), sum(x^2), sum(x^3), sum(x^4), sum(y), sum(x*y), sum(x^2*y).

Solve the resulting 3x3 linear system using Cramer's rule or an equivalent method.

Round each coefficient to 6 decimal places before returning the list.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.