🔢 mathematics

On the convergence of the new SOR-like method for solving absolute value equations

This paper refutes the original convergence proof of the new SOR-like method for absolute value equations by providing a counterexample, and establishes a rigorous convergence criterion based on a control matrix that identifies a more reliable optimal parameter pair (1, 1) which, despite potentially requiring more iterations, yields lower total computing time.

Original authors: Liqian Lin, Dongmei Yu, Cairong Chen, Deren Han

Published 2026-09-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Liqian Lin, Dongmei Yu, Cairong Chen, Deren Han

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of mathematics, there are problems that look simple on the surface but hide a labyrinth of difficulty beneath. One such challenge involves finding a specific set of numbers that satisfy a particular balance between a linear relationship and the absolute values of those numbers. Imagine trying to find a point on a map where a straight-line rule and a rule about distance from zero must both be true at the same time. These are known as absolute value equations, and they appear in many real-world situations, from economics to engineering, where systems must obey strict constraints. Because of the way absolute values work—turning negative numbers positive—the path to a solution is often jagged and unpredictable, making these problems notoriously hard to solve. For decades, mathematicians have developed various tools to navigate this terrain, hoping to find a reliable way to reach the correct answer without getting lost in an infinite loop of calculations.

Recently, a team of researchers from universities in China revisited a specific tool designed for this task, a method known as the new SOR-like algorithm. This technique was proposed not long ago as a promising way to solve these equations quickly and efficiently. The original creators of the method claimed to have proven that it would always work, provided certain settings were chosen correctly. They offered a formula to calculate the best settings, promising that if users followed their instructions, the algorithm would inevitably find the solution. However, a closer look by Liqian Lin, Dongmei Yu, Cairong Chen, and Deren Han revealed a critical flaw in that original promise. They discovered that the mathematical logic used to guarantee the method's success was incomplete. The original proof relied on checking the behavior of the algorithm at each individual step, assuming that if every single step looked safe, the entire journey would be safe. The researchers showed that this assumption is false. Just because a traveler takes a safe step today does not mean they will not wander off a cliff tomorrow, especially when the terrain changes with every move.

To demonstrate this danger, the team constructed a specific, simple example where the algorithm followed all the original rules perfectly. They set the parameters exactly as the original paper suggested, and at every single step, the numbers appeared to be behaving well. Yet, when they let the process run, the numbers did not settle down to a solution. Instead, they began to grow larger and larger, spiraling out of control until the calculation failed completely. This was not a minor glitch; it was a definitive proof that the original method could fail even when it seemed to be working correctly. The researchers found that the original analysis missed the fact that the algorithm's behavior depends on the sign of the numbers it is currently processing, and this dependency can cause the system to drift away from the solution over time, even if no single step looks dangerous.

Having exposed the flaw, the team did not stop at criticism; they built a new, solid foundation for the method. They developed a fresh way to analyze the algorithm, one that looks at the entire journey rather than just individual steps. They introduced a new concept, a control matrix, which acts as a master regulator for the whole process. By studying this regulator, they were able to prove that if a specific condition is met, the algorithm is guaranteed to converge to the correct answer from any starting point. This new condition is stricter and more reliable than the old one, ensuring that the method does not just look good in isolation but remains stable throughout the entire calculation.

With a secure method in hand, the researchers then turned their attention to finding the best settings to make the algorithm run as fast as possible. The original paper had suggested a complex formula for choosing these settings, one that required knowing details about the exact solution before the calculation even began. This was a practical hurdle, as you cannot know the solution before you find it. The new analysis showed that the best settings are actually much simpler. The researchers proved that the optimal choice is a fixed pair of values, both equal to one. This means the algorithm does not need to perform complex calculations to figure out its settings before it starts; it can simply begin with these standard values and still achieve the best possible performance in terms of total computing time.

The team tested these findings with a series of computer experiments to see how the new approach compared to the old one. They ran the algorithm on several different types of problems, using both the original complex settings and their new simple settings. The results were striking. While the original method sometimes required fewer steps to reach a solution, it often spent a significant amount of time calculating the complex settings, and in some cases, it failed to converge at all, just as the theory predicted. In contrast, the new method, using the fixed settings of one and one, consistently solved the problems faster in terms of total time. Even though it sometimes took a few more steps to finish, the simplicity of the settings meant the computer spent less time overall. In one set of tests, the new method completed the work in a fraction of a second, while the old method took several seconds, a massive difference in the world of high-speed computing.

