Math Problems Vault

Problem 7.10.1

Which of the following are convergent, and which are summable?

\mathbf{A} = \begin{pmatrix} -1/2 & 3/2 & -3/2 \\ 1 & 0 & -1/2 \\ 1 & -1 & 1/2 \end{pmatrix}, \quad \mathbf{B} = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}, \quad \mathbf{C} = \begin{pmatrix} -1 & -2 & -3/2 \\ 1 & 2 & 1 \\ 1 & 1 & 3/2 \end{pmatrix}.

?

Problem 7.10.2

For the matrices in Exercise 7.10.1, evaluate the limit of each convergent matrix, and evaluate the Cesaro limit for each summable matrix.

If $\mathbf{A}$ is convergent or summable to $\mathbf{G}$ , and if $\mathbf{I}-\mathbf{A} = \mathbf{B}\mathbf{C}$ is a full-rank factorization, then $\mathbf{G} = \mathbf{I} - \mathbf{B}(\mathbf{C}\mathbf{B})^{-1}\mathbf{C}$ .

?

Problem 7.10.3

Verify that

\overrightarrow {x}(k) = \mathbf{A}^k\overrightarrow {x}(0) \quad \text{and} \quad \overrightarrow {x}(k) = \mathbf{A}^k\overrightarrow {x}(0) + \sum _{j=0}^{k-1}\mathbf{A}^{k-j-1}\overrightarrow {b}(j) \quad \text{for } k=1,2,3,\ldots

are indeed the respective solutions to the difference equations $\overrightarrow {x}(k+1) = \mathbf{A}\overrightarrow {x}(k)$ (a homogeneous system) and $\overrightarrow {x}(k+1) = \mathbf{A}\overrightarrow {x}(k)+\overrightarrow {b}(k)$ (a nonhomogeneous system).

?

Problem 7.10.4

Determine the limiting vector for the following shell game by first computing the Cesaro limit $\mathbf{G}$ with a full-rank factorization.

Shell game: a pea starts under one of four shells and, after each move, is shuffled to one of the (at most three) adjacent shells with equal probability, described by a $4\times 4$ column-stochastic transition matrix $\mathbf{A}$ with $\overrightarrow {p}(k) = \mathbf{A}^k\overrightarrow {p}(0)$ giving the probability distribution over shell positions after $k$ moves. If $\mathbf{I}-\mathbf{A} = \mathbf{B}\mathbf{C}$ is a full-rank factorization, then the Cesaro limit is $\mathbf{G} = \mathbf{I}-\mathbf{B}(\mathbf{C}\mathbf{B})^{-1}\mathbf{C}$ , and the limiting vector of expected proportions is $\overrightarrow {p} = \mathbf{G}\overrightarrow {p}(0)$ .

?

Problem 7.10.5

Verify that

\overrightarrow {x}(k) = \mathbf{A}^k\overrightarrow {x}(0) \quad \text{and} \quad \overrightarrow {x}(k) = \mathbf{A}^k\overrightarrow {x}(0) + \sum _{j=0}^{k-1}\mathbf{A}^{k-j-1}\overrightarrow {b}(j) \quad \text{for } k=1,2,3,\ldots

are indeed the respective solutions to the difference equations $\overrightarrow {x}(k+1) = \mathbf{A}\overrightarrow {x}(k)$ (a homogeneous system) and $\overrightarrow {x}(k+1) = \mathbf{A}\overrightarrow {x}(k)+\overrightarrow {b}(k)$ (a nonhomogeneous system).

?

Problem 7.10.6

Prove that if there exists a matrix norm such that $\left\| \mathbf{A}\right\| < 1$ , then $\lim_{k\to \infty }\mathbf{A}^k = \mathbf{0}$ .

?

Problem 7.10.7

By examining the iteration matrix, compare the convergence of Jacobi's method and the Gauss--Seidel method for each of the following coefficient matrices with an arbitrary right-hand side. Explain why this shows that neither method can be universally favored over the other.

\mathbf{A}_1 = \begin{pmatrix} 1 & 2 & -2 \\ 1 & 1 & 1 \\ 2 & 2 & 1 \end{pmatrix}, \quad \mathbf{A}_2 = \begin{pmatrix} 2 & -1 & 1 \\ 2 & 2 & 2 \\ -1 & -1 & 2 \end{pmatrix}.

?

Problem 7.10.8

(a)(b)(c)(d)

Let $\mathbf{A} = \begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix}$ (the finite-difference matrix of Example 1.4.1).

?

(a)

Verify that $\mathbf{A}$ satisfies the special-case conditions that guarantee the validity of the SOR optimum-relaxation formula: $\operatorname {det}\left(\alpha \mathbf{D}-\mathbf{L}-\mathbf{U}\right) = \operatorname {det}\left(\alpha \mathbf{D}-\beta \mathbf{L}-\beta^{-1}\mathbf{U}\right)$ for all real $\alpha$ and $\beta \ne 0$ , and the Jacobi iteration matrix $\mathbf{H}_J$ has real eigenvalues with $\rho (\mathbf{H}_J)<1$ , where $\mathbf{D}$ , $\mathbf{L}$ , $\mathbf{U}$ are $\mathbf{A}$ 's diagonal, strictly-lower, and strictly-upper parts.

