Numerical methods in linear algebra

While linear algebra deals with very general vectors, linear numerical analysis essentially considers vectors with a finite number of numerical components, i.e. in finite-dimensional spaces. The aim of this set of methods is to derive explicit procedures that lead to the most accurate approximations possible to the "ideal" objects that theory has identified.

We'll soon see that the notion of precision is itself imprecise, since we may or may not accept a certain margin of error on the results, and measure this error by various means. So we'll be looking to see in what sense(s) a vector can be considered "small", an "acceptable" solution. The rigorous study of errors and their propagation during calculations is difficult, however, and generally leads to overly pessimistic results. Different points of view, based on probability theory, often lead to more engaging conclusions.

This study, pushed to its extreme limit, will lead us to a dead end insofar as certain concepts of linear algebra are expressed in terms of integer values (these are dimensions), for which the notion of approximate value makes no sense.

The notion of an algorithm will soon come to the fore, as it is usually through iteration that we succeed in "calculating" the objects we're looking for. To take a very simple example, the scalar product of two vectors v and w with n components can be calculated using the following algorithm:

Initialize a sum S to 0.

Vary a counter i from 1 to n.

For each value of i, add v _i w _i to S.

The result is the final value of S.

We present the algorithms "in French", without reference to any particular computer language. In fact, most, if not all, of the reported algorithms are already coded in one of the existing program libraries, in Fortran or C. It is not very difficult to adapt these same algorithms to other programming languages.

Last but not least, this field, on the borderline between Algebra and Analysis, is currently undergoing a certain renewal thanks to the growing influence of software that enables formal calculation, i.e. exact calculation rather than approximate calculation. These products, which are now well developed, enable us to take a more favorable approach to the search for whole quantities mentioned above. Under these conditions, the question arises of the effective calculation of certain objects of linear algebra, such as eigenvectors; thus, "formal" work on eigenvalues naturally leads to calculation in bodies of algebraic numbers.

Readers are invited to refer...