"""ch08_thomas.py Solve a tridiagonal system C*x = b by the Thomas algorithm. Origin: Python translation of ch08_thomas.f90 by Alexander Godunov, based on Thomas.f90. The elimination multiplier updates both the diagonal and right-hand side, as in the corrected Fortran code. Example: Eight equations with diagonal 4 and adjacent diagonals -1. All entries of b are zero except b[7] = 16. The matrix is strictly diagonally dominant, so the example does not require pivoting. The three stored diagonals, solution, and maximum residual are printed. """ def main(): """Set up the eight-equation example and check its solution.""" # Each row holds [subdiagonal, diagonal, superdiagonal]. # c[0][0] and c[n-1][2] are unused. c = [[ 0.0, 4.0, -1.0], [-1.0, 4.0, -1.0], [-1.0, 4.0, -1.0], [-1.0, 4.0, -1.0], [-1.0, 4.0, -1.0], [-1.0, 4.0, -1.0], [-1.0, 4.0, -1.0], [-1.0, 4.0, 0.0]] b = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 16.0] n = len(c) print("Thomas algorithm for a tridiagonal system") print("\nSubdiagonal, diagonal, superdiagonal, and b:") for i in range(n): print("".join(f"{value:12.6f}" for value in c[i]) + f"{b[i]:12.6f}") # The routine changes its inputs. Keep originals for the residual. c_work = [row.copy() for row in c] b_work = b.copy() x, info = thomas(c_work, b_work) if info != 0: if info < 0: raise ValueError("Invalid tridiagonal matrix or RHS size") raise ArithmeticError(f"Zero pivot at row {info}; pivoting is needed") print("\nSolution x:") for i, value in enumerate(x, start=1): print(f"x({i}) = {value:12.6f}") # Each row of the original system contains at most three terms. max_residual = 0.0 for i in range(n): row_residual = c[i][1] * x[i] - b[i] if i > 0: row_residual += c[i][0] * x[i-1] if i < n-1: row_residual += c[i][2] * x[i+1] max_residual = max(max_residual, abs(row_residual)) print(f"\nMaximum residual |C*x-b| = {max_residual:.4e}") def thomas(c, b): """Solve a tridiagonal system without row pivoting. Input/output: c - n-by-3 array holding subdiagonal, diagonal, superdiagonal by row; c[0][0] and c[n-1][2] are unused b - right-hand side, overwritten during forward elimination Output: x - solution on success info - 0 success; -1 invalid sizes; positive one-based row of an exact zero pivot The multiplier coeff = c[i][0]/c[i-1][1] updates both the diagonal and the right-hand side. No pivoting is used, so even a nonsingular system can have a zero pivot or be unstable. """ n = len(c) if n < 1 or len(b) != n or any(len(row) != 3 for row in c): return [], -1 x = [0.0] * n if c[0][1] == 0.0: return x, 1 # Eliminate the subdiagonal, leaving the superdiagonal unchanged. for i in range(1, n): coeff = c[i][0] / c[i-1][1] c[i][1] -= coeff * c[i-1][2] b[i] -= coeff * b[i-1] if c[i][1] == 0.0: return x, i + 1 # Solve the upper triangular equations from bottom to top. x[n-1] = b[n-1] / c[n-1][1] for i in range(n-2, -1, -1): x[i] = (b[i] - c[i][2] * x[i+1]) / c[i][1] return x, 0 if __name__ == "__main__": main()