Introduction to Probability

Multivariable Calculus

Algorithms: Part II

Algorithms: Part I

Introduction to Software Design and Architecture

Calculus Two: Sequences and Series

LAFF Linear Algebra

Stanford Machine Learning

Calculus One

Computational Thinking

Effective Thinking Through Mathematics

CS50 Introduction to Computer Science

Others

Week 6 - Gaussian Elimination

Gaussian Elimination

  • To solv the linear system:
    • 2χ0+4χ12χ2=104χ02χ1+6χ2=206χ04χ1+2χ2=18\begin{array}{c c c c c c} 2 \chi_0 & + & 4 \chi_1 & - & 2 \chi_2 & = & -10 \\ 4 \chi_0 & - & 2 \chi_1 & + & 6 \chi_2 & = & 20 \\ 6 \chi_0 & - & 4 \chi_1 & + & 2 \chi_2 & = & 18 \end{array}

Procedures

  • Transform linear system of equations to an upper triangular system

    • Subtract λ1,0=(4/2)=2\lambda_{1,0} = (\color{blue}{4} / \color{red}{2} ) = 2 times the first equation from the second equation:

      • BeforeAfter2χ0+4χ12χ2=104χ02χ1+6χ2=206χ04χ1+2χ2=182χ0+4χ12χ2=1010χ1+10χ2=406χ04χ1+2χ2=18\begin{array}{c | c} \text{Before} & \text{After} \\ \begin{array}{c c c c c c} \color{red}{2} \chi_0 & + & 4 \chi_1 & - & 2 \chi_2 & = & -10 \\ 4 \chi_0 & - & 2 \chi_1 & + & 6 \chi_2 & = & 20 \\ 6 \chi_0 & - & 4 \chi_1 & + & 2 \chi_2 & = & 18 \end{array} & \begin{array}{c c c c c c} 2 \chi_0 & + & 4 \chi_1 & - & 2 \chi_2 & = & -10 \\ & - & 10 \chi_1 & + & 10 \chi_2 & = & 40 \\ 6 \chi_0 & - & 4 \chi_1 & + & 2 \chi_2 & = & 18 \end{array} \end{array}

    • Subtract λ2,0=(6/2)=3\lambda_{2,0} = ( \color{blue}{6} / \color{red}{2} ) = 3 times the first equation from the third equation:

      • BeforeAfter2χ0+4χ12χ2=1010χ1+10χ2=406χ04χ1+2χ2=182χ0+4χ12χ2=1010χ1+10χ2=4016χ1+8χ2=48\begin{array}{c | c} \text{Before} & \text{After} \\ \begin{array}{c c c c c c} \color{red}{2} \chi_0 & + & 4 \chi_1 & - & 2 \chi_2 & = & -10 \\ & - & 10 \chi_1 & + & 10 \chi_2 & = & 40 \\ \color{blue}{6} \chi_0 & - & 4 \chi_1 & + & 2 \chi_2 & = & 18 \end{array} & \begin{array}{c c c c c c} 2 \chi_0 & + & 4 \chi_1 & - & 2 \chi_2 & = & -10 \\ & - & 10 \chi_1 & + & 10 \chi_2 & = & 40 \\ & - & 16 \chi_1 & + & 8 \chi_2 & = & 48 \end{array} \end{array}

    • Subtract λ2,0=(16/10)=1.6\lambda_{2,0} = ( \color{blue}{-16} / \color{red}{-10} ) = 1.6 times the second equation from the third equation:

    • BeforeAfter2χ0+4χ12χ2=1010χ1+10χ2=4016χ1+8χ2=482χ0+4χ12χ2=1010χ1+10χ2=408χ2=16\begin{array}{c | c} \text{Before} & \text{After} \\ \begin{array}{c c c c c c} 2 \chi_0 & + & 4 \chi_1 & - & 2 \chi_2 & = & -10 \\ & \color{red}{-} & \color{red}{10 \chi_1} & + & 10 \chi_2 & = & 40 \\ & \color{red}{-} & \color{red}{16 \chi_1} & + & 8 \chi_2 & = & 48 \end{array} & \begin{array}{c c c c c c} 2 \chi_0 & + & 4 \chi_1 & - & 2 \chi_2 & = & -10 \\ & - & 10 \chi_1 & + & 10 \chi_2 & = & 40 \\ & & & - & 8 \chi_2 & = & - 16 \end{array} \end{array}

    • This now leaves us with an upper triangular system of linear equations.

  • Back substitution (solve the upper triangular system)

    • The equivalent upper triangular system of equations is now solved via back substitution:
      • Consider the last equation, $$-8 \chi_2 = -16.$$ Scaling both sides by by 1/(−8) we find that $$\chi_2 = -16/(-8) = 2.$$
      • Next, consider the second equation, $$-10 \chi_1 + 10 \chi_2 = 40.$$ We know that χ2=2\chi_2 = 2, which we plug into this equation to yield $$-10\chi_1 + 10( \color{blue}{2} = 40.)$$ Rearranging this we find that $$\chi_1 = (40 - 10( \color{blue}{2} ))/(-10) = -2.$$
      • Finally, consider the first equation, $$2\chi_0 + 4\chi_1 - 2\chi_2 = -10$$ We know that χ2=2\chi_2 = \color{blue}{2} and χ1=2\chi_1 = \color{blue}{-2}, which we plug into this equation to yield $$2\chi_0 + 4( \color{blue}{-2} ) - 2( \color{blue}{2} ) = -10.$$ Rearranging this we find that $$\chi_0 = (-10 - (4( \color{blue}{-2} ) - (2)( \color{blue}{2} )))/2 = 1.$$
  • Thus, the solution is vector $$x = \left(\begin{array}{c} \chi_0 \ \chi_1 \ \chi_2 \end{array}\right) = \left(\begin{array}{c} 1 \ -2 \ 2 \end{array}\right).$$

  • Check your answer (by plugging χ0=1,χ1=2,and χ2=2\chi_0 = 1, \chi_1 = -2, \text{and} \ \chi_2 = 2 into the original system).

