PDF
\(\newcommand{\footnotename}{footnote}\) \(\def \LWRfootnote {1}\) \(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\) \(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\) \(\let \LWRorighspace \hspace \) \(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\) \(\newcommand {\mathnormal }[1]{{#1}}\) \(\newcommand \ensuremath [1]{#1}\) \(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \) \(\newcommand {\setlength }[2]{}\) \(\newcommand {\addtolength }[2]{}\) \(\newcommand {\setcounter }[2]{}\) \(\newcommand {\addtocounter }[2]{}\) \(\newcommand {\arabic }[1]{}\) \(\newcommand {\number }[1]{}\) \(\newcommand {\noalign }[1]{\text {#1}\notag \\}\) \(\newcommand {\cline }[1]{}\) \(\newcommand {\directlua }[1]{\text {(directlua)}}\) \(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\) \(\newcommand {\protect }{}\) \(\def \LWRabsorbnumber #1 {}\) \(\def \LWRabsorbquotenumber "#1 {}\) \(\newcommand {\LWRabsorboption }[1][]{}\) \(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\) \(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\) \(\def \mathcode #1={\mathchar }\) \(\let \delcode \mathcode \) \(\let \delimiter \mathchar \) \(\def \oe {\unicode {x0153}}\) \(\def \OE {\unicode {x0152}}\) \(\def \ae {\unicode {x00E6}}\) \(\def \AE {\unicode {x00C6}}\) \(\def \aa {\unicode {x00E5}}\) \(\def \AA {\unicode {x00C5}}\) \(\def \o {\unicode {x00F8}}\) \(\def \O {\unicode {x00D8}}\) \(\def \l {\unicode {x0142}}\) \(\def \L {\unicode {x0141}}\) \(\def \ss {\unicode {x00DF}}\) \(\def \SS {\unicode {x1E9E}}\) \(\def \dag {\unicode {x2020}}\) \(\def \ddag {\unicode {x2021}}\) \(\def \P {\unicode {x00B6}}\) \(\def \copyright {\unicode {x00A9}}\) \(\def \pounds {\unicode {x00A3}}\) \(\let \LWRref \ref \) \(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\) \( \newcommand {\multicolumn }[3]{#3}\) \(\require {textcomp}\) \(\newcommand {\intertext }[1]{\text {#1}\notag \\}\) \(\let \Hat \hat \) \(\let \Check \check \) \(\let \Tilde \tilde \) \(\let \Acute \acute \) \(\let \Grave \grave \) \(\let \Dot \dot \) \(\let \Ddot \ddot \) \(\let \Breve \breve \) \(\let \Bar \bar \) \(\let \Vec \vec \)

Convergence Analysis for Nonlinear GMRES

Yunhui He

Department of Mathematics, University of Houston, Houston, USA

Abstract

We are interested in solving the following nonlinear system of equations

\begin{equation} g(x)=0, \end{equation}

where \(x\in \mathbb {R}^n\) and \(g: \mathbb {R}^n \rightarrow \mathbb {R}^n\).

Consider the following fixed-point iteration

\begin{equation} x_{k+1}=q(x_k)=x_k-g(x_k). \end{equation}

In practice, the fixed-point iteration converges slowly or even diverges. We seek methods to accelerate it.

Define the k-th residual of the fixed-point iteration as

\begin{equation} r(x_k)=x_k-q(x_k)=g(x_k). \end{equation}

We revisit the nonlinear generalized minimal residual method (NGMRES) following [2, 1]. NGMRES has been used to accelerate the convergence of a fixed-point iteration, given by Algorithm 1. In practice, we consider the windowed NGMRES, i.e., fixing \(m\), denoted as NGMRES(\(m\)), which is different than restart GMRES.

Algorithm 1: NGMRES with window size \(m\), denoted as (NGMRES(\(m\)))

  • 1: Given \(x_0\) and \(m\geq 0\)

  • 2: For \(k=1,2,\cdots \) until convergence Do:

    • • set \(m_k=\min \{k,m\}\)

    • • compute

      \begin{equation} \label {eq:xkp1} x_{k+1} = q(x_k) + \sum _{i=0}^{m_k}\beta _i^{(k)} \left (q(x_k)-x_{k-i} \right ), \end{equation}

      where \(\beta _i^{(k)}\) is obtained by solving the following least-squares problem

      \begin{equation} \label {eq:min} \min _{\beta _i^{(k)}} \left \|g(q(x_k))+\sum _{i=0}^{m_k} \beta _i^{(k)} \left (g(q(x_k))-g(x_{k-i}) \right ) \right \|_2^2. \end{equation}

    EndDo

To the best of our knowledge, no convergence analysis exists for NGMRES(\(m\)) when applied to nonlinear problems. In this work, under some standard assumptions used for iterative methods in nonlinear problems, we prove that for general \(m>0\), the residuals of NGMRES(\(m\)) converge r-linearly. For \(m=0\), we prove that the residuals of NGMRES(0) converge q-linearly.

Finally, we present numerical results to demonstrate the performance of the NGMRES(\(m\)) method, and we make a comparison with the well-known Anderson acceleration [3]

References