Choosing Solution Methods - Linear Algebra

  1. How is Qx=bQ\mathbf{x} = \mathbf{b} solved most efficiently when QQ is an orthogonal matrix?
    x=QTb\mathbf{x} = Q^T\mathbf{b}, since Q−1=QTQ^{-1} = Q^T.
  2. To solve Ax=bA\mathbf{x} = \mathbf{b} once for a large n×nn \times n matrix, why is elimination preferred over computing A−1A^{-1}?
    Elimination takes about 23n3\frac{2}{3}n^3 operations, roughly a third of the cost of forming A−1A^{-1}, and is usually more accurate.
  3. Which method fits a system whose matrix is singular or not square, to describe all solutions?
    Row reduce the augmented matrix to (reduced) echelon form. No inverse exists to use.
  4. Which method is efficient for solving Ax=bA\mathbf{x} = \mathbf{b} with one matrix AA and many different vectors b\mathbf{b}?
    Factor A=LUA = LU once, then for each b\mathbf{b} do one forward and one back substitution.
  5. Why is QR factorization usually preferred over the normal equations for least squares in floating point?
    Forming ATAA^TA squares the condition number, which can lose accuracy; QR works with AA directly.
  6. What is the purpose of partial pivoting in Gaussian elimination?
    Choosing the largest available pivot in absolute value avoids dividing by small numbers and limits round-off growth.
  7. Why is Cramer's rule impractical for solving a large system Ax=bA\mathbf{x} = \mathbf{b}?
    It needs n+1n + 1 determinants of size nn; it is useful only for small systems or theoretical formulas.
  8. How is Dx=bD\mathbf{x} = \mathbf{b} solved when DD is diagonal with nonzero diagonal entries?
    Divide each entry: xi=bidiix_i = \frac{b_i}{d_{ii}}.
  9. About how many operations does solving a triangular n×nn \times n system by substitution take, in order of magnitude?
    About n2n^2, which is far cheaper than the order n3n^3 cost of elimination.
  10. Which factorization is the efficient choice when AA is symmetric positive definite?
    The Cholesky factorization A=LLTA = LL^T, which needs about half the work of LU.
  11. How should Ax=bA\mathbf{x} = \mathbf{b} be solved when AA is upper triangular with nonzero diagonal?
    By back substitution directly. No elimination is needed.

Study these flashcards