# Nakafa Learning Content

> For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`.

URL: https://nakafa.com/en/subjects/ai-ds/linear-methods/system-linear-equation
Source: https://raw.githubusercontent.com/nakafaai/nakafa.com/refs/heads/main/packages/contents/material/lesson/ai-ds/linear-methods/system-linear-equation/en.mdx

Solve overdetermined linear systems using least squares method. Learn curve fitting, polynomial models, and matrix solutions for real-world data.

---

## 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".

Visible text: This system has a special characteristic. The number of equations is greater than the number of unknown variables.
Mathematically, if we have equations and variables,
then the condition 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.

Visible text: Let's look at a concrete example. Suppose we have 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$$ |

Visible text: | | | | | | | | |
|---|---|---|---|---|---|---|---|
| | | | | | | | |
| | | | | | | | |

We want to find a parabola with the following form.

```math
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).

Visible text: Here we are looking for parameters, namely (quadratic coefficient),
 (linear coefficient), and (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.

Visible text: 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 data points, we will get equations.

Component: MathContainer
Children:

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

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

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

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

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

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

```math
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.

Visible text: Now let's calculate the square values for each .
For example, for , we have .
Similarly for the others. After calculating everything, our equations become like this.

Component: MathContainer
Children:

```math
9a_2 - 3a_1 + a_0 = -2.2
```

```math
4a_2 - 2a_1 + a_0 = -4.2
```

```math
1a_2 - 1a_1 + a_0 = -4.2
```

```math
0a_2 + 0a_1 + a_0 = -1.8
```

```math
1a_2 + 1a_1 + a_0 = 1.8
```

```math
4a_2 + 2a_1 + a_0 = 8.2
```

```math
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$$.

Visible text: The system of equations above can be written in matrix form .

Component: MathContainer
Children:

```math
\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.

Visible text: In general, for a quadratic polynomial model with data points,
the matrix form is as follows.

Component: MathContainer
Children:

```math
\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.

Visible text: Now we face an interesting situation. In our example, matrix has size 
and vector has size .
This means we have equations but only unknown variables.

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

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$$.

Visible text: The three columns of matrix are linearly independent, so the rank of matrix is .
However, when we add vector to matrix 
to form the augmented matrix , its rank becomes .

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.

Visible text: 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 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.