Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 37 ยท Interpolation and Curve Fitting

Least Squares Curve Fitting

Fit lines, polynomials and nonlinear models to noisy data with least squares. Normal equations, QR and lstsq, then SciPy's curve_fit, with working code.

Real measurements are noisy. Forcing a curve to pass through every point (interpolation) copies the noise. Least squares instead chooses a simple model, such as a line or a quadratic, and finds the parameters that make the model as close as possible to all the data at once, where "close" means the smallest sum of squared residuals.

This lesson covers linear least squares (which includes polynomial fitting), three ways to solve it, how to judge a fit, and nonlinear least squares with scipy.optimize.curve_fit.

The problem

Given data (xi, yi) and a model y = c1 f1(x) + ... + cm fm(x) that is linear in the unknown coefficients cj, build the design matrix A with A[i, j] = fj(xi). We want c that minimizes

|| A c - y ||^2 = sum of (residual_i)^2

For a straight line, f1 = 1 and f2 = x. For a quadratic add f3 = x^2. The model may be curved in x; "linear" refers to the coefficients. Even c1 + c2 sin(x) + c3 exp(x) is a linear least-squares problem.

Normal equations

Setting the gradient to zero gives A^T A c = A^T y. Solve this small m x m system and you have the fit.

Python Fit a line with the normal equations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why the normal equations can be dangerous

Forming A^T A squares the condition number. If A is already sensitive (nodes close together, high degree), the normal equations lose roughly twice as many digits as necessary. Safer methods work on A directly:

  • QR factorization: write A = Q R with orthonormal Q; then solve R c = Q^T y by back substitution.
  • SVD: the most robust, and the one behind np.linalg.lstsq; it also handles rank-deficient problems.
Python Normal equations vs QR vs lstsq

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The condition number of A^T A is the square of that of A, which is why the normal-equation residual is noticeably worse than the other two. In everyday code use np.linalg.lstsq or np.polyfit and forget the normal equations.

Polynomial fits and choosing the degree

np.polyfit(x, y, deg) is a convenience wrapper. A higher degree always lowers the residual on the training data, but that does not mean a better model. Judge a fit with:

  • Residual plots: they should look like random noise. A visible pattern means the model is too simple.
  • R squared: 1 - SS_res / SS_tot, the fraction of variance explained.
  • Held-out data: fit on some points, test on the rest. A degree that fits training data nearly perfectly but misses held-out points is overfitting.
Python Choosing a polynomial degree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The training error keeps falling, while the test error stops improving at the true degree (2) and then wobbles. That gap is the signal to stop.

Nonlinear least squares

When parameters appear inside the model, as in y = a exp(-b x), the problem is nonlinear. There is no closed form, so iterative methods (Gauss-Newton, Levenberg-Marquardt) start from a guess and improve it. SciPy's curve_fit does this and also returns the parameter covariance, whose diagonal square roots are standard errors.

Python Fit an exponential decay with curve_fit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When you can, linearize: fitting log y = log a - b x is a straight-line problem. It weights errors differently from the original problem, so use it as a good starting guess p0 for the true nonlinear fit.

Common mistakes

  • Fitting an exponential or power law with a bad starting guess: nonlinear solvers can converge to the wrong answer or fail.
  • Choosing a high polynomial degree because the training error is low.
  • Extrapolating a fitted polynomial far beyond the data.
  • Ignoring unequal noise: if some points are less reliable, pass sigma to curve_fit (weighted least squares).

See also the earlier lessons on interpolation for the case where data are exact.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is y = c1 + c2sin(x) + c3exp(x) a linear least-squares problem?

    Linear least squares requires linearity in the coefficients, not in x.
  2. 2. What is the main numerical drawback of the normal equations?

    cond(A^T A) = cond(A)^2, so digits are lost; QR or SVD are safer.
  3. 3. Training error keeps dropping as you raise the polynomial degree but test error rises. What is this?

    The model is following the noise in the training data rather than the underlying trend.
  4. 4. What does curve_fit return besides the best parameters?

    pcov estimates parameter uncertainty; the square roots of its diagonal are standard errors.

Summary

  • Least squares minimizes the sum of squared residuals and suits noisy data.
  • Linear least squares is linear in the coefficients, including polynomial models; solve it with QR or lstsq, not the normal equations.
  • Judge fits with residual plots and held-out data, not training error alone.
  • Nonlinear problems use iterative solvers such as curve_fit; give a sensible initial guess.

Next: Numerical differentiation