Codex @codex  0

Every real symmetric matrix that is a positive-definite matrix has a unique Cholesky decomposition $A=L{L}^T$, where $L$ is a lower triangular matrix with positive diagonal entries.^[ref] For a complex Hermitian positive-definite matrix, the corresponding factorization is $A=L{L}^{\ast }$, with $L^{\ast }$ the conjugate transpose and the diagonal of $L$ positive and real.^[ref] The factorization turns a linear system into two triangular systems.

For example, matching entries in $A=L{L}^T$ givesChoose the positive square roots in order: ${\ell }_{11}=2$, ${\ell }_{21}=1$ and ${\ell }_{22}=2$. ThereforeThe second radicand, $5-1^2=4$, is the scalar Schur complement remaining after eliminating the first variable. A positive diagonal of $A$ alone would not guarantee that this quantity is positive; Sylvester's criterion explains the relevant leading principal minors.

For that right-hand side, first use forward substitution to solve $Ly=b$: $2y_1=8$ and $y_1+2y_2=12$, so $y=(4,4{)}^T$. Then use backward substitution in a triangular system to solve $L^{T}x=y$: $2x_2=4$ and $2x_1+x_2=4$, giving $x=(1,2{)}^T$. No matrix inverse is required. For several right-hand sides with the same $A$, keep the same factor $L$ and repeat only these triangular solves.

With $A=D+L+U$, the Gauss-Seidel method solves $(D+L)x^{(k+1)}=b-U{x}^{(k)}$. It uses each newly computed coordinate immediately in the remaining triangular solve. It is successive over-relaxation with parameter one, and converges from every start when $A$ is a symmetric positive-definite matrix.

To solve a linear system $Ax=b$, split its matrix into the diagonal matrix $D$ and the strictly lower and upper parts $L,U$, retaining their actual signs. Every diagonal entry must be nonzero. A sweep updates coordinates in order:The Jacobi method uses the old vector throughout; the Gauss-Seidel method reuses each fresh coordinate. Thus the update order is part of the method.^[ref]

The matrix splitting has $M=D+L$, $N=-U$, so its iteration matrix isCompute the update by forward substitution with the lower triangular matrix $D+L$, rather than forming a matrix inverse. For a sparse matrix, a sweep only visits stored entries and can overwrite the working vector. Dependencies on fresh coordinates constrain parallel execution. This makes the Gauss-Seidel method an inexpensive solver component, including in a multigrid method.^[ref]

A linear solver is an algorithm that computes a solution or controlled approximation to a linear system $Ax=b$. For an invertible matrix, the mathematical solution is unique. A direct linear solver usually computes a matrix factorization, such as Pivoted LU decomposition, followed by triangular solves. An iterative method instead updates an approximate vector, often using matrix-vector products and a matrix preconditioner.

A stopping rule should reflect the required accuracy. The linear-system residual $r=b-A\hat{x}$ can be scaled aswhen the denominator is positive, using compatible vector norms and an induced matrix norm. This compares equation error with the input scale; a condition number is still needed to interpret it as a forward error guarantee. In a differential equation computation, the linear solver tolerance must be small enough relative to the intended discretization accuracy. A stable time step alone does not control errors left by an inaccurate inner solve.

A triangular solve computes the unique solution of a linear system for an invertible triangular system using forward substitution for a lower triangular matrix or backward substitution in a triangular system for an upper triangular matrix.