Numerical Linear Algebra

Matrices¶

It is often useful to think of a matrix-vector product can be though of as a linear combination of the columns of the matrix. That is,

Norms¶

It is often useful to bound different norms with each other.

Factorizations¶

The above definition is sometimes called a reduced or thin SVD. By extending $\vec{U}$ to an orthonormal basis for $\R^n$ and appending zeros below $\vec{\Sigma}$ we obtain a full SVD.

The SVD provides the best low-rank approximation to a matrix.

Conditioning¶

A problem/task is said to be well-conditioned if small perturbations in problem don’t change the solution by much. If a small change to the problem can cause a large change in the solution, then the problem is said to be ill-conditioned. Ill-conditioned problems are difficult (or impossible) to solve accurately on computers, since even small errors made representing the problem on a computer can drastically change the solution.

In numerical linear algebra the condition-number of a matrix $\vec{A}$ is defined as

where $\smax(\vec{A})$ and $\smin(\vec{A})$ are the largest and smallest singular values of $\vec{A}$, respectively. The conditioning of many core linear algebra tasks depends on the condition number.

Krylov subspace methods¶

Krylov subspace methods are an important and powerful class of algorithms in numerical linear algebra. Such algorithms make use of the information in the so-called Krylov subspace.

Computationally, it is useful to obtain an orthonormal basis for relevant subspaces. In the case of Krylov subspaces, this can be done by the Arnoldi algorithm. When applied to a symmetric matrix $\vec{A}$ for $k$ iterations, the arnoldi algorithm produces an orthonormal basis $\vec{Q}\in\R^{n\times k}$ for the Krylov subspace $\mathcal{K}_k(\vec{A}, \vec{x})$ and an upper-Hessenberg matrix $\vec{H}\in\R^{k\times k}$ such that $\vec{H} = \vec{Q}^\T\vec{A}\vec{Q}$.

In the special case that $\vec{A}$ is symmetric, we observe that $\vec{Q}^\T\vec{A}\vec{Q}$ is also symmetric. This means $\vec{H}$ is both upper-Hessenberg and symmetric, and thus tridiagonal. This allows substantial simplifications to the Arnoldi algorithm, which is then called the Lanczos algorithm.