0
$\begingroup$

I am studying linear alegbra and came across over-determined system(https://en.wikipedia.org/wiki/Overdetermined_system) By plotting it makes sense that it may not have solution in most cases. But intuitively I can't understand it.

It seems to me as if there is more information and lesser unknowns. Then should there be a problem to find the solution.

$\endgroup$
  • $\begingroup$ Not more information. Less freedom (=number of variables) and more constraints! (=equations) $\endgroup$ – Peter Franek Nov 5 '16 at 19:21
1
$\begingroup$

Let $$ A x = b $$ the system, with $A \in \mathbb{R}^{m \times n}, x \in \mathbb{R}^n, b \in \mathbb{R}^m$. This is equivalent to $m$ equations in $n$ dimensions $$ \alpha_i \cdot x = \beta_i $$ which for $\alpha_i \ne 0$ can be interpreted as the equation of an affine hyper plane (a plane with dimension $n-1$, not necessarily through the origin) with normal vector $\alpha_i$ and (signed) distance $d = \beta_i / \lVert \alpha_i \rVert$ to the origin.

The solution to the system must lie in the intersection of all the $m$ hyperplanes.

For $n=2$ the hyperplanes are one-dimensional, thus lines.

And the images illustrate nicely the more random lines you add, the less likely it gets that there is a common intersection point to all lines.

$\endgroup$
1
$\begingroup$

It seems to me as if there are more information and lesser unknowns. Then should there be a problem to find the solution.

In general it is the opposite. Suppose you have the linear equation system

$x+y=15$

$x-y=5$

$2y=x$

This is an overdetermind equation system. If a solution exist, then you need only two of the three equations to solve the system. You can use the first two equations.

$x=15-y$

Inserting the expression for x into the second equation.

$(15-y)-y=5$

$15-2y=5$

$10=2y$

$y=5$

And from the equtions 1 or 2 your get $x=10$.

Firnally you have to prove if the third equation holds with these values.

$2\cdot 5=10$

This is true.

If you would have 3 equations and 3 variables then it is in general more time consuming to find a solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.