Incremental Unknowns in Finite Differences: Condition Number of the Matrix

The utilization of incremental unknowns (IU) with multilevel finite differences was proposed in [R. Temam, SIAM J. Math. Anal., 21 (1991), pp. 154–178] for the integration of elliptic partial differential equations, instead of the usual nodal unknowns. Although turbulence and nonlinear problems were the primary motivations, it appears that the IU method is also interesting for linear problems. For such problems it was shown in [M. Chen and R. Temam, Nmmer. Math., 59 (1991), pp. 255–271] that the incremental unknown method which is very easy to program is also very efficient, in fact, it is comparable to the classical V-cycle multigrid method. In this article the condition number of the five-points discretization matrix in space dimension two for the Dirichlet problem is analyzed; more general second-order elliptic boundary value problems are also considered. It is shown that the condition number is $O( ( \log h )^2 )$ where h is the mesh size instead of $O( 1/h^2 )$ with the usual nodal unknowns. This gives a theoretical justification of the efficiency of the method since the number of operations needed to solve the linear system by the conjugate gradient methods is $O( \sqrt{k} )$, where $\kappa$ is the condition number of the matrix.