Solving a learning system (Ax=b) by iterative methods

Jacobi Method
for i = 1 : n
　x[ i ]^k+1 = ( b[ i ]
　　　　　　　 - SIGMA(j = 1 : i-1)( a[ i ][ j ] * x[ j ]^k )
　　　　　　　 - SIGMA(j = i+1 : n)( a[ i ][ j ] * x[ j ]^k ) )
　　　　　　/ a[ i ][ i ]
end

[Convergence]
M = diag( diag( A ) )　N = - ( A - M )
若M^-1*N的eigenvalue皆在-1~1之間的話，則其會收斂。



Gauss-Seidal Method
for i = 1 : n
　x[ i ]^k+1 = ( b[ i ]
　　　　　　　 - SIGMA(j = 1 : i-1)( a[ i ][ j ] * x[ j ]^k+1 )
　　　　　　　 - SIGMA(j = i+1 : n)( a[ i ][ j ] * x[ j ]^k ) )
　　　　　　/ a[ i ][ i ]
end



Steepest Descent Method
x(0) = initial guess
r(0) = b - A * x(0)
k = 0
while r^k != 0
　k = k + 1
　alpha(k) = ( (r^k-1)' * r^k-1 ) / ( (r^k-1)' * A * r^k-1 )
　x^k = x^k-1 - alpha^k * r^k-1
　r^k = b - A * x^k
end



Conjugate Gradient Method
k = 0
r(0) = b - A * x(0)
while r^k != 0
　k = k + 1
　if k = 1
　　p(1) = r(0)
　else
　　beta^k = ( (r^k-1)' * r^k-1 ) / ( (r^k-2)' * r^k-2 )
　　p^k = r^k-1 + beta^k * p^k-1
　end
　alpha^k = ( (r^k-1)' * r^k-1 ) / ( (p^k)' * A * p^k )
　x^k = x^k-1 + alpha^k * p^k
　r^k = r^k-1 - alpha^k * A * p^k
end
x = x^k



[Reference]

• Gene H. Golub and Charles Van Loan, Matrix computation, 1996.
  [Part 1] [Part 2]