The orthogonal reflection method for the numerical solution of linear systems

This paper extends the convergence analysis of the reflection method from the case of $2$ equations to the case of $n$ equations. A novel approach called the orthogonal reflection method is also proposed. The orthogonal reflection method comprises two key steps. First, a Householder transformation is employed to derive an equivalent system of equations with an orthogonal coefficient matrix that maintains the same solution set as the original system. Second, the reflection method is applied to efficiently solve this transformed system. Compared with the reflection method, the orthogonal reflection method significantly enhances the convergence speed, especially when the angles are acute between the hyperplanes represented by the linear system. We also derive the convergence rate for it, demonstrating that the orthogonal reflection method is always convergent for an arbitrary point in ${\mathbb{R}}^n$. The necessity of orthogonalization is presented in the form of a theorem in ${\mathbb{R}}^2$. When the coefficient matrix has a large condition number, the orthogonal reflection method can still compute relatively accurate numerical solutions rapidly. By comparing with algorithms including Jacobi iteration, Gauss-Seidel iteration, the conjugate gradient method, GMRES, weighted RBAS, and the reflection method on coefficient matrices of 10×10 random matrices, 1000×1000 sparse matrices, and 1000×1000 randomly generated full-rank matrices, the efficiency and robustness of the orthogonal reflection method are demonstrated.