From 166f32f18ec198e8744c5092290f640921199099 Mon Sep 17 00:00:00 2001 From: Christophe Guyeux Date: Sat, 11 Oct 2014 11:25:27 +0200 Subject: [PATCH] =?utf8?q?Avanc=C3=A9es=20dans=20la=20r=C3=A9=C3=A9criture?= =?utf8?q?=20de=20la=20preuve?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- paper.tex | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) diff --git a/paper.tex b/paper.tex index 812326f..82cc12a 100644 --- a/paper.tex +++ b/paper.tex @@ -748,8 +748,9 @@ these operations are easy to implement in PETSc or similar environment. 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 +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 we have the following boundaries: \begin{itemize} @@ -770,20 +771,20 @@ where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta \begin{proof} 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\|, . +\|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*} 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*} ||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| , \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$. -Such well-known results can be found, \emph{e.g.}, in~\cite{Saad86}. +the convergence of GMRES($m$) for all $m$ under such assumptions regarding $A$. +These 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 the results recalled above. Suppose now that the claim holds for all $m=1, 2, \hdots, k-1$, that is, $\forall m \in \{1,2,\hdots, k-1\}$, $||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||$. We will show that the statement holds too for $r_k$. Two situations can occur: -- 2.39.5