I'm currently creating a program for a class that uses linear algebra to perform linear and non-linear regression. using $\hat{x} = (A^T*A)^{-1}*A^T*Y$. If i have n points, I should be able to find a polynomial that fits those n points of order n-1. For example if I have 4 points I should be able to find a cubic that fits those 4 points.
If I have 4 points, but two of those lie on the same x coordinate, I get:
$A = \begin{bmatrix}1 & 1 & 1 & 1\\1 & 2 & 4 & 8 \\ 1 & 3 & 9 & 27 \\ 1 & 3 & 9 & 27\end{bmatrix}$
If we then multiply this by $A^T$ I get:
$A^TA = \begin{bmatrix} 4 & 9 & 23 & 63 \\ 9 & 23 & 63 & 179 \\ 23 & 63 & 179 & 519 \\ 63 & 179 & 519 & 1523 \end{bmatrix}$
However, you may notice this matrix is singular, meaning I cannot find the inverse I need to perform the regression.
Is there any way around this or will I have to implement a different method of non-linear regression?