/*======================================================================= ch08_matrix_inverse.cpp Compute the inverse of a small matrix by Doolittle LU factorization. Origin: C++ translation of ch08_matrix_inverse.f90 by Alexander Godunov, based on Inverse.f90. The no-pivot LU factorization and repeated triangular solves match the Fortran program. Example: A = [ 3 2 4; 2 -3 1; 1 1 2 ]. The program solves A*x = e_k for each column e_k of the identity and places the solutions in the columns of A^{-1}. Explicit inversion is seldom needed to solve A*x=b. If only x is needed, solve the system directly. This example shows how an LU factorization can be reused for several right-hand sides. =======================================================================*/ #include #include #include #include #include // Each inner vector holds one row of the matrix. using Matrix = std::vector>; int inverse_lu(Matrix& a, Matrix& c); int main() { const Matrix a = { {3.0, 2.0, 4.0}, {2.0, -3.0, 1.0}, {1.0, 1.0, 2.0} }; const int n = static_cast(a.size()); std::cout << "Matrix inverse from Doolittle LU factorization\n" << "\nMatrix A:\n" << std::fixed << std::setprecision(6); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) std::cout << std::setw(12) << a[i][j]; std::cout << '\n'; } // Keep the original A for the identity check. Factorization changes // the working matrix, as in the Fortran version. Matrix a_work = a; Matrix inverse; const int info = inverse_lu(a_work, inverse); if (info != 0) { if (info < 0) std::cerr << "Invalid matrix size or shape.\n"; else std::cerr << "Zero pivot at factorization step " << info << ".\n" << "This no-pivot LU method cannot invert the matrix.\n"; return 1; } std::cout << "\nInverse matrix A^{-1}:\n"; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) std::cout << std::setw(12) << inverse[i][j]; std::cout << '\n'; } // Check A*A^{-1} against the identity with explicit loops. double max_error = 0.0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { double element = 0.0; for (int k = 0; k < n; ++k) element += a[i][k] * inverse[k][j]; if (i == j) element -= 1.0; max_error = std::max(max_error, std::abs(element)); } } std::cout << "\nMaximum |A*A^{-1}-I| = " << std::scientific << std::setprecision(4) << max_error << '\n'; return 0; } int inverse_lu(Matrix& a, Matrix& c) /*======================================================================= Form C = A^{-1} by Doolittle LU and repeated triangular solves. Input/output: a - square coefficient matrix, overwritten during elimination Output: c - inverse matrix when the return value is zero Return value: 0 - success -1 - empty or nonsquare matrix k - zero pivot at step k, numbered from 1 Factor A = L*U, with unit diagonal in L. For each identity column e_k, solve L*d=e_k and U*x=d. Store x in column k of C. The same factors are used for all columns. No row pivoting is performed, as in the Fortran version. A nonsingular matrix can have a zero pivot in this factorization; then a pivoted LU solver is needed. A small identity-check error alone does not establish accuracy for an ill-conditioned matrix. =======================================================================*/ { const int n = static_cast(a.size()); if (n == 0) return -1; for (const auto& row : a) { if (static_cast(row.size()) != n) return -1; } c.assign(n, std::vector(n, 0.0)); Matrix lower(n, std::vector(n, 0.0)); Matrix upper(n, std::vector(n, 0.0)); std::vector rhs(n, 0.0), d(n, 0.0), x(n, 0.0); // Record the elimination multipliers in L and update the trailing // coefficients in the working matrix A. for (int k = 0; k < n - 1; ++k) { if (a[k][k] == 0.0) return k + 1; for (int i = k + 1; i < n; ++i) { const double coeff = a[i][k] / a[k][k]; lower[i][k] = coeff; for (int j = k + 1; j < n; ++j) a[i][j] -= coeff * a[k][j]; } } if (a[n - 1][n - 1] == 0.0) return n; // L has unit diagonal; U is the upper triangle of the matrix // after elimination. Entries below that triangle hold no U data. for (int i = 0; i < n; ++i) lower[i][i] = 1.0; for (int j = 0; j < n; ++j) { for (int i = 0; i <= j; ++i) upper[i][j] = a[i][j]; } // Solve one system for each column of the identity matrix. for (int k = 0; k < n; ++k) { std::fill(rhs.begin(), rhs.end(), 0.0); rhs[k] = 1.0; // Forward substitution: L*d = e_k. for (int i = 0; i < n; ++i) { d[i] = rhs[i]; for (int j = 0; j < i; ++j) d[i] -= lower[i][j] * d[j]; } // Back substitution: U*x = d. for (int i = n - 1; i >= 0; --i) { x[i] = d[i]; for (int j = i + 1; j < n; ++j) x[i] -= upper[i][j] * x[j]; x[i] /= upper[i][i]; } // The solution of A*x=e_k becomes column k of the inverse. for (int i = 0; i < n; ++i) c[i][k] = x[i]; } return 0; }