Back to Notes

LECTURE 8: Linear Algebra

• matrix algebra There are many elegant theorems in LA algebra. I am not gonna to prove or state any. Will concentrate on computing techniques. All linear (some nonlinear) differential equations must be converted to linear equations to use computers. a11 x1 + a12 x2 + a1n xn = b1 a21 x1 + a22 x2 + a2n xn = b2 an1 x1 + an2 x2 + ann xn = bn Ax = b (A=matrix, x=unknown vector, b=known vector.)
  
• linear operations
  • Vector and vector (dot product)
  • Vector and matrix
  • Matrix and matrix
  • matrix transpose
  • matrix inversion

  
  11. Solving Ax=b, direct and iterative.
  	a.	Gaussian eliminations:
  		Forward:
  		backward:
  	
  	b.	LU decomposition
  		A = LU	
  	                LUx = b
  		Suppose Ux = z
  	                Then, Lz = b
  		Step 1: solve Lower triangular system Lz = b
  		Step 2: solve upper triangular system Ux = z
  	
  	c. 	Jacobi method:
  		7x1 - 6x2 = 3			(1)
  		-8x1 + 9x2 = -4			(2)
  		EXACT Result: x1=.2, x2=-.2666
  	Using (1), 
  	
  	Using (2), 
  	
  	Set x1^0 = x2^0 = 0.
  	then iterate:
  		k	x1	x2
  		0 	0	0
  		10	.1486	-.1982
  		30	.1966	-.2621
  		50	.1998	-.2664
  
  	d. 	Gauss-Seidel:
  		7x1 - 6x2 = 3			(1)
  		-8x1 + 9x2 = -4			(2)
  	Using (1), 
  	
  	Using (2), 
  	
  	then iterate:
  		k	x1	x2
  		0 	0	0
  		10	.2198	-.2491
  		30	.2001	-.2666
  		50	.2000	-.2666
  	Obviously, Gauss-Seidel is faster than Jacobi.
  
  	e. 	Basic concept
  		Ax=b.
  	If we introduce a matrix Q (splitting matrix)
  		Qx = (Q-A)x + b
  	suggesting
  		(k>=1)
  	or
      	                (k>=1)
  	Thus, the main problem is to find .
  	 must be easy to find.
  	Problem of inverting A reduces to inverting Q.
  	In Jacobi, Q = diag(A)
  	In Gauss-Seidel, Q = lower triangle(A) + diag(A)
  
  		Q = A_L + diag(A)
  	These two methods are efficient for digital dominant matrices.
  	One more example for Gauss-Seidel:
  		A = (2 -1 0, 1 6 -2, 4 -3 8)
  		b = (2 -4 5)
  	D = diag(A) = (2 6 8)
  	 A = (1 -1/2 0, 1/6 1 -1/3, 1/2 -3/8 1)
  	 b = (1 -2/3 5/8)
  	We then construct the Gauss-Seidel iteration formula
  		(k>=1)
  	where	
  		 = (.62, -.76, .03) 
  	There are many other interation methods (SOR)
  	and their accelerations.
  optional: Matrix-vector,  Matrix-Matrix products 
  optional: Finding eigenvalues and eigenvectors
  

  ---

  Last Modified: 10/08/00