This work serves as a reminder that in mathematics, a proof that looks convincing on the surface can sometimes hide deep cracks. The researchers successfully corrected a significant error in the understanding of how to solve these difficult equations, replacing a fragile promise with a robust guarantee. They showed that the path to a solution is not always about finding the most complex or sophisticated settings, but often about finding the right, simple rule that holds true no matter how the numbers shift. By proving that a fixed, simple approach is not only safe but also faster, they have provided a more reliable tool for anyone who needs to solve these challenging equations in the future. The journey from a flawed assumption to a verified truth highlights the importance of rigorous testing and the value of looking at the whole picture rather than just the parts.

Technical Summary: On the Convergence of the New SOR-like Method for Solving Absolute Value Equations

Problem Statement
The paper addresses the Absolute Value Equation (AVE), formulated as $Ax - |x| = b$ , where $A \in \mathbb{R}^{n \times n}$ and $b \in \mathbb{R}^{n}$ . This problem is closely related to linear complementarity problems and is generally NP-hard to solve. The authors focus on the New SOR-like (NSOR) method recently proposed by Dong et al. [45] for solving this equation. While Dong et al. provided a convergence analysis and an optimal parameter selection formula, this paper identifies critical flaws in their theoretical justification and demonstrates that their proposed conditions do not guarantee convergence.

Methodology and Analysis
The authors employ a rigorous convergence analysis and numerical experimentation to evaluate the NSOR method.

Critique of Existing Theory: The paper first demonstrates that the convergence argument in [45] is insufficient. The original proof relies on the condition that the spectral radius of the iteration matrix $M^{(k)}$ is less than one at each step. However, since $M^{(k)}$ depends on the sign of the current iterate $x^{(k)}$ , the matrix changes dynamically. The authors construct a one-dimensional counterexample (Example 2.1) where the parameters satisfy the original conditions and every individual iteration matrix has a spectral radius less than one, yet the generated sequence diverges.
New Convergence Analysis: To establish a valid convergence guarantee, the authors analyze the successive iteration differences ( $\Delta x_k, \Delta y_k$ ). They construct a fixed nonnegative control matrix $W$ that bounds the growth of these differences. Using the Cauchy convergence criterion and properties of nonnegative matrices, they prove that if the spectral radius $\rho(W) < 1$ , the NSOR method converges globally to the unique solution of the AVE from any initial point. This leads to a new sufficient convergence region defined by specific inequalities involving the parameters $\omega$ and $\sigma$ , and the norms of $A$ and $A^{-1}$ .
Optimal Parameter Selection: Based on the new control matrix $W$ , the authors seek to minimize its spectral radius to determine optimal parameters. They prove that the minimum spectral radius $\rho(W) = \|A^{-1}\|_p$ is achieved when the parameters are fixed at the pair $(\omega, \sigma) = (1, 1)$ . This choice reduces the NSOR method to a Picard-type iteration. Unlike the original method, which requires computing eigenvalues of a matrix dependent on the exact solution (or iterates) to determine parameters, the new approach uses fixed parameters without needing prior knowledge of the solution.

Key Results and Numerical Experiments
The paper validates its theoretical findings through three numerical experiments:

Experiment 1 (Convergence Domain): The authors tested the original theoretical parameter region $D$ against an empirical convergence region. Results showed that $D$ is not a subset of the empirical convergence region; a significant number of parameter points within the original theoretical bounds failed to converge, confirming the insufficiency of the original analysis.
Experiment 2 (Divergence of Original Formula): Using the optimal parameter formula from [45] on a specific AVE instance, the authors demonstrated that the method diverges, with residuals growing exponentially. This confirms that the original parameter selection strategy can lead to failure.
Experiment 3 (Performance Comparison): The fixed pair $(1, 1)$ (NSOR-New) was compared against the original parameter formula (NSOR-Old) on three standard test problems. While NSOR-Old required fewer iteration counts in some cases, NSOR-New consistently achieved lower total CPU time. This efficiency gain is attributed to the elimination of the expensive parameter precomputation step required by the original method.

Significance and Claims
The paper claims to provide a rigorous correction to the convergence analysis of the NSOR method. Its primary contributions are:

Refutation of Previous Claims: It establishes that the original convergence proof in [45] is incomplete and that the original parameter conditions do not guarantee convergence.
Rigorous Convergence Guarantee: It provides a new, mathematically sound sufficient condition for global convergence based on a fixed control matrix $W$ .
Robust Parameter Selection: It proposes a fixed parameter pair $(\omega, \sigma) = (1, 1)$ that ensures convergence under the new conditions and offers superior computational efficiency in practice by avoiding dynamic parameter recalculations.

The authors conclude that while the fixed pair $(1, 1)$ may require slightly more iterations than the original optimal choice in specific cases, it provides a more reliable and computationally efficient approach overall, avoiding the divergence risks associated with the original method's parameter formula.

More like this