• Choose a category
• All
• Classic-Fiction

By Root 1419 0

this line with the points used to determine it. From the standpoint of least-squares estimation, no other line is a better fit for the data than this one.

Interface for Least-Squares Estimation

Name

lsqe

Synopsis

void lsqe(const double *x, const double *y, int n, double *b1, double *b0);

Return Value

None.

Description

Uses least-squares estimation to obtain b 1 and b 0 in y (x) = b 1 x + b 0 so that y (x) is a best-fit line through a set of points. The x-coordinates of the points are specified in x. The y-coordinates are specified in y. The number of points is specified in n. The operation returns the appropriate values in b1 and b0.

Complexity

O (n), where n is the number of points used in determining b 1 and b 0.

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 xi in sumx, all values for yi in sumy, all values of xi 2 in sumx2, and all values of xi yi in sumxy (see Example 13-2). Once we have completed this, we compute b 1 and b 0 using the formulas presented earlier.

The runtime complexity of lsqe is O (n), where n is the number of points used to determine b 1 and b 0. 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

#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. *

* *

*****************************************************************************/

sumx = 0.0;

sumy = 0.0;

sumx2 = 0.0;

sumxy = 0.0;

for (i = 0; i < n; i++) {

sumx = sumx + x[i];

sumy = sumy + y[i];

sumx2 = sumx2 + pow(x[i], 2.0);

sumxy = sumxy + (x[i] * y[i]);

}

/*****************************************************************************

* *

* Compute the least-squares estimators. *

* *

*****************************************************************************/

*b1 = (sumxy - ((sumx * sumy)/(double)n)) / (sumx2-(pow(sumx,2.0)/(double)n));

*b0 = (sumy - ((*b1) * sumx)) / (double)n;

return;

}

Description of the Solution of Equations

One of the most fundamental problems in scientific computing is solving equations of the form f (x) = 0. This is often referred to as finding the roots, or zeros, of f (x). Here, we are interested in the real roots of f (x), as opposed to any complex roots it might have. Specifically, we will focus on finding real roots when f (x) is a polynomial.

Finding Roots with Newton's Method

Although factoring and applying formulas are simple ways to determine the roots of polynomial equations, a great majority of the time polynomials are of a large enough degree and sufficiently complicated that we must turn to some method of approximation. One of the best approaches is Newton's method. Fundamentally, Newton's method looks for a root of f (x) by moving closer and closer to it through a series of iterations. We begin by choosing an initial value x = x 0 that we think is near the root we are interested in. Then, we iterate using the formula:

until xi + 1 is a satisfactory approximation. In this formula, f (x) is the polynomial for which we are trying to find a root, and f ' (x) is the derivative