Sharp Convergence Rates and Optimal Weights for Cimmino's Reflection Algorithm
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911713579761664 |
|---|---|
| author | Sharma, Hemant |
| author_facet | Sharma, Hemant |
| contents | In this paper, Cimmino's classical reflection algorithm for solving the $n\times n$ nonsingular linear system $A\bx=\bb$ is analysed through the lens of spectral theory. Reformulating the weighted iteration as $\e^{(ν+1)}=M_w\,\e^{(ν)}$, where $M_w = I - A^\top D_w A$, the error is shown to contract by the spectral radius $\sprad(M_w)$ at every step, with a sharp, asymptotically tight bound. For $n=2$, a closed-form expression for the contraction factor is derived, \[
\sprad(M_w) \;=\; |1-μ|
+ \tfrac{1}{2}\sqrt{(w_1-w_2)^2 + 4w_1w_2\cos^2\!θ}, \] where $μ=(w_1+w_2)/2$ and $θ$ denotes the angle between the hyperplane normals. A central result of this paper is that the standard unit weights $w_1^*=w_2^*=1$ are \emph{globally optimal} over all positive weight pairs, uniquely achieving the minimum contraction factor $\sprad^*=|\cosθ|$ -- a quantity determined solely by the geometry of the hyperplane normals. The inter-normal angle $θ$ thus emerges as the single diagnostic parameter governing both convergence speed and weight selection. Extensions to a single-step convergence criterion at $θ=π/2$ and to an exact spectral rate for general~$n$ are also established. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_24692 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sharp Convergence Rates and Optimal Weights for Cimmino's Reflection Algorithm Sharma, Hemant Numerical Analysis 65F10, 65F15, 15A60 In this paper, Cimmino's classical reflection algorithm for solving the $n\times n$ nonsingular linear system $A\bx=\bb$ is analysed through the lens of spectral theory. Reformulating the weighted iteration as $\e^{(ν+1)}=M_w\,\e^{(ν)}$, where $M_w = I - A^\top D_w A$, the error is shown to contract by the spectral radius $\sprad(M_w)$ at every step, with a sharp, asymptotically tight bound. For $n=2$, a closed-form expression for the contraction factor is derived, \[ \sprad(M_w) \;=\; |1-μ| + \tfrac{1}{2}\sqrt{(w_1-w_2)^2 + 4w_1w_2\cos^2\!θ}, \] where $μ=(w_1+w_2)/2$ and $θ$ denotes the angle between the hyperplane normals. A central result of this paper is that the standard unit weights $w_1^*=w_2^*=1$ are \emph{globally optimal} over all positive weight pairs, uniquely achieving the minimum contraction factor $\sprad^*=|\cosθ|$ -- a quantity determined solely by the geometry of the hyperplane normals. The inter-normal angle $θ$ thus emerges as the single diagnostic parameter governing both convergence speed and weight selection. Extensions to a single-step convergence criterion at $θ=π/2$ and to an exact spectral rate for general~$n$ are also established. |
| title | Sharp Convergence Rates and Optimal Weights for Cimmino's Reflection Algorithm |
| topic | Numerical Analysis 65F10, 65F15, 15A60 |
| url | https://arxiv.org/abs/2605.24692 |