System of Linear Equations

Overdetermined Linear Equation Systems

Imagine we are trying to fit a curve to a set of data. In many practical cases, we have more data than parameters we want to find. Such situations create what is called overdetermined linear equation systems.

This system has a special characteristic. The number of equations is greater than the number of unknown variables. Mathematically, if we have $m$ equations and $n$ variables, then the condition $m > n$ makes this system "overdetermined".

Real Example with Quadratic Polynomial Model

Let's look at a concrete example. Suppose we have $7$ data points that we want to fit with a parabola or quadratic curve.

The data we have is as follows.

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$t_i$	$-3$	$-2$	$-1$	$0$	$1$	$2$	$3$
$y_i$	$-2.2$	$-4.2$	$-4.2$	$-1.8$	$1.8$	$8.2$	$15.8$

We want to find a parabola with the following form.

y = a_2 \cdot t^2 + a_1 \cdot t + a_0

Here we are looking for $3$ parameters, namely $a_2$ (quadratic coefficient), $a_1$ (linear coefficient), and $a_0$ (constant).

Setting Up the System of Equations

Now, how do we use this data to find the parabola parameters? The idea is simple. For each data point, we can write one equation. With $7$ data points, we will get $7$ equations.

a_2 \cdot (-3)^2 + a_1 \cdot (-3) + a_0 = -2.2

a_2 \cdot (-2)^2 + a_1 \cdot (-2) + a_0 = -4.2

a_2 \cdot (-1)^2 + a_1 \cdot (-1) + a_0 = -4.2

a_2 \cdot 0^2 + a_1 \cdot 0 + a_0 = -1.8

a_2 \cdot 1^2 + a_1 \cdot 1 + a_0 = 1.8

a_2 \cdot 2^2 + a_1 \cdot 2 + a_0 = 8.2

a_2 \cdot 3^2 + a_1 \cdot 3 + a_0 = 15.8

Now let's calculate the square values for each $t_i$ . For example, for $t_1 = -3$ , we have $(-3)^2 = 9$ . Similarly for the others. After calculating everything, our equations become like this.

9a_2 - 3a_1 + a_0 = -2.2

4a_2 - 2a_1 + a_0 = -4.2

1a_2 - 1a_1 + a_0 = -4.2

0a_2 + 0a_1 + a_0 = -1.8

1a_2 + 1a_1 + a_0 = 1.8

4a_2 + 2a_1 + a_0 = 8.2

9a_2 + 3a_1 + a_0 = 15.8

Matrix Form

The system of equations above can be written in matrix form $A \cdot x = b$ .

\begin{pmatrix} 9 & -3 & 1 \\ 4 & -2 & 1 \\ 1 & -1 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ 4 & 2 & 1 \\ 9 & 3 & 1 \end{pmatrix} \begin{pmatrix} a_2 \\ a_1 \\ a_0 \end{pmatrix} = \begin{pmatrix} -2.2 \\ -4.2 \\ -4.2 \\ -1.8 \\ 1.8 \\ 8.2 \\ 15.8 \end{pmatrix}

In general, for a quadratic polynomial model with $m$ data points, the matrix form is as follows.

\begin{pmatrix} t_1^2 & t_1 & 1 \\ \vdots & \vdots & \vdots \\ t_m^2 & t_m & 1 \end{pmatrix} \begin{pmatrix} a_2 \\ a_1 \\ a_0 \end{pmatrix} = \begin{pmatrix} y_1 \\ \vdots \\ y_m \end{pmatrix}

Why There Is No Exact Solution

Now we face an interesting situation. In our example, matrix $A$ has size $7 \times 3$ and vector $x$ has size $3 \times 1$ . This means we have $7$ equations but only $3$ unknown variables.

Does this mean the system cannot be solved? Let's examine this more deeply.

The three columns of matrix $A$ are linearly independent, so the rank of matrix $A$ is $3$ . However, when we add vector $b$ to matrix $A$ to form the augmented matrix $(A|b)$ , its rank becomes $4$ .

This condition tells us something important. This system has no exact solution. In simple terms, there is no single parabola that can pass through all $7$ data points perfectly.

Solution with Least Squares

So what should we do? Give up? Of course not!

When an overdetermined linear equation system has no exact solution, we use the least squares approach. The basic idea makes perfect sense. If we cannot find a parabola that passes through all points, let's find the parabola that is "closest" to all points.

Mathematically, this method seeks parameters that minimize the sum of squared differences between predicted values and observed values. Imagine we draw a parabola, then measure the vertical distance from each data point to that parabola. The least squares method finds the parabola that makes the total squared distances as small as possible.

Overdetermined linear equation systems are very common in the real world, especially when we have many measurement data but a relatively simple model.

The least squares approach provides an optimal solution in the sense of minimizing overall error, making it very practical for engineering and scientific applications.