Timo Heister - Scientific Computing: For Scientists and Engineers

There are infinitely many solutions to the linear system

Here the equations can be reduced to the same equation. Thus we have two unknowns, x1 and x2 , but only one equation. Thus any point on the line 2x1+x2=0 solves the system.

A geometric interpretation of solving linear systems is that if you were to plot each equation, the solution would be where they intersect. Hence, most often, two lines intersect at a point. However, the lines could be parallel and never intersect (this is the inconsistent case), or they could be the same line and intersect at every point on the line. The same idea can be extended to larger systems, and generally speaking, an n-equation, n-unknown consistent linear system will have a unique solution, provided that no equation is repeated.

In the 22 case, it is easy to see when an equation is repeated or inconsistent, but for larger systems, it is not always so easy. For example, consider the system of equations

Here the third equation is merely the sum of the first two equations. Hence it is not inconsistent, but it does not add anything to the system: if the first two equations are satisfied, then the third will automatically be satisfied. Two consistent equations with three unknowns means infinitely many solutions (two planes intersecting along a line).

It will be more convenient to use matrixvector notation to represent linear systems of equations. For example, the above 3-equation 3-unknown system can be equivalently written as

If we are going to try to use a numerical algorithm to find a solution to a system of equations, it would be nice to know up front whether or not a unique solution exists for a particular linear system. It turns out that there are many ways to determine this for small systems (say, n<10,000 ); for example, if the determinant of the matrix of coefficients is nonzero, then a solution exists and is unique. For larger systems, however, this determination can be very difficult. Fortunately, most linear systems that arise in science and engineering from common approaches such as finite element and finite difference methods are uniquely solvable, and if not, then often a mistake has been made in the derivation of the coefficients, or there is a different approach to the problem that would lead to a solvable system. Thus we will assume for the rest of this chapter that all the square linear systems have a unique solution, but we will keep in mind this potential problem when we analyze the algorithms. As the definition below states, this assumption can be made in several equivalent ways.

A first step along the way to solving general linear systems of equations is solving triangular systems, which get their name because the matrix representation of their coefficients has only 0s either above or below the main diagonal (which goes from the top left to the bottom right). For such systems, finding solutions is straightforward, as we show in the following example.