The utilization of incremental unknowns (IU in short) with multilevel finite differences was proposed by R.Temam in [13] for the integration of elliptic partial differential equations, instead of the usual nodal unknowns. The idea, which stems from dynamical systems approach, consists in writing the approximate solution $u_{i}$ in the form $u_{i}=y_{i}+z_{i}$, where $z$ is a small increment. Passing from the nodal unknowns $u_{i}$ to the IUs $\left(y_{i},z_{i}\right)$ amounts to a linear change of variables, that is to say, in the language of linear algebra to the construction of a preconditioner. Many numerical simulations have shown the efficiency of such induced preconditioners.

Report issue for preceding element

The incremental unknowns play the role of the small structures. Unfortunately they are not always "small", in certain practical cases. Indeed this situation arises typically when the number of points is not large enough and the discretized function has strong gradients (this is the case of convection diffusion problems). A small step size (or a large number of grid points) can be a limitation for practical applications since the dimension of the system will be increased artificially. The use of high-order schemes can be a solution to the above problem. Exist two main classes of high-order schemes: explicit schemes and compact schemes. Explicit schemes directly compute the numerical derivative by employing large computational stencils for accuracy. High-order schemes achieved in this manner always require non-compact stencils that utilize grid points located beyond those directly adjacent to the node about which the differences are taken. Compact scheme, proposed by Kreiss and Oliger[6] and which was later improved upon by Lele[7], use smaller stencils but requires a scalar tridiagonal or pentadiagonal matrix inversion. Another idea (proposed,

Report issue for preceding element

for convection diffusion problems, by MacKinnon, Carey, Johnson and Langerman [8],[9],[10],[11]) to obtain high-order compact schemes is to operate on the differential equation as an auxiliary relation to obtain expressions for higherorder derivatives in the truncation error. We will use this idea (also presented in [12]) to approximate the solution of the following (1D) convection-diffusion equation:

Report issue for preceding element

