16 - Matrices and Solution of Linear Systems

Summary

Linear systems of algebraic equations are one of the most important subjects in mathematics, since most other subjects, methods and problems involve or reduce to this subject.

Aims of the project

As numerical methods involve truncations and finite precisions, we investigate their effect on solution accuracy. Most of us know some theory about linear systems but may not be aware of the good or bad choice of solution methods on computers, what determines the accuracy of the numerical solution and whether an obtained solution can be improved. Large scale problems arising from practice often involve sparse matrices and special techniques can be developed. This project addresses all such issues.

Mathematical ideas used

You have learnt that to solve Ax = b you just type x = A\b. To investigate the sensitivity of the solution x with regard to the matrix A (or its condition number) and the right-hand side vector b, we use a controllable number of digits in our calculations. The use of iterative refinements is illustrated. Finally we discuss how a sparse matrix may be condensed towards band forms by use of permutation matrices.

MATLAB techniques used

Seven M-files lin_solv.m, chop.m, lu2.m, lu3.m, lu4.m, solv6.m and spar_ex.m are used to assist this project. The last two M-files are listed in the chapter. Here chop.m, used to fix digits, is used by lu2.m, lu3.m and lu4.m. You will get useful experience of MATLAB's easy and simple commands for both dense and sparse matrices.