28.1 Solving systems of linear equations

28.1-1

Solve the equation

\[ \begin{pmatrix} 1 & 0 & 0 \\\\ 4 & 1 & 0 \\\\ -6 & 5 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\\\ x_2 \\\\ x_3 \end{pmatrix} = \begin{pmatrix} 3 \\\\ 14 \\\\ -7 \end{pmatrix} \]

by using forward substitution.

\[ \begin{pmatrix} 3 \\\\ 14 - 4 \cdot 3 \\\\ -7 - 5 \cdot (14 - 4 \cdot 3) - (-6) \cdot 3 \end{pmatrix} = \begin{pmatrix} 3 \\\\ 2 \\\\ 1 \end{pmatrix} . \]

28.1-2

Find an \(\text{LU}\) decomposition of the matrix

\[ \begin{pmatrix} 4 & -5 & 6 \\\\ 8 & -6 & 7 \\\\ 12 & -7 & 12 \end{pmatrix} . \]

\[ \begin{pmatrix} 4 & -5 & 6 \\\\ 8 & -6 & 7 \\\\ 12 & -7 & 12 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\\\ 2 & 1 & 0 \\\\ 3 & 2 & 1 \end{pmatrix} \begin{pmatrix} 4 & -5 & 6 \\\\ 0 & 4 & -5 \\\\ 0 & 0 & 4 \end{pmatrix} . \]

28.1-3

Solve the equation

\[ \begin{pmatrix} 1 & 5 & 4 \\\\ 2 & 0 & 3 \\\\ 5 & 8 & 2 \end{pmatrix} \begin{pmatrix} x_1 \\\\ x_2 \\\\ x_3 \end{pmatrix} = \begin{pmatrix} 12 \\\\ 9 \\\\ 5 \end{pmatrix} \]

by using forward substitution.

We have

\[ \begin{aligned} A & = \begin{pmatrix} 1 & 5 & 4 \\\\ 2 & 0 & 3 \\\\ 5 & 8 & 2 \end{pmatrix} , \\\\ b & = \begin{pmatrix} 12 \\\\ 9 \\\\ 5 \end{pmatrix} , \end{aligned} \]

and we with to solve for the unknown \(x\). The \(\text{LUP}\) decomposition is

\[ \begin{aligned} L & = \begin{pmatrix} 1 & 0 & 0 \\\\ 0.2 & 1 & 0 \\\\ 0.4 & -\frac{3.2}{3.4} & 1 \end{pmatrix} , \\\\ U & = \begin{pmatrix} 5 & 8 & 2 \\\\ 0 & 3.4 & 3.6 \\\\ 0 & 0 & 2.2 + \frac{11.52}{3.4} \end{pmatrix} , \\\\ P & = \begin{pmatrix} 0 & 0 & 1 \\\\ 1 & 0 & 0 \\\\ 0 & 1 & 0 \end{pmatrix} . \end{aligned} \]

Using forward substitution, we solve \(Ly = Pb\) for \(y\):

\[ \begin{pmatrix} 1 & 0 & 0 \\\\ 0.2 & 1 & 0 \\\\ 0.4 & -\frac{3.2}{3.4} & 1 \end{pmatrix} \begin{pmatrix} y_1 \\\\ y_2 \\\\ y_3 \end{pmatrix} = \begin{pmatrix} 5 \\\\ 12 \\\\ 9 \end{pmatrix} , \]

obtaining

\[ y = \begin{pmatrix} 5 \\\\ 11 \\\\ 7 + \frac{35.2}{3.4} \end{pmatrix} \]

by computing first \(y_1\), then \(y_2\), and finally \(y_3\). Using back substitution, we solve \(Ux = y\) for \(x\):

\[ \begin{pmatrix} 5 & 8 & 2 \\\\ 0 & 3.4 & 3.6 \\\\ 0 & 0 & 2.2 + \frac{11.52}{3.4} \end{pmatrix} \begin{pmatrix} x_1 \\\\ x_2 \\\\ x_3 \end{pmatrix} = \begin{pmatrix} 5 \\\\ 11 \\\\ 7 + \frac{35.2}{3.4} \end{pmatrix} , \]

thereby obtaining the desired answer

\[ x = \begin{pmatrix} -\frac{3}{19} \\\\ -\frac{1}{19} \\\\ \frac{49}{19} \end{pmatrix} \]

by computing first \(x_3\), then \(x_2\), and finally \(x_1\).

28.1-4

Describe the \(\text{LUP}\) decomposition of a diagonal matrix.

The \(\text{LUP}\) decomposition of a diagonal matrix \(D\) is \(D = IDI\) where \(I\) is the identity matrix.

28.1-5

Describe the \(\text{LUP}\) decomposition of a permutation matrix \(A\), and prove that it is unique.

(Omit!)

28.1-6

Show that for all \(n \ge 1\), there exists a singular \(n \times n\) matrix that has an \(\text{LU}\) decomposition.

The zero matrix always has an \(\text{LU}\) decomposition by taking \(L\) to be any unit lower-triangular matrix and \(U\) to be the zero matrix, which is upper triangular.

28.1-7

In \(\text{LU-DECOMPOSITION}\), is it necessary to perform the outermost for loop iteration when \(k = n\)? How about in \(\text{LUP-DECOMPOSITION}\)?

For \(\text{LU-DECOMPOSITION}\), it is indeed necessary. If we didn't run the line 6 of the outermost for loop, \(u_{nn}\) would be left its initial value of \(0\) instead of being set equal to \(a_{nn}\). This can clearly produce incorrect results, because the \(\text{LU-DECOMPOSITION}\) of any non-singular matrix must have both \(L\) and \(U\) having positive determinant. However, if \(u_{nn} = 0\), the determinant of \(U\) will be \(0\) by problem D.2-2.

For \(\text{LUP-DECOMPOSITION}\), the iteration of the outermost for loop that occurs with \(k = n\) will not change the final answer. Since \(\pi\) would have to be a permutation on a single element, it cannot be non-trivial. and the for loop on line 16 will not run at all.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用