Stabilization of the Gradient Method for Solving Linear Algebraic Systems A Method Related to the Normal Equation Journal: Journal of Scientific Computing This research was supported by the NSERC Canadian grant number RGPIN-2024-05291. I confirm that this work is original and has not been published

Ibrahima Dione · 2025

Read Stabilization of the Gradient Method for Solving Linear Algebraic Systems A Method Related to the Normal Equation Journal: Journal of Scientific Computing This research was supported by the NSERC Canadian grant number RGPIN-2024-05291. I confirm that this work is original and has not been published by Ibrahima Dione (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00702.txt.

Introduction

The gradient method is the simplest way to solve a system of linear equations, yet it crawls when the matrix is awkward. Ibrahima Dione proposes a stabilized version tied to the normal equation. The classic method needs the matrix to be symmetric and positive, and it leans heavily on a well-chosen step size.

The stabilized algorithm drops both demands. It converges globally as long as the matrix is merely nonsingular, with no structure assumed and no step-size artistry required. Tests cover small and large systems, structured and unstructured matrices, and well- and ill-conditioned cases. The 2025 paper gives a humble method new reach for the linear systems that sit inside countless computations.

Catalog record

CREATORIbrahima Dione
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-00702

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stabilization of the Gradient Method for Solving Linear Algebraic Systems A Method Related to the Normal Equation Journal: Journal of Scientific Computing This research was supported by the NSERC Canadian grant number RGPIN-2024-05291. I confirm that this work is original and has not been published elsewhere, nor is it currently under consideration for publication elsewhere. Ibrahima Dione Abstract Although it is relatively easy to apply, the gradient method often displays a disappointingly slow rate of convergence. Its convergence is specially based on the structure of the matrix of the algebraic linear system, and on the choice of the stepsize defining the new iteration. We propose here a simple and robust stabilization of the gradient method, which no longer assumes a structure on the matrix (neither symmetric, nor positive definite) to converge, and which no longer requires an approach on the choice of the stepsize. We establish the global convergence of the proposed stabilized algorithm under the only assumption of nonsingular matrix. Several numerical examples illustrating its performances are presented, where we have tested small and large scale linear systems, with and not structured matrices, and with well and ill conditioned matrices. 1 Introduction This paper is devoted to the solving of the linear system \displaystyle\mathbf{A}\mbox{\boldmath$x$}=\mbox{\boldmath$b$}, (1) by means of a stabilized gradient iterative method, where \mathbf{A}\in\mathbb{R}^{n\times n} is a n\times n matrix (which is ill-conditioned or not) and \mbox{\boldmath$b$}\in\mathbb{R}^{n} is a given n -vector. The only requirement on this matrix is that it is nonsingular (whatever the structure of the eigenvalues), the exact solution being thus given as follows \mbox{\boldmath$x$}^{\star}=\mathbf{A}^{-1}\mbox{\boldmath$b$}\in\mathbb{R}^{n} . Throughout this work, \|\cdot\|_{n} denotes the euclidean vector norm in \mathbb{R}^{n} , \left<\cdot,\cdot\right>_{n} its associated scalar product, and \|\cdot\| is the induced matrix norm to \|\cdot\|_{n} . The linear system ( 1 ) is the standard formulation of many problems coming from different fields in science and engineering whose economy, chemistry, physics, models of partial differential equations, ect. The solving of this linear system is still challenging, and also represents one of the most time consuming part of the numerical simulation process. We may distinguish two main methods for its solving: Direct and iterative methods. The former methods, which are widely used in many industrial codes, are based on the factorization of the matrix \mathbf{A} into easily invertible matrices and require a predictable amount of ressources in time and storage [ 2 , 9 , 37 ] . Unfortunately, these methods are inefficient when the problem size becomes large since the factorization becomes impractical due to lack of time or storage capacity. The use of the latter methods, the iterative methods , becomes thus mandatory. Iterative methods require fewer storage, and often, fewer operations than direct methods during the solving process [ 2 , 9 , 37 , 25 , 41 ] . However, these methods may fail to converge in a reasonable amount of time, and sometimes may not have the same reliability than direct methods. The gradient method which is traced back to A. L. Cauchy [ 10 ] , is one of the most straightforward iterative method to build an approximation solution of the linear system ( 1 ). A simple way to establish this iterative method is to reformulate equation ( 1 ) under the linear fixed-point equation \mbox{\boldmath$x$}=\mbox{\boldmath$x$}-\alpha(\mathbf{A}\mbox{\boldmath$x$}-\mbox{\boldmath$b$}) , from which the following iterative scheme is built \displaystyle\mbox{\boldmath$x$}^{[k+1]}=\mbox{\boldmath$x$}^{[k]}-\alpha_{k}(\mathbf{A}\mbox{\boldmath$x$}^{[k]}-\mbox{\boldmath$b$}),\;\;k=0,1,2,\cdots, (2) where \alpha_{k} is a parameter (a stepsize) to be defined. The gradient method ( 2 ) can be written under the iterative form (see [ 2 ] - Definition 9.1.1 ) \displaystyle\mathbf{M}_{\alpha_{k}}\mbox{\boldmath$x$}^{[k+1]}=\mathbf{N}_{\alpha_{k}}\mbox{\boldmath$x$}^{[k]}+\mbox{\boldmath$b$}, (3) where the regular decomposition of the matrix \mathbf{A}=\mathbf{M}_{\alpha}-\mathbf{N}_{\alpha} , with \mathbf{M}_{\alpha}=\frac{1}{\alpha}\mathbf{I} and \mathbf{N}_{\alpha}=\left(\frac{1}{\alpha}\mathbf{I}-\mathbf{A}\right) , is made. In the case where the matrix \mathbf{A} is symmetric, the gradient method is based on the natural idea of choosing the direction of the greatest rate of change of the quadratic functional \displaystyle J(\mbox{\boldmath$x$})=\frac{1}{2}\left<\mathbf{A}\mbox{\boldmath$x$},\mbox{\boldmath$x$}\right>_{n}-\left<\mbox{\boldmath$b$},\mbox{\boldmath$x$}\right>_{n}, namely, the direction opposite to the gradient \nabla J(\mbox{\boldmath$x$})=\mathbf{A}\mbox{\boldmath$x$}-\mbox{\boldmath$b$} . A process of finding the appropriate stepsize \alpha_{k} is also needed. Many iterative algorithms, typically called line search algorithms , have been proposed for the choice of this parameter. The most known are the constant stepsize , the exact line search stepsize and the backtracking stepsize (see [ 7 ] - Chap. 4). The main advantage of the constant stepsize strategy is of course its simplicity, but its drawback is how to fixe its value since a large stepsize can cause a non converging gradient method, while a small stepsize can slow the convergence. As for the exact line search stepsize, even in the simplest case where the marix \mathbf{A} is symmetric and positive definite, the gradient method may not be very efficient [ 1 ] . With the exact line search, the gradient method converges linearly and behaves increasingly badly when the condition number of the matrix deteriorates. Attempts to increase the performance of this method have also been investigated [ 19 , 31 , 40 ] . The exact line search method is mainly applied in the special cases of quadratic problems, where the stepsize \alpha_{k} is analytically computed. Otherwise, its approximation is used, generating the so called inexact line search procedures widely investigated in the litterature [ 4 , 21 , 42 , 35 , 13 , 18 , 36 , 32 , 33 ] . The backtracking stepsize is a version of this approximation. Later on, Barzilai and Borwein [ 5 ] proposed a surprising superlinear convergence result of the steepest descent method, based on a different strategy for choosing the step lenght. For the simplest case of symmetric and positive definite matrix \mathbf{A} with n=2 , Barzilai and Borwein show that the gradient method ( 2 ), with the stepsize \alpha_{k} defined from informations of the previous iteration, converges superlinearly. Their works have also been the origin of many others researches on the steepest descent method. Raydan [ 38 , 39 ] established convergence of the Barzilai and Borwein’s approach in the quadratic case by providing numerical results, whereas Fletcher [ 17 ] analysed its links with the spectrum of the matrix \mathbf{A} . The possibility to apply the Barzilai and Borwein’s approach to constrained optimization problems was considered by Friedlander et al. [ 20 ] (in the case of quadratic functionals), and by Birgin et al. [ 8 ] . Others more rescent investigations on the Barzilai and Borwein’s approach have also been made [ 11 , 12 ] , and some explained why it is competitive to the conjugate gradient based method [ 16 ] . More recently, under a quadratic functional, Yuan [ 43 ] proposed a new computational process of the stepsize \alpha_{k} , enabling a fast convergence of the steepest descent method. Moreover, its approach also possesses the monotoniticity property that permits a generalization to non-linear functions. Despite these performances on the gradient method, it is supplanted by the use of the conjugate gradient method or its variants. In the solving of the linear system ( 1 ), the conjugate gradient method [ 30 ] and some of its preconditionings [ 22 ] remain still the methods of choices. The main feature of these methods is that, they are able to deliver a reasonably accurate approximation solution in few iterations, specially when

Read the complete text