Representing the system of equations with an appended matrix

Transform matrix to upper triangular matrix

  • Forward substitution (applying the transforms to the right-hand side)

Algorithms

Solving Ax = b via LU Factorization

LU Factorization

  • A matrix ARn×nA \in R^{n \times n} can be factored into the product of two matrices L,URn×nL,U \in R^{n \times n} : $$A= LU$$ where L is unit lower triangular and U is upper triangular.
  • LU Factorization is transfer A to a LU combined matrix.
    • We can do this, because L is unit lower triangle matrix and U is upper triangle matrix.
  • After rearrange, we get:
  • Partition matrix A:
    • Update a21=a21/α11(=l21)a_{21} = a_{21}/ \alpha_{11} (= l_{21})
    • Update A22=A22a21a12TA_{22} = A_{22} - a_{21} a_{12}^T (Rank-1 update!)
    • Overwrite A22A_{22} with L22L_{22} and U22U_{22} by repeating with A=A22A = A_{22}.
  • This will leave U in the upper triangular part of A and the strictly lower triangular part of L in the strictly lower triangular part of A. The diagonal elements of L need not be stored, since they are known to equal one.

Algorithm

Where is this going?

  1. Want to solve: Ax=bAx = b

    • Give A and b, solve x.
    • A=(2+4242+664+2),b=(102018)A = \left(\begin{array}{c c c} 2 & + 4 & - 2 \\ 4 & - 2 & + 6 \\ 6 & - 4 & + 2 \end{array}\right), b = \left(\begin{array}{c} -10 \\ 20 \\ 18 \end{array}\right)

  2. Now we find triangular L and U so that: A=LUA = LU

    • U is the transformed A matrix
    • A is the coefficients which transfers A to U
    • Transfered:
      • A(2+422101031.68),L=(10021031.61),U=(2+42010+10008)A \to \left(\begin{array}{c c c} 2 & + 4 & - 2 \\ \scriptsize{2} & - 10 & - 10 \\ \scriptsize{3} & \scriptsize{1.6} & - 8 \end{array}\right), L = \left(\begin{array}{c c c} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 1.6 & 1 \end{array}\right), U = \left(\begin{array}{c c c} 2 & + 4 & - 2 \\ 0 & - 10 & + 10 \\ 0 & 0 & - 8 \end{array}\right)

  3. Substitute: (LU)x=b(LU)x = b => L(Ux)=bL(Ux) = b

  4. Replace Ux with y. (y=Uxy = Ux) => Ly=bLy = b

  5. Solve Ly=bLy = b for yy. (More details in next section)

    • This is forward substitution (applying the transforms to the right-hand side).
    • (10021031.61)×(y0y1y2)=(102018)\left(\begin{array}{c c c} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 1.6 & 1 \end{array}\right) \times \left(\begin{array}{c} y_0 \\ y_1 \\ y_2 \end{array}\right) = \left(\begin{array}{c} -10 \\ 20 \\ 18 \end{array}\right)

    • (10202y0183y0)(1040481.6y1)(104016)\to \left(\begin{array}{c} -10 \\ 20 - 2 y_0 \\ 18 - 3 y_0 \end{array}\right) \to \left(\begin{array}{c} -10 \\ 40 \\ 48 - 1.6 y_1 \end{array}\right) \to \left(\begin{array}{c} -10 \\ 40 \\ -16 \end{array}\right)

  6. Solve Ux=yUx = y for xx. (More details in next next section)

    • This is back substitution (solve x).
    • (2+42010+10008)×(x0x1x2)=(104016)\left(\begin{array}{c c c} 2 & + 4 & - 2 \\ 0 & - 10 & + 10 \\ 0 & 0 & - 8 \end{array}\right) \times \left(\begin{array}{c} x_0 \\ x_1 \\ x_2 \end{array}\right) = \left(\begin{array}{c} -10 \\ 40 \\ -16 \end{array}\right)

      • (1040168=2)(104010×210=22)(104×(2)(2)×22=122)(122)\to \left(\begin{array}{c} -10 \\ 40 \\ \frac{-16}{-8} = \color{blue}{2} \end{array}\right) \to \left(\begin{array}{c} - 10 \\ \frac{40 - 10 \times \color{blue}{2} }{-10} = \color{red}{- 2} \\ \color{blue}{2} \end{array}\right) \to \left(\begin{array}{c} \frac{-10 - 4 \times ( \color{red}{- 2} ) - ( -2 ) \times \color{blue}{2}}{2} = \color{green}{1} \\ \color{red}{- 2} \\ \color{blue}{2} \end{array}\right) \to \left(\begin{array}{c} \color{green}{1} \\ \color{red}{- 2} \\ \color{blue}{2} \end{array}\right)

Solving Lz = b (Forward substitution)

  • Given a unit lower triangular matrix LRn×nL \in \mathbb{R}^{n \times n} and vectors z,bRnz, b \in \mathbb{R}^{n} , consider the equation Lz=bLz = b where L and b are known and z is to be computed. Partition
  • So, solving Lz=bLz = b, overwriting b with z, is forward substitution when L is the unit lower triangular matrix that results from LU factorization.

Algorithm

  • Algorithm for solving Lx = b, overwriting b with the result vector x. Here L is a lower triangular matrix.

Solving Ux = b (Back substitution)

Algorithm

Cost

  • Factoring A=LUA = LU requires, approximately, 23n3\frac{2}{3}n^3 floating point operations.
  • Solve Lz=bLz = b requires, approximately, n2n^2 floating point operations.
  • Solve Ux=zUx = z requires, approximately, n2n^2 floating point operations.