Week 6 - Gaussian Elimination

1. 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}

1.1. 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χ2=16.-8 \chi_2 = -16. Scaling both sides by by 1/(−8) we find that χ2=16/(8)=2.\chi_2 = -16/(-8) = 2.
      • Next, consider the second equation, 10χ1+10χ2=40.-10 \chi_1 + 10 \chi_2 = 40. We know that χ2=2\chi_2 = 2, which we plug into this equation to yield 10χ1+10(2=40.)-10\chi_1 + 10( \color{blue}{2} = 40.) Rearranging this we find that χ1=(4010(2))/(10)=2.\chi_1 = (40 - 10( \color{blue}{2} ))/(-10) = -2.
      • Finally, consider the first equation, 2χ0+4χ12χ2=102\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χ0+4(2)2(2)=10.2\chi_0 + 4( \color{blue}{-2} ) - 2( \color{blue}{2} ) = -10. Rearranging this we find that χ0=(10(4(2)(2)(2)))/2=1.\chi_0 = (-10 - (4( \color{blue}{-2} ) - (2)( \color{blue}{2} )))/2 = 1.
  • Thus, the solution is vector x=(χ0χ1χ2)=(122).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).

1.2. Representing the system of equations with an appended matrix

1.3. Transform matrix to upper triangular matrix

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

1.4. Algorithms

2. Solving Ax = b via LU Factorization

2.1. 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=LUA= 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

2.2. 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. (Next Section)

    • This is forward substitution (applying the transforms to the right-hand side).
    • (10021031.61)×(y0y1y2)=(102018)(10202y0183y0)(1040481.6y1)(104016)\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) \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. (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)

2.3. 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.

2.4. Solving Ux = b (Back substitution)

Algorithm

2.5. 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.

results matching ""

    No results matching ""