4

What Is the Second Difference Matrix?

 3 years ago
source link: https://nhigham.com/2022/01/31/what-is-the-second-difference-matrix/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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 = 2 - 2 \cos( k \phi) = 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.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK