1
$\begingroup$

I have the following overdetermined linear equation system:

$Ax=b$

where $A$ is a matrix of $n \times k$, $x$ is of $k \times 1$,$b$ is of $n \times 1$, where $n>k$.

We all know this is an overdetermined linear equation system.

The question is how to check whether the solve for $x$, and check that the vector is consistent in this case? Consistent as in the sense that when we plug in the $x$ vector value into the above linear equation systems, then the above matrix will be satisfied.

I can separate out the $k$ linear equations and find $x$ from $x_1$ to $x_k$, and then substitute in the remaining equations to check for consistency.

I afraid that this method can be numerically unstable; I would like to implement this on a computer, so I would prefer a solution that fully works here. Let us consider one pitfall of my above solution:

$A=\begin{bmatrix} 10 & 10 \\ 0 & 0 \\0 & 10 \end{bmatrix}$

Note that if you separate the $1$ and $2$ rows out, and compute the solution, you may not be able to even solve it ( equation $2$ is an equation here with no unknown terms, after you times in the $0$ factor)!

Is there other method?

  • 1
    You can still swap rows. Gaussian elimination routines generally swap rows for stability purposes anyway. Look up "partial pivoting".2010-12-15

3 Answers 3

4

Updated according to comments.

If you are worried about the numerical stability do QR decomposition of matrix $A$. Then $A=QR$, where $Q$ is orthogonal and $R$ is triangular. Then you need to check whether $x$ satisfies the equation

$Rx=Q^Tb$

Now since $R$ is triangular and $n>k$ we will have that the last $n-k$ rows of $R$ are zero. Since $Ax=b$ it follows that the last $n-k$ elements of $Q^Tb$ should be zero also. If they are not, then $x$ is not a solution.

Furthermore since we have an overdetermined matrix the solution exists only if $b$ lies in the linear space spanned by columns of $A$. So the real question is, how do we reliably check whether $b$ is in linear space spanned by columns of $A$.

Update 2

Since $n>k$, the $R$ matrix will look like:

\begin{align*} R=\begin{bmatrix} R_1\\ 0 \end{bmatrix} \end{align*} where $R_1$ is $k\times k$ upper triangular matrix. If the solution exists, then

\begin{align*} Q^Tb=\begin{bmatrix} b_1\\ 0 \end{bmatrix} \end{align*} where $b_1$ is $k\times 1$ vector. The solution for our system is then $x=R_1^{-1}b_1$

  • 0
    Matrix $A$ dimension is $n\times k$, matrix $Q$ dimension is $n\times n$, matrix $R$ dimension is $n\times k$. Vector $x$ dimension is $k\times 1$, vector $b$ dimension is $n\times 1$, so $Rx$ dimension is $n\times 1$, and $Q^Tb$ dimension is $n\times 1$. Everything is ok.2010-12-16
0

I am not sure why I cannot comment, but anyway, you can always do an RREF and then you should be fine.

  • 0
    perform a GJ elimination to solve for x2010-12-15
0

Consider the related least squares question: find x minimizing $||Ax-b||_2$. In the unlikely scenario that the overdetermined system has a solution, then we in fact have $||Ax-b||_2=0$.

The x solving the least squares problem can be found via the Moore-Penrose pseudoinverse:

$x=(A^tA)^{-1}A^tb$

So, one algorithm would be as follows:

1) Solve $(A^tA)x=A^tb$ via your favorite linear solver.

2) Check if $Ax-b=0$.

  • 0
    Krylov methods are appropriate only for large sparse systems. For small dense problems, QR and SVD remain standard.2010-12-16