2.3-exam1-2011¶
Quiz 1, 2011 · Section 2.3: Matrix Computations and A = LU Source: exam1_2.pdf, pp. 9-10
Problem¶
2 (23 pts.) \(A\) is a square 3 by 3 matrix whose LU decomposition exists with no row exchanges. Carefully provide a count of the exact number of operations required to compute the three parameters \(l_{12}, l_{13}\), and \(l_{23}\) of \(L\) and the six parameters of \(U\). The questions below count first all the divisions, then all the multiplications, and then all the subtractions that occur. Avoid any unnecessary operations. (Operations on the elements being eliminated are unnecessary since that element's ultimate fate is known to be 0.) (a) (5 pts.) We recall that computation of each multiplier \(l_{ij}\) requires one division. The exact number of divisions in the LU decomposition of our 3 by 3 \(A\) is _. (b) (9 pts.) We recall that multipliers \(l_{ij}\) multiply the \(j\)th row but only to the right of column \(j\). The exact number of multiplications in the entire LU decomposition of our 3 by 3 \(A\) is _. (c) (9 pts.) We recall that after \(l_{ij}\) does its job of multiplying row \(j\) to the right of column \(i\), we subtract row \(j\) from row \(i\) but only to the right of column \(i\). The exact number of subtractions in the entire LU decomposition of our 3 by 3 \(A\) is __.
Solution
(a) 3. Each of the three multipliers \(l_{21}, l_{31}, l_{32}\) requires one division to compute. (b) \(5 = 2^2 + 1^2\). The first row (column) is the pivot row (column) for the first two eliminations. First \(l_{21}\) scales \(A_{12}\) and \(A_{13}\) as a byproduct of the elimination of the (2,1) entry. Then \(l_{31}\) also scales \(A_{12}\) and \(A_{13}\). By the time we have computed \(l_{32}\), it multiplies the value now in \(A_{23}\). In general, no computation need occur in the first row or first column; the total number of multiplications would then be \((n - 1)^2 + \dots + 1\). (c) \(5 = 2^2 + 1\). The subtraction count is always the same as the multiplication count: after \(l_{ij}\) does its job of multiplying row \(j\) to the right of column \(i\), we subtract row \(j\) from row \(i\) but only to the right of column \(i\).Keywords: LU decomposition, operations count, divisions, multiplications, subtractions