## 6 Numerical Methods and Algorithms
### Models at the Macro-Scale
#### 6.1.2 Solution of the \"Discrete in Space\"
This is carried out by imposing the conditions that \(\mathbf{x}_{N}\) belongs to \(\mathcal{K}_{N}\) and that the new residual vector is orthogonal to \(\mathcal{L}_{N}\), where \(\mathbf{x}_{0}\) is the initial guess to the solution; that is,  
\[\text{Find }\mathbf{x}_{N}\in\mathbf{x}_{0}+\mathcal{K}_{N}\text{, such that }\mathbf{y}-\mathbf{A}\mathbf{x}_{N}\perp\mathcal{L}_{N}.\]  
Note that if \(\mathbf{x}_{N}\) is written in the form \(\mathbf{x}_{N}=\mathbf{x}_{0}+\delta\), and the initial residual vector \(\mathbf{r}_{0}\) is defined as \(\mathbf{r}_{0}=\mathbf{y}-\mathbf{A}\mathbf{x}_{0}\), then the above condition becomes,  
\[\text{Find }\delta\in\mathcal{K}_{N}\text{, such that }\mathbf{r}_{0}-\mathbf{A}\delta\perp \mathcal{L}_{N}. \tag{129}\]  
In other words, the approximate solution can be defined as  
\[\text{Find }\delta\in\mathcal{K}_{N}\text{ such that }\qquad\langle\mathbf{r}_{0}-\mathbf{A}\delta,\mathbf{w} \rangle=0, \forall\mathbf{w}\in\mathcal{L}_{N} \tag{130}\] \[\text{Compute }\qquad\qquad\qquad\qquad\mathbf{x}_{N}=\mathbf{x}_{0}+\delta, \tag{131}\]  
where the symbol \(\langle\cdot,\cdot\rangle\) denotes the Euclidean inner product. In the most general form, this is a basic projection step. A series of these projections is used in the majority of common techniques. A new pair of subspaces, \(\mathcal{K}_{N+1}\) and \(\mathcal{L}_{N+1}\), are used in a new projection step to compute \(\mathbf{x}_{N+1}\). An initial guess, \(\mathbf{x}_{N}\), is equal to the most recent solution estimate obtained from the previous projection step. Many well-known techniques in scientific computing, such as the more complex KSM procedure or the simpler Gauss-Seidel step, have a unifying framework that is provided by projection methods. A Krylov subspace method is a method for which the subspace \(\mathcal{K}_{N}=\mathcal{K}_{N}(\mathbf{A},\mathbf{r}_{0})\) is the Krylov subspace [152]  
\[\mathcal{K}_{N}(\mathbf{A},\mathbf{r}_{0})=span\Big{\{}\mathbf{A}^{i}\mathbf{r}_{0}\Big{\}}_{i =0,\ldots,N-1}. \tag{132}\]  
Variations in the choices of subspace \(\mathcal{L}_{N}\) give rise to different Krylov subspace methods. The most popular methods arise from two general options for \(\mathcal{L}_{N}\). The first is simply \(\mathcal{L}_{N}=\mathcal{K}_{N}\) and the minimum residual variation \(\mathcal{L}_{N}=A\mathcal{K}_{N}\). The most representative among the KSMs is related to the choice \(\mathcal{L}_{N}=A\mathcal{K}_{N}\), and it will be described in this work: the \"Generalized Minimum Residual Method (GMRES)\". The second class of methods is based on defining \(\mathcal{L}_{N}\) to be a Krylov subspace method associated with \(\mathbf{A}^{T}\), namely, \(\mathcal{L}_{N}=\mathcal{K}_{N}\big{(}\mathbf{A}^{T},\mathbf{r}_{0}\big{)}\) (see [152] for details). The GMRES method can be used to solve sparse linear systems whose matrix \(\mathbf{A}\) is general (i.e., not necessarily symmetric or positive definite). Let \(\mathbf{V}_{N}\) matrices whose columns are an orthonormal basis for space \(\mathcal{K}_{N}=\mathcal{K}_{N}(\mathbf{A},\mathbf{r}_{0})\), then \(\delta\) can be expressed as as \(\delta=\mathbf{V}_{N}\mathbf{\vartheta}\) where \(\mathbf{\vartheta}\in\mathcal{K}_{N}\). Furthermore, let \(\mathcal{L}_{N}=A\mathcal{K}_{N}\) and define  
\[J_{N}(\mathbf{\vartheta})=\left\|\mathbf{r}_{N}\right\|_{2} = \left\|\mathbf{y}-\mathbf{A}\mathbf{x}_{N}\right\|_{2},\] \[= \left\|\mathbf{y}-\mathbf{A}(\mathbf{x}_{0}+\mathbf{V}_{N}\mathbf{\vartheta})\right\|_ {2},\] \[= \left\|\mathbf{r}_{0}-\mathbf{A}\mathbf{V}_{N}\mathbf{\vartheta}\right\|_{2}, \tag{133}\]  
where \(\left\|\cdot\right\|_{2}\) is the spectral norm, that is, the matrix norm induced by the Euclidean vector's inner product.