What Is the Second Difference Matrix?

The second difference matrix is the tridiagonal matrix T_n with diagonal elements 2 and sub- and superdiagonal elements -1:

\notag    T_n = \left[    \begin{array}{@{}*{4}{r@{\mskip10mu}}r}                 2  & -1 &        &        &    \\                 -1 & 2  & -1     &        &    \\[-5pt]                    & -1 & 2      & \ddots &    \\                    &    & \ddots & \ddots & -1 \\                    &    &        & -1     & 2    \end{array}\right] \in\mathbb{R}^{n\times n}.

It arises when a second derivative is approximated by the central second difference f''(x) \approx (f(x+h) -2 f(x) + f(x-h))/h^2. (Accordingly, the second difference matrix is sometimes defined as -T_n.) In MATLAB, T_n can be generated by gallery('tridiag',n), which is returned as a aparse matrix.

This is Gil Strang’s favorite matrix. The photo, from his home page, shows a birthday cake representation of the matrix.

strang_second_diff_cake.jpg

The second difference matrix is symmetric positive definite. The easiest way to see this is to define the full rank rectangular matrix

\notag  L_n = \begin{bmatrix}                1  &      &        &  \\                -1 &  1   &        &  \\                   & -1   & \ddots &  \\                   &      & \ddots & 1 \\                   &      &        &  -1     \end{bmatrix} \in\mathbb{R}^{(n+1)\times n}

and note that T_n = L_n^T L_n. The factorization corresponds to representing a central difference as the product of a forward difference and a backward difference. Other properties of the second difference matrix are that it is diagonally dominant, a Toeplitz matrix, and an M-matrix.

Cholesky Factorization

In an LU factorization A = LU the pivots u_{ii} are 2, 3/2, 4/3, …, (n+1)/n. Hence the pivots form a decreasing sequence tending to 1 as n\to\infty. The diagonal of the Cholesky factor contains the square roots of the pivots. This means that in the Cholesky factorization A = R^*R with R upper bidiagonal, r_{nn} \to 1 and r_{n,n-1}\to -1 as n\to\infty.

Determinant, Inverse, Condition Number

Since the determinant is the product of the pivots, \det(T_n) = n+1.

The inverse of T_n is full, with (i,j) element i(n-j+1)/(n+1) for j\ge i. For example,

\notag   T_5^{-1} = \displaystyle\frac{1}{6}  \begin{bmatrix} 5 & 4 & 3 & 2 & 1\\ 4 & 8 & 6 & 4 & 2\\ 3 & 6 & 9 & 6 & 3\\ 2 & 4 & 6 & 8 & 4\\ 1 & 2 & 3 & 4 & 5  \end{bmatrix}.

The 2-norm condition number satisfies \kappa_2(T_n) \sim 4n^2/\pi^2 (as follows from the formula (1) below for the eigenvalues).

Eigenvalues and Eigenvectors

The eigenvalues of T_n are

\notag      \mu_k       = 4 \sin^2\Bigl(\displaystyle\frac{k \phi}{2} \Bigr),         \quad k = 1:n, \qquad (1)

where \phi = \pi/(n+1), with corresponding eigenvector

\notag   v_k = \begin{bmatrix} \sin(k\phi), &\sin(2k\phi), &\dots, &\sin(nk\phi)   \end{bmatrix}^T.

The matrix Q with

\notag    q_{ij} = \Bigl(\displaystyle\frac{2}{n+1}\Bigr)^{1/2} \sin\Bigl( \frac{ij\pi}{n+1} \Bigr)

is therefore an eigenvector matrix for T_n: Q^*AQ = \mathrm{diag}(\mu_k).

Variations

Various modifications of the second difference matrix arise and similar results can be derived. For example, consider the matrix obtained by changing the (n,n) element to 1:

\notag    \widetilde{T}_n = \left[    \begin{array}{@{}*{4}{r@{\mskip10mu}}r}                 2  & -1 &        &        &    \\                 -1 & 2  & -1     &        &    \\[-5pt]                    & -1 & 2      & \ddots &    \\                    &    & \ddots & \ddots & -1 \\                    &    &        & -1     & 1    \end{array}\right] \in\mathbb{R}^{n\times n}.

It can be shown that \widetilde{T}_n^{-1} has (i,j) element \min(i,j) and eigenvalues 4\cos( j \pi/(2n+1))^2, j=1:n.

If we perturb the (1,1) of \widetilde{T}_n to 1, we obtain a singular matrix, but suppose we perturb the (1,1) element to 3:

\notag    \widehat{T}_n = \left[    \begin{array}{@{}*{4}{r@{\mskip10mu}}r}                 3  & -1 &        &        &    \\                 -1 & 2  & -1     &        &    \\[-5pt]                    & -1 & 2      & \ddots &    \\                    &    & \ddots & \ddots & -1 \\                    &    &        & -1     & 1    \end{array}\right] \in\mathbb{R}^{n\times n}.

The inverse is \widehat{T}_n^{-1} = G/2, where G with (i,j) element 2\min(i,j)-1 is a matrix of Givens, and the eigenvalues are 4\cos((2j-1)\pi/(4n))^2, j=1:n.

Notes

The factorization T_n = L_n^TL_n is noted by Strang (2012).

For a derivation of the eigenvalues and eigenvectors see Todd (1977, p. 155 ff.). For the eigenvalues of \widetilde{T}_n see Fortiana and Cuadras (1997). Givens’s matrix is described by Newman and Todd (1958) and Todd (1977).

References

This is a minimal set of references, which contain further useful references within.

Related Blog Posts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s