Mastering Algorithms with C

Implementation and Analysis of Least-Squares Estimation

The implementation of least-squares estimation presented here requires us to do little more than compute a few summations and apply the results to the formulas presented earlier. The operation begins by summing all values for x_i in sumx, all values for y_i in sumy, all values of x_i ² in sumx2, and all values of x_i y_i in sumxy (see Example 13-2). Once we have completed this, we compute b ₁ and b ₀ using the formulas presented earlier.

The runtime complexity of lsqe is O (n), where n is the number of points used to determine b ₁ and b ₀. This is because a single loop that iterates n times is used to compute the summations.

Example 13.2. Implementation of Least-Squares Estimation

/***************************************************************************** * * * -------------------------------- lsqe.c -------------------------------- * * * *****************************************************************************/ #include <math.h> #include "nummeths.h" /***************************************************************************** * * * --------------------------------- lsqe --------------------------------- * * * *****************************************************************************/ void lsqe(const double *x, const double *y, int n, double *b1, double *b0) { double sumx, sumy, sumx2, sumxy; int i; /***************************************************************************** * * * Compute the required summations. ...