Linear Systems

Direct and iterative methods for solving systems of linear equations Ax = b

Interactive Visualizer

System: 4x₁ - x₂ + x₃ = 7, 4x₁ - 8x₂ + x₃ = -21, -2x₁ + x₂ + 5x₃ = 15

Solution: x = [2, 4, 3]

Practice Problem

Solve the system using Gaussian elimination:

2x₁ + x₂ - x₃ = 8

-3x₁ - x₂ + 2x₃ = -11

-2x₁ + x₂ + 2x₃ = -3

x₁ =

x₂ =

x₃ =

Matrix & Vector Norms

A vector norm is a function that assigns a non-negative length or size to a vector. For a vector $\mathbf{x} = (x_1, x_2, \ldots, x_n)$ , the three most common norms are:

1-norm (Manhattan / Taxicab)

\|\mathbf{x}\|_1 = \sum_{i=1}^{n} |x_i|

Sum of absolute values of all components.

2-norm (Euclidean)

\|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^{n} x_i^2}

The familiar straight-line distance from the origin.

∞-norm (Maximum / Chebyshev)

\|\mathbf{x}\|_\infty = \max_i |x_i|

The largest absolute value among all components.

Norm Properties (for any valid norm $\|\cdot\|$ )

Non-negativity: $\|\mathbf{x}\| \geq 0$ , and $\|\mathbf{x}\| = 0 \iff \mathbf{x} = \mathbf{0}$
Homogeneity: $\|\alpha \mathbf{x}\| = |\alpha|\, \|\mathbf{x}\|$ for any scalar $\alpha$
Triangle inequality: $\|\mathbf{x} + \mathbf{y}\| \leq \|\mathbf{x}\| + \|\mathbf{y}\|$

Matrix norms extend the concept of vector norms to matrices. The most common induced norms are derived from vector norms via $\|A\| = \max_{\mathbf{x} \neq \mathbf{0}} \frac{\|A\mathbf{x}\|}{\|\mathbf{x}\|}$

1-norm (Maximum Column Sum)

\|A\|_1 = \max_j \sum_i |a_{ij}|

Take the absolute column sums; the largest one is the 1-norm.

∞-norm (Maximum Row Sum)

\|A\|_\infty = \max_i \sum_j |a_{ij}|

Take the absolute row sums; the largest one is the ∞-norm.

Frobenius Norm

\|A\|_F = \sqrt{\sum_i \sum_j a_{ij}^2}

The Frobenius norm is the square root of the sum of all squared entries. It is not an induced norm but satisfies all norm axioms and is submultiplicative.

Interactive Vector Norm Calculator

Enter vector components to compute all three norms in real time.

$\mathbf{x} = (x_1,\, x_2,\, x_3,\, x_4)$

x₁ =

x₂ =

x₃ =

x₄ =

1-norm

\|\mathbf{x}\|_1 = 6.4200

2-norm

\|\mathbf{x}\|_2 = 5.2996

∞-norm

\|\mathbf{x}\|_\infty = 5.1500

Interactive Matrix Norm Calculator

Enter a 2×2 matrix to compute all three matrix norms.

$A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$

a =

b =

c =

d =

1-norm (max col sum)

\|A\|_1 = 10.0000

∞-norm (max row sum)

\|A\|_\infty = 14.0000

Frobenius norm

\|A\|_F = 10.5357

Error in Linear Systems

Given the linear system $A\mathbf{x} = \mathbf{b}$ , let $\bar{\mathbf{x}}$ be an approximate solution. We can quantify and correct the error using the residual vector.

Residual

\mathbf{r} = \mathbf{b} - A\bar{\mathbf{x}}

The residual measures how far $A\bar{\mathbf{x}}$ is from $\mathbf{b}$ . A small residual suggests a good approximation, but a small residual does not always imply a small error — the condition number of $A$ matters.

Error

\mathbf{e} = \mathbf{x} - \bar{\mathbf{x}} = A^{-1}\mathbf{r}

The true error satisfies $A\mathbf{e} = \mathbf{r}$ because $A(\mathbf{x} - \bar{\mathbf{x}}) = A\mathbf{x} - A\bar{\mathbf{x}} = \mathbf{b} - A\bar{\mathbf{x}} = \mathbf{r}$ .

Norm Bound

\|\mathbf{e}\| \leq \|A^{-1}\| \cdot \|\mathbf{r}\|

This gives an upper bound on the error in terms of the residual and the norm of $A^{-1}$ . When $A$ is ill-conditioned, $\|A^{-1}\|$ is large, so even a small residual can correspond to a large error.

Iterative Refinement

Once we have the residual, we can solve for the error correction $\bar{\mathbf{e}}$ and improve our solution:

A\bar{\mathbf{e}} = \mathbf{r} \quad \Longrightarrow \quad \bar{\mathbf{x}}_{\text{corrected}} = \bar{\mathbf{x}} + \bar{\mathbf{e}}

Solving $A\bar{\mathbf{e}} = \mathbf{r}$ for the correction $\bar{\mathbf{e}}$ and adding it to $\bar{\mathbf{x}}$ yields a refined approximate solution. This process can be repeated.

Worked Example

System

A = \begin{pmatrix}6 & -2 & 1\\-2 & 7 & 2\\1 & 2 & -5\end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix}11\\5\\-1\end{pmatrix}

True solution: $\mathbf{x} = (2,\,1,\,1)^T$ . Gauss-Seidel approximate solution after several iterations:

\bar{\mathbf{x}} = (2.000119,\;1.000068,\;1.000051)^T

Step 1: Compute $\mathbf{r} = \mathbf{b} - A\bar{\mathbf{x}}$

\mathbf{r} = \mathbf{b} - A\bar{\mathbf{x}} \approx (-0.000629,\;-0.000340,\;0.000000)^T

Step 2: Solve $A\bar{\mathbf{e}} = \mathbf{r}$

\bar{\mathbf{e}} = (-0.000119,\;-0.000068,\;-0.000051)^T

Step 3: Correct

\bar{\mathbf{x}}_{\text{corrected}} = \bar{\mathbf{x}} + \bar{\mathbf{e}} = (2.000119 - 0.000119,\;1.000068 - 0.000068,\;1.000051 - 0.000051)^T

Result: $\bar{\mathbf{x}}_{\text{corrected}} = (2,\,1,\,1)^T$ — the true solution. ■

Interactive Residual Calculator

Enter a 3×3 matrix $A$ , vector $\mathbf{b}$ , and approximate solution $\bar{\mathbf{x}}$ . The residual $\mathbf{r} = \mathbf{b} - A\bar{\mathbf{x}}$ is computed live.

Matrix A

Vector b

Approximate $\bar{x}$

Results

Component	$b_i$	$(A\bar{x})_i$	$r_i$
r₁	11.000000	11.000629	-6.2900e-4
r₂	5.000000	5.000340	-3.4000e-4
r₃	-1.000000	-1.000000	0.0000e+0

Residual vector

\mathbf{r}

(-6.2900e-4, -3.4000e-4, 0.0000e+0)

Infinity norm

\|\mathbf{r}\|_\infty

6.2900e-4

Moderate residual. Iterative refinement may improve accuracy.

Linear Systems

Theory

Interactive Visualizer

Practice Problem

Worked Example (Gauss-Jordan)

Matrix & Vector Norms

Vector Norms

Matrix Norms

Interactive Vector Norm Calculator

Interactive Matrix Norm Calculator

Worked Examples

Error in Linear Systems

Error Analysis & Iterative Refinement

Worked Example

Interactive Residual Calculator