Chapter 1 Linear Equations
1.1 Introduction
A fundamental problem that surfaces in all mathematical sciences is that of analyzing and solving $m$ algebraic equations in $n$ unknowns.
1.2 Gaussian Elimination and Matrices
The problem is to calculate, if possible, a common solution for a system of $m$ linear algebraic equations in $n$ unknowns
\[\begin{equation*} \begin{aligned} a_{11}x_1 \; + \; a_{12}x_2 \; + \; \dots \; + \; a_{1n}x_n \; &= \; b_1, \\ a_{21}x_1 \; + \; a_{22}x_2 \; + \; \dots \; + \; a_{2n}x_n \; &= \; b_2, \\ \vdots \\ a_{m1}x_1 \; + \; a_{m2}x_2 \; + \; \dots \; + \; a_{mn}x_n \; &= \; b_m, \end{aligned} \end{equation*}\]where $a_{ij}$’s are the coefficients of the system.
For any such system, there are exactly three possibilities for the set of solutions.
Three Possiblities
- Unique solution
- No solution
- Infinitely many solution
Dealing with a linear system is
- to decide which one of these three possibilities is true.
- to compute the solution if it is unique or to describe the set of all solutions if there are many solutions.
Gaussian elimination is a tool that can be used to accomplish all of these goals.
The elimination process relies on three simple operations by which to transform one system to another equivalent system.
- Interchange the $i^{th}$ and $j^{th}$ equations.
- Replace thr $i^{th}$ equation by a nonzero multiple of itself.
- Replace the $j^{th}$ equation by a combination of itself plus a multiple of the $i^{th}$ equation.
At each step, the strategy is to focus on one position, called the pivot position, and to eliminate all terms below this position using the three elementary operations. The coefficient in the pivot position is called a pivotal element, while the equation in which the pivot lies is referred to as the pivotal equation.
Only nonzero numbers are allowed to be pivots. If a coefficient in a pivot position is ever 0, then the pivotal equation is interchanged with an equation below the pivotal equation to produce a nonzero pivot. Unless it is 0,the first coefficient of the first equation is taken as the first pivot.
In general, at each step you move down and to the right to select the next pivot, then eliminate all terms below the pivot until you can no longer proceed. At this point, we say that the system has been triangularized. A triangular system is easily solved by a simple method known as back substitution.
Algorithm for Back Substitution
If an $n \times n$ system has been triangularized to the form
\[\left( \begin{array}{cccc|c} t_{11} & t_{12} & \dots & t_{1n} & c_1\\ 0 & t_{22} & \dots & t_{2n} & c_2\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \dots & t_{nn} & c_n\\ \end{array} \right) \tag{1.2.10}\]in which each $t_{ii} \neq 0$.
So determine the $x_i$’s from $(1.2.10)$ by first setting $x_n = \frac{c_n}{t_{nn}}$ and then recursively computing
\[\bbox[#58F, 8px] { x_i = \frac{1}{t_{ii}} \left( c_i - t_{i, i + 1} x_{i + 1} - t_{i, i + 2}x_{i + 2} - \dots -t_{in} x_n \right) }\]for $i = n - 1, n - 2, …, 2, 1$.
Gaussian Elimination Operation Counts
Gaussian elimination with back substitution applied to an $n \times n$ system requires
\[\frac{n^3}{3} + n^2 - \frac{n}{3} \quad \text{multiplications/divisions}\]and
\[\frac{n^3}{3} + \frac{n^2}{2} - \frac{5n}{6} \quad \text{additions/subtractions}\]Some notations
coefficient matrix: $\mathbf{A}$
augmented matrix: $\left[ \mathbf{A} \vert \mathbf{b} \right]$
$\mathbf{A}{i*}$ denotes the $i^{th}$ row, $\mathbf{A}{*j}$ denotes the $j^{th}$ column of matrix $\mathbf{A}$.
$\mathbf{A}_{m \times n}$ emphasize that matrix $\mathbf{A}$ has shape $m \times n$.
Whenever $m = n$, $\mathbf{A}$ is called a square matrix. Otherwise, $\mathbf{A}$ is said to be rectangular.
1.3 Gauss-Jordan Method
Gauss-Jordan method is a variation of Gaussian elimination. Two features are as follows.
- At each step, the pivot element is forced to be 1.
- At each step, all terms above the pivot as well as all terms below the pivot are eliminated.
Then the solution is the last column(i.e., $x_i = s_i$), this method circumvents the need to perform back substitution.
Gauss-Jordan Operation Counts
For an $n \times n$ system, the Gauss-Jordan procedure requires
\[\frac{n^3}{2} + \frac{n^2}{2} \quad \text{multiplications/divisions}\]and
\[\frac{n^3}{2} - \frac{n}{2} \quad \text{additions/subtractions}\]Although the Guass-Jordan method requires about $50\%$ more effort than Gaussian elimination with back substitution and is not recommended for solving linear systems that arise in practical applications, it can be a useful technique for tasks other than computing solutions to linear systems. Guass-Jordan precedure will be used when matrix inversion is discussed.
1.5 Making Gaussian Elimination Work
Numerical computation in digital computers is performed by approximating the infinite set of real numbers with a finite set of numbers as described below. Due to this, computers produce a predictable kind of error, called roundoff error.
Floating-Point Numbers
A $t$-digit, base-$\beta$ floating-point number has the form
where the base $\beta$, the exponent $\epsilon$, and the digits $0 \leq d_i \geq \beta - 1$ are integers. The value of $t$ is called the precision.
Given a real number $x$, the floating-point approximation
\[fl(x) = \begin{cases} .d_1 d_2 \dots d_t \times \beta^{\epsilon} & \text{if} \; d_{t+1} \lt 5, \\ \left(\left[.d_1 d_2 \dots d_t\right] + 10^{-t} \right) \times \beta^{\epsilon} & \text{if} \; d_{t+1} \geq 5. \end{cases}\]Patial Pivoting
At each step, search the positions on and below the pivotal position for the coefficient of maximum magnitude. If necessary perform the appropriate row interchange to bring this maximal coefficient into the pivotal position.
Tha answer why did partial pivoting make a difference lies in that the large multiplier prevents some smaller numbers from being fully accounted for, thus resulting in the exact solution of another system that is very different from the original system.
By using partial pivoting, we guarantee that no multiplier exceeds 1 in magnitude, the possibility of producing relatively large numbers that can swamp the significance of smaller numbers is much reduced, but not completely eliminated.
Practical Scaling Strategy
- Choose units that are natural to the problem and do not distort the relationships between the sizes of things. These natural units are usually self-evident, and further column scaling past this point is not ordinarily attempted.
- Row scale the system $\left[\mathbf{A} \vert \mathbf{b}\right]$ so that the coefficient of maximum magnitude in each row of $\mathbf{A}$ is equal to 1. That is, divide each equation by the coefficient of maximum magnitude.
Complete Pivoting
Although it is not extensively used, there is an extension of partial pivoting known as complete pivoting.
If $\left[\mathbf{A} \vert \mathbf{b}\right]$ is the augmented matrix at the $k^{th}$ step of Gaussian elimination, then search the pivotal position together with every position in $\mathbf{A}$ that is below or to the right of the pivotal position for the coefficient of maximum magnitude. If necessary, perform the appropriate row and column interchanges to bring the coefficient of maximum magnitude into the pivotal position.
We should be able to see that complete pivoting is at least as effective as partial pivoting. However, it approximately doubles the cost over straight Gaussian elimination, whereas partial pivoting adds only a negligible amount. Couple this with the fact that it is extremely rare to encounter a practical system where scaled partial pivoting is not adequate while complete pivoting is, and it is easy to understand why complete pivoting is seldom used in practice. Gaussian elimination with scaled partial pivoting is the preferred method for dense systems (i.e., not a lot of zeros) of moderate size.
1.6 Ill-conditioned Systems
A system of linear equations is said to be ill-conditioned when some small perturbation in the system can produce relatively large changes in the exact solution. Otherwise, the system is said to be well-conditioned.
