Première version finalisée de la prop.

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 8adef83dd8d3db276c8385c9ccd0e9b951d98ba3..812326f0a520ef867be69f9f7582e322f3b564fe 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -747,6 +747,7 @@ these operations are easy to implement in PETSc or similar environment.
 
 We can now claim that,
 \begin{proposition}
 
 We can now claim that,
 \begin{proposition}

+\label{prop:saad}

 If $A$ is either a definite positive or a positive matrix and GMRES($m$) is used as solver, then the TSIRM algorithm is convergent. Furthermore, 
 let $r_k$ be the
 $k$-th residue of TSIRM, then
 If $A$ is either a definite positive or a positive matrix and GMRES($m$) is used as solver, then the TSIRM algorithm is convergent. Furthermore, 
 let $r_k$ be the
 $k$-th residue of TSIRM, then


@@ -757,29 +758,30 @@ we have the following boundaries:
 ||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0|| ,
 \end{equation}
 where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$;
 ||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0|| ,
 \end{equation}
 where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$;

-\item when $A$ is definite positive:
+\item when $A$ is positive definite:

 \begin{equation}
 \begin{equation}

-\|r_n\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{n/2} \|r_0\|,
+\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_0\|.

 \end{equation}
 \end{itemize}
 %In the general case, where A is not positive definite, we have
 \end{equation}
 \end{itemize}
 %In the general case, where A is not positive definite, we have

-%$\|r_n\| \le \inf_{p \in P_n} \|p(A)\| \le \kappa_2(V) \inf_{p \in P_n} \max_{\lambda \in \sigma(A)} |p(\lambda)| \|r_0\|, \,$
-
+%$\|r_n\| \le \inf_{p \in P_n} \|p(A)\| \le \kappa_2(V) \inf_{p \in P_n} \max_{\lambda \in \sigma(A)} |p(\lambda)| \|r_0\|, .$

 \end{proposition}
 
 \begin{proof}
 \end{proposition}
 
 \begin{proof}

-We will prove by a mathematical induction that, for each $k \in \mathbb{N}^\ast$, 
-$||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{mk}{2}} ||r_0||.$
-
-Let us first recall that,
+Let us first recall that the residue is under control when considering the GMRES algorithm on a positive definite matrix, and it is bounded as follows:
+\begin{equation*}
+\|r_n\| \le \inf_{p \in P_n} \|p(A)\| \le \kappa_2(V) \inf_{p \in P_n} \max_{\lambda \in \sigma(A)} |p(\lambda)| \|r_0\|, .
+\end{equation*}

 Additionally, when $A$ is a positive real matrix with symmetric part $M$, then the residual norm provided at the $m$-th step of GMRES satisfies:
 Additionally, when $A$ is a positive real matrix with symmetric part $M$, then the residual norm provided at the $m$-th step of GMRES satisfies:

-\begin{equation}
+\begin{equation*}

 ||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,
 ||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,

-\end{equation}
+\end{equation*}

 where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}, which proves 
 the convergence of GMRES($m$) for all $m$ under that assumption regarding $A$.
 where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}, which proves 
 the convergence of GMRES($m$) for all $m$ under that assumption regarding $A$.

-Let us recall the following result, see~\cite{Saad86} for further readings.
+Such well-known results can be found, \emph{e.g.}, in~\cite{Saad86}.

 
 

+We will now prove by a mathematical induction that, for each $k \in \mathbb{N}^\ast$, 
+$||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{mk}{2}} ||r_0||$ when $A$ is positive, and $\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_0\|$ when $A$ is positive definite.

 
 The base case is obvious, as for $k=1$, the TSIRM algorithm simply consists in applying GMRES($m$) once, leading to a new residual $r_1$ which follows the inductive hypothesis due to Proposition~\ref{prop:saad}.
 
 
 The base case is obvious, as for $k=1$, the TSIRM algorithm simply consists in applying GMRES($m$) once, leading to a new residual $r_1$ which follows the inductive hypothesis due to Proposition~\ref{prop:saad}.