Linear Regression, Closed Form

Gradient descent finds the best-fitting line by walking downhill. For ordinary linear regression you don't have to walk at all — there's an exact formula that lands on the answer in one step.

It's called the normal equation:

The only setup it needs is a column of 1s glued to the front of your features. That extra column is what lets the model have an intercept: its coefficient is the value the line predicts when every real feature is zero.

Task: write fit_linear(X, y) returning [intercept, coef_1, coef_2, ...], each rounded to 4 decimal places.

• X is a list of rows, each row holding that example's features (without the column of ones — you add that yourself). y is the list of targets.
• The returned list starts with the intercept, followed by one coefficient per feature, in the same order as the columns of X.
• There are always more rows than features and no duplicate columns, so $X^T X$ is always invertible.
• NumPy is available. np.linalg.solve(A, b) solves $A\beta = b$ and is both faster and numerically steadier than building an explicit inverse with np.linalg.inv.

When the data lies exactly on a line, this returns that line's slope and intercept with no error at all — which makes it a very satisfying thing to test.