Gaussian Elimination Method for Solving Ax=b

This assignment requires solving linear systems Ax=b using different numerical methods: Gaussian Elimination, LU Decomposition, Jacobi Iteration, Gauss-Seidel Iteration, and SOR Iteration. Each method possesses distinct advantages and limitations, requiring appropriate selection based on practical problem characteristics. Gaussian Elimination represents a fundamental direct method for linear system solving, where partial pivoting implementation enhances numerical stability by selecting the maximum element in each column as the pivot. The algorithm proceeds through forward elimination to create an upper triangular matrix, followed by back substitution to obtain the solution vector. LU Decomposition factors matrix A into lower (L) and upper (U) triangular matrices, significantly reducing computational complexity for multiple right-hand sides. The implementation typically employs Doolittle's or Crout's algorithm, where L has unit diagonal elements and U contains the pivots. Jacobi Iteration employs a splitting approach where the matrix is decomposed into diagonal (D), lower (L), and upper (U) components. The iterative formula x^(k+1) = D^(-1)(b - (L+U)x^(k)) updates all variables simultaneously using previous iteration values, requiring explicit storage of both x^(k) and x^(k+1) vectors. Gauss-Seidel Iteration improves upon Jacobi by utilizing immediately updated values during iteration. The implementation follows x^(k+1) = (D-L)^(-1)(Ux^(k) + b), where newly computed components replace old values sequentially, typically converging faster than Jacobi method. SOR (Successive Over-Relaxation) Iteration accelerates Gauss-Seidel convergence through a relaxation parameter ω. The core algorithm combines current Gauss-Seidel update with previous iterate using x^(k+1) = (1-ω)x^(k) + ω(D-L)^(-1)(Ux^(k) + b). Optimal ω selection critically affects convergence rate, with values between 1 and 2 often providing significant acceleration. Therefore, when solving Ax=b systems, appropriate method selection and parameter tuning are essential for achieving optimal computational efficiency and accuracy, considering factors like matrix size, sparsity pattern, and condition number.