"""ch08_gaussian_elimination.py Solve A*x = b by Gaussian elimination with scaled row pivoting. Origin: Python translation of ch08_gaussian_elimination.f90 by Alexander Godunov, based on Gauss_2.f90. The active-row scaling, pivot choice, elimination, and back substitution match the Fortran version. Example: A = [[0, 1, 2], [2, 1, 4], [2, 4, 6]], b = [4, 3, 7]. Exact solution: x = [-2.5, 0, 2]. A row swap is required. The original and triangular systems, solution, and maximum residual are printed. A small residual alone does not establish accuracy for an ill-conditioned system. """ def main(): """Set up the example and check the computed solution.""" a = [[0.0, 1.0, 2.0], [2.0, 1.0, 4.0], [2.0, 4.0, 6.0]] b = [4.0, 3.0, 7.0] n = len(a) print("Gaussian elimination with scaled row pivoting") print("\nOriginal matrix A and right-hand side b:") for i in range(n): print("".join(f"{value:12.5f}" for value in a[i]) + f" {b[i]:12.5f}") # Elimination changes its inputs. Preserve a and b for the check. a_work = [row.copy() for row in a] b_work = b.copy() x, info = gauss_scaled(a_work, b_work) if info != 0: if info < 0: raise ValueError("Invalid matrix or right-hand-side size") raise ArithmeticError(f"No unique solution: zero pivot at step {info}") print("\nMatrix A and right-hand side b after elimination:") for i in range(n): print("".join(f"{value:12.5f}" for value in a_work[i]) + f" {b_work[i]:12.5f}") print("\nSolution x:") for i, value in enumerate(x, start=1): print(f"x({i}) = {value:12.6f}") # Evaluate each original equation with explicit loops. max_residual = 0.0 for i in range(n): residual = -b[i] for j in range(n): residual += a[i][j] * x[j] max_residual = max(max_residual, abs(residual)) print(f"\nMaximum residual |A*x-b| = {max_residual:.4e}") def gauss_scaled(a, b): """Solve a*x=b by scaled-pivot elimination and back substitution. Input/output: a - square coefficient matrix, overwritten by its upper triangle b - right-hand side, overwritten during elimination Output: x - solution on success info - 0 on success; -1 for invalid sizes; positive pivot step for an exact zero pivot At step k, scale each candidate row by its largest absolute entry in the active columns k:n, then select the largest pivot ratio. A zero row is skipped before dividing by its scale. A small nonzero pivot may still indicate an ill-conditioned system. """ n = len(a) if n < 1 or len(b) != n or any(len(row) != n for row in a): return [], -1 x = [0.0] * n # Choose a scaled pivot, exchange rows, and eliminate below it. for k in range(n - 1): best = 0.0 pivot_row = k for i in range(k, n): scale = 0.0 for j in range(k, n): scale = max(scale, abs(a[i][j])) if scale == 0.0: continue score = abs(a[i][k]) / scale if score > best: best = score pivot_row = i if best == 0.0: return x, k + 1 # Exchange only the active coefficients, as in the Fortran. if pivot_row != k: for j in range(k, n): a[k][j], a[pivot_row][j] = a[pivot_row][j], a[k][j] b[k], b[pivot_row] = b[pivot_row], b[k] for i in range(k + 1, n): factor = a[i][k] / a[k][k] a[i][k] = 0.0 b[i] -= factor * b[k] for j in range(k + 1, n): a[i][j] -= factor * a[k][j] # The final diagonal entry has not been used as a pivot yet. if a[n - 1][n - 1] == 0.0: return x, n # Back substitution through the upper triangular system. for i in range(n - 1, -1, -1): row_sum = 0.0 for j in range(i + 1, n): row_sum += a[i][j] * x[j] x[i] = (b[i] - row_sum) / a[i][i] return x, 0 if __name__ == "__main__": main()