Residual Symmetry for Linear Algebraic Equations and the Lorentz-Group Algorithm


  •  Chein-Shan Liu    

Abstract

In the iterative solution of $n$ linear algebraic equations ${\bf B}{\bf x}={\bf b}$
by using the steepest descent method, i.e.,
${\bf x}_{k+1}={\bf x}_k-\alpha_k {\bf B}^{\mbox{\scriptsize T}}{\bf r}_k$,
it is known that the steplength
$\alpha_k:={\bf r}_k^{\mbox{\scriptsize T}} {\bf A}{\bf r}_k/\|{\bf A}{\bf r}_k\|^2$ causes
a slow convergence, where ${\bf r}={\bf B}{\bf x}-{\bf b}$ is the residual vector and ${\bf A}={\bf B}{\bf B}^{\mbox{\scriptsize T}}$.
In this paper we study the residual symmetry of the residual dynamics
for a scaled residual vector ${\bf y}\in {\mathbb S}^{n-1}_{\|{\bf r}_0\|}$, which
as expressed in the augmented space is a nonlinear Lorentzian dynamical system, and is endowed with a cone structure in the Minkowski
space with the Lorentz group $SO_o(n,1)$ being the internal symmetry group. Consequently,
we can modify the steplength to $\alpha_k={\bf y}_k^{\mbox{\scriptsize T}} {\bf A}{\bf y}_k/\|{\bf A}{\bf y}_k\|^2$
with ${\bf y}_k$ being computed by a Lorentz group algorithm (LGA)
based on $SO_o(n,1)$,
which can significantly improve the convergence speed and enhance the stability.
Several linear inverse problems are used to assess the numerical performance of the LGA.



This work is licensed under a Creative Commons Attribution 4.0 License.