§3.2 Linear Algebra

To solve the system

with Gaussian elimination, where $𝐀$ is a nonsingular $n\times n$ matrix and $𝐛$ is an $n\times 1$ vector, we start with the augmented matrix

By repeatedly subtracting multiples of each row from the subsequent rows we obtain a matrix of the form

During this reduction process we store the multipliers ${\mathrm{\ell }}_{jk}$ that are used in each column to eliminate other elements in that column. This yields a lower triangular matrix of the form

If we denote by $𝐔$ the upper triangular matrix comprising the elements $u_{jk}$ in (3.2.3), then we have the factorization, or triangular decomposition,

With $𝐲={[y_1,y_2,\mathrm{\dots },y_n]}^{\mathrm{T}}$ the process of solution can then be regarded as first solving the equation $𝐋𝐲=𝐛$ for $𝐲$ (forward elimination), followed by the solution of $𝐔𝐱=𝐲$ for $𝐱$ (back substitution).

For more details see Golub and Van Loan (1996, pp. 87–100).

Tridiagonal matrices are ones in which the only nonzero elements occur on the main diagonal and two adjacent diagonals. Thus

Assume that $𝐀$ can be factored as in (3.2.5), but without partial pivoting. Then

where $u_j=c_j$, $j=1,2,\mathrm{\dots },n-1$, $d_1=b_1$, and

Forward elimination for solving $𝐀𝐱=𝐟$ then becomes $y_1=f_1$,

and back substitution is $x_n=y_n/d_n$, followed by

For more information on solving tridiagonal systems see Golub and Van Loan (1996, pp. 152–160).

The $p$-norm of a vector $𝐱={[x_1,\mathrm{\dots },x_n]}^{\mathrm{T}}$ is given by

The Euclidean norm is the case $p=2$.

The $p$-norm of a matrix $𝐀=[a_{jk}]$ is

The cases $p=1,2$, and $\mathrm{\infty }$ are the most important:

where $\rho (𝐀{𝐀}^{\mathrm{T}})$ is the largest of the absolute values of the eigenvalues of the matrix $𝐀{𝐀}^{\mathrm{T}}$; see §3.2(iv). (We are assuming that the matrix $𝐀$ is real; if not ${𝐀}^{\mathrm{T}}$ is replaced by ${𝐀}^{\mathrm{H}}$, the transpose of the complex conjugate of $𝐀$.)

The sensitivity of the solution vector $𝐱$ in (3.2.1) to small perturbations in the matrix $𝐀$ and the vector $𝐛$ is measured by the condition number

where ${\Vert \mathrm{\cdot }\Vert }_p$ is one of the matrix norms. For any norm (3.2.14) we have $\kappa (𝐀)\ge 1$. The larger the value $\kappa (𝐀)$, the more ill-conditioned the system.

Let ${𝐱}^{\ast }$ denote a computed solution of the system (3.2.1), with $𝐫=𝐛-𝐀{𝐱}^{\ast }$ again denoting the residual. Then we have the a posteriori error bound

For further information see Brezinski (1999) and Trefethen and Bau (1997, Chapter 3).

If $𝐀$ is an $n\times n$ matrix, then a real or complex number $\lambda$ is called an eigenvalue of $𝐀$, and a nonzero vector $𝐱$ a corresponding (right) eigenvector, if

A nonzero vector $𝐲$ is called a left eigenvector of $𝐀$ corresponding to the eigenvalue $\lambda$ if ${𝐲}^{\mathrm{T}}𝐀=\lambda {𝐲}^{\mathrm{T}}$ or, equivalently, ${𝐀}^{\mathrm{T}}𝐲=\lambda 𝐲$. A normalized eigenvector has Euclidean norm 1; compare (3.2.13) with $p=2$.

The polynomial

is called the characteristic polynomial of $𝐀$ and its zeros are the eigenvalues of $𝐀$. The multiplicity of an eigenvalue is its multiplicity as a zero of the characteristic polynomial (§3.8(i)). To an eigenvalue of multiplicity $m$, there correspond $m$ linearly independent eigenvectors provided that $𝐀$ is nondefective, that is, $𝐀$ has a complete set of $n$ linearly independent eigenvectors.

If $𝐀$ is nondefective and $\lambda$ is a simple zero of $p_n(\lambda )$, then the sensitivity of $\lambda$ to small perturbations in the matrix $𝐀$ is measured by the condition number

where $𝐱$ and $𝐲$ are the normalized right and left eigenvectors of $𝐀$ corresponding to the eigenvalue $\lambda$. Because $\left|{𝐲}^{\mathrm{T}}𝐱\right|=\left|\cos \theta \right|$, where $\theta$ is the angle between ${𝐲}^{\mathrm{T}}$ and $𝐱$ we always have $\kappa (\lambda )\ge 1$. When $𝐀$ is a symmetric matrix, the left and right eigenvectors coincide, yielding $\kappa (\lambda )=1$, and the calculation of its eigenvalues is a well-conditioned problem.

Let $𝐀$ be an $n\times n$ symmetric matrix. Define the Lanczos vectors ${𝐯}_j$ and coefficients ${\alpha }_j$ and ${\beta }_j$ by ${𝐯}_0=\mathrm{𝟎}$, a normalized vector ${𝐯}_1$ (perhaps chosen randomly), ${\alpha }_1={𝐯}_1^{\mathrm{T}}𝐀{𝐯}_1$, ${\beta }_1=0$, and for $j=1,2,\mathrm{\dots },n-1$ by the recursive scheme

Then ${𝐯}_j^{\mathrm{T}}{𝐯}_k={\delta }_{j,k}$, $j,k=1,2,\mathrm{\dots },n$. The tridiagonal matrix

has the same eigenvalues as $𝐀$. Its characteristic polynomial can be obtained from the recursion

with $p_{-1}(\lambda )=0$, $p_0(\lambda )=1$.

In the case that the orthogonality condition is replaced by $𝐒$-orthogonality, that is, ${𝐯}_j^{\mathrm{T}}𝐒{𝐯}_k={\delta }_{j,k}$, $j,k=1,2,\mathrm{\dots },n$, for some positive definite matrix $𝐒$ with Cholesky decomposition $𝐒={𝐋}^{\mathrm{T}}𝐋$, then the details change as follows. Start with ${𝐯}_0=\mathrm{𝟎}$, vector ${𝐯}_1$ such that ${𝐯}_1^{\mathrm{T}}𝐒{𝐯}_1=1$, ${\alpha }_1={𝐯}_1^{\mathrm{T}}𝐀{𝐯}_1$, ${\beta }_1=0$. Then for $j=1,2,\mathrm{\dots },n-1$

For more details see Guan et al. (2007).

For numerical information see Stewart (2001, pp. 347–368).

Lanczos’ method is related to Gauss quadrature considered in §3.5(v). When the matrix $𝐀$ is replaced by a scalar $x$, the recurrence relation in the first line of (3.2.21) with $𝐮={\beta }_{j+1}{𝐯}_{j+1}$ is similar to the one in (3.5.30_5). Also, the recurrence relations in (3.2.23) and (3.5.30) are similar, as well as the matrix $𝐁$ in (3.2.22) and the Jacobi matrix ${𝐉}_n$ in (3.5.31).

Many methods are available for computing eigenvalues; see Golub and Van Loan (1996, Chapters 7, 8), Trefethen and Bau (1997, Chapter 5), and Wilkinson (1988, Chapters 8, 9).