4.6 Practice Problems
Problem 4.6.1. Solve \(2x_1+x_2+x_3 = 1\), \(4x_1+3x_2+3x_3 = 1\), \(8x_1+7x_2+9x_3 = -1\) by Gaussian elimination, and find the LU factorization of the coefficient matrix. Use it to compute \(\det A\).
Show solution
Solution. The multipliers are \(m_{21} = 2\), \(m_{31} = 4\), then \(m_{32} = 3\): \[L = \begin {pmatrix}1&0&0\\2&1&0\\4&3&1\end {pmatrix},\qquad U = \begin {pmatrix}2&1&1\\0&1&1\\0&0&2\end {pmatrix}.\] Forward substitution gives \(\mathbf y = (1,-1,-2)\) and backward substitution \(\mathbf x = (1,0,-1)\). Since \(\det L = 1\), \(\det A = \det U = 2\cdot 1\cdot 2 = 4\).
Problem 4.6.2. Find the Cholesky factor of \(A = \begin {pmatrix}4&2&2\\2&10&7\\2&7&21\end {pmatrix}\).
Show solution
Solution. \(l_{11} = 2\), \(l_{21} = 1\), \(l_{31} = 1\); \(l_{22} = \sqrt {10-1} = 3\), \(l_{32} = \frac {7-1}{3} = 2\); \(l_{33} = \sqrt {21-1-4} = 4\). So \(L = \begin {pmatrix}2&0&0\\1&3&0\\1&2&4\end {pmatrix}\), and since the algorithm ran with positive square roots, \(A\) is positive definite.
Problem 4.6.3. Show that \(A = \begin {pmatrix}1&2\\2&1\end {pmatrix}\) is not positive definite, and show how Cholesky’s algorithm detects this.
Show solution
Solution. With \(\mathbf x = (1,-1)^T\), \(\mathbf x^TA\mathbf x = 1-2-2+1 = -2<0\). Cholesky’s algorithm gives \(l_{11} = 1\), \(l_{21} = 2\), and then requires \(l_{22} = \sqrt {1-4} = \sqrt {-3}\), which is not real: the algorithm fails exactly as Theorem 4.5.4 predicts.
Problem 4.6.4. Show that the product of two unit lower triangular matrices is unit lower triangular, and that the inverse of a unit lower triangular matrix is unit lower triangular.
Show solution
Solution. If \(L, M\) are lower triangular, \((LM)_{ij} = \sum _kl_{ik}m_{kj}\), and \(l_{ik} = 0\) unless \(k\leq i\), \(m_{kj} = 0\) unless \(k\geq j\); so the sum is empty when \(i<j\), and for \(i = j\) it is \(l_{ii}m_{ii} = 1\). For the inverse, solving \(L\mathbf x = \mathbf e_j\) by forward substitution gives \(x_i = 0\) for \(i<j\) and \(x_j = 1\), so the \(j\)th column of \(L^{-1}\) has zeros above a \(1\) on the diagonal.
Problem 4.6.5. Verify that \(A = \begin {pmatrix}7&2&0\\3&5&-1\\0&5&-6\end {pmatrix}\) is strictly diagonally dominant, and perform Gaussian elimination without pivoting to find \(\det A\). Check that each reduced matrix is again strictly diagonally dominant. Are the multipliers all less than \(1\) in absolute value?
Show solution
Solution. \(7>2+0\), \(5>3+1\), \(6>0+5\). Elimination: \(m_{21} = \frac 37\), giving row \(2\): \((0, 5-\frac 67, -1) = (0,\frac {29}{7},-1)\); \(m_{32} = \frac {5}{29/7} = \frac {35}{29}\). The reduced \(2\times 2\) matrix \(\begin {pmatrix}29/7&-1\\5&-6\end {pmatrix}\) is strictly diagonally dominant (\(\frac {29}{7}>1\) and \(6>5\)), as Theorem 4.5.2 guarantees, but the multiplier \(\frac {35}{29}\) exceeds \(1\): row dominance bounds the growth of the entries, not the size of the multipliers. The last pivot is \(-6+\frac {35}{29} = -\frac {139}{29}\), so \(\det A = 7\cdot \frac {29}{7}\cdot \left (-\frac {139}{29}\right ) = -139\).
Problem 4.6.6. How many multiplications does Gaussian elimination need for a tridiagonal system of size \(n\) if the zeros are not exploited, and how many with Algorithm 4.5.6? Compare for \(n = 10^4\).
Show solution
Solution. Ignoring the zeros, about \(\frac {n^3}{3} = 3.3\times 10^{11}\) multiplications; with the tridiagonal algorithm, \(5n-4\approx 5\times 10^4\). At \(10^9\) operations per second, the first takes over five minutes and the second fifty microseconds. Exploiting structure matters more than the speed of the machine.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.