From 9300a8195f1fd0aba96819dbd29244ca8bc90a33 Mon Sep 17 00:00:00 2001 From: Christophe Guyeux Date: Sat, 11 Oct 2014 11:20:19 +0200 Subject: [PATCH 1/1] =?utf8?q?Premi=C3=A8re=20version=20finalis=C3=A9e=20d?= =?utf8?q?e=20la=20prop.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- paper.tex | 24 +++++++++++++----------- 1 file changed, 13 insertions(+), 11 deletions(-) diff --git a/paper.tex b/paper.tex index 8adef83..812326f 100644 --- 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} +\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 @@ -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)$; -\item when $A$ is definite positive: +\item when $A$ is positive definite: \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 -%$\|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} -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: -\begin{equation} +\begin{equation*} ||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$. -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}. -- 2.39.5