Week 8 - More on Matrix Inversion

1. Gauss-Jordan Elimination

  • The key of Gauss-Jordan Elimination is to transfer matrix A to the identity matrix:

  • Ax=bAx=b

  • If A is non-singular, then:
    • A1Ax=xA1b=xx=A1bA^{-1}Ax = x \to A^{-1}b = x \to x = A^{-1}b

1.1. Computing A^−1 via Gauss-Jordan Elimination

  • Notice ,α11=1/α11\alpha_{11} = 1 / \alpha_{11}. Every iteration, we scale α11\alpha_{11} to 1.

1.2. Cost of inverting a matrix

  • Via Gauss-Jordan, taking advantage of zeroes in the appended identity matrix, requires approximately 2n32n^3 floating point operations.

1.3. (Almost) never, ever invert a matrix

  • Solving Ax = b should be accomplished by first computing its LU factorization (possibly with partial pivoting) and then solving with the triangular matrices.

2. Symmetric Positive Definite(SPD) Matrices

  • Definition: Let ARn×nA \in \mathbb{R}^{n \times n}. Matrix A is said to be symmetric positive definite(SPD) if

    • A is symmetric; and
    • xTAx>0x^T A x > 0 for all nonzero vector xRnx \in \mathbb{R}^n.
  • Consider the quadratic polynomial p(χ)=αχ2+βχ+γ=χαχ+βχ+γp(\chi) = \alpha \chi^2 + \beta \chi + \gamma = \chi \alpha \chi + \beta \chi + \gamma

  • The graph of this function is a parabola that is “concaved up” if α>0\alpha > 0. In that case, it attains a minimum at a unique value χ\chi.
  • Now consider the vector function f:RnRf: \mathbb{R}^n \to \mathbb{R} given by f(x)=xTAx+bTx+γf(x) = x^T A x + b^T x + \gamma where ARn×n,bRn, and γRA \in \mathbb{R}^{n \times n}, b \in \mathbb{R}^n, \text{ and } \gamma \in \mathbb{R} are all given. If A is a SPD matrix, then this equation is minimized for a unique vector x. If n=2n = 2, plotting this function when A is SPD yields a paraboloid that is concaved up:

2.1. Solving Ax = b when A is Symmetric Positive Definite

Cholesky factorization theorem

  • Let ARn×nA \in \mathbb{R}^{n \times n} be a SPD matrix. Then there exists a lower trianglar matrix LRn×nL \in \mathbb{R}^{n \times n} such that A=LLTA = LL^T. If the diagonal elements of L are chosen to be positive, this factorization is unique.
  • Algorithm:
  • Notice that α11:=α11\alpha_{11} := \sqrt{\alpha_{11} } and a21:=a21/α11a_{21} := a_{21}/\alpha_{11} which are legal if α>0\alpha > 0. It turns out that if A is SPD, then
    • α11>0\alpha_{11} > 0 in the first iteration and hence α11:=α11\alpha_{11} := \sqrt{\alpha_{11} } and a21:=a21/α11a_{21} := a_{21}/\alpha_{11} are legal; and
    • A22:=A22a21a21TA_{22} := A_{22} - a_{21} a_{21}^T is again a SPD matrix.

results matching ""

    No results matching ""