## 6 Numerical Methods and Algorithms
### Models at the Macro-Scale
#### 6.1.2 Solution of the \"Discrete in Space\"
The problem (113) is linear, the schema is conditionally stable, and its order of accuracy (see Definition 2 for a definition of the _\"order of accuracy\"_ terms) is \(O(\Delta t)\);  
\(\alpha=0.5\)**, the Crank-Nicolson implicit scheme**. The problem (113) is nonlinear, the schema is unconditionally stable, and its order of accuracy is \(O\Big{(}(\Delta t)^{2}\Big{)}\);  
\(\alpha=\frac{2}{3}\)**, the Galerkin implicit scheme**. The problem (113) is nonlinear, the schema is unconditionally stable, and its order of accuracy is \(O\Big{(}(\Delta t)^{2}\Big{)}\);  
\(\alpha=1\)**, the backward difference Euler implicit scheme**. The problem (113) is nonlinear, the schema is unconditionally stable, and its order of accuracy is \(O(\Delta t)\). For \(\alpha\geq 0.5\), the scheme is stable, and for \(\alpha<0.5\), the scheme is stable only if the time step meets the following restrictions (i.e., conditionally stable schemes) (see Reddy [136]):  
\[u_{n+1} =f(u_{n},\dot{u}_{n},) \text{explicit schema}\]2  
where the greatest eigenvalue of the eigenvalue problem related to the matrix Equation (113) is denoted by \(\lambda_{max}\):  
\[u_{n+1} =f(u_{n},\dot{u}_{n},) \text{explicit schema}\]3  
See [144] for further definitions and descriptions of the _\"stability\"_ and _\"accuracy\"_ terms. Generally, Algorithm 1 requires the solution of a nonlinear problem (see line 9) that can be solved by methods described in the next point 2. If the problem degenerates into a linear one (i.e., when \(a_{1}=0\)) its solution can be obtained by methods described at next point 3. 2. **The Non-linear problem solver** Let us consider the following nonlinear algebraic system:  
\[u_{n+1} =f(u_{n},\dot{u}_{n},) \text{explicit schema}\]4  
where \(\mathbf{G}=[G_{i}(\mathbf{u})]_{i=1,\ldots,M}^{T}\) and \(\mathbf{u}=[u_{i}]_{i=1,\ldots,M}^{T}\) are vectors in \(\Re^{M}\). Assuming the existence of a solution \(\tilde{\mathbf{u}}\) for the system (122), an approximation of that solution can be obtained by different methods. The _\"Newton-Raphson methods\"_, and their derivatives, should be cited as the most commonly used [145]. Such methods iteratively compute an approximation \(\mathbf{u}_{n+1}\) of \(\tilde{\mathbf{u}}\), and they are based on a Taylor series development of the left term of (122) at an already known state \(\mathbf{u}_{n}\)  
\[u_{n+1} =f(u_{n},\dot{u}_{n},) \text{explicit schema}\]5  
where \(D[\mathbf{G}(\mathbf{u}_{n})]\) is the Jacobi matrix of \(\mathbf{G}\) at \(\mathbf{u}_{n}\), i.e.,  
\[u_{n+1} =f(u_{n},\dot{u}_{n},) \text{explicit schema}\]6  
Let \(\mathbf{u}_{n+1}=\mathbf{u}_{n}+\Delta u\); then  
\[u_{n+1} =f(u_{n},\dot{u}_{n},) \text{explicit schema}\]7Therefore, an approximation \(\mathbf{u}_{N}\) of \(\bar{\mathbf{u}}\) can be computed using the iterative algorithm represented in Algorithm 2. The rate of convergence of the Newton-Raphson scheme is characterized by the following inequality:  
\[u_{n+1} =f(u_{n},\dot{u}_{n},) \text{explicit schema}\]8  
```
1:procedureNewtonSolver(\(\mathbf{G}\), \(\mathbf{u}_{0}\), \(N\), \(\mathbf{u}_{N}\))
2:Input:\(\mathbf{G}\), \(\mathbf{u}_{0}\), \(N\)
3:Output:\(\mathbf{u}_{N}\)
4:for\(n=0\) to \(N-1\)do
5:\(\mathbf{G}(\mathbf{u}_{n})\leftarrow\)Compute \(\mathbf{G}(\mathbf{u}_{n})\)
6:\(\mathbf{J}_{n}\leftarrow\)Compute \(\mathbf{J}_{n}\)
7:\(\Delta\mathbf{u}_{n}\leftarrow\)Solve \(\mathbf{J}_{n}\Delta\mathbf{u}_{n}=-\mathbf{G}(\mathbf{u}_{n})\)
8:\(\mathbf{u}_{n+1}\leftarrow\)Compute \(\mathbf{u}_{n+1}=\mathbf{u}_{n}+\Delta\mathbf{u}_{n}\)
9:endfor
10:endprocedure
```  
**Algorithm 2** The algorithm implementing the _\"Newton-Raphson methods\"_ for the approximated solution of Equation (122). Depending on the approach used to approximate/compute the Jacobi-matrix (or tangent matrix) \(\mathbf{J}_{n}\) of \(\mathbf{G}(\mathbf{u}_{n})\), different derivations of the scheme can be obtained: Table 8 lists some of them. Also, when the application of the BFGS-update is considered, Algorithm 2 can be used.