## 3 Maximally Decreasing Residual and Automatically Preserving Orthogonality  
In this section, we develop a new iterative algorithm based on GMRES to solve Equation (1). The iterative form is  
\[\mathbf{x}_{k+1}=\mathbf{x}_{k}+\mathbf{u}_{k}, \tag{17}\]  
where \(\mathbf{u}_{k}\) is the \(k\)th step descent vector, which is determined by the iterative algorithm. For instance, \(\mathbf{u}_{k}\) in GMRES is \(\mathbf{u}_{k}=\mathbf{V}_{k}\mathbf{y}_{k}\). **Lemma 1**. : _A better iterative scheme than that in Equation (17) is_  
\[\mathbf{x}_{k+1}=\mathbf{x}_{k}+\frac{\mathbf{r}_{k}^{T}\mathbf{A}\mathbf{u}_{ k}}{\|\mathbf{A}\mathbf{u}_{k}\|^{2}}\mathbf{u}_{k}. \tag{18}\]  
Proof. : Let  
\[\mathbf{x}_{k+1}=\mathbf{x}_{k}+\eta\mathbf{u}_{k}; \tag{19}\]  
it follows that  
\[\mathbf{r}_{k+1}=\mathbf{r}_{k}-\eta\mathbf{A}\mathbf{u}_{k}. \tag{20}\]Taking the squared norms of both sides yields  
\[\|\mathbf{r}_{k+1}\|^{2}=\|\mathbf{r}_{k}\|^{2}-(2\eta\mathbf{r}_{k}^{\mathrm{T}} \mathbf{A}\mathbf{u}_{k}-\eta^{2}\|\mathbf{A}\mathbf{u}_{k}\|^{2})=:\|\mathbf{r }_{k}\|^{2}-h. \tag{21}\]  
To maximally reduce the residual we consider  
\[\max_{\eta}\Bigl{\{}h=2\eta\mathbf{r}_{k}^{\mathrm{T}}\mathbf{A}\mathbf{u}_{k} -\eta^{2}\|\mathbf{A}\mathbf{u}_{k}\|^{2}\Bigr{\}}, \tag{22}\]  
which leads to  
\[\eta_{k}=\frac{\mathbf{r}_{k}^{\mathrm{T}}\mathbf{A}\mathbf{u}_{k}}{\|\mathbf{ A}\mathbf{u}_{k}\|^{2}}. \tag{23}\]  
Inserting \(\eta_{k}\) into Equation (19), the proof of Equation (18) is finished. Lemma 2: _In Equation (18) the following orthogonal property holds:_  
\[\mathbf{r}_{k+1}\cdot(\mathbf{A}\mathbf{u}_{k})=0. \tag{24}\]  
Proof: Apply \(\mathbf{A}\) to Equation (18):  
\[\mathbf{A}\mathbf{x}_{k+1}=\mathbf{A}\mathbf{x}_{k}+\frac{\mathbf{r}_{k}^{ \mathrm{T}}\mathbf{A}\mathbf{u}_{k}}{\|\mathbf{A}\mathbf{u}_{k}\|^{2}}\mathbf{ A}\mathbf{u}_{k}. \tag{25}\]  
Using \(\mathbf{A}\mathbf{x}_{k+1}=\mathbf{b}-\mathbf{r}_{k+1}\) and \(\mathbf{A}\mathbf{x}_{k}=\mathbf{b}-\mathbf{r}_{k}\), Equation (25) changes to  
\[\mathbf{r}_{k+1}=\mathbf{r}_{k}-\frac{\mathbf{r}_{k}^{\mathrm{T}}\mathbf{A} \mathbf{u}_{k}}{\|\mathbf{A}\mathbf{u}_{k}\|^{2}}\mathbf{A}\mathbf{u}_{k}. \tag{26}\]  
Taking the inner product with \(\mathbf{A}\mathbf{u}_{k}\) yields  
\[\mathbf{x}_{k+1}=\mathbf{x}_{k}+\frac{\mathbf{r}_{k}^{T}\mathbf{A}\mathbf{u}_{ k}}{\|\mathbf{A}\mathbf{u}_{k}\|^{2}}\mathbf{u}_{k}. \tag{18}\]0  
Equation (24) is proven. It follows from Equation (5) that \(\eta=1\) is implied by GMRES. However, during the GMRES iteration the numerical values of \(\eta\) may deviate from 1 to a great extent, even being zero or a negative value. Therefore, we propose a re-orthogonalized version of GMRES, namely the ROGMRES method (Algorithm 4), as follows. ```
1:Give \(m_{0}\), \(\mathbf{x}_{0}\), and \(\varepsilon\)
2:Do \(m=m_{0},\ldots\) (\(k=m-m_{0}\)), until \(\|\mathbf{r}_{k}\|<\varepsilon\)
3:\(\mathbf{r}_{k}=\mathbf{b}-\mathbf{A}\mathbf{x}_{k}\)
4:\(\mathbf{v}_{1}^{k}=\frac{\mathbf{r}_{k}}{\|\mathbf{r}_{k}\|}\)
5:\(\mathbf{V}_{k}=[\mathbf{v}_{1}^{\mathrm{T}},\ldots,\mathbf{v}_{m}^{k}]\) (by Arnoldi process)
6:Solve \((\mathbf{H}_{k}^{\mathrm{T}}\mathbf{H}_{k})\mathbf{y}_{k}=\|\mathbf{r}_{k}\| \mathbf{\bar{H}}_{k}^{\mathrm{T}}\mathbf{e}_{1}\)
7:\(\mathbf{u}_{k}=\mathbf{V}_{k}\mathbf{y}_{k}\)
8:\(\mathbf{x}_{k+1}=\mathbf{x}_{k}+\frac{\mathbf{r}_{k}^{\mathrm{T}}\mathbf{A} \mathbf{u}_{k}}{\|\mathbf{A}\mathbf{u}_{k}\|^{2}}\mathbf{u}_{k}\)
```  
**Algorithm 4**ROGMRES  
Correspondingly, the ROGMRES(m) Algorithm 5 is given as follows. Upon comparing with GMRES(m) in Section 2, the computational cost of ROGMRES(m) is slightly increased by computing an extra term, \(\mathbf{r}_{k}^{\mathrm{T}}\mathbf{A}\mathbf{u}_{k}/\|\mathbf{A}\mathbf{u}_{k}\|^ {2}\), at each iteration; it needs one matrix-vector product and two inner products of vectors. **Theorem 1**.