Linear systems

From Algorithmist
Jump to: navigation, search

The solution of various aspects of linear systems is fundamental to the computational sciences. Linear systems of equations can be written in matrix form and expressed as relations between matrices and vectors. Of particular importance is the establishment of efficent and numerically stable algorithms for performing various linear algebraic manipulations. We briefly outline the main classes of problems involving linear systems.

Inhomogeneous problems[edit]

In homogeneous problems involve solving for particular solutions to a set of equations. The most basic relation considered is


where A is a square matrix, and x and b are vectors. The elements of these objects may be taken from any ring, and as long as A is not singular, there exists a unique solution x.

One may also consider non-square A matrices in which one then seeks either a least squares approximate solution x to an over-determined set of equations (A has more rows than columns) or specific solutions to the under-determined equations (A has fewer rows than columns).

The above discussion is greatly simplified and there are many subtleties in the structure of the objects involved. From an algorithmic point of view, there is a distinction between algorithms which can directly compute solutions (exact under exact arithmetical operations) and iterative methods which compute solutions with successively greater accuracy.

Homogeneous problems[edit]

Homogeneous linear problems are of the variety Ax=0 or (A-\lambda I)x=0. In the case of the former, one seeks non-zero solutions in the kernel of the operator A and the latter is a linear eigensystem with eigenvalues \lambda . In both cases, one typically expects a multitude of solution vectors x, and in the eigensystem case, the corresponding eigenvalues.

Due to Abel's theorem, one can prove there does not exist a direct solution method for eigensystems of dimension greater than 5, so all general eigenvalue solvers are iterative, however direct methods exist for computing nullspaces.