System of Linear Equations

A linear equation is an equation that may be put in the form:

where are variables, ’s are coefficients, and is constant.

A system of linear equations (or linear system) is a collection of linear equations involving the same set of variables.

A general system of linear equations with unknowns can be written as:

It can also be written in matrix form:

where is called the coefficient matrix, is a variable or unknown matrix, and is a constant matrix.

Iterative Techniques

The solution is guessed and then iteratively improved.

Jacobi Method

A slow method for solving systems of linear equations iteratively. An initial guess is made for the solution vector . Then iteratively, subsequent approximations are made using the equation: ( is made subject in -th equation).

For each , generate the components of using the components of previous iteration for each using:

Cannot be used for singular matrix.

Diagonally dominant matrix

is diagonally dominant when :

is strictly diagonally dominant when :

Relative error is given by:

Here any convenient matrix norms can be used. Usually infinity norm is used.

Note

The equation can be converted to the form .

Here:

• is a diagonal matrix whose entries are of .
• is the strictly lower-triangular part of .
• is the strictly upper-triangular part of .

Gauss-Seidel Method

An improvement over the Jacobi method. Major difference from Jacobi method is instead of using values from the previous iteration, here newest approximations for are used.

When computing , the components would have already been computed. They will be used to compute the as follows for each .

As in Jacobi Method, Gauss-Seidel Method can be written in matrix form as:

For to be non-singular, .

This method can also be expressed as:

Here:

Convergence of iterative methods

Theorem 1

Suppose . And .

The sequence converges to the unique solution of iff . Here denotes the spectral radius.

Suppose a sequence defined by .

If for any natural matrix norm and is a given vector, then for any , the sequence converges to a vector , with , and the following error bounds hold:

Theorem 2

If is strictly diagonally dominant, then for any choice of , both Jacobi and Gauss-Seidel methods gives sequences that converge to the unique solution of .