Linear Algebra

Intro

Basic idea behind linear algebra: solving large number of linear algebraic equations simultaneously.

$ a_{i,1} x_1 + a_{i,2} x_2 + a_{i,3} x_3 + \dots + a_{i,N} x_{N} = b_{N} \qquad i=1 \dots M $

There are N unknowns and M equations, forming a linear system from matrices:

$ \mathbf{A \cdot x} = \mathbf{b} $

where lowercase letters denote vectors, and the dot represents multiplication of two matrices or a matrix and a vector, or dot product of two vectors.

Nonsingular vs Singular

We are not guaranteed to find a solution to a given linear system Ax=b

• row degeneracy - one or more of the M equations is a linear combination of other equations
• column degeneracy - one or more of the N variables are interchangeable and cannot be distinguished (are non-unique)
• for square matrices, these two conditions are equivalent

Having singular system of equations means we can't find good solutions.

Other things preventing good solution:

• Equations being equivalent to within roundoff error (approximately degenerate)
• Accumulation of roundoff error during solution can swamp solution

Many linear equation solving packages dedicate a good chunk of their code to solving these problems

Sense of scale:

• Linear equations with 20-50 unknowns are routine, can almost always be solved in single precision with straightforward routines
• Linear equations with up to 1,000 unknowns require double precision
• Larger sets of thousands or millions of equations can be solved with coefficients are sparse (mostly zero) by using specialty sparse methods

Tasks of Computational Linear Algebra

Beyond simply solving Ax=b for the unknowns x, we may want to do other things:

• Solve more than one matrix equation, <math>\mathbf{A \cdot x}_j = \mathbf{b}_j