$$\left\{\begin{array}[]{c}-u^{\prime\prime}(x)+c(x)u^{\prime}(x)=f(x),x\in(0,1)\\ u(0)=u(1)=0\end{array}\right.$$

where $f\in L^{2}(0,1)$ and $c(x)\in L^{\infty}(0,1)$.
This equation often appears in the description of transport phenomena. The magnitude of $\mathrm{c}(\mathrm{x})$ determines the ratio of the convection to diffusion. Of course the 1D problems are not difficult from a computational point of view; we consider them because the algebra is more transparent than for higher dimensions.

Report issue for preceding element

Numerical solution of a problem such as (1) using Incremental Unknowns has been considered in [3] and [4] but the IUs that have been used in these articles were connected to the second derivative only.

Report issue for preceding element

In [1], the authors propose a construction of IUs that are more adapted to the problem in the sense that they take into account and the convection term in the construction of the IUs.

Report issue for preceding element

We consider approximations to (1) on a uniform mesh $x_{i}=ih(h=1/2N$, $N$ a positive integer, $i=0,1,\ldots,2N)$ having the form

Report issue for preceding element

$$\beta_{i}\left(u_{i}-u_{i-1}\right)+\alpha_{i}\left(u_{i}-u_{i+1}\right)=hf_{i};i=1,\ldots,2N.$$

(2)

Here $u_{i}\simeq u\left(x_{i}\right),f_{i}=f\left(x_{i}\right)$ and $\alpha_{i}$ and $\beta_{i}$ are real numbers whose definition depends on the discretization scheme; we have indeed, for example the two following possibilities: the firs one consists in approaching the first derivative by a (centered type) three points scheme and the second one consists in using an uncentered type scheme for the approximation of $u^{\prime}$ at the grid points. For the moment we do not explicite the discretization scheme.

Report issue for preceding element

As usual when an IU method is implemented, two different kinds of unknowns must be distinguished: those associated with the coarse grid components and which are on $G_{c}$ (coarse grid), and whose indices are even and those associated with complementary points (odd indices) which are on $G_{f}\backslash G_{c}\left(G_{f}\right.$ is the fine grid),

Report issue for preceding element

$$.o\times o\times o\ldots o\times o.$$

Fig.1: $\Omega=(0,1),x$ : points in $G_{c},o:$ points in $G_{f}\backslash G_{c}$,
If we write the system (2) at the complementary points, we obtain

Report issue for preceding element

$$\left(\alpha_{2i+1}+\beta_{2i+1}\right)u_{2i+1}-\beta_{2i+1}u_{2i}-\alpha_{2i+1}u_{2i+2}=hf_{2i+1}$$

Hence, assuming that $\alpha_{2i+1}+\beta_{2i+1}\neq 0$, we have

Report issue for preceding element

$$u_{2i+1}=\frac{1}{\alpha_{2i+1}+\beta_{2i+1}}\left(\beta_{2i+1}u_{2i}+\alpha_{2i+1}u_{2i+2}\right)+\frac{1}{\alpha_{2i+1}+\beta_{2i+1}}hf_{2i+1}$$

We note that $u_{2i+1}$ is expressed as the sum of a convex combination of $u_{2i}$ and $u_{2i+2}$ which is nothing but a bilinear interpolation scheme, and a correction term whose order is connected to the order of the interpolation scheme. If we set

Report issue for preceding element

$$z_{2i+1}=u_{2i+1}-\frac{1}{\alpha_{2i+1}+\beta_{2i+1}}\left(\beta_{2i+1}u_{2i}+\alpha_{2i+1}u_{2i+2}\right)$$

(3)

then the system (1), at the complementary points, is reduced to

Report issue for preceding element

$$z_{2i+1}=\frac{1}{\alpha_{2i+1}+\beta_{2i+1}}hf_{2i+1}$$

The numbers $z_{2i+1}$ are the incremental unknowns attached to the (discrete) problem (2). They depend closely on the scheme used for the discretization.

Report issue for preceding element

We can obviously repeat recursively the process described above and if the coarsest grid is reduced to one point only, the preconditioned matrix becomes diagonal.

Report issue for preceding element

From the point of view of the matriceal framework, this construction can be summarized by the determination of two matrices $S$ and ${}^{t}T$ under and upper triangular respectively such that ${}^{t}TAS$ is bloc diagonal, A being the discretization matrix.

Report issue for preceding element

We first consider two grid levels. The discretization matrix $A$ is written with the hierarchical ordering (considering first the coarse grid unknowns and then the complementary ones) in the form

Report issue for preceding element

$$\widetilde{A}=\left(\begin{array}[]{ll}\Lambda_{1}&B_{1}\\ B_{2}&\Lambda_{2}\end{array}\right)$$

where $\Lambda_{i},i=1,2$ are invertible diagonal matrices.

Report issue for preceding element

We want to construct a matrix $S$ of the form:

Report issue for preceding element

$$S=\left(\begin{array}[]{rr}I&0\\ G_{1}&I\end{array}\right)$$

and such that $\widetilde{A}S$ is upper triangular. We have

Report issue for preceding element

$$\widetilde{A}S=\left(\begin{array}[]{ll}\Lambda_{1}&B_{1}\\ B_{2}&\Lambda_{2}\end{array}\right)\left(\begin{array}[]{rr}I&0\\ G_{1}&I\end{array}\right)=\left(\begin{array}[]{ll}\Lambda_{1}+B_{1}G_{1}&B_{1}\\ B_{2}+\Lambda_{2}G_{1}&\Lambda_{2}\end{array}\right)$$

Therefore the under-matrix $G_{1}$ satisfies $G_{1}=-\Lambda_{2}^{-1}B_{2}$, hence

Report issue for preceding element

$$S=\left(\begin{array}[]{rr}I&0\\ -\Lambda_{2}^{-1}B_{2}&I\end{array}\right)$$

We now want to construct a matrix ${}^{t}T$ of the form:

Report issue for preceding element

$${}^{t}T=\left(\begin{array}[]{rr}I&G_{2}\\ 0&I\end{array}\right)$$

and such that ${}^{t}T\widetilde{A}S$ is bloc diagonal. We have

Report issue for preceding element

$$\hat{A}={}^{t}T\tilde{A}S=\left(\begin{array}[]{rr}\Lambda_{1}+B_{1}G_{1}&B_{1}+G_{2}\Lambda_{2}\\ 0&\Lambda_{2}\end{array}\right)$$

and then $G_{2}$ must satisfy $B_{1}+G_{2}\Lambda_{2}=0$.
Thus

Report issue for preceding element

$${}^{t}T=\left(\begin{array}[]{rr}I&-B_{1}\Lambda_{2}^{-1}\\ 0&I\end{array}\right)$$

and then $\hat{A}$ can be written in the form

Report issue for preceding element

$$\hat{A}={}^{t}T\widetilde{A}S=\left(\begin{array}[]{rr}\Lambda_{1}+B_{1}G_{1}&0\\ 0&\Lambda_{2}\end{array}\right)$$

We note that since the linear system is non-symmetric, these IUs lead to a non-symmetric hierarchical preconditioner.

Report issue for preceding element

The first diagonal bloc of $\hat{A}$ is still tridiagonal and we can repeat recursively the reduction procedure described above by using $d$ levels of IUs.

Report issue for preceding element

We can obtain (see [1])a priori energy estimates that show that the (induced) IUs are indeed small structures as expected.

Report issue for preceding element

We multiply (2) by $\delta_{i}u_{i},\delta_{i}$ to be fixed later, and summing these expressions on all indices $i$, we obtain

Report issue for preceding element

$$\sum_{i=1}^{2N-1}\beta_{i}\delta_{i}\left(u_{i}-u_{i-1}\right)u_{i}-\sum_{i=1}^{2N-1}\alpha_{i}\delta_{i}\left(u_{i+1}-u_{i}\right)u_{i}=\sum_{i=1}^{2N-1}hf_{i}\delta_{i}u_{i}$$

Hence,

Report issue for preceding element

$$\sum_{i=0}^{2N-1}\left(\beta_{i+1}\delta_{i+1}u_{i+1}-\alpha_{i}\delta_{i}u_{i}\right)\left(u_{i+1}-u_{i}\right)=\sum_{i=1}^{2N-1}hf_{i}\delta_{i}u_{i}.$$

(4)

We now choose $\delta_{i}$ such that

Report issue for preceding element

$$\delta_{0}=1,\delta_{i+1}=\frac{\alpha_{i}}{\beta_{i+1}}\delta_{i}$$

and we make the following hypothesis [1]:
Hypothesis(H)
i. There exists two strictly positive real numbers $\alpha$ and $\beta$ such that

Report issue for preceding element

$$\alpha\leq\delta_{i}\leq\beta\forall i.$$

ii. $\alpha_{i}$ and $\beta_{i}$ are strictly positive numbers, $\forall i=0,\ldots,2N$.
iii. There exists a strictly positive real number $\gamma$ such that

Report issue for preceding element

$$\alpha_{i}\geq\frac{\gamma}{h}\forall i$$

We shall see later that (H) is not too restrictive for practical cases.
From (4) we infer

Report issue for preceding element

$$\sum_{i=0}^{2N-1}\alpha_{i}\delta_{i}\left(u_{i+1}-u_{i}\right)^{2}=\sum_{i=1}^{2N-1}hf_{i}\delta_{i}u_{i}$$

(5)

We recall the discrete Poincaré inequality (see e.g. [2]):
Lemma 1 Let $u_{i},i=0,\ldots,2N$ be a sequence of real numbers such that $u_{0}=u_{2N}=0$. Then we have

Report issue for preceding element

$$\sum_{i=1}^{2N-1}hu_{i}^{2}\leq\sum_{i=0}^{2N-1}\frac{1}{h}\left(u_{i+1}-u_{i}\right)^{2}$$

Using (H), Cauchy-Schwartz inequality and Poincaré inequality, we bound the right-hand side of (5) by

Report issue for preceding element

$$\sum_{i=1}^{2N-1}hf_{i}\delta_{i}u_{i}\leq\beta\sum_{i=1}^{2N-1}hf_{i}u_{i}\leq\beta\sqrt{\sum_{i=0}^{2N-1}hu_{i}^{2}}\sqrt{\sum_{i=1}^{2N-1}hf_{i}^{2}}\leq\beta\sqrt{\sum_{i=0}^{2N-1}\frac{1}{h}\left(u_{i+1}-u_{i}\right)^{2}}\sqrt{\sum_{i=1}^{2N-1}hf_{i}^{2}}$$

(6)

Also, using (H) we can bound the left-hand side of (5) by

Report issue for preceding element

$$\sum_{i=0}^{2N-1}\alpha_{i}\delta_{i}\left(u_{i+1}-u_{i}\right)^{2}\geq\alpha\sum_{i=0}^{2N-1}\alpha_{i}\left(u_{i+1}-u_{i}\right)^{2}\geq\alpha\gamma\sum_{i=0}^{2N-1}\frac{1}{h}\left(u_{i+1}-u_{i}\right)^{2}.$$

(7)

From (6) and (7) we have:

Report issue for preceding element

$$\sum_{i=0}^{2N-1}\frac{1}{h}\left(u_{i+1}-u_{i}\right)^{2}\leq\frac{\beta^{2}}{\alpha^{2}\gamma^{2}}\sum_{i=1}^{2N-1}hf_{i}^{2}$$

(8)

We now introduce the incremental unknowns defined by (3). Since

Report issue for preceding element

$$\sum_{i=0}^{2N-1}\frac{1}{h}\left(u_{i+1}-u_{i}\right)^{2}=\sum_{i=0}^{N-1}\frac{1}{h}\left(u_{2i+1}-u_{2i}\right)^{2}+\sum_{i=0}^{N-1}\frac{1}{h}\left(u_{2i+2}-u_{2i+1}\right)^{2}$$

we find, setting $y_{2i}=u_{2i}$

Report issue for preceding element

$$\sum_{i=0}^{N-1}\frac{1}{h}\left(z_{2i+1}+\frac{1}{\alpha_{2i+1}+\beta_{2i+1}}\left(\beta_{2i+1}y_{2i}+\alpha_{2i+1}y_{2i+2}\right)-y_{2i}\right)^{2}$$

$$+\sum_{i=0}^{N-1}\frac{1}{h}\left(y_{2i+2}-z_{2i+1}-\frac{1}{\alpha_{2i+1}+\beta_{2i+1}}\left(\beta_{2i+1}y_{2i}+\alpha_{2i+1}y_{2i+2}\right)\right)^{2}\leq\frac{\beta^{2}}{\alpha^{2}\gamma^{2}}\sum_{i=1}^{2N-1}hf_{i}^{2}$$

which yields

Report issue for preceding element

$$\begin{gathered}\sum_{i=0}^{N-1}\left(z_{2i+1}+\frac{\alpha_{2i+1}}{\alpha_{2i+1}+\beta_{2i+1}}\left(y_{2i+2}-y_{2i}\right)\right)^{2}+\\ +\sum_{i=0}^{N-1}\left(z_{2i+1}-\frac{\beta_{2i+1}}{\alpha_{2i+1}+\beta_{2i+1}}\left(y_{2i+2}-y_{2i}\right)\right)^{2}\leq\frac{\beta^{2}}{\alpha^{2}\gamma^{2}}\sum_{i=1}^{2N-1}h^{2}f_{i}^{2}\end{gathered}$$

Replacing $f_{i}=f\left(x_{i}\right)$ by $f_{i}=\frac{1}{2h}\int_{x_{i-1}}^{x_{i+1}}f(x)dx$ and using Hölder inequality we

Report issue for preceding element

$$\begin{gathered}\sum_{i=0}^{N-1}\left(z_{2i+1}+\frac{\alpha_{2i+1}}{\alpha_{2i+1}+\beta_{2i+1}}\left(y_{2i+2}-y_{2i}\right)\right)^{2}+\\ +\sum_{i=0}^{N-1}\left(z_{2i+1}-\frac{\beta_{2i+1}}{\alpha_{2i+1}+\beta_{2i+1}}\left(y_{2i+2}-y_{2i}\right)\right)^{2}\leq\frac{\beta^{2}}{4\alpha^{2}\gamma^{2}}\sum_{i=1}^{2N-1}\left[\int_{x_{i-1}}^{x_{i+1}}f(x)dx\right]^{2}\leq\\ \leq\frac{\beta^{2}}{4\alpha^{2}\gamma^{2}}\sum_{i=1}^{2N-1}\left(\int_{x_{i-1}}^{x_{i+1}}f^{2}(x)dx\right)\left(\int_{x_{i-1}}^{x_{i+1}}dx\right)=\frac{\beta^{2}}{2\alpha^{2}\gamma^{2}}h\sum_{i=1}^{2N-1}\left(\int_{x_{i-1}}^{x_{i+1}}f^{2}(x)dx\right)\leq\frac{\beta^{2}}{\alpha^{2}\gamma^{2}}h\|f\|^{2}\end{gathered}$$

where $\|f\|=|f|_{L^{2}(0,1)}$.
We now develop the left-hand side of this inequality and we obtain:

Report issue for preceding element

$$A=2\sum_{i=0}^{N-1}z_{2i+1}^{2}+\sum_{i=0}^{N-1}\frac{\alpha_{2i+1}^{2}+\beta_{2i+1}^{2}}{\left(\alpha_{2i+1}+\beta_{2i+1}\right)^{2}}\left(y_{2i+2}-y_{2i}\right)^{2}+2\sum_{i=0}^{N-1}\frac{\alpha_{2i+1}-\beta_{2i+1}}{\alpha_{2i+1}+\beta_{2i+1}}z_{2i+1}\left(y_{2i+2}-y_{2i}\right).$$

Using Young inequality, we then find

Report issue for preceding element

$$2\sum_{i=0}^{N-1}\frac{\alpha_{2i+1}-\beta_{2i+1}}{\alpha_{2i+1}+\beta_{2i+1}}z_{2i+1}\left(y_{2i+2}-y_{2i}\right)\geq-\varepsilon\sum_{i=0}^{N-1}z_{2i+1}^{2}-\frac{1}{\varepsilon}\sum_{i=0}^{N-1}\frac{\left(\alpha_{2i+1}-\beta_{2i+1}\right)^{2}}{\left(\alpha_{2i+1}+\beta_{2i+1}\right)^{2}}\left(y_{2i+2}-y_{2i}\right)^{2}.$$

Here $\varepsilon$ is a strictly positive real number which will be fixed later. Hence

Report issue for preceding element

$$A\geq(2-\varepsilon)\sum_{i=0}^{N-1}z_{2i+1}^{2}+\sum_{i=0}^{N-1}\left(\frac{\alpha_{2i+1}^{2}+\beta_{2i+1}^{2}}{\left(\alpha_{2i+1}+\beta_{2i+1}\right)^{2}}-\frac{1}{\varepsilon}\frac{\left(\alpha_{2i+1}-\beta_{2i+1}\right)^{2}}{\left(\alpha_{2i+1}+\beta_{2i+1}\right)^{2}}\right)\left(y_{2i+2}-y_{2i}\right)^{2}$$

Since $\alpha_{i}>0$ and $\beta_{i}>0,\forall i$, we have

Report issue for preceding element

$$\frac{1}{\left(\alpha_{2i+1}+\beta_{2i+1}\right)^{2}}\left(\alpha_{2i+1}^{2}+\beta_{2i+1}^{2}-\frac{1}{\varepsilon}\left(\alpha_{2i+1}-\beta_{2i+1}\right)^{2}\right)\geq\left(1-\frac{1}{\varepsilon}\right)\frac{\alpha_{2i+1}^{2}+\beta_{2i+1}^{2}}{\left(\alpha_{2i+1}+\beta_{2i+1}\right)^{2}}.$$

We set $\xi_{i}=\frac{\alpha_{i}}{\beta_{i}}$ and we introduce the function $\phi(\xi)=\frac{1+\xi^{2}}{(1+\xi)^{2}}$ for $\xi>0$. It is easy to check that $\phi(\xi)\geq\frac{1}{2},\forall\xi>0$. Hence

Report issue for preceding element

$$\frac{\alpha_{2i+1}^{2}+\beta_{2i+1}^{2}}{\left(\alpha_{2i+1}+\beta_{2i+1}\right)^{2}}=\phi\left(\xi_{2i+1}\right)\geq\frac{1}{2},\forall i=0,\ldots,N$$

and we then have

Report issue for preceding element

$$\frac{1}{\left(\alpha_{2i+1}+\beta_{2i+1}\right)^{2}}\left(\alpha_{2i+1}^{2}+\beta_{2i+1}^{2}-\frac{1}{\varepsilon}\left(\alpha_{2i+1}-\beta_{2i+1}\right)^{2}\right)\geq\frac{1}{2}\left(1-\frac{1}{\varepsilon}\right).$$

Thus, taking $\varepsilon=\frac{3}{2}$, we obtain, after some simplifications

Report issue for preceding element

$$A\geq\frac{1}{6}\sum_{i=0}^{N-1}z_{2i+1}^{2}+\frac{1}{6}\sum_{i=0}^{N-1}\left(y_{2i+2}-y_{2i}\right)^{2}$$

We have then the following result:
Proposition 2 [1]Under the hypothesis $(H)$, the incremental unknowns defined by (3) satisfy the following a priori estimates:

Report issue for preceding element

$$\begin{gathered}\sum_{i=0}^{N-1}z_{2i+1}^{2}\leq\frac{6\beta^{2}}{\alpha^{2}\beta^{2}}h\\ \sum_{i=0}^{N-1}\left(y_{2i+2}-y_{2i}\right)^{2}\leq\frac{6\beta^{2}}{\alpha^{2}\beta^{2}}h.\end{gathered}$$

Proposition is valid for general definition of the IUs given in (3), under Hypothesis (H). In particular, the scheme used for the discretization of the convective term is not specified.
i. Centered Convection-Diffusion IUs

Report issue for preceding element

We have

Report issue for preceding element

$$\alpha_{i}=\frac{1}{h}\left(1-\frac{c_{i}h}{2}\right),\beta_{i}=\frac{1}{h}\left(1+\frac{c_{i}h}{2}\right).$$

Hence, if there exists a strictly positive real number $\gamma$ such that

Report issue for preceding element

$$1-\max_{i}\frac{\left|c_{i}\right|h}{2}\geq\gamma$$

then the asumptions i., ii. and iii. of (H) are satisfied. This condition can be satisfied by taking $h$ small enough.
ii. Uncentered Convection-Diffusion IUs

Report issue for preceding element

• •

  If $c_{i}\geq 0$ then

  Report issue for preceding element

$$\alpha_{i}=\alpha_{i}^{+}=\frac{1}{h},\quad\beta_{i}=\beta_{i}^{+}=\frac{1}{h}+c_{i}.$$

Hence, $\alpha_{i}$ and $\beta_{i}$ are stricly positive real numbers.

Report issue for preceding element

• •

  If $c_{i}\leq 0$ then

  Report issue for preceding element

$$\alpha_{i}=\alpha_{i}^{-}=\frac{1}{h}-c_{i},\quad\beta_{i}=\beta_{i}^{-}=\frac{1}{h}$$

Here again, $\alpha_{i}$ and $\beta_{i}$ are strictly positive real numbers.
In conclusion, and without any asumption, the asumptions i., ii. and iii. of (H) are satisfied.

Report issue for preceding element

The real advantage of (HOC) lies not in the increased accuracy (although this is sometimes important), but rather in the fact that problems requiring fine grid can be solved on coarse grids. This implies that less memory and thus less time is required to solve the same problem to the same accuracy. Since "time is money", (HOC) schemes directly reduce the expense of approximating a differential equation numerically.

Report issue for preceding element

High-order compact (HOC) schemes of the type studied here increase the accuracy of the standard central difference approximation from $O\left(h^{2}\right)$ to $O\left(h^{4}\right)$ by including compact approximation to the leading truncation error terms. The idea is to operate on the differential equation as an auxiliary relation to obtain expressions for higher-order derivatives in the truncation error.

Report issue for preceding element

We define $\delta_{x}^{n}u_{i},n=1,2$ to be the standard central difference operator for the $n$ - th derivative of $u$ at point $i$ on a uniform grid of mesh size $h$,

Report issue for preceding element

$$\delta_{x}u_{i}=\frac{u_{i+1}-u_{i-1}}{2h},\delta_{x}^{2}u_{i}=\frac{u_{i+1}-2u_{i}+u_{i-1}}{h^{2}}$$

Central differencing (1) yields

Report issue for preceding element

$$-\delta_{x}^{2}u_{i}+c_{i}\delta_{x}u_{i}-\tau_{i}=f_{i}$$

(9)

where $\tau_{i}$ is the local truncation error at node $i$,

Report issue for preceding element

$$\tau_{i}=\frac{h^{2}}{12}\left[2c\frac{d^{3}u}{dx^{3}}-\frac{d^{4}u}{dx^{4}}\right]_{i}+O\left(h^{4}\right)$$

(10)

We seek to approximate the leading term in (10) and include it in the difference formulation to yield an $O\left(h^{4}\right)$ method. Assuming the solution is sufficiently regular, we may accomplish this by differentiating (1) to yield

Report issue for preceding element

$$\left.\frac{d^{3}u}{dx^{3}}\right|_{i}=\left[c\frac{d^{2}u}{dx^{2}}+\frac{dc}{dx}\frac{du}{dx}-\frac{df}{dx}\right]_{i}$$

which can be approximated compactly as

Report issue for preceding element

$$\left.\frac{d^{3}u}{dx^{3}}\right|_{i}=c_{i}\delta_{x}^{2}u_{i}+\delta_{x}c_{i}\delta_{x}u_{i}-\delta_{x}f_{i}+O\left(h^{2}\right)$$

(11)

and similarly

Report issue for preceding element

	$$\displaystyle\left.\frac{d^{4}u}{dx^{4}}\right|_{i}=\left[c\frac{d^{3}u}{dx^{3}}+2\frac{dc}{dx}\frac{d^{2}u}{dx^{2}}+\frac{d^{2}c}{dx^{2}}\frac{du}{dx}-\frac{d^{2}f}{dx^{2}}\right]_{i}$$		(12)
	$$\displaystyle=\left.c_{i}\frac{d^{3}u}{dx^{3}}\right|_{i}+2\delta_{x}c_{i}\delta_{x}^{2}u_{i}+\delta_{x}^{2}c_{i}\delta_{x}c_{i}-\delta_{x}^{2}f_{i}+O\left(h^{2}\right)$$

Relations (11) and (12) can be combined with (10) to yield the new truncation error expression:

Report issue for preceding element

$$\tau_{i}=\frac{h^{2}}{12}\left[\left(c_{i}^{2}-2\delta_{x}c_{i}\right)\delta_{x}^{2}u_{i}+\left(c_{i}\delta_{x}c_{i}-\delta_{x}^{2}c_{i}\right)\delta_{x}u_{i}-c_{i}\delta_{x}f_{i}+\delta_{x}^{2}f_{i}\right]+O\left(h^{4}\right)$$

which can be use to increase the accuracy of the approximation scheme. The resulting high-order compact scheme is

Report issue for preceding element

$$-A_{i}\delta_{x}^{2}u_{i}+C_{i}\delta_{x}u_{i}=F_{i}+O\left(h^{4}\right)$$

(13)

where

Report issue for preceding element

	$$\displaystyle A_{i}=1+\frac{h^{2}}{12}\left(c_{i}^{2}-2\delta_{x}c_{i}\right)$$		(14)
	$$\displaystyle C_{i}=c_{i}+\frac{h^{2}}{12}\left(\delta_{x}^{2}c_{i}-c_{i}\delta_{x}c_{i}\right)$$		(15)
	$$\displaystyle F_{i}=f_{i}+\frac{h^{2}}{12}\left(\delta_{x}^{2}f_{i}-c_{i}\delta_{x}f_{i}\right)$$		(16)

We can write (13) in the form (2) where:

Report issue for preceding element

$$\alpha_{i}=\frac{A_{i}}{h}-\frac{C_{i}}{2},\beta_{i}=\frac{A_{i}}{h}+\frac{C_{i}}{2},f_{i}:=F_{i}\text{ for }i=1,\ldots,2N$$

and we can define IU in this case. If we consider 1D convection diffusion problem with constant coefficients then:

Report issue for preceding element

$$A_{i}=1+\frac{h^{2}c^{2}}{12},C_{i}=c\text{ and }F_{i}=f_{i}\text{ for }i=1,\ldots,2N$$

In this case we can see that, without any asumptions, the hypothesis (H) are satisfied.

Report issue for preceding element

The condition number is defined by

Report issue for preceding element

$$\kappa=\frac{\max\left|\lambda_{k}\right|}{\min\left|\lambda_{k}\right|}$$

(17)

where $\left\{\lambda_{k}\right\}$ is the set of eigenvalues of the real matrix we wish to solve.
The tridiagonal matrices generated by compact 1D numerical schemes lend themselves to theoretical eigenvalue analysis, and our hope is that we can draw some conclusions from such analysis that might apply to higher dimensions.

Report issue for preceding element

We will consider 1D convection diffusion problem with constant coefficients. For a tridiagonal Toeplitz matrix which has the form

Report issue for preceding element

$$T_{N}(c,d,e)=\left(\begin{array}[]{cccccc}d&e&&&&\\ c&d&\cdot&&&\\ &\cdot&\cdot&\cdot&&\\ &&\cdot&\cdot&\cdot&\\ &&&\cdot&\cdot&e\\ &&&&c&d\end{array}\right)$$

the eigenvalues are known explicitly (see [5]),

Report issue for preceding element

$$d+2(ce)^{1/2}\cos(k\pi/(N+1)),k=1,\ldots,N$$

Using this result, we can obtain condition number for each of the 3 schemes (see [12]):

Report issue for preceding element

	$$\displaystyle\kappa_{HOC}=\frac{c^{2}h^{2}+12+\sqrt{\left(c^{2}h^{2}+6ch+12\right)\left(c^{2}h^{2}-6ch+12\right)}}{c^{2}h^{2}+12-\sqrt{\left(c^{2}h^{2}+6ch+12\right)\left(c^{2}h^{2}-6ch+12\right)}},$$		(18)
	$$\displaystyle\kappa_{CDS}=\left\{\begin{array}[]{c}\frac{2+\sqrt{4-c^{2}h^{2}}}{2+\sqrt{4-c^{2}h^{2}}},|ch|\leq 2\\ \frac{|c|}{2},|ch|>2\end{array},\right.$$		(19)
	$$\displaystyle\kappa_{CDS}=\left\{\begin{array}[]{c}\frac{2+\sqrt{4-c^{2}h^{2}}}{2+\sqrt{4-c^{2}h^{2}}},|ch|\leq 2\\ \frac{|c|}{2},|ch|>2\end{array},\right.$$		(19)
	$$\displaystyle\kappa_{UDS}=\frac{|ch|+2+\sqrt{|ch|+2}}{|ch|+2-\sqrt{|ch|+2}}$$		(20)

For HOC scheme, as $ch\rightarrow 0$, the condition number behaves as $c^{-2}h^{-2}$ and for large $ch$, the condition number behaves as $c^{2}h^{2}$. This means that for large $N$ and $|ch|$ very large or very small, the condition number is extremely large and may pose some difficulty for an iterative solver. This is one instance where CDS and UDS appear to compare favorably with HOC, except of course for the fact that for $ch>2$, CDS is oscillatory and for large $ch$, the UDS models an overly diffusive problem.

Report issue for preceding element

Introducing IU, after using all the levels (what means $L$ if $h=\frac{1}{2^{L}}$ ) we will obtain a diagonal matrix which have the elements,

Report issue for preceding element

$$\alpha_{1}=\frac{c^{2}h^{2}+12}{6h^{2}},\alpha_{n}=\frac{\left(\frac{c^{2}h^{2}+6ch+12}{12h^{2}}\right)^{2^{n-1}}+\left(\frac{c^{2}h^{2}-6ch+12}{12h^{2}}\right)^{2^{n-1}}}{\prod_{i=0}^{n-2}\left[\left(\frac{c^{2}h^{2}+6ch+12}{12h^{2}}\right)^{2^{i}}+\left(\frac{c^{2}h^{2}-6ch+12}{12h^{2}}\right)^{2^{i}}\right]},n=2,\ldots,L,$$

and $\alpha_{1}>\alpha_{2}>\ldots>\alpha_{L}$. In conclusion, the condition number will be:

Report issue for preceding element

$$\kappa_{IUHOC}=2\frac{\left(12+c^{2}h^{2}\right)\prod_{i=0}^{L-2}\left[\left(c^{2}h^{2}+6ch+12\right)^{2^{i}}+\left(c^{2}h^{2}-6ch+12\right)^{2^{i}}\right]}{\left(c^{2}h^{2}+6ch+12\right)^{2^{L-1}}+\left(c^{2}h^{2}-6ch+12\right)^{2^{L-1}}}$$

(21)

In the next table we have a comparison between condition number of HOC scheme and condition number of HOC scheme preconditioned by IU method.

Report issue for preceding element

$\mathrm{ch}=2$			$\mathrm{ch}=5$		ch $=10$		ch $=20$
h	c	k	c	k	c	k	c	k
$\frac{1}{8}$	16	4.1426	40	3.3550	80	8.0960	160	16.215
		1.5960		1.4133		2.5549		4.5692
		1.3322		1.2330		1.8357		2.8620
$\frac{1}{16}$	32	4.6936	80	3.6955	160	10.639	320	31.394
		1.7267		1.4915		3.1834		8.3567
		1.3718		1.2524		2.1057		4.6964
		1.3333		1.2333		1.8664		3.3772
$\frac{1}{32}$	64	4.8523	160	3.7903	320	11.526	640	40.698
		1.7646		1.5135		3.4032		10.680
		1.3844		1.2584		2.2051		5.8448
		1.3341		1.2335		1.8887		3.8699
		1.3333		1.2333		1.8667		3.4329

A more acurate bound for $k_{IUHOC}$ can be given as follows:
Proposition 3 Let $k_{IUHOC}$ be the condition number given by (21), where $h=1/2^{L}(L\in N)$. Then

Report issue for preceding element

$$k_{IUHOC}\leqslant 2^{L-1}=\frac{1}{2h},$$

for each $L=2,3,\ldots$.
Proof. Let

Report issue for preceding element