A simple-to-implement nonlinear preconditioning of Newton’s method for solving the steady Navier-Stokes equations Muhammad Mohebujjaman, Mengying Xiao, Cheng Zhang Abstract Newton’s method for solving stationary Navier-Stokes equations (NSE) is known for its fast convergence; however, it may fail when provided with a poor initial guess. This work presents a simple-to-implement nonlinear preconditioning technique for Newton’s iteration that retains quadratic convergence and expands the domain of convergence. The proposed AAPicard-Newton method adds an Anderson accelerated Picard step at each iteration of Newton’s method for solving NSE. This approach has been shown to be globally stable with a relaxation parameter β k + 1 ≡ 1 \beta_{k+1}\equiv 1 in the Anderson acceleration optimization step, converges quadratically, and achieves faster convergence with a small convergence rate for large Reynolds numbers. Several benchmark numerical tests have been carried out and are well aligned with the theoretical results. Key words: Nonlinear preconditioning, Newton’s method, Navier-Stokes equations, Anderson acceleration. Mathematics Subject Classifications (2000): 65N12, 65N15, 65N30, 76D05 1 Introduction The incompressible Navier-Stokes equations (NSE) are governed by the form \left\{\begin{aligned} -\nu\Delta u+u\cdot\nabla u+\nabla p&={f}\quad\text{in}~\Omega,\\ \nabla\cdot{u}&=0\quad\text{in}~\Omega,\end{aligned}\right. (1.1) on a domain \Omega\subset\mathbb{R}^{d},d=2,3 . Here, u is the velocity of the fluid, p is the pressure, \nu is the kinematic viscosity of the fluid, and {f} is an external forcing term. The parameter Re:=\frac{1}{\nu} represents the Reynolds number, which characterizes the complexity of the fluid problem. This work focuses on nonlinear solvers for the steady system defined by ( 1.1 ) with homogeneous Dirichlet boundary conditions; however, with some extra work, the results can also be extended to solve the time-dependent NSE at a fixed temporal discretization step, as well as non-homogeneous mixed Dirichlet/Neumann boundary conditions. Finding the NSE solution efficiently and accurately is an open problem, as the NSE is notorious for being one of the hard nonlinear differential equations for which analytical solutions are often unavailable. In practice, the nonlinear problem may exhibit poor convergence rates or be sensitive to the choice of initial conditions, as seen with methods like Picard and Newton methods. The Picard method is known for its global stability if a unique solution exists. Specifically, it guarantees convergence to a solution regardless of the initial guess. Moreover, for sufficiently small problem data, the Picard is globally convergent with a linear convergence rate smaller than 1 [ 8 , 24 ] . However, this can be seen as a limitation in practical applications due to the convergence rate being close to 1. On the other hand, Newton’s iteration demonstrates local quadratic convergence for small data and a sufficiently close initial guess [ 8 , 14 ] . Common alternative strategies involve using methods with a larger domain of convergence initially (such as Picard, Anderson accelerated Picard methods [ 6 , 24 ] or damped Newton [ 18 ] ) and subsequently switching to Newton’s method once the iterates are sufficiently close to the solution [ 11 ] . Nonlinear preconditioning is a widely adopted technique in many fields [ 9 , 19 , 31 ] , including computational fluid dynamics, structural analysis, and optimization problems, where nonlinearities are prevalent. This technique enhances the efficiency and robustness of numerical methods for solving nonlinear problems by converting the nonlinear problem into better-conditioned forms. Several works [ 2 , 4 , 15 ] have focused on nonlinear preconditioning for Newton’s method, leading to faster convergence and a larger domain of convergence. For instance, [ 23 ] proposes a nonlinear preconditioning of Newton’s method by adding a Picard step at each iteration of Newton’s method, called the Picard-Newton method (P-N), and is in the form of Step 1. Finding (\tilde{u}_{k+1},\tilde{p}_{k+1}) such that \displaystyle-\nu\Delta\tilde{u}_{k+1}+u_{k}\cdot\nabla\tilde{u}_{k+1}+\nabla\tilde{p}_{k+1} \displaystyle={f}, \displaystyle\nabla\cdot{\tilde{u}}_{k+1} \displaystyle=0. Step 2. Finding (u_{k+1},p_{k+1}) such that \displaystyle-\nu\Delta u_{k+1}+\tilde{u}_{k+1}\cdot\nabla u_{k+1}+u_{k+1}\cdot\nabla\tilde{u}_{k+1}+\nabla p_{k+1} \displaystyle={f}+\tilde{u}_{k+1}\cdot\nabla\tilde{u}_{k+1}, \displaystyle\nabla\cdot{u}_{k+1} \displaystyle=0. We denote it by u_{k+1}=g_{PN}(u_{k})=g_{N}(g_{P}(u_{k})) . In Step 1, we apply the standard Picard iteration, using the previous velocity u_{k} . In Step 2, we utilize the usual Newton’s method with the intermediate velocity \tilde{u}_{k+1}. Thus, the P-N method linearizes the nonlinear system ( 1.1 ), though it requires two linear solves at each iteration. The P-N method is advantageous because it is easy to implement, globally stable, quadratically convergent, and has an extended convergence radius compared to the usual Newton method. The 2D lid-driven cavity numerical experiment in [ 23 ] indicates that this 2-step method can converge for significantly higher Reynolds numbers ( Re\leq 12000 ) than the Picard method ( Re\leq 4000 ), Newton’s method ( Re\leq 2500 ), or Newton with line search ( Re\leq 3000 ). This technique has been applied to other nonlinear partial differential equations; see [ 7 ] . Our work is inspired by [ 23 ] and aims to further improve the performance of the Newton method by adding an Anderson accelerated Picard (AAPicard) preconditioning step [ 1 , 6 ] . Anderson acceleration (AA) adds an easy-to-implement optimization step of Picard solutions in the iteration, leading to solid convergence results from recent work [ 6 , 21 , 26 ] . AA improves the convergence of linearly convergent methods by slightly reducing the convergence rate and adjusting the convergence order of sublinearly and/or superlinearly convergent methods from r to \frac{r+1}{2} . Specifically, for the NSE, [ 24 , 30 ] found that AA enhances the Picard iteration with a small decrease in the convergence rate while decelerating Newton’s method to a superlinear convergence order of 1.5 . Thus, it is reasonable to apply AA solely to the Picard step to obtain optimal performance, and we refer to this approach as the AAPicard-Newton method. We establish that the AAPicard-Newton method is globally stable, quadratically convergent, and optimizing convergent performance when \beta_{k+1}\equiv 1 . Our theoretical results, along with numerical tests, indicate that the AAPicard-Newton method significantly improves the convergence for large Reynolds numbers. For example, the 2D lid-driven cavity solved by AAPicard-Newton method converges for Reynolds number Re\leq 20,000 and the 3D lid-driven cavity test for Re\leq 3000 . These values are higher than Re\leq 12,000 and Re\leq 1800 , respectively, for the results obtained using the P-N method. The rest of the paper is arranged as follows. Section 2 provides mathematical preliminaries for a smoother analysis to follow. Section 3 analyzes the AAPicard-Newton method with various depths m and relaxation parameter \beta . Section 4 presents several benchmark numerical experiments to verify the theoretical results. Section 5 discusses the conclusion and future study. 2 Mathematical preliminaries We denote the natural function spaces for the NSE by \displaystyle Q:=\{v\in{L}^{2}(\Omega):\int_{\Omega}v\ dx=0\}, (2.1) \displaystyle X:=\{v\in H^{1}\left(\Omega\right):v=0~~\text{on}~\partial\Omega\}, (2.2) \displaystyle V:=\{v\in X:(\nabla\cdot v,q)=0\ \forall q\in Q\}, (2.3) where \Omega is an open connected set. The L^{2} inner product and norm are denoted by (\cdot,\cdot) and \|\cdot\| , respectively. The notation \langle\cdot,\cdot\rangle , defined as \langle f,v\rangle=\int_{\Omega}fv\ dx, is used to represent the duality between H^{-1} and X , and \|\cdot\|_{-1} denotes the norm on H^{-1} . We define the nonlinear term: for all v,w,z\in X, b^{*}(v,w,z)=(v\cdot\nabla w,z)+\frac{1}{2}((\nabla\cdot v)w,z). Alternative energy-conserving formulations of the nonlinear term, including the rotational form and the EMAC (Energy, Momentum, and Angular Momentum Conserving) scheme [ 3 , 10 , 20 ] , can be utilized in this framework. A key characteristic of b^{*} is its skew-symmetric property [ 28 ] , which is defined by the equation: \displaystyle b^{*}(u,v,v)=0, (2.4) for all u,v\in X . If the first argument of b^{*} meets the condition \|\nabla\cdot u\|=0 , then the skew-symmetry is not required and does not influence the outcome. However, when certain finite element subspaces of X and Q are employed—like Taylor-Hood elements—it’s possible that the discretely divergence free space does not produce entirely divergence-free functions. Therefore, to ensure generality and address all scenarios, we incorporate skew-symmetry in our analysis. The following inequality holds for all v,w,z\in X \displaystyle b^{*}(v,w,z) \displaystyle\leq M\|\nabla v\|\|\nabla w\|\|\nabla z\|, (2.5) where M dependent only on the domain \Omega , see [ 13 , 28 ] . We present two inequalities in a Hilbert space X . For any vectors u,v\in X , we have the polarization identity [ 27 ] \displaystyle 2(u,v) \displaystyle=\|u\|^{2}+\|v\|^{2}-\|u-v\|^{2}, (2.6) and Young’s inequality [ 13 ] \displaystyle(u,v) \displaystyle\leq\frac{\epsilon}{2}\|u\|^{2}+\frac{1}{2\epsilon}\|v\|^{2}, (2.7) for any \epsilon>0. 2.1 NSE preliminaries Here we present the weak form [ 28 ] of the NSE ( 1.1 ), given by: Find u\in V satisfying \nu(\nabla u,\nabla v)+b^{*}(u,u,v)=\langle f,v\rangle,\ \forall v\in V. (2.8) It is well known that for any f\in H^{-1}(\Omega) and \nu>0 , the weak steady NSE system ( 2.8 ) is well-posed [ 8 , 13 ] if the small data condition is satisfied \sigma:=M\nu^{-2}\|f\|_{-1}<1, and that any solution to ( 1.1 ) or ( 2.8 ) satisfies \|\nabla u\|\leq\nu^{-1}\|f\|_{-1}, (2.9) by setting v=u in equation ( 2.8 ) and applying ( 2.4 ) and Hölder’s inequality. For the rest of this paper, we assume \sigma<1 . Of course, all works stated below are globally applicable and can be extended to \sigma>0 for local results with extra work (see [ 13 ] Chapter 6.4, [ 23 ] ). The newly introduced, simple-to-implement, 2-step iterative method – Picard-Newton method [ 23 ] is stated below. Algorithm 2.1 (Picard-Newton method [ 23 ] ) . The Picard-Newton method consists of applying the composition of the Newton and Picard iteration for solving Navier-Stokes equations: g_{N}\circ g_{P} , i.e., Step 1: Find \hat{u}_{k+1}=g_{P}(u_{k}) by finding \hat{u}_{k+1}\in V satisfying for all v\in V \nu(\nabla\hat{u}_{k+1},\nabla v)+b^{*}(u_{k},\hat{u}_{k+1},v)=\langle f,v\rangle. (2.10) Step 2: Find u_{k+1}=g_{N}(\hat{u}_{k+1}) by finding u_{k+1}\in V satisfying for all v\in V \displaystyle\nu(\nabla u_{k+1},\nabla v)+b^{*}(\hat{u}_{k+1},u_{k+1},v)+b^{*}(u_{k+1},\hat{u}_{k+1},v)-b^{*}(\hat{u}_{k+1},\hat{u}_{k+1},v)=\langle f,v\rangle. (2.11) [ 23 ] has manifested that Algorithm 2.1 is globally stable, \displaystyle\|\nabla\hat{u}_{k}\|\leq\nu^{-1}\|f\|_{-1},\quad\|\nabla u_{k+1}\|\leq \displaystyle\frac{1+\sigma}{1-\sigma}\nu^{-1}\|f\|_{-1}. (2.12) quadratically convergent for \sigma<1 , and has a larger domain of convergence than the usual Newton’s method. Similar local convergence results can be derived for \sigma\geq 1 and any given data f , see [ 23 ] . 2.2 Anderson acceleration preliminary Anderson acceleration has recently been shown to enhance the convergence of linearly converging fixed point methods, such as the Picard method for NSE [ 6 , 21 , 24 ] , and reduce the asymptotic convergence order of the Newton’s method for NSE [ 26 , 30 ] . It is optimal to apply AA solely to the Picard step of the Picard-Newton method [ 23 ] . Given a fixed point function g:X\rightarrow X with X a Hilbert space with norm \|\cdot\|_{X} , the Anderson acceleration algorithm with depth m=1,2,3,\dots and damping parameters 0<\beta_{k+1}\leq 1 is given by: Step 0: Choose x_{0}\in X. Step 1: Find w_{1}\in X such that w_{1}=g(x_{0})-x_{0} . Set x_{1}=x_{0}+w_{1} . Step k+1 : For k=1,2,3,\ldots Set m_{k}=\min\{k,m\}. [a.] Find w_{k+1}=g(x_{k})-x_{k} . [b.] Solve the minimization problem for \{\alpha_{j}^{k+1}\}_{k-m_{k}}^{k} \displaystyle\min_{\sum_{j=k-m_{k}}^{k}\alpha_{j}^{k+1}=1}\left\|\sum_{j=k-m_{k}}^{k}\alpha_{j}^{k+1}w_{j+1}\right\|_{X} (2.13) [c.] For a selected damping factor 0<\beta_{k+1}\leq 1 , set \displaystyle x_{k+1}=\sum_{j=k-m_{k}}^{k}\alpha_{j}^{k+1}x_{j}+\beta_{k+1}\sum_{j=k-m_{k}}^{k}\alpha_{j}^{k+1}w_{j+1}, (2.14) where w_{k+1}:=g(x_{k})-x_{k} represents the stage k residual. Remark 2.2 . We assume the \alpha_{j}^{k+1} are uniformly bounded. As discussed in [ 21 , 22 ] , this is equivalent to assuming the full column rank of the matrix with columns (w_{j+1}-w_{j})_{j=k,k-1,...k-m} and can be controlled by the length and angle filtering. It is the optimization step that improves the linearly convergent methods, and we define the Anderson gain \displaystyle\theta_{k}:=\frac{\left\|\sum_{j=k-m_{k}}^{k}\alpha_{j}^{k+1}w_{j+1}\right\|_{X}}{\|w_{k+1}\|_{X}}. (2.15) Clearly 0<\theta_{k}\leq 1 . With this, it can be proven that AA improves the linear convergence rate by scaling it by the gain factor \theta_{k} of the underlying AA optimization problem [ 6 , 21 , 24 ] . For AA with depth m , using the result from Theorem 5.1 of [ 21 ] we have that \displaystyle\left\|{w_{k+1}}\right\|_{X} \displaystyle\leq\left\|{w_{k}}\right\|_{X}\Bigg\{\theta_{k}((1-\beta_{k})+\kappa_{g}\beta_{k})+C\hat{\kappa}_{g}\sum_{n=k-{m_{k-1}}}^{k}\left\|{w_{n}}\right\|_{X}\Bigg\}, (2.16) where \kappa_{g} is the linear convergence rate of the usual fixed point iteration, \hat{\kappa}_{g} is the Lipschitz constant of g^{\prime} , C depends on relaxation and gain parameters, as well as the degree to which the past m differences w_{j+1}-w_{j} are linearly independent. The residual w_{k+1} is bounded by a linear term and several quadratic terms. The linear term will be dominant if the initial guess is good enough, and therefore, AA improves the rate of convergence as \theta_{k}<1 and further enhances the performance if 0<\beta_{k}<1 , especially for large \kappa_{g} . A greater depth results in a smaller \theta_{k} , and accelerates convergence. However, finding the optimal value of \beta_{k} is case-dependent and should be evaluated through numerical tests. 3 Analysis of AAPicard-Newton [ 23 ] manifests that the Picard-Newton method converges quadratically (globally for \sigma<1 and locally for \sigma>0 ). In the following subsections, we will study the convergence behavior of AA with depth m=1 applied to this method, and present the general depth case m=2,3,\dots in the subsequent subsections. To make the work clean, we restrict ourselves to \sigma<1 , but all results presented below can be extended locally to \sigma>0 with some additional effort (see [ 13 ] Chapter 6.4, [ 23 ] ), and hence the analysis is omitted here. 3.1 AAPicard-Newton m=1 We now analyze the AAPicard-Newton method using depth m=1 . We begin by formally stating the method. Algorithm 3.1 (AAPicard-Newton m=1 ) . The AAPicard-Newton iteration with depth m=1 consists of applying the composition of the Newton and Anderson accelerated Picard iterations for solving Navier-Stokes equations: g_{N}\circ g_{AP} , i.e., Step 1: Find \tilde{u}_{k+1}=g_{P}(u_{k}) by finding \tilde{u}_{k+1}\in V satisfying for all v\in V \nu(\nabla\tilde{u}_{k+1},\nabla v)+b^{*}(u_{k},\tilde{u}_{k+1},v)=\langle f,v\rangle. (3.1) Step 2: For a selected damping factor 0<\beta_{k+1}\leq 1 , set \displaystyle\hat{u}_{k+1}= \displaystyle\beta_{k+1}\left((1-\alpha_{k+1})\tilde{u}_{k+1}+\alpha_{k+1}\tilde{u}_{k}\right)+(1-\beta_{k+1})\left((1-\alpha_{k+1})u_{k}+\alpha_{k+1}u_{k-1}\right) \displaystyle= \displaystyle(1-\alpha_{k+1})\tilde{u}_{k+1}+\alpha_{k+1}\tilde{u}_{k}-(1-\beta_{k+1})w_{k+1}^{\alpha}, (3.2) where \alpha_{k+1} minimizes \displaystyle\|\nabla w_{k+1}^{\alpha}\|\coloneqq\left\|(1-\alpha_{k+1})\nabla(\tilde{u}_{k+1}-u_{k})+\alpha_{k+1}\nabla(\tilde{u}_{k}-u_{k-1})\right\|. (3.3) Step 3: Find u_{k+1}=g_{N}(\hat{u}_{k+1}) by finding u_{k+1}\in V satisfying for all v\in V \displaystyle\nu(\nabla u_{k+1},\nabla v)+b^{*}(\hat{u}_{k+1},u_{k+1},v)+b^{*}(u_{k+1},\hat{u}_{k+1},v)-b^{*}(\hat{u}_{k+1},\hat{u}_{k+1},v)=\langle f,v\rangle. (3.4) Remark 3.2 . The AAPicard-Newton m=1 Algorithm in [ 23 , 7 ] differs slightly from Algorithm 3.1 discussed here. For comparison, we present the algorithm in [ 23 ] below. Algorithm (PRTX [ 23 ] AAPicard-Newton algorithm m=1 and no relaxation): The method consists four steps at each iteration, and is described as follows: Step 1. Find \tilde{u}_{k+1}=g_{P}(u_{k}) by finding \tilde{u}_{k+1}\in V satisfying ( 3.1 ) for all v\in V . Step 2. Find \tilde{\tilde{u}}_{k+1}=g_{P}(\tilde{u}_{k+1}) by finding \tilde{\tilde{u}}_{k+1}\in V satisfying for all v\in V \displaystyle\nu(\nabla\tilde{\tilde{u}}_{k+1},\nabla v)+b^{*}(\tilde{u}_{k+1},\tilde{\tilde{u}}_{k+1},v)=\langle f,v\rangle. Step 3. Set \displaystyle\hat{u}_{k+1}= \displaystyle(1-\alpha_{k+1})\tilde{\tilde{u}}_{k+1}+\alpha_{k+1}\tilde{u}_{k+1}, where \alpha_{k+1} minimizes \displaystyle\left\|(1-\alpha_{k+1})\nabla(\tilde{\tilde{u}}_{k+1}-\tilde{u}_{k+1})+\alpha_{k+1}\nabla(\tilde{u}_{k+1}-u_{k})\right\|. Step 4. Find u_{k+1}=g_{N}(\hat{u}_{k+1}) by finding u_{k+1}\in V satisfying ( 3.4 ) for all v\in V . The differences between the two algorithms lie in Step 2 and Step 3. In Step 3, the algorithm uses Picard solutions from the current iteration only, requiring an additional Picard solve in Step 2 at each iteration. Thus, this method takes four linear solves per iteration: two Picard solves, one linear solve for optimization, and one Newton solve. Generally, increasing the Anderson depth m enhances the convergence if the initial guess is good enough. However, adding more residual terms in Step 3 as m increases will necessitate more Picard solves at each iteration. Consequently, for large m , the algorithm will need m+3 linear solves (including m+1 Picard solves, one linear solve for optimization, and one Newton solve) at each iteration. Furthermore, the computation time for Step 3 may increase significantly with larger m , making this algorithm less advisable for high depths. In contrast, Algorithm 3.1 involves only 1 Picard solve ( 3.1 ) at each iteration and reuses the Picard solution(s) from the previous iteration(s) for the Anderson optimization step ( 3.3 ). This same approach is taken by Algorithm 3.11 and Algorithm 3.16 , with depth m\geq 2 . Overall, Algorithms 3.1 , 3.11 and 3.16 require 3 linear solves at each iteration for any m\geq 1 . This modification makes the method more practical for larger Anderson depth m , although it complicates convergence analysis. Let \alpha_{k+1} minimize ( 3.3 ), define the Anderson gain \displaystyle\theta_{k+1}=\frac{\|\nabla w_{k+1}^{\alpha}\|}{\|\nabla(\tilde{u}_{k+1}-u_{k})\|}=\frac{\left\|(1-\alpha_{k+1})\nabla(\tilde{u}_{k+1}-u_{k})+\alpha_{k+1}\nabla(\tilde{u}_{k}-u_{k-1})\right\|}{\|\nabla(\tilde{u}_{k+1}-u_{k})\|}. (3.5) Obviously, 0\leq\theta_{k+1}\leq 1 , and moreover \theta_{k+1}=1 if and only if \alpha_{k+1}=0 , which implies Algorithm 3.1 is back to Algorithm 2.1 . From now on, we analyze this AAPicard-Newton iteration to show how it improves on Picard-Newton with \theta_{k+1}<1 . Because we are using AA and will draw from the AA theory of [ 21 ] , convergence is analyzed in terms of residuals, not the difference between successive iterations. First, we assume on the parameters \{\alpha_{k}\} we obtained from the Algorithm 3.1 . Assumption 3.3 ( m=1 ) . Let the sequence \{\alpha_{k}\} from Algorithm 3.1 be uniformly bounded such that for all k \displaystyle|\alpha_{k}|\leq|1-\alpha_{k}|+|\alpha_{k}|\leq C_{A}, (3.6) for some constant C_{A}>0 . Below presents the bounds for the Picard solution \tilde{u}_{k+1} and the difference between successive iterations \tilde{u}_{k+1}-\tilde{u}_{k} , which is satisfied for any \sigma>0 . Of course, it is also satisfied under the assumption \sigma<1 . Lemma 3.4 . For any positive integer k , we have \displaystyle\|\nabla\tilde{u}_{k+1}\| \displaystyle\leq\nu^{-1}\|f\|_{-1}, (3.7) \displaystyle\|\nabla(\tilde{u}_{k+1}-\tilde{u}_{k})\| \displaystyle\leq\sigma\|\nabla(u_{k}-u_{k-1})\|. (3.8) Proof. Setting v=\tilde{u}_{k+1} in ( 3.1 ) eliminates the second term and yields ( 3.7 ) using Cauchy-Schwarz inequality. We next prove ( 3.8 ). Subtracting ( 3.1 ) with k from ( 3.1 ) with k+1 yields \displaystyle\nu(\nabla(\tilde{u}_{k+1}-\tilde{u}_{k}),\nabla v)+b^{*}(u_{k}-u_{k-1},\tilde{u}_{k},v)+b^{*}(u_{k},\tilde{u}_{k+1}-\tilde{u}_{k},v)=0. (3.9) Letting v=\tilde{u}_{k+1}-\tilde{u}_{k} eliminates the last term and gives \displaystyle\|\nabla(\tilde{u}_{k+1}-\tilde{u}_{k})\|\leq\nu^{-1}M\|\nabla(u_{k}-u_{k-1})\|\|\nabla\tilde{u}_{k}\|\leq\sigma\|\nabla(u_{k}-u_{k-1})\|, thanks to ( 2.5 ) and ( 3.7 ). Next, we find the bounds of \hat{u}_{k+1} and u_{k+1} . Assumption 3.5 . Let u_{0} be a good initial guess such that for all k , the inequality is satisfied \displaystyle\|\nabla u_{k+1}\|\leq L\nu^{-1}\|f\|_{-1}, (3.10) for some constant L>0 . Consequently, applying the triangle inequality, ( 3.6 ) and ( 3.7 ) to equation ( 3.2 ), we can bound \hat{u}_{k+1} as \displaystyle\|\nabla\hat{u}_{k+1}\| \displaystyle\leq|1-\alpha_{k+1}|\|\nabla\tilde{u}_{k+1}\|+|\alpha_{k+1}|\|\nabla\tilde{u}_{k}\|+|1-\alpha_{k+1}|\|\nabla u_{k}\|+|\alpha_{k+1}|\|\nabla u_{k-1}\| \displaystyle\leq\max\{1,L\}C_{A}\nu^{-1}\|f\|_{-1}, (3.11) thanks to 0<\beta_{k}\leq 1. Moreover, from equation ( 3.2 ), we have \displaystyle\|\nabla(\hat{u}_{k+1}-\hat{u}_{k})\| \displaystyle\leq\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|+|\alpha_{k+1}|\|\nabla(\tilde{u}_{k+1}-\tilde{u}_{k})\|+(1-\beta_{k+1})\|\nabla w_{k+1}^{\alpha}\| \displaystyle\leq\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|+\sigma C_{A}\|\nabla(u_{k}-u_{k-1})\|+(1-\beta_{k+1})\theta_{k+1}\|\tilde{u}_{k+1}-u_{k}\|, (3.12) thanks to triangle inequality and ( 3.8 ). Remark 3.6 . Assumption 3.5 is not necessary for \beta_{k+1}=1 . As one can easily obtain \|\nabla\hat{u}_{k+1}\|\leq C_{A}\nu^{-1}\|f\|_{-1}, from ( 3.2 ), triangle inequality and ( 3.7 ). And then we have the following equation similar to ( 2.12 ) \|\nabla u_{k+1}\|\leq\frac{1+\sigma C_{A}^{2}}{1-\sigma C_{A}}\ \nu^{-1}\|f\|_{-1}, by letting v=u_{k+1} in equation ( 3.4 ) and followed by applying ( 2.5 ) and Hölder’s inequality. This indicates that Algorithm 3.1 is globally stable when \beta_{k+1}=1 and \sigma,\sigma C_{A}<1 . Next, we present two preliminary lemmas in order to show the convergence of Algorithm 3.1 . We first show that \|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|=\mathcal{O}(\|\nabla(u_{k}-\hat{u}_{k})\|) , which means that the convergence of Algorithm 3.1 is essentially determined by the Newton’s iteration step. Lemma 3.7 . For any integer k , we have \displaystyle\|\nabla(\tilde{u}_{k+1}-u_{k})\| \displaystyle\leq\nu^{-1}M\|\nabla(u_{k}-\hat{u}_{k})\|^{2}. (3.13) If Assumptions 3.3 , 3.5 and \sigma C_{A}\max\{1,L\}<1 hold, we have inequality \displaystyle\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\| \displaystyle=\mathcal{O}(\|\nabla(u_{k}-\hat{u}_{k})\|)=C_{k}\|\nabla(u_{k}-\hat{u}_{k})\|, (3.14) for some constants C_{k}>0 independent of \nu,h . Proof. Subtracting ( 3.4 ) at iteration k from ( 3.1 ) at iteration k+1 , we obtain \displaystyle\nu(\nabla(\tilde{u}_{k+1}-u_{k}),\nabla v)+b^{*}(u_{k},\tilde{u}_{k+1}-u_{k},v)+b^{*}(u_{k}-\hat{u}_{k},u_{k}-\hat{u}_{k},v)=0. (3.15) Setting v=\tilde{u}_{k+1}-u_{k} eliminates the second term. Applying ( 2.5 ) establishes ( 3.13 ). On the other hand, setting v=\hat{u}_{k}-u_{k} in equation ( 3.15 ) eliminates the third term. Applying ( 2.6 ) to the first term and ( 2.5 ) then ( 2.7 ) with \epsilon=4 to the second term yields \displaystyle\frac{\nu}{2}\left(\|\nabla(\tilde{u}_{k+1}-u_{k})\|^{2}+\|\nabla(u_{k}-\hat{u}_{k})\|^{2}-\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}\right) \displaystyle= \displaystyle b^{*}(u_{k},\tilde{u}_{k+1}-\hat{u}_{k},u_{k}-\hat{u}_{k}) \displaystyle\leq \displaystyle\frac{\nu}{4}\|\nabla(u_{k}-\hat{u}_{k})\|^{2}+\nu^{-1}M^{2}\|\nabla u_{k}\|^{2}\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}. Dropping the term \|\nabla(\tilde{u}_{k+1}-u_{k})\|^{2} reduces to \displaystyle\frac{\nu}{4}\|\nabla(u_{k}-\hat{u}_{k})\|^{2} \displaystyle\leq\left(\frac{\nu}{2}+\nu^{-1}M^{2}\|\nabla u_{k}\|^{2}\right)\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2} \displaystyle\leq\nu\left(\frac{1}{2}+L^{2}\sigma^{2}\right)\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}, (3.16) thanks to ( 3.10 ). To get the reverse inequality necessary for ( 3.14 ), we can rearrange equation ( 3.15 ) to get \displaystyle\nu(\nabla(\tilde{u}_{k+1}-u_{k}),\nabla v)+b^{*}(\hat{u}_{k},\tilde{u}_{k+1}-u_{k},v)+b^{*}(u_{k}-\hat{u}_{k},\tilde{u}_{k+1}-\hat{u}_{k},v)=0. Setting v=\tilde{u}_{k+1}-\hat{u}_{k} eliminates the third term. Again applying ( 2.6 ) to the first term and ( 2.5 ) followed by ( 2.7 ) to the second yields \displaystyle\frac{\nu}{2}\left(\|\nabla(\tilde{u}_{k+1}-u_{k})\|^{2}+\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}-\|\nabla(u_{k}-\hat{u}_{k})\|^{2}\right) \displaystyle\leq\frac{M}{2}\|\nabla\hat{u}_{k}\|\left(\|\nabla(\tilde{u}_{k+1}-u_{k})\|^{2}+\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}\right). This reduces to \displaystyle(1-\max\{1,L\}C_{A}\sigma)\left(\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}+\|\nabla(\tilde{u}_{k+1}-u_{k})\|^{2}\right)\leq\|\nabla(u_{k}-\hat{u}_{k})\|^{2}, using ( 3.11 ). Since \max\{1,L\}C_{A}\sigma<1 , dropping the term \|\nabla(\tilde{u}_{k+1}-u_{k})\|^{2} yields \displaystyle(1-\max\{1,L\}C_{A}\sigma)\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}\leq\|\nabla(u_{k}-\hat{u}_{k})\|^{2}. (3.17) Inequalities ( 3.16 ) and ( 3.17 ) show the equivalence of \tilde{u}_{k+1}-\hat{u}_{k} and u_{k}-\hat{u}_{k} satisfying \displaystyle(1-\max\{1,L\}C_{A}\sigma)\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}\leq\|\nabla(u_{k}-\hat{u}_{k})\|^{2}\leq\left(2+4\sigma^{2}L^{2}\right)\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}. This establishes ( 3.14 ) and finishes the proof. Next, we bound the difference of u_{k} between successive iterations. Lemma 3.8 . Let Assumptions 3.3 , 3.5 and \sigma C_{A}\max\{1,L\}<1 hold, then we have \|\nabla(u_{k+1}-u_{k})\|\leq\frac{6\nu^{-1}M\sigma^{2}C_{A}^{2}}{1-\sigma C_{A}\max\{1,L\}}\|\nabla(u_{k}-u_{k-1})\|^{2}\\ +\frac{(C_{k}^{-2}+6)\nu^{-1}M}{1-\sigma C_{A}\max\{1,L\}}\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}+\mathcal{O}(\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{4}), (3.18) where C_{k}>0 is given in Lemma 3.7 . Proof. Subtracting ( 3.4 ) with k from ( 3.4 ) with k+1 yields \displaystyle\nu(\nabla(u_{k+1}-u_{k}),\nabla v)+b^{*}(u_{k}-\hat{u}_{k},\hat{u}_{k+1}-\hat{u}_{k},v)+b^{*}(u_{k+1}-u_{k},\hat{u}_{k+1},v) \displaystyle-b^{*}(\hat{u}_{k+1}-\hat{u}_{k},\hat{u}_{k+1}-u_{k},v)+b^{*}(\hat{u}_{k+1},u_{k+1}-u_{k},v)=0. (3.19) Setting v=u_{k+1}-u_{k} eliminates the last term. Applying ( 2.5 ), ( 3.11 ) and followed by triangle inequality and inequality 2ab\leq a^{2}+b^{2} , for any a,b\geq 0 gives \displaystyle\nu(1-\sigma C_{A}\max\{1,L\})\|\nabla(u_{k+1}-u_{k})\| \displaystyle\leq \displaystyle M\|\nabla(\hat{u}_{k+1}-\hat{u}_{k})\|\|\nabla(u_{k}-\hat{u}_{k})\|+M\|\nabla(\hat{u}_{k+1}-\hat{u}_{k})\|\|\nabla(\hat{u}_{k+1}-u_{k})\| \displaystyle\leq \displaystyle 2M\|\nabla(\hat{u}_{k+1}-\hat{u}_{k})\|\|\nabla(u_{k}-\hat{u}_{k})\|+M\|\nabla(\hat{u}_{k+1}-\hat{u}_{k})\|^{2} \displaystyle\leq \displaystyle M\|\nabla(u_{k}-\hat{u}_{k})\|^{2}+2M\|\nabla(\hat{u}_{k+1}-\hat{u}_{k})\|^{2}. Then utilizing ( 3.12 ) and (a+b+c)^{2}\leq 3(a^{2}+b^{2}+c^{2}) for any a,b,c\geq 0 and followed by Lemma 3.7 , we obtain \displaystyle\nu(1-\sigma C_{A}\max\{1,L\})\|\nabla(u_{k+1}-u_{k})\| \displaystyle\leq \displaystyle M\|\nabla(u_{k}-\hat{u}_{k})\|^{2}+6M\left(\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}+\sigma^{2}C_{A}^{2}\|\nabla(u_{k}-u_{k-1})\|^{2}\right) \displaystyle+6M(1-\beta_{k+1})^{2}\theta_{k+1}^{2}\|\nabla(\tilde{u}_{k+1}-u_{k})\|^{2} \displaystyle\leq \displaystyle M(C_{k}^{-2}+6)\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}+6M\sigma^{2}C_{A}^{2}\|\nabla(u_{k}-u_{k-1})\|^{2} \displaystyle+6\nu^{-2}M^{3}(1-\beta_{k+1})^{2}\theta_{k+1}^{2}C_{k}^{-4}\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{4}. Dividing both sides by \nu(1-\sigma C_{A}\max\{1,L\}) , we obtain ( 3.18 ) and complete the proof. Finally, we are ready to prove a quadratic convergence result. The quadratic convergence is proven for differences of (\tilde{u}_{k+1}-\hat{u}_{k}) , as this is how the analysis naturally leads us, i.e., the Step 1 solution minus the Step 2 solution of the previous iteration. This can still be considered as quadratic convergence of the algorithm in the usual sense, if we consider Step 1 on iteration 1 to be the initial guess instead, and reorder Steps 1,2,3 to be Steps 2,3,1. Theorem 3.9 ( m=1 ) . Let \alpha_{k}\neq 0 , Assumptions 3.3 , 3.5 and \sigma C_{A}\max\{1,L\},\sigma<1 hold, we have \|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|\leq\frac{\nu^{-1}MC_{k-1}^{-2}C_{k}}{1-\sigma}\left(\theta_{k}\beta_{k}\sigma+(1-\beta_{k})C_{A}\right)\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}\\ +(1-\beta_{k})\frac{C_{A}\nu^{-1}MC_{k-2}^{-2}}{1-\sigma}\|\nabla(\tilde{u}_{k-1}-\hat{u}_{k-2})\|^{2}\\ +\text{higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k}\text{ and }u_{1}-u_{0}, (3.20) where \theta_{k},C_{A},L are defined in ( 3.5 ), ( 3.6 ) and ( 3.10 ) respectively, and C_{k} are some constants independent of \nu,h . Remark 3.10 . First of all, Algorithm 3.1 converges quadratically for 0<\beta_{k+1}\leq 1 . Evidently, \beta_{k+1}=1 optimizes the convergence as fewer residual terms are on the RHS of ( 3.20 ), which reduces to \|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|\leq\frac{\nu^{-1}MC_{k-1}^{-2}C_{k}}{1-\sigma}\sigma\theta_{k}\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}\\ +\text{higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k}\text{ and }u_{1}-u_{0}. (3.21) Besides that, the solutions \{u_{k+1}\} are globally stable due to the discussion in Remark 3.6 . In addition, AAPicard-Newton method with m=1 is superior to Algorithm 2.1 as \theta_{k}<1 when \alpha_{k}\neq 0 and Re=\nu^{-1} large enough, leading to a small convergence rate. Otherwise, the higher-order terms may be dominant and decelerate the convergence. Proof. From ( 3.2 ), we rewrite u_{k}-\hat{u}_{k} as \displaystyle u_{k}-\hat{u}_{k}= \displaystyle u_{k}-\tilde{u}_{k}+\alpha_{k}(\tilde{u}_{k}-\tilde{u}_{k-1})+(1-\beta_{k})w_{k}^{\alpha}, and would like to construct an equation of u_{k}-\hat{u}_{k} below. We begin by subtracting ( 3.4 ) with u_{j-1} from ( 3.1 ) with \tilde{u}_{j} gives \displaystyle\nu(\nabla(\tilde{u}_{j}-u_{j-1}),\nabla v)+b^{*}(u_{j-1},\tilde{u}_{j}-u_{j-1},v)+b^{*}(u_{j-1}-\hat{u}_{j-1},u_{j-1}-\hat{u}_{j-1},v) \displaystyle=0. (3.22) Adding (1-\alpha_{k})\times ( 3.22 ) with j=k and \alpha_{k}\times ( 3.22 ) with j=k-1 gives an equation of w^{\alpha}_{k} \nu(\nabla w^{\alpha}_{k},\nabla v)+b^{*}(u_{k-1},w_{k}^{\alpha},v)-\alpha_{k}b^{*}(u_{k}-u_{k-1},\tilde{u}_{k-1}-u_{k-2},v)\\ +(1-\alpha_{k})b^{*}(u_{k-1}-\hat{u}_{k-1},u_{k-1}-\hat{u}_{k-1},v)+\alpha_{k}b^{*}(u_{k-2}-\hat{u}_{k-2},u_{k-2}-\hat{u}_{k-2},v)=0. (3.23) Adding (1-\alpha_{k})\times ( 3.1 ) with \tilde{u}_{k} and \alpha_{k}\times ( 3.1 ) with \tilde{u}_{k-1} yields \nu(\nabla((1-\alpha_{k})\tilde{u}_{k}+\alpha_{k}\tilde{u}_{k-1}),\nabla v)-b^{*}(w_{k}^{\alpha},\tilde{u}_{k},v)+b^{*}((1-\alpha_{k})\tilde{u}_{k}+\alpha_{k}\tilde{u}_{k-1},\tilde{u}_{k},v)\\ -\alpha_{k}b^{*}(u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v)=\langle f,v\rangle. Subtracting it from the sum of equation ( 3.4 ) with u_{k} and (1-\beta_{k})\times ( 3.23 ), we obtain an equation of u_{k}-\hat{u}_{k} \nu(\nabla(u_{k}-\hat{u}_{k}),\nabla v)=-b^{*}(\hat{u}_{k},u_{k}-\hat{u}_{k},v)-b^{*}(u_{k},\hat{u}_{k},v)-b^{*}(w_{k}^{\alpha},\tilde{u}_{k},v)+b^{*}((1-\alpha_{k})\tilde{u}_{k}+\alpha_{k}\tilde{u}_{k-1},\tilde{u}_{k},v)\\ -\alpha_{k}b^{*}(u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v)-(1-\beta_{k})b^{*}(u_{k-1},w_{k}^{\alpha},v)+(1-\beta_{k})\alpha_{k}b^{*}(u_{k}-u_{k-1},\tilde{u}_{k-1}-u_{k-2},v)\\ -(1-\beta_{k})(1-\alpha_{k})b^{*}(u_{k-1}-\hat{u}_{k-1},u_{k-1}-\hat{u}_{k-1},v)-(1-\beta_{k})\alpha_{k}b^{*}(u_{k-2}-\hat{u}_{k-2},u_{k-2}-\hat{u}_{k-2},v). Combining the third, fifth and sixth terms gives \displaystyle-b^{*}(u_{k},\hat{u}_{k},v)+b^{*}((1-\alpha_{k})\tilde{u}_{k}+\alpha_{k}\tilde{u}_{k-1},\tilde{u}_{k},v)-\alpha_{k}b^{*}(u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v) \displaystyle= \displaystyle-b^{*}(u_{k}-\hat{u}_{k}-(1-\beta_{k})w_{k}^{\alpha},\tilde{u}_{k},v)-b^{*}(u_{k},\hat{u}_{k}-\tilde{u}_{k},v)-\alpha_{k}b^{*}(u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v) \displaystyle= \displaystyle-b^{*}(u_{k}-\hat{u}_{k},\tilde{u}_{k},v)+(1-\beta_{k})b^{*}(w_{k}^{\alpha},\tilde{u}_{k},v)+(1-\beta_{k})b^{*}(u_{k},w_{k}^{\alpha},v)+\alpha_{k}b^{*}(u_{k}-u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v), thanks to ( 3.2 ), and then the equation of u_{k}-\hat{u}_{k} becomes \nu(\nabla(u_{k}-\hat{u}_{k}),\nabla v)=-b^{*}(\hat{u}_{k},u_{k}-\hat{u}_{k},v)-\beta_{k}b^{*}(w_{k}^{\alpha},\tilde{u}_{k},v)-b^{*}(u_{k}-\hat{u}_{k},\tilde{u}_{k},v)\\ +\alpha_{k}b^{*}(u_{k}-u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v)+(1-\beta_{k})b^{*}(u_{k}-u_{k-1},w_{k}^{\alpha},v)+(1-\beta_{k})\alpha_{k}b^{*}(u_{k}-u_{k-1},\tilde{u}_{k-1}-u_{k-2},v)\\ -(1-\beta_{k})(1-\alpha_{k})b^{*}(u_{k-1}-\hat{u}_{k-1},u_{k-1}-\hat{u}_{k-1},v)-(1-\beta_{k})\alpha_{k}b^{*}(u_{k-2}-\hat{u}_{k-2},u_{k-2}-\hat{u}_{k-2},v). Setting v=u_{k}-\hat{u}_{k} eliminates the second term, and applying inequalities ( 2.5 ), ( 3.6 ) and Lemma 3.4 gives \displaystyle\nu(1-\sigma)\|\nabla(u_{k}-\hat{u}_{k})\| \displaystyle\leq \displaystyle\beta_{k}M\|\nabla w_{k}^{\alpha}\|\cdot\nu^{-1}\|f\|_{-1}+|\alpha_{k}|M\|\nabla(u_{k}-u_{k-2})\|\cdot\sigma\|\nabla(u_{k-1}-u_{k-2})\| \displaystyle+(1-\beta_{k})M\|\nabla(u_{k}-u_{k-1})\|\|\nabla w_{k}^{\alpha}\|+(1-\beta_{k})C_{A}M\|\nabla(u_{k}-u_{k-1})\|\|\nabla(\tilde{u}_{k-1}-u_{k-2})\| \displaystyle+(1-\beta_{k})C_{A}M\|\nabla(u_{k-1}-\hat{u}_{k-1})\|^{2}+(1-\beta_{k})C_{A}M\|\nabla(u_{k-2}-\hat{u}_{k-2})\|^{2}. Utilizing ( 3.5 ), Lemma 3.7 and the inequality 2ab\leq a^{2}+b^{2} , we bound the second and fourth terms by \displaystyle\beta_{k}M\|\nabla w_{k}^{\alpha}\|\|\nabla\tilde{u}_{k}\|+(1-\beta_{k})M\|\nabla(u_{k}-u_{k-1})\|\|\nabla w_{k}^{\alpha}\| \displaystyle\leq \displaystyle\beta_{k}\nu^{-1}\|f\|_{-1}M\theta_{k}\|\nabla(\tilde{u}_{k}-u_{k-1})\|+(1-\beta_{k})M\|\nabla(u_{k}-u_{k-1})\|\cdot\theta_{k}\|\nabla(\tilde{u}_{k}-u_{k-1})\| \displaystyle\leq \displaystyle\beta_{k}\sigma\theta_{k}MC_{k-1}^{-2}\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}+(1-\beta_{k})\theta_{k}\nu^{-1}M^{2}C_{k-1}^{-2}\|\nabla(u_{k}-u_{k-1})\|\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2} \displaystyle\leq \displaystyle\beta_{k}\sigma\theta_{k}MC_{k-1}^{-2}\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}+\frac{1}{2}(1-\beta_{k})\theta_{k}\nu^{-1}M^{2}\|\nabla(u_{k}-u_{k-1})\|^{2} \displaystyle+\frac{1}{2}(1-\beta_{k})\theta_{k}\nu^{-1}M^{2}C_{k-1}^{-4}\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{4}, the third term by \displaystyle\sigma C_{A}M\|\nabla(u_{k}-u_{k-2})\|\|\nabla(u_{k-1}-u_{k-2})\| \displaystyle\leq \displaystyle\sigma C_{A}M\left(\|\nabla(u_{k}-u_{k-1})\|\|\nabla(u_{k-1}-u_{k-2})\|+\|\nabla(u_{k-1}-u_{k-2})\|^{2}\right) \displaystyle\leq \displaystyle\frac{1}{2}C_{A}\sigma M\left(\|\nabla(u_{k}-u_{k-1})\|^{2}+3\|\nabla(u_{k-1}-u_{k-2})\|^{2}\right), the fifth term by \displaystyle(1-\beta_{k})C_{A}M\|\nabla(u_{k}-u_{k-1})\|\|\nabla(\tilde{u}_{k-1}-u_{k-2})\| \displaystyle\leq \displaystyle(1-\beta_{k})C_{A}\nu^{-1}M^{2}\|\nabla(u_{k}-u_{k-1})\|\cdot C_{k-2}^{-2}\|\nabla(\tilde{u}_{k-1}-\hat{u}_{k-2})\|^{2} \displaystyle\leq \displaystyle\frac{1}{2}(1-\beta_{k})C_{A}\nu^{-1}M^{2}\|\nabla(u_{k}-u_{k-1})\|^{2}+\frac{1}{2}(1-\beta_{k})C_{A}\nu^{-1}M^{2}C_{k-2}^{-4}\|\nabla(\tilde{u}_{k-1}-\hat{u}_{k-2})\|^{4}, and the last two terms by \displaystyle(1-\beta_{k})C_{A}M\|\nabla(u_{k-1}-\hat{u}_{k-1})\|^{2}+(1-\beta_{k})C_{A}M\|\nabla(u_{k-2}-\hat{u}_{k-2})\|^{2} \displaystyle\leq \displaystyle(1-\beta_{k})C_{A}MC_{k-1}^{-2}\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}+(1-\beta_{k})C_{A}MC_{k-2}^{-2}\|\nabla(\tilde{u}_{k-1}-\hat{u}_{k-2})\|^{2}. Combining the above five inequalities, we obtain \displaystyle(1-\sigma)C_{k}^{-1}\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\| \displaystyle\leq \displaystyle\nu^{-1}MC_{k-1}^{-2}\left(\theta_{k}\beta_{k}\sigma+(1-\beta_{k})C_{A}\right)\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}+(1-\beta_{k})C_{A}\nu^{-1}MC_{k-2}^{-2}\|\nabla(\tilde{u}_{k-1}-\hat{u}_{k-2})\|^{2} \displaystyle+\mathcal{O}(\|\nabla(u_{k}-u_{k-1})\|^{2}+\|\nabla(u_{k-1}-u_{k-2})\|^{2})+(1-\beta_{k})\cdot\mathcal{O}\left(\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{4}+\|\nabla(\tilde{u}_{k-1}-\hat{u}_{k-2})\|^{4}\right). Applying Lemma 3.8 recursively to the fourth term yields \displaystyle\mathcal{O}(\|\nabla(u_{k}-u_{k-1})\|^{2}+\|\nabla(u_{k-1}-u_{k-2})\|^{2}) \displaystyle\leq \displaystyle\mathcal{O}(\|\nabla(u_{k-1}-u_{k-2})\|^{4}+\|\nabla(u_{k-2}-u_{k-3})\|^{4})+\sum\limits_{j=k-1}^{k}\mathcal{O}(\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{4}+\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{8}) \displaystyle\leq \displaystyle\cdots \displaystyle\leq \displaystyle\mathcal{O}(\|\nabla(u_{2}-u_{1})\|^{2^{k-1}}+\|\nabla(u_{1}-u_{0})\|^{2^{k-1}})+\text{ higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k} \displaystyle\leq \displaystyle\mathcal{O}(\|\nabla(u_{1}-u_{0})\|^{2^{k}}+\|\nabla(u_{1}-u_{0})\|^{2^{k-1}})+\text{ higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k}. Combining the previous two inequalities yields ( 3.20 ) and we complete the proof. 3.2 AAPicard-Newton m=2 In this subsection, we analyze the AAPicard-Newton method with m=2 . We add an additional previous residual term \tilde{u}_{k-1}-u_{k-2} in the Anderson optimization step (Step 2 of Algorithm 3.1 ). Although this modification retains the quadratic convergence order, it improves the convergence rate of the iterative method and may enlarge the domain of convergence. Similarly, we can add more previous residuals in the Anderson step to shrink the convergence rate further and possibly enlarge the domain of convergence. We will discuss the case m>2 in the following subsection. The algorithm of AAPicard-Newton method with depth m=2 is stated below. Algorithm 3.11 (AAPicard-Newton m=2 ) . The AAPicard-Newton iteration with m=2 consists of applying the composition of the Newton and Anderson accelerated Picard iteration for solving Navier-Stokes equations: g_{N}\circ g_{AP} , i.e., Step 1: Find \tilde{u}_{k+1}=g_{P}(u_{k}) by finding \tilde{u}_{k+1}\in V satisfying ( 3.1 ) for all v\in V . Step 2: For a selected damping factor 0<\beta_{k+1}\leq 1 , set \displaystyle\hat{u}_{k+1}= \displaystyle\beta_{k+1}\big((1-\alpha_{k+1}^{1}-\alpha_{k+1}^{2})\tilde{u}_{k+1}+\alpha_{k+1}^{1}\tilde{u}_{k}+\alpha_{k+1}^{2}\tilde{u}_{k-1}\big) \displaystyle+(1-\beta_{k+1})\big((1-\alpha_{k+1}^{1}-\alpha_{k+1}^{2})u_{k}+\alpha_{k+1}^{1}u_{k-1}+\alpha_{k+1}^{2}u_{k-2}\big) \displaystyle= \displaystyle(1-\alpha_{k+1}^{1}-\alpha_{k+1}^{2})\tilde{u}_{k+1}+\alpha_{k+1}^{1}\tilde{u}_{k}+\alpha_{k+1}^{2}\tilde{u}_{k-1}-(1-\beta_{k+1})w_{k+1,2}^{\alpha}, (3.24) where \alpha_{k+1}^{1},\alpha_{k+1}^{2} minimizes \displaystyle\|\nabla w_{k+1,2}^{\alpha}\|\coloneqq\left\|(1-\alpha_{k+1}^{1}-\alpha_{k+1}^{2})\nabla(\tilde{u}_{k+1}-u_{k})+\alpha_{k+1}^{1}\nabla(\tilde{u}_{k}-u_{k-1})+\alpha_{k+1}^{2}\nabla(\tilde{u}_{k-1}-u_{k-2})\right\|. (3.25) Step 3: Find u_{k+1}=g_{N}(\hat{u}_{k+1}) by finding u_{k+1}\in V satisfying ( 3.4 ) for all v\in V . Similarly, let \alpha_{k+1}^{1},\alpha_{k+1}^{2} minimize ( 3.25 ), we define the Anderson gain with m=2 as \displaystyle\theta_{k+1,2}= \displaystyle\frac{\|\nabla w_{k+1,2}^{\alpha}\|}{\|\nabla(\tilde{u}_{k+1}-u_{k})\|}. (3.26) Clearly, 0\leq\theta_{k+1,2}\leq 1 and \theta_{k+1,2}=1 if and only if \alpha_{k+1}^{1}=\alpha_{k+1}^{2}=0 , which implies Algorithm 3.11 is back to Algorithm 2.1 . Moreover, \alpha_{k+1}^{2}\neq 0 evinces \theta_{k+1,2}<\theta_{k+1}\leq 1 , where \theta_{k+1} is defined in ( 3.5 ). Otherwise, Algorithm 3.11 is back to either Algorithm 2.1 or Algorithm 3.1 . For the rest of this subsection, we always assume that \alpha_{k+1}^{2}\neq 0. Like Assumption 3.3 , we make an uniform bounded assumption for \{\alpha_{k+1}^{i}\} as below. Assumption 3.12 ( m=2 ) . There exists a constant C_{A}>0 such that for all k \displaystyle|1-\alpha_{k+1}^{1}-\alpha_{k+1}^{2}|+|\alpha_{k+1}^{1}|+|\alpha_{k+1}^{2}| \displaystyle\leq C_{A}, (3.27) Compared to Algorithm 3.1 , Step 1 and Step 3 from Algorithm 3.11 are unchanged. We assume that Assumption 3.5 holds in this subsection, and then the following results from the previous subsection are also satisfied here: Lemma 3.4 , equation ( 3.11 ), Remark 3.6 , and Lemma 3.7 . Nevertheless, we need to update equations ( 3.12 ), Lemma 3.8 as below. From ( 3.24 ), triangle inequality and followed by ( 3.8 ) and ( 3.26 ), we have \displaystyle\|\nabla(\hat{u}_{k}-\hat{u}_{k-1})\|\leq \displaystyle\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|+\sigma C_{A}\|\nabla(u_{k-1}-u_{k-2})\| \displaystyle+\sigma C_{A}\|\nabla(u_{k-2}-u_{k-3})\|+(1-\beta_{k})\theta_{k,2}\|\nabla(\tilde{u}_{k}-u_{k-1})\|. (3.28) Lemma 3.13 ( m=2 ) . Let Assumption 3.12 , 3.5 and \sigma C_{A}\max\{1,L\}<1 hold, then we have \displaystyle\|\nabla(u_{k+1}-u_{k})\|\leq \displaystyle\frac{8\nu^{-1}M\sigma^{2}C_{A}^{2}}{1-\sigma C_{A}\max\{1,L\}}\left(\|\nabla(u_{k}-u_{k-1})\|^{2}+\|\nabla(u_{k-1}-u_{k-2})\|^{2}\right) \displaystyle+\frac{\nu^{-1}M(C_{k}^{-2}+8)}{1-\sigma C_{A}\max\{1,L\}}\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{2}+\mathcal{O}(\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|^{4}). (3.29) The proof is similar to Lemma 3.8 except replacing inequality ( 3.12 ) by ( 3.28 ), and therefore omitted. Theorem 3.14 ( m=2 ) . Let \alpha_{k}^{2}\neq 0 , Assumptions 3.12 and 3.5 , and \sigma,\sigma C_{A}\max\{1,L\}<1 , we have \|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|\leq\frac{\nu^{-1}MC_{k-1}^{-2}C_{k}}{1-\sigma}\left(\beta_{k}\sigma\theta_{k,2}+(1-\beta_{k})C_{A}\right)\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}\\ +(1-\beta_{k})\frac{C_{A}\nu^{-1}M}{1-\sigma}\sum\limits_{j=k-2}^{k-1}(C_{j-1}^{-2}\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{2})\\ +\text{higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k}\text{ and }u_{1}-u_{0}, (3.30) where \theta_{k,2},C_{A},L are defined in ( 3.26 ), ( 3.27 ) and ( 3.10 ) respectively, and C_{k} are some constants independent of \nu,h . Remark 3.15 . Similar to Theorem 3.9 , Algorithm 3.11 converges quadratically, and \beta_{k+1}=1 optimizes the convergence and provides global stability of the solutions when \sigma,\sigma C_{A}<1 , and ( 3.30 ) reduces to \|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|\leq\frac{\nu^{-1}MC_{k-1}^{-2}C_{k}}{1-\sigma}\sigma\theta_{k,2}\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}\\ +\text{higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k}\text{ and }u_{1}-u_{0}. (3.31) From the inequality, we can tell that Algorithm 3.11 is superior to Algorithm 2.1 as \theta_{k,2}<1 when \alpha_{k}^{2}\neq 0 and Re large enough. Otherwise, the higher-order terms may be dominant and decelerate the convergence. Comparing ( 3.21 ) and ( 3.31 ), we conclude that Algorithm 3.11 is better than Algorithm 3.1 for large Reynolds numbers as \theta_{k,2}<\theta_{k}\leq 1 . Proof. From ( 3.24 ), we rewrite u_{k}-\hat{u}_{k} as \displaystyle u_{k}-\hat{u}_{k}= \displaystyle u_{k}-(1-\alpha_{k}^{1}-\alpha_{k}^{2})\tilde{u}_{k}-\alpha_{k}^{1}\tilde{u}_{k-1}-\alpha_{k}^{2}\tilde{u}_{k-2}+(1-\beta_{k})w_{k,2}^{\alpha}. (3.32) and would like to construct an equation of u_{k}-\hat{u}_{k} below. Adding equation (1-\alpha_{k}^{1}-\alpha_{k}^{2})\times ( 3.22 ) with j=k , \alpha_{k}^{1}\times ( 3.22 ) with j=k-1 , and \alpha_{k}^{2}\times ( 3.22 ) with j=k-2 , we obtain an equation of w_{k,2}^{\alpha} \nu(\nabla w_{k,2}^{\alpha},\nabla v)+b^{*}(u_{k-1},w_{k,2}^{\alpha},v)-\alpha_{k}^{1}b^{*}(u_{k-1}-u_{k-2},\tilde{u}_{k-1}-u_{k-2},v)\\ -\alpha_{k}^{2}b^{*}(u_{k-1}-u_{k-3},\tilde{u}_{k-2}-u_{k-3},v)+(1-\alpha_{k}^{1}-\alpha_{k}^{2})b^{*}(u_{k-1}-\hat{u}_{k-1},u_{k-1}-\hat{u}_{k-1},v)\\ +\alpha_{k}^{1}b^{*}(u_{k-2}-\hat{u}_{k-2},u_{k-2}-\hat{u}_{k-2},v)+\alpha_{k}^{2}b^{*}(u_{k-3}-\hat{u}_{k-3},u_{k-3}-\hat{u}_{k-3},v)=0. (3.33) Adding equation (1-\alpha_{k}^{1}-\alpha_{k}^{2})\times ( 3.1 ) with j=k , \alpha_{k}^{1}\times ( 3.1 ) with j=k-1 , and \alpha_{k}^{2}\times ( 3.1 ) with j=k-2 yields \nu(\nabla((1-\alpha_{k}^{1}-\alpha_{k}^{2})\tilde{u}_{k}+\alpha_{k}^{1}\tilde{u}_{k-1}+\alpha_{k}^{2}\tilde{u}_{k-2}),\nabla v)+b^{*}((1-\alpha_{k}^{1}-\alpha_{k}^{2})\tilde{u}_{k}+\alpha_{k}^{1}\tilde{u}_{k-1}+\alpha_{k}^{2}\tilde{u}_{k-2},\tilde{u}_{k},v)\\ -b^{*}(w_{k,2}^{\alpha},\tilde{u}_{k},v)-\alpha_{k}^{1}b^{*}(u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v)-\alpha_{k}^{2}b^{*}(u_{k-3},\tilde{u}_{k}-\tilde{u}_{k-2},v)=\langle f,v\rangle. Subtracting it from the sum of equation ( 3.4 ) with u_{k} and (1-\beta_{k})\times ( 3.33 ) produces an equation of u_{k}-\hat{u}_{k} \nu(\nabla(u_{k}-\hat{u}_{k}),\nabla v)=-b^{*}(\hat{u}_{k},u_{k}-\hat{u}_{k},v)-b^{*}(u_{k},\hat{u}_{k},v)+b^{*}((1-\alpha_{k}^{1}-\alpha_{k}^{2})\tilde{u}_{k}+\alpha_{k}^{1}\tilde{u}_{k-1}+\alpha_{k}^{2}\tilde{u}_{k-2},\tilde{u}_{k},v)\\ -b^{*}(w_{k,2}^{\alpha},\tilde{u}_{k},v)-\alpha_{k}^{1}b^{*}(u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v)-\alpha_{k}^{2}b^{*}(u_{k-3},\tilde{u}_{k}-\tilde{u}_{k-2},v)-(1-\beta_{k})b^{*}(u_{k-1},w_{k,2}^{\alpha},v)\\ +(1-\beta_{k})\alpha_{k}^{1}b^{*}(u_{k-1}-u_{k-2},\tilde{u}_{k-1}-u_{k-2},v)+(1-\beta_{k})\alpha_{k}^{2}b^{*}(u_{k-1}-u_{k-3},\tilde{u}_{k-2}-u_{k-3},v)\\ -(1-\beta_{k})(1-\alpha_{k}^{1}-\alpha_{k}^{2})b^{*}(u_{k-1}-\hat{u}_{k-1},u_{k-1}-\hat{u}_{k-1},v)-(1-\beta_{k})\alpha_{k}^{1}b^{*}(u_{k-2}-\hat{u}_{k-2},u_{k-2}-\hat{u}_{k-2},v)\\ -(1-\beta_{k})\alpha_{k}^{2}b^{*}(u_{k-3}-\hat{u}_{k-3},u_{k-3}-\hat{u}_{k-3},v). Combining the 3rd, 4th, 6th and 7th terms leads to \displaystyle-b^{*}(u_{k},\hat{u}_{k},v)+b^{*}((1-\alpha_{k}^{1}-\alpha_{k}^{2})\tilde{u}_{k}+\alpha_{k}^{1}\tilde{u}_{k-1}+\alpha_{k}^{2}\tilde{u}_{k-2},\tilde{u}_{k},v) \displaystyle-\alpha_{k}^{1}b^{*}(u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v)-\alpha_{k}^{2}b^{*}(u_{k-3},\tilde{u}_{k}-\tilde{u}_{k-2},v) \displaystyle= \displaystyle-b^{*}(u_{k}-\hat{u}_{k}-(1-\beta_{k})w_{k,2}^{\alpha},\tilde{u}_{k},v)-b^{*}(u_{k},\hat{u}_{k}-\tilde{u}_{k},v) \displaystyle-\alpha_{k}^{1}b^{*}(u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v)-\alpha_{k}^{2}b^{*}(u_{k-3},\tilde{u}_{k}-\tilde{u}_{k-2},v) \displaystyle= \displaystyle-b^{*}(u_{k}-\hat{u}_{k},\tilde{u}_{k},v)+(1-\beta_{k})b^{*}(w_{k,2}^{\alpha},\tilde{u}_{k},v)+(1-\beta_{k})b^{*}(u_{k},w_{k,2}^{\alpha},v) \displaystyle+\alpha_{k}^{1}b^{*}(u_{k}-u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v)+\alpha_{k}^{2}b^{*}(u_{k}-u_{k-3},\tilde{u}_{k}-\tilde{u}_{k-2},v), thanks to ( 3.24 ), and then update the equation of u_{k}-\hat{u}_{k} to \nu(\nabla(u_{k}-\hat{u}_{k}),\nabla v)=-b^{*}(\hat{u}_{k},u_{k}-\hat{u}_{k},v)-\beta_{k}b^{*}(w_{k,2}^{\alpha},\tilde{u}_{k},v)-b^{*}(u_{k}-\hat{u}_{k},\tilde{u}_{k},v)\\ +(1-\beta_{k})b^{*}(u_{k}-u_{k-1},w_{k,2}^{\alpha},v)+\alpha_{k}^{1}b^{*}(u_{k}-u_{k-2},\tilde{u}_{k}-\tilde{u}_{k-1},v)+\alpha_{k}^{2}b^{*}(u_{k}-u_{k-3},\tilde{u}_{k}-\tilde{u}_{k-2},v)\\ +(1-\beta_{k})\alpha_{k}^{1}b^{*}(u_{k-1}-u_{k-2},\tilde{u}_{k-1}-u_{k-2},v)+(1-\beta_{k})\alpha_{k}^{2}b^{*}(u_{k-1}-u_{k-3},\tilde{u}_{k-2}-u_{k-3},v)\\ -(1-\beta_{k})(1-\alpha_{k}^{1}-\alpha_{k}^{2})b^{*}(u_{k-1}-\hat{u}_{k-1},u_{k-1}-\hat{u}_{k-1},v)-(1-\beta_{k})\alpha_{k}^{1}b^{*}(u_{k-2}-\hat{u}_{k-2},u_{k-2}-\hat{u}_{k-2},v)\\ -(1-\beta_{k})\alpha_{k}^{2}b^{*}(u_{k-3}-\hat{u}_{k-3},u_{k-3}-\hat{u}_{k-3},v). Setting v=u_{k}-\hat{u}_{k} eliminate the second term. Applying ( 2.5 ), ( 3.27 ), Lemma 3.4 and ( 3.26 ) gives \displaystyle\nu(1-\sigma)\|\nabla(u_{k}-\hat{u}_{k})\| \displaystyle\leq \displaystyle\beta_{k}\nu\sigma\theta_{k,2}\|\nabla(\tilde{u}_{k}-u_{k-1})\|+(1-\beta_{k})M\|\nabla(u_{k}-u_{k-1})\|\cdot\theta_{k,2}\|\nabla(\tilde{u}_{k}-u_{k-1})\| \displaystyle+C_{A}M\|\nabla(u_{k}-u_{k-2})\|\cdot\sigma\|\nabla(u_{k-1}-u_{k-2})\|+C_{A}M\|\nabla(u_{k}-u_{k-3})\|\cdot\sigma\|\nabla(u_{k-1}-u_{k-3})\| \displaystyle+(1-\beta_{k})C_{A}M\|\nabla(u_{k-1}-u_{k-2})\|\|\nabla(\tilde{u}_{k-1}-u_{k-2})\| \displaystyle+(1-\beta_{k})C_{A}M\|\nabla(u_{k-1}-u_{k-3})\|\|\nabla(\tilde{u}_{k-2}-u_{k-3})\|+(1-\beta_{k})C_{A}M\sum\limits_{j=k-3}^{k-1}\|\nabla(u_{j}-\hat{u}_{j})\|^{2}. Utilizing triangle inequality, (a+b)^{2}\leq 2(a^{2}+b^{2}) and 2ab\leq a^{2}+b^{2} , we bound the RHS term-wisely as below \displaystyle C_{A}M\|\nabla(u_{k}-u_{k-2})\|\cdot\sigma\|\nabla(u_{k-1}-u_{k-2})\| \displaystyle\leq \displaystyle\sigma C_{A}M\left(\|\nabla(u_{k}-u_{k-1})\|\|\nabla(u_{k-1}-u_{k-2})\|+\|\nabla(u_{k-1}-u_{k-2})\|^{2}\right) \displaystyle\leq \displaystyle\frac{3}{2}\sigma C_{A}M\|\nabla(u_{k-1}-u_{k-2})\|^{2}+\frac{1}{2}\sigma C_{A}M\|\nabla(u_{k}-u_{k-1})\|^{2}, and \displaystyle C_{A}M\|\nabla(u_{k}-u_{k-3})\|\cdot\sigma\|\nabla(u_{k-1}-u_{k-3})\| \displaystyle\leq \displaystyle\sigma C_{A}M\left(\|\nabla(u_{k}-u_{k-1})\|\cdot\|\nabla(u_{k-1}-u_{k-3})\|+\|\nabla(u_{k-1}-u_{k-3})\|^{2}\right) \displaystyle\leq \displaystyle\frac{3}{2}\sigma C_{A}M(\|\nabla(u_{k-1}-u_{k-2})\|+\|\nabla(u_{k-2}-u_{k-3})\|)^{2}+\frac{1}{2}\sigma C_{A}M\|\nabla(u_{k}-u_{k-1})\|^{2} \displaystyle\leq \displaystyle 3\sigma C_{A}M\|\nabla(u_{k-2}-u_{k-3})\|^{2}+3\sigma C_{A}M\|\nabla(u_{k-1}-u_{k-2})\|^{2}+\frac{1}{2}\sigma C_{A}M\|\nabla(u_{k}-u_{k-1})\|^{2}. Now using Lemma 3.7 , we have the following bounds \displaystyle\beta_{k}\nu\sigma\theta_{k,2}\|\nabla(\tilde{u}_{k}-u_{k-1})\|+(1-\beta_{k})M\|\nabla(u_{k}-u_{k-1})\|\cdot\theta_{k,2}\|\nabla(\tilde{u}_{k}-u_{k-1})\| \displaystyle\leq \displaystyle\beta_{k}\sigma MC_{k-1}^{-2}\theta_{k,2}\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}+\frac{1}{2}(1-\beta_{k})\nu M^{2}C_{k-1}^{-2}\theta_{k,2}\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{4}+\mathcal{O}(\|\nabla(u_{k}-u_{k-1})\|^{2}), \displaystyle(1-\beta_{k})C_{A}M\|\nabla(u_{k-1}-u_{k-2})\|\|\nabla(\tilde{u}_{k-1}-u_{k-2})\| \displaystyle\leq \displaystyle(1-\beta_{k})C_{A}\nu^{-1}M^{2}C_{k-2}^{-2}\|\nabla(u_{k-1}-u_{k-2})\|\|\nabla(\tilde{u}_{k-1}-\hat{u}_{k-2})\|^{2} \displaystyle\leq \displaystyle\mathcal{O}(\|\nabla(u_{k-1}-u_{k-2})\|^{2}+\|\nabla(\tilde{u}_{k-1}-\hat{u}_{k-2})\|^{4}), \displaystyle(1-\beta_{k})C_{A}M\|\nabla(u_{k-1}-u_{k-3})\|\|\nabla(\tilde{u}_{k-2}-u_{k-3})\| \displaystyle\leq \displaystyle(1-\beta_{k})C_{A}M\|\nabla(u_{k-1}-u_{k-3})\|\cdot\nu^{-1}MC_{k-3}^{-2}\|\nabla(\tilde{u}_{k-2}-\hat{u}_{k-3})\|^{2} \displaystyle\leq \displaystyle(1-\beta_{k})C_{A}\nu^{-1}M^{2}C_{k-3}^{-2}(\|\nabla(u_{k-1}-u_{k-2})\|+\|\nabla(u_{k-2}-u_{k-3})\|)^{2}+\mathcal{O}(\|\nabla(\tilde{u}_{k-2}-\hat{u}_{k-3})\|^{4}) \displaystyle\leq \displaystyle\mathcal{O}(\|\nabla(u_{k-1}-u_{k-2})\|^{2}+\|\nabla(u_{k-2}-u_{k-3})\|^{2})+\mathcal{O}(\|\nabla(\tilde{u}_{k-2}-\hat{u}_{k-3})\|^{4}), and \displaystyle(1-\beta_{k})C_{A}M\sum\limits_{j=k-3}^{k-1}\|\nabla(u_{j}-\hat{u}_{j})\|^{2}\leq(1-\beta_{k})C_{A}M\sum\limits_{j=k-3}^{k-1}C_{j}^{-2}\|\nabla(\tilde{u}_{j+1}-\hat{u}_{j})\|^{2}. Combining the above seven inequalities, we obtain \nu(1-\sigma)C_{k}^{-1}\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|\leq MC_{k-1}^{-2}\left(\beta_{k}\sigma\theta_{k,2}+(1-\beta_{k})C_{A}\right)\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}\\ +(1-\beta_{k})C_{A}M\sum\limits_{j=k-2}^{k-1}(C_{j-1}^{-2}\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{2})+\sum\limits_{j=k-2}^{k}\mathcal{O}(\|\nabla(u_{j}-u_{j-1})\|^{2})+\sum\limits_{j=k-2}^{k}\mathcal{O}(\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{4}). Applying Lemma 3.13 recursively to the fourth term produces \displaystyle\sum\limits_{j=k-2}^{k}\mathcal{O}(\|\nabla(u_{j}-u_{j-1})\|^{2}) \displaystyle\leq \displaystyle\sum\limits_{j=k-3}^{k-1}\mathcal{O}(\|\nabla(u_{j}-u_{j-1})\|^{4})+\sum\limits_{j=k-2}^{k}\mathcal{O}(\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{4}+\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{8}) \displaystyle\leq \displaystyle\sum\limits_{j=k-4}^{k-2}\mathcal{O}(\|\nabla(u_{j}-u_{j-1})\|^{2^{3}})+\sum\limits_{j=k-3}^{k-1}\mathcal{O}(\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{2^{3}}+\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{2^{4}}) \displaystyle+\sum\limits_{j=k-2}^{k}\mathcal{O}(\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{4}+\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{8}) \displaystyle\leq \displaystyle\cdots \displaystyle\leq \displaystyle\sum\limits_{j=1}^{3}\mathcal{O}(\|\nabla(u_{j}-u_{j-1})\|^{2^{k-2}})+\text{ higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k} \displaystyle\leq \displaystyle\sum\limits_{j=1}^{3}\mathcal{O}(\|\nabla(u_{1}-u_{0})\|^{2^{k-3+j}})+\text{ higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k}. Combining the previous two inequalities and then dividing both sides by \nu(1-\sigma)C_{k}^{-1} yields ( 3.30 ). We complete the proof. 3.3 AAPicard-Newton m>2 By adding more previous residual terms in the optimization step (Step 2 in Algorithm 3.1 , 3.11 ), we obtain the general AAPicard-Newton algorithm. Similar results can be obtained with additional analyses; thus, the proof is omitted here. Now we present the algorithm and general convergence result of the AAPicard-Newton method below. Algorithm 3.16 ( m=1,2,3,\dots ) . The AAPicard-Newton iteration with m=1,2,\dots consists of applying the composition of the Newton and Anderson accelerated Picard iteration for solving Navier-Stokes equations: g_{N}\circ g_{AP} , i.e., Step 1: Find \tilde{u}_{k+1}=g_{P}(u_{k}) by finding \tilde{u}_{k+1}\in V satisfying ( 3.1 ) for all v\in V . Step 2: For 0<\beta_{k+1}\leq 1, let m_{k}=\min\{k-1,m\} , and \hat{u}_{k+1}=\beta_{k+1}\left(\left(1-\sum\limits_{j=1}^{m_{k}}\alpha_{k+1}^{j}\right)\tilde{u}_{k+1}+\sum\limits_{j=1}^{m_{k}}\alpha_{k+1}^{j}\tilde{u}_{k+1-j}\right)\\ +(1-\beta_{k+1})\left(\left(1-\sum\limits_{j=1}^{m_{k}}\alpha_{k+1}^{j}\right)u_{k}+\sum\limits_{j=1}^{m_{k}}\alpha_{k+1}^{j}u_{k-j}\right)\\ =\left(1-\sum\limits_{j=1}^{m_{k}}\alpha_{k+1}^{j}\right)\tilde{u}_{k+1}+\sum\limits_{j=1}^{m_{k}}\alpha_{k+1}^{j}\tilde{u}_{k+1-j}-(1-\beta_{k+1})w_{k+1,m}^{\alpha}, where \alpha_{k+1}^{j} minimizes \displaystyle\|\nabla w_{k+1,m}^{\alpha}\|\coloneqq\left\|\left(1-\sum\limits_{j=1}^{m_{k}}\alpha_{k+1}^{j}\right)\nabla(\tilde{u}_{k+1}-u_{k})+\sum\limits_{j=1}^{m_{k}}\alpha_{k+1}^{j}\nabla(\tilde{u}_{k+1-j}-u_{k-j})\right\|. Step 3: Find u_{k+1}=g_{N}(\hat{u}_{k+1}) by finding u_{k+1}\in V satisfying ( 3.4 ) for all v\in V . Clearly, Algorithm 3.16 reduces to a lower depth Anderson acceleration or Algorithm 2.1 if \alpha_{k+1}^{m_{k}}=0 . Let \alpha_{k+1}^{j} minimize \|\nabla w_{k+1,m}^{\alpha}\| and define \displaystyle\theta_{k+1,m}=\|\nabla w_{k+1,m}^{\alpha}\|/\|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|. (3.34) Thus \theta_{k+1,m}<1 if \alpha_{k+1}^{m_{k}}\neq 0. Furthermore, we assume \alpha_{k+1}^{j} satisfying the inequality \displaystyle\left|1-\sum\limits_{j=1}^{m_{k}}\alpha_{k+1}^{j}\right|+\sum\limits_{j=1}^{m_{k}}|\alpha_{k+1}^{j}|\leq C_{A}, (3.35) for some constant C_{A}>0. With similar analyses as above, we have the quadratic convergence of AAPicard-Newton method. Theorem 3.17 ( m=1,2,3,\dots, ) . Let \alpha_{k}^{m}\neq 0 , ( 3.35 ), Assumption 3.5 and \sigma C_{A}\max\{1,L\},\sigma<1 hold, then we have \|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|\leq\frac{\nu^{-1}MC_{k-1}^{-2}C_{k}}{1-\sigma}\left(\beta_{k}\sigma\theta_{k,m}+(1-\beta_{k})C_{A}\right)\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}\\ +(1-\beta_{k})\frac{C_{A}\nu^{-1}M}{1-\sigma}\sum\limits_{j=k-m}^{k-1}(C_{j-1}^{-2}\|\nabla(\tilde{u}_{j}-\hat{u}_{j-1})\|^{2})\\ +\text{higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k}\text{ and }u_{1}-u_{0}, (3.36) where \theta_{k,m},C_{A},L are defined in ( 3.34 ), ( 3.35 ) and ( 3.10 ) respectively, and C_{k} are some constants independent of \nu,h . Remark 3.18 . Likewise before, AAPicard-Newton method converges quadratically and \beta_{k+1}=1 optimizes the convergence and provides global stability when \sigma,\sigma C_{A}<1 . Reducing ( 3.36 ) to \|\nabla(\tilde{u}_{k+1}-\hat{u}_{k})\|\leq\frac{\nu^{-1}MC_{k-1}^{-2}C_{k}}{1-\sigma}\sigma\theta_{k,m}\|\nabla(\tilde{u}_{k}-\hat{u}_{k-1})\|^{2}\\ +\text{higher order terms of }\{\tilde{u}_{j}-\hat{u}_{j-1}\}_{j=2}^{k}\text{ and }u_{1}-u_{0}, (3.37) we found that Algorithm 3.16 is superior to the Picard-Newton method and AAPicard-Newton methods with smaller depth l(