1.4. Linear system of equations

<=>

2)			A =

where

A = a11 ··· a1n , : : am1 ··· amn

= x1 , : xn

= b1 . : bm

If A ^{- 1} exists, the system of equations has a unique solution which is

= A ^{- 1} .

This is so, because

(2) <=> A ^{- 1}A = A ^{- 1} <=> = A ^{- 1} .

Since the inverse matrix does not necessarily exist (and since finding A ^{- 1} often requires more work than solving (1)), we first take a look at other methods for solving a linear system of equations.

The substitution method: Solve one unknown x_i from one equation and substitute to the other equations. Then again solve one unknown and so on. By continuing this way, if we obtain one linear equation with one unknown, it can be solved and other unknowns are obtained by backward substitution.

The Gaussian elimination (algorithm)

(3)		a11	a12	···	a1n	b1
		a21	···		a2n	b2
		:			:	:
		am1	···		amn	bn

If two of the equations in (1) are interchanged, one of the equations is multiplied by a scalar c 0 or if a scalar multiple of an equation is added to another equation, we obtain a linear system of equations which is equivalent to (1) and its corresponding matrix, which is equivalent to (3), is obtained from (3) by using elementary row operations:
1) Interchange of two rows
2) Multiplying all elements in a row by a scalar c 0
3) Adding a scalar multiple of one row to another equation.

In Gaussian elimination (1) is converted into an equivalent upper triangular system by using elementary row operations on the matrix (3). From the system of equations obtained in this way we solve the unknowns by backward substitution.

Example 1: Gaussian elimination

If some of the pivots is zero, we rearrange the equations (the rows). Also the unknowns may be rearranged but if this is done, it must be taken into account in the end. Also an upper triangular system can be solved by means of row operations.

Example 2: Gaussian elimination

Gaussian elimination with partial pivoting

Computers use floating point numbers, which are of the form

± 0._{1 2} ..._M · ß^k ,

which is a representation for the number

± (_i ß ^{- i}) ß^k.

Here ß is a base, ₁ ..._M mantissa of the floating point number, ₁ , ..., _M numbers 0, 1, 2, ..., ß - 1, k such that ₁ 0.

Calculations involve rounding errors whose effect may accumulate. For example, in Gaussian elimination it may cause trouble if some of the pivots has a small absolut value compared to other elements. ( => scalars needed in the addition of rows have large absolut values and this increase the rounding errors which already exist.)
In partial pivoting we find the element of the first column which has the largest absolut value and change this element to be the pivot. This is done for every matrix involved in the Gaussian elimination.