CS 314 CLASS NOTES

Upper Triangular System

Lower Triangular System

An Upper Triangular System can be solved easily

This is called "Back Propogation"

• # operations =
  • # divisions = N
  • # subtractions = 1 + 2 + 3 + ... + N = N*(N-1)/2 = O(N²)
  • # multiplications = O(N²)
• O(N²)

Back Substitution

1. 3x + 4y + z = 2
2. 3y + 2z = 1
3. 5z = 10

• Solving an Upper Triangle System of linear equations is O(N²)
• We can convert an arbitrary system of linear equations to be Upper Triangular and then use Back Substitution
  This is what Gauss substitution does

3 elementary transformations that do not affect a linear system of equations:

1. Interchange
      The order of equations can be changed without affecting the solution
   
2. Scaling
      A linear equation can be multiplied by a constant without affecting the solution
   

      Ex:

   x + y = 3

   2(x + y) = 3(2)

   2x + 2y = 6

3. Replacement
      A linear equation can be replaced by the sum of itself and a non-zero multiple of another equation in the system

Gauss Elimination

• Convert a system of linear equations to Upper Triangular using the transformations
• Solve it with back substitution

Augmented Matrix

• Choose a pivot row and pivot element in that row
• Divide the entire row by the pivot element
• Apply transformations to make the elements in the same column as the pivot a

Implementation in Matlab

function x = gauss(A,B)
% Input - A is a NxN nonsingular matrix
%	  B is a Nx1 matrix
% Output - x is a Nx1 matrix with the solution to Ax=B
% Get the dimensions of A
[N N] = size(A)
% Initialize x vector with zero's
x = zeros(N,1)
% construct the augmented matrix
Aug = [A B]
% Gauss Elimination
% pivot all rows
  for p=1:N
    % get pivot
    % include code to handle when pivot is 0
    piv = Aug(p,p)  % not putting a ";" on the end will print out the results to the screen
    % Divide pivotal row by the pivot
    for k = p:N+1
      Aug(p,k) = Aug(p,k)/piv
    end
	% this for loop would be the same with: Aug(p,p:N+1) = Aug(p,p:N+1)/piv
    %put 0's in the other elements of the pivotal column
    for k = p+1:N  % for all remaining rows
      m = Aug(k,p);
      for i = p:N+1
        Aug(k,i) = Aug(k,i) - m*Aug(p,i)
      end
% Back Substitution
    for k = N:1
      % Accumulate all elements remaining in that row times x
      sum = 0
      for i = k+1:N
        sum = sum + Aug(k,i) * x(i,1)
      end
    x(k,1) = Aug(k,N+1) - sum;
    end

Some remarks about Gauss elimination

• If the pivot is 0, then switch the rows
• To reduce arithmetic arror, choose as pivot the largest element in the remaining elements in the pivotal column

LU Factorization

• Ax₁ = B₁
• Ax₂ = B₂
• Ax_k = B_k

• y = Ux
• Ly = B

1. Factor A into 2 matrices LU
2. Solve Ly = B using forward substitution
3. Solve Ux = y using backward substitution

Complexity of Gauss Elimination and LU Factorization

• Factor A into LU -> O(n³)
• Gauss Elimination (no backward substitution) -> O(n³)
• Back Substitution -> O(n²)
• Forward Substitution -> O(n²)

• O(n³) + 2mnO(n²)

• They are going to be useful when you have many variables (Ex. 100,000 vars) and A is sparse (a large % of the coefficients in A are 0's).
• This situation often happens when solving partial differential equations numerically.
• Also arises when computing a web page ranking based on the ranking of pages that point to it.

Jacobi Iteration

Gauss Seidel Iteration

• 3x + y = 5
• x + 3y = 7

Gauss Seidel Example

• 3x + y = 5 => x + 3y = 7
• x + 3y = 7 => 3x + y = 5

Strictly Diangonal Dominant Matrix

• 3x + y = 5    => x_k = (5-y_k-1)/3
• x + 3y = 7    => y_k = (7-x_k-1)/3

This Web page was created by John A. Cotiguala and was last updated on July 10, 2003