(b)

Determine the optimum SOR relaxation parameter, given that $\omega_{\text{opt}} = \dfrac {2}{1+\sqrt{1-\rho^2(\mathbf{H}_J)}}$ and $\rho (\mathbf{H}_{\omega_{\text{opt}}}) = \omega_{\text{opt}}-1$ .

(c)

Find the asymptotic rates of convergence for Jacobi, Gauss--Seidel, and optimum SOR.

(d)

Use $\overrightarrow {x}(0) = (1,1,1)^T$ and $\overrightarrow {b} = (2,4,6)^T$ to run through several steps of Jacobi, Gauss--Seidel, and optimum SOR to solve $\mathbf{A}\overrightarrow {x}=\overrightarrow {b}$ until you can see a convergence pattern.

Problem 7.10.9

Prove that if $\rho (\mathbf{H}_{\omega }) < 1$ , where $\mathbf{H}_{\omega }$ is the iteration matrix for the SOR method, then $0 < \omega < 2$ .

?

Remark.

?

Hint: Use $\operatorname {det}\left(\mathbf{H}_{\omega }\right)$ to show $\left|\lambda_k\right| \ge \left|1-\omega \right|$ for some $\lambda_k \in \sigma (\mathbf{H}_{\omega })$ .

Problem 7.10.10

Show that the spectral radius of the Jacobi iteration matrix for the discrete Laplacian $\mathbf{L}_{n^2\times n^2}$ described in Example 7.6.2 is $\rho (\mathbf{H}_J) = \cos \bigl(\pi /(n+1)\bigr)$ .

?

Problem 7.10.11

Consider a scalar sequence $\left\{ \alpha_1, \alpha_2, \alpha_3, \ldots \right\}$ and the associated Cesaro sequence of averages $\left\{ \mu_1, \mu_2, \mu_3, \ldots \right\}$ , where $\mu_n = (\alpha_1+\alpha_2+\cdots +\alpha_n)/n$ . Prove that if $\left\{ \alpha_n\right\}$ converges to $\alpha$ , then $\left\{ \mu_n\right\}$ also converges to $\alpha$ .

?

Remark.

?

Like scalars, a vector sequence $\left\{ \overrightarrow {v}_n\right\}$ in a finite-dimensional space converges to $\overrightarrow {v}$ if and only if for each $\varepsilon >0$ there is a natural number $N=N(\varepsilon )$ such that $\left\| \overrightarrow {v}_n-\overrightarrow {v}\right\| <\varepsilon$ for all $n\ge N$ , and it doesn't matter which norm is used. Therefore, your proof should also be valid for vectors (and matrices).

Problem 7.10.12

For matrices with nonpositive off-diagonal entries ( $Z$ -matrices), prove that the following statements are equivalent.

?

(a)

$\mathbf{A}$ is an $M$ -matrix.

(b)

All leading principal minors of $\mathbf{A}$ are positive.

(c)

$\mathbf{A}$ has an $\mathbf{L}\mathbf{U}$ factorization, and both $\mathbf{L}$ and $\mathbf{U}$ are $M$ -matrices.

(d)

There exists a vector $\overrightarrow {x}>\overrightarrow {0}$ such that $\mathbf{A}\overrightarrow {x}>\overrightarrow {0}$ .

(e)

Each $a_{ii}>0$ and $\mathbf{A}\mathbf{D}$ is diagonally dominant for some diagonal matrix $\mathbf{D}$ with positive diagonal entries.

(f)

$\mathbf{A}\overrightarrow {x} \ge \overrightarrow {0}$ implies $\overrightarrow {x} \ge \overrightarrow {0}$ .

Problem 7.10.13

(a)(b)

Suppose that $\lambda \in \sigma (\mathbf{A})$ , and let $\mathbf{M}_1 = \mathbf{A}-\lambda \mathbf{I}$ . The following procedure yields the value of $\operatorname {index}(\lambda )$ : factor $\mathbf{M}_1 = \mathbf{B}_1\mathbf{C}_1$ as a full-rank factorization, set $\mathbf{M}_2 = \mathbf{C}_1\mathbf{B}_1$ , factor $\mathbf{M}_2 = \mathbf{B}_2\mathbf{C}_2$ as a full-rank factorization, set $\mathbf{M}_3 = \mathbf{C}_2\mathbf{B}_2$ , and so on. In general, $\mathbf{M}_i = \mathbf{C}_{i-1}\mathbf{B}_{i-1}$ , where $\mathbf{M}_{i-1} = \mathbf{B}_{i-1}\mathbf{C}_{i-1}$ is a full-rank factorization.

?

(a)

Explain why this procedure must eventually produce a matrix $\mathbf{M}_k$ that is either nonsingular or zero.

(b)

Prove that if $k$ is the smallest positive integer such that $\mathbf{M}_k^{-1}$ exists or $\mathbf{M}_k = \mathbf{0}$ , then

\operatorname {index}(\lambda ) = \begin{cases} k-1 & \text{if } \mathbf{M}_k \text{ is nonsingular}, \\ k & \text{if } \mathbf{M}_k = \mathbf{0}. \end{cases}

Problem 7.10.14

Use the procedure in Exercise 7.10.13 to find the index of each eigenvalue of $\mathbf{A} = \begin{pmatrix} -3 & -8 & -9 \\ 5 & 11 & 9 \\ -1 & -2 & 1 \end{pmatrix}$ .

?

Remark.

?

Hint: $\sigma (\mathbf{A}) = \left\{ 4,1\right\}$ .

Problem 7.10.15

(a)(b)

Let $\mathbf{A}$ be the matrix given in Exercise 7.10.14.

?

(a)

Find the Jordan form for $\mathbf{A}$ .

(b)

For any function $f$ defined at $\mathbf{A}$ , find the Hermite interpolation polynomial, and describe $f(\mathbf{A})$ .

Problem 7.10.16

Given a matrix $\mathbf{B}_{n\times n}$ of rank $r$ such that $\operatorname {index}(\mathbf{B}) \le 1$ (i.e., $\operatorname {index}(\lambda =0)\le 1$ ), the Jordan form for $\mathbf{B}$ looks like $\begin{pmatrix} 0 & 0 \\ 0 & \mathbf{C}_{r\times r} \end{pmatrix} = \mathbf{P}^{-1}\mathbf{B}\mathbf{P}$ , so $\mathbf{B} = \mathbf{P}\begin{pmatrix} 0 & 0 \\ 0 & \mathbf{C} \end{pmatrix}\mathbf{P}^{-1}$ , where $\mathbf{C}$ is nonsingular. This implies that $\mathbf{B}$ belongs to an algebraic group $\mathcal{G}$ with respect to matrix multiplication, and the inverse of $\mathbf{B}$ in $\mathcal{G}$ is $\mathbf{B}^{\# } = \mathbf{P}\begin{pmatrix} 0 & 0 \\ 0 & \mathbf{C}^{-1} \end{pmatrix}\mathbf{P}^{-1}$ ; $\mathbf{B}^{\# }$ is called the group inverse of $\mathbf{B}$ . Prove that if $\lim_{k\to \infty }\mathbf{A}^k$ exists, and if $\mathbf{B} = \mathbf{I}-\mathbf{A}$ , then

\lim _{k\to \infty }\mathbf{A}^k = \mathbf{I}-\mathbf{B}\mathbf{B}^{\# }.

In other words, the limiting matrix can be characterized as the difference of two identity elements--- $\mathbf{I}$ is the identity in the multiplicative group of nonsingular matrices, and $\mathbf{B}\mathbf{B}^{\# }$ is the identity element in the multiplicative group containing $\mathbf{B}$ .

Limits of powers: for $\mathbf{A} \in \mathbb {C}^{n \times n}$ , $\lim_{k\to \infty }\mathbf{A}^k$ exists if and only if $\rho (\mathbf{A})<1$ , or else $\rho (\mathbf{A})=1$ where $\lambda =1$ is the only eigenvalue on the unit circle and $\lambda =1$ is semisimple.

?

Problem 7.10.17

If $\mathbf{M}_{n\times n}$ is a group matrix (i.e., if $\operatorname {index}(\mathbf{M}) \le 1$ ), then the group inverse of $\mathbf{M}$ can be characterized as the unique solution $\mathbf{M}^{\# }$ of the equations $\mathbf{M}\mathbf{M}^{\# }\mathbf{M} = \mathbf{M}$ , $\mathbf{M}^{\# }\mathbf{M}\mathbf{M}^{\# } = \mathbf{M}^{\# }$ , and $\mathbf{M}\mathbf{M}^{\# } = \mathbf{M}^{\# }\mathbf{M}$ . In fact, some authors use these equations to define $\mathbf{M}^{\# }$ . Use this characterization to show that if $\mathbf{M} = \mathbf{B}\mathbf{C}$ is any full-rank factorization of $\mathbf{M}$ , then $\mathbf{M}^{\# } = \mathbf{B}(\mathbf{C}\mathbf{B})^{-2}\mathbf{C}$ . In particular, if $\mathbf{M} = \mathbf{U}_1\mathbf{D}\mathbf{V}_1^{*}$ is the full-rank factorization derived from the singular value decomposition, then

\mathbf{M}^{\# } = \mathbf{U}_1\mathbf{D}^{-1/2}(\mathbf{V}_1^{*}\mathbf{U}_1)^{-2}\mathbf{D}^{-1/2}\mathbf{V}_1^{*} = \mathbf{U}_1\mathbf{D}^{-1}(\mathbf{V}_1^{*}\mathbf{U}_1)^{-2}\mathbf{V}_1^{*} = \mathbf{U}_1(\mathbf{V}_1^{*}\mathbf{U}_1)^{-2}\mathbf{D}^{-1}\mathbf{V}_1^{*}.

?