Finding a line of approximation using the normal equations for $A\vec{x}=\vec{b}$

64 Views Asked by At

To find the line $y=ax+b$ that best approximates the data points $\{(-2,3),(0,5),(1,7)\}$ I need to use the equation

$$A\vec{x}=\vec{b}\ \ \ (\mbox{where}\ \vec{x}=\left({a\atop b}\right))$$

Then use the normal equation

$$A^TA\vec{x}=A^T\vec{b}\ \ \rightarrow\ \ \vec{x}=(A^TA)^{-1}(A^T\vec{b})$$

  • Given the points above how do I construct a matrix $A$ and a vector $\vec{b}$ ?
  • Is there a name for this process of find an equation of a line ?
2

There are 2 best solutions below

0
On

Here is the classical least squares line fit.

We want to minimize $$ \sum_{i=1}^n\left|ax_i+b-y_i\right|^2\tag{1} $$ To do this, we consider the varying $a$ and $b$ and look for stationary points: $$ \begin{align} 0 &=\frac{\partial}{\partial a}\sum_{i=1}^n\left|ax_i+b-y_i\right|^2\\ &=2\sum_{i=1}^n\left(ax_i+b-y_i\right)x_i\\ \sum_{i=1}^nx_iy_i &=a\sum_{i=1}^nx_i^2+b\sum_{i=1}^nx_i\tag{2} \end{align} $$ and $$ \begin{align} 0 &=\frac{\partial}{\partial b}\sum_{i=1}^n\left|ax_i+b-y_i\right|^2\\ &=2\sum_{i=1}^n\left(ax_i+b-y_i\right)\\ \sum_{i=1}^ny_i &=a\sum_{i=1}^nx_i+bn\tag{3} \end{align} $$ Thus, we want to solve $$ \begin{bmatrix} \sum_{i=1}^nx_i^2&\sum_{i=1}^nx_i\\ \sum_{i=1}^nx_i&n \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix} = \begin{bmatrix} \sum_{i=1}^nx_iy_i\\ \sum_{i=1}^ny_i \end{bmatrix}\tag{4} $$ for $a$ and $b$.


Note that if we write $$ A=\begin{bmatrix} x_1&1\\ x_2&1\\ \vdots&\vdots\\ x_n&1 \end{bmatrix} \quad \text{and} \quad \vec{b}=\begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_n \end{bmatrix}\tag{5} $$ then $(4)$ becomes $$ A^TA\begin{bmatrix}a\\b\end{bmatrix}=A^T\,\vec{b}\tag{6} $$

0
On

As John said in the comments, this method is known as Least Square Fitting. In this case, think of how matrix multiplication works, and consider the point $(c, d)$. You would have $cx + b = d$. So, in your question, the matrix $A$ would be $$ \left[ \begin{array}{rr} -2 & 1\\ 0 & 1\\ 1 & 1 \end{array} \right] $$ and your $\vec{b}$ would be the $y$-values. $$ \left[\begin{array}{r} 3\\ 5\\ 7 \end{array} \right] $$ Afterwards, it is simple to solve $A^tA\vec{x} = A^t\vec{b}$ through Gaussian elimination.