The Question That Pushed LU Beyond Small Examples
After understanding that LU factorization is essentially Gaussian elimination with its multipliers saved, another practical question appears:
Elimination is easy for a small matrix, but what happens with a large \(n\times n\) matrix? We still need some way to solve \(Ax=b\).
This question reveals why elimination and factorization are much more than techniques for solving small textbook systems.
What If A Is 1000 × 1000?
Suppose
\[A\in\mathbb{R}^{1000\times1000}.\]
Then
\[Ax=b\]
can represent 1000 simultaneous equations with 1000 unknowns.
Doing Gaussian elimination manually would obviously be impractical. But the mathematical procedure does not stop working merely because the matrix becomes large.
A computer can perform the elimination algorithm for us.
For a general dense \(n\times n\) matrix, the LU factorization work grows approximately like
\[\frac{2}{3}n^3\]
arithmetic operations, or in complexity notation,
\[O(n^3).\]
This can represent an enormous amount of arithmetic from a human perspective, but it is precisely the kind of systematic calculation computers are designed to perform.
Why Saving LU Becomes Important
Suppose we need to solve
\[Ax=b_1.\]
The computer can factor \(A\):
\[A=LU.\]
Factorization is the relatively expensive part.
Once \(L\) and \(U\) are available, solving for a particular right-hand side can be split into
\[Lc=b\]
followed by
\[Ux=c.\]
Because both matrices are triangular, these systems are much easier to solve.
The triangular solution work grows approximately like \(O(n^2)\), substantially less than performing a new \(O(n^3)\) factorization.
Question: Why Can’t We Just Substitute Directly in A?
It is tempting to say that since we already have \(A\) and \(b\), we should simply write
\[A\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=b\]
and substitute directly.
For example, consider
\[A=\begin{bmatrix}2&1&1\\4&3&3\\8&7&9\end{bmatrix}.\]
Then \(Ax=b\) gives equations in which several unknowns appear simultaneously. There is generally no single equation containing only one unknown from which substitution can immediately begin.
Gaussian elimination fixes exactly this problem by transforming \(A\) into an upper triangular matrix:
\[U=\begin{bmatrix}2&1&1\\0&1&1\\0&0&2\end{bmatrix}.\]
Now the last equation contains only \(x_3\). Once \(x_3\) is known, the equation above gives \(x_2\), and finally the first equation gives \(x_1\).
This is back substitution.
So if we decide to solve directly from the original \(A\), we have not avoided elimination. We will generally need to transform the system into a form that permits easy substitution.
The Advantage When b Changes
Now suppose the matrix represents a system whose rules remain fixed, while the input or observation vector changes:
\[Ax_1=b_1,\]
\[Ax_2=b_2,\]
\[Ax_3=b_3.\]
The matrix \(A\) is unchanged.
If we perform Gaussian elimination from scratch for every new \(b\), we repeatedly rediscover the same elimination multipliers and the same upper triangular structure.
LU avoids that repetition.
Factor once:
\[A=LU.\]
Then for each new \(b_i\), solve only
\[Lc_i=b_i\]
and
\[Ux_i=c_i.\]
The expensive structural work associated with \(A\) can therefore be reused.
But What If Elimination Encounters a Zero Pivot?
Consider
\[A=\begin{bmatrix}0&2\\3&4\end{bmatrix}.\]
Ordinary elimination would try to use the first entry as the pivot.
To eliminate the \(3\) below it, the multiplier would have to be
\[\ell_{21}=\frac30.\]
This is undefined.
But this does not automatically mean that the system cannot be solved.
There is a perfectly usable \(3\) immediately below the zero.
Swap the rows:
\[\begin{bmatrix}0&2\\3&4\end{bmatrix}\longrightarrow\begin{bmatrix}3&4\\0&2\end{bmatrix}.\]
Now elimination can proceed.
A Row Swap Is Also a Matrix Operation
The row exchange can itself be represented by
\[P=\begin{bmatrix}0&1\\1&0\end{bmatrix}.\]
Multiplying from the left gives
\[PA=\begin{bmatrix}0&1\\1&0\end{bmatrix}\begin{bmatrix}0&2\\3&4\end{bmatrix}=\begin{bmatrix}3&4\\0&2\end{bmatrix}.\]
The matrix \(P\) is called a permutation matrix. In this example its action is to exchange the two rows.
Once row exchanges become part of elimination, the simple relationship
\[A=LU\]
is commonly extended to
\[\boxed{PA=LU}.\]
Here \(P\) records the row permutations required during elimination.
Zero Is Not the Only Problem: Tiny Pivots
Now consider
\[A=\begin{bmatrix}0.000001&1\\1&1\end{bmatrix}.\]
The first pivot is not zero, so mathematically we could proceed.
But the multiplier would be
\[\ell_{21}=\frac{1}{0.000001}=1,000,000.\]
Elimination would therefore involve subtracting one million times the first row from the second.
Computers normally perform numerical calculations using finite-precision floating-point numbers. Very large elimination multipliers can contribute to numerical error and instability.
There is a much better pivot available: the \(1\) below the tiny number.
Swap the rows:
\[\begin{bmatrix}0.000001&1\\1&1\end{bmatrix}\longrightarrow\begin{bmatrix}1&1\\0.000001&1\end{bmatrix}.\]
Now the elimination multiplier is only
\[\ell_{21}=0.000001.\]
Partial Pivoting
This motivates a practical improvement to Gaussian elimination called partial pivoting.
When choosing a pivot in a column, the algorithm examines the available entries at and below the current pivot position and typically chooses the one with the largest absolute value. Rows are exchanged to move that entry into the pivot position.
This avoids division by zero when an alternative pivot exists and generally improves numerical stability by avoiding unnecessarily small pivots.
The Picture Has Now Expanded
The progression of ideas is becoming:
\[Ax=b\]
\[\downarrow\]
\[\text{Gaussian elimination}\]
\[\downarrow\]
\[A\rightarrow U\]
Save the elimination multipliers:
\[A=LU.\]
If row exchanges are required, record them using \(P\):
\[\boxed{PA=LU}.\]
Then solve the resulting triangular systems using forward and backward substitution.
The Deeper Computational Lesson
Small matrices are useful because they allow us to see every arithmetic step by hand. But the concepts are not primarily limited to small matrices.
For large systems, computers execute systematic numerical algorithms based on the same underlying ideas.
A high-level numerical computing command that appears simply to solve
\[Ax=b\]
may internally rely on matrix factorizations, pivoting and triangular solution algorithms.
Different matrix structures can eventually lead to other approaches such as QR or Cholesky factorizations, while extremely large sparse systems may use iterative methods. Those are later topics.
For the present stage, the important mental model is:
\[\boxed{\text{Large }Ax=b\rightarrow\text{factor/pivot systematically}\rightarrow\text{solve simpler triangular systems}.}\]
A Useful Correction to Remember
A zero pivot does not automatically mean that \(A\) is singular or that \(Ax=b\) has no solution.
Sometimes it simply means that the current row ordering gives us a bad pivot and that a row exchange is required.
This is why practical elimination naturally develops from
\[A=LU\]
into the more general computational form
\[\boxed{PA=LU}.\]
Note metadata
- Note type: learning-note
- Subject: learning-notes
- Source: Introduction to Linear Algebra, Fifth Edition