The edge sits where the cells meet the flow

The smaller cell downstream asked whether upwinding gives back the certificate a graded mesh takes away. A Galerkin reduced model of a linear system $\dot x = Ax$ inherits stability whenever the numerical range of $A$ — the set of values $x^{\mathsf T}Ax/x^{\mathsf T}x$ — lies in the left half plane, because the projection cannot move a reduced eigenvalue outside it. On a convection–diffusion operator discretised on a mesh graded towards its outflow, in nodal coordinates, it does not: the range reaches into the right half plane, and reduced models fail. Upwinding adds diffusion, and on a uniform mesh that diffusion is dissipative; on the graded mesh it was not enough. Every interior row of the upwind stencil’s symmetric part sums to half the difference between the inverse widths of the cell ahead of the node and the cell behind it, positive wherever cells shrink downstream, and at Péclet 100 with a grading of a thousand the range’s edge stayed at 6.78.

Its last section left three questions, and two of them are answered here. “The account above places the nodal edge in the cells where diffusion and convection are comparable. Drawing the eigenvector of the symmetric part that attains the edge against the mesh, for both schemes, would say whether that is right.” And: “Whether any consistent first-order stencil can be dissipative in nodal coordinates on a mesh graded towards the outflow … is the direct next measurement.”

The first account is right. The second question has an answer that takes one line of algebra and a column of numbers.

The eigenvector at the edge #

The operators are the earlier essays’: thirty interior nodes on the unit interval, cells growing geometrically so that the largest over the smallest is the grading ratio, the small cells at the outflow, the centred or upwind difference for convection and the standard three-point difference for diffusion, at Péclet numbers of 10, 40 and 100. The edge of the nodal numerical range is the largest eigenvalue of the symmetric part $(A + A^{\mathsf T})/2$, and the vector that attains it is its eigenvector. Where that vector carries its weight is where the operator is least dissipative.

The local balance of convection and diffusion on a cell is its cell Péclet number, the cell width times the Péclet number over two. On a uniform mesh at Péclet 100 every cell has cell Péclet number 1.6, convection-dominated throughout. Grading towards the outflow shrinks the cells there, so the cell Péclet number falls along the mesh: large upstream, where the cells are wide and convection rules, small in the layer, where they are narrow and diffusion rules, and through one somewhere between.

One is not an arbitrary place to look. The stencil that is not symmetric found that the centred difference’s solution starts to oscillate from point to point at a cell Péclet number of exactly one, because that is where the off-diagonal entry of the stencil on the downstream side changes sign: below one, the row is a weighted average of its neighbours and the discrete maximum principle holds; above it, the downstream neighbour enters with the wrong sign. The graded mesh puts that crossing at a definite node, different for each grading, and a node is something an eigenvector can be measured against. If the account is right, the eigenvector should move with the crossing as the grading changes, and should not move with anything else — not with the smallest cell, which is always at the last node, and not with the steepest change in cell width, which on a geometric mesh is always at the outflow too.

The figure at the top of the page is the picture the earlier essay asked to see. On the thousand-to-one mesh at Péclet 100 the eigenvector is a single bump, almost nothing upstream of $x = 0.7$, rising to a peak at node 13 of 30 — $x = 0.951$ — and falling to nothing over the last few nodes. The cell Péclet number crosses one just upstream of the peak, at $x = 0.92$, and at the peak it is 0.58 for both schemes. The upwind eigenvector is a little wider and a little further upstream than the centred one, but the two peak at the same node.

The dial moves the grading. At ten to one the cell Péclet number is above one over most of the mesh and crosses it near $x = 0.8$; the eigenvector peaks there, at node 16 of 30 for the upwind stencil, with cell Péclet number 1.24. At a hundred to one the crossing has moved to $x = 0.9$ and the peak with it, at cell Péclet number 0.78 for upwind and 0.67 for centred. At a thousand it is where the first figure showed. Whatever the grading, the edge follows the place where the cells and the flow are in balance.

The two schemes differ in a way that says something about what upwinding does. The upwind stencil adds artificial diffusion proportional to the cell width, so upstream, where cells are wide, it damps more than the centred stencil; in the layer, where cells are narrow, it adds almost nothing. Its eigenvector is pushed slightly away from the wide cells, which it damps, towards the crossing from upstream — and the crossing itself it barely touches, because there the added diffusion is of the same order as the physical diffusion and both are of the same order as the grading term that undoes them. That is why the earlier essay found upwinding reduced the edge only modestly: it adds damping where the edge is not, and adds too little where it is.

The edge’s value tells the same story from the other side. At Péclet 100 with a grading of a thousand the centred operator’s edge is 8.94 and the upwind one’s 6.78, both well into the right half plane, while every eigenvalue of both operators sits in the left half plane, because the cell-weighted range contains them all and is itself in the left half plane — the full models are stable. Nothing about the spectrum predicts where the eigenvector lives or that it exists; it is the non-normality of the graded operator, a property of the gap between its spectrum and its range, and a spectral radius that grows first is the same gap seen in the powers of a matrix rather than in a quadratic form. A reduced model that captures the edge’s direction inherits the transient growth that direction carries, and has no stable eigenvalue of the full operator to bring it back.

Where diffusion and convection are comparable #

Across all eighteen operators the rule holds wherever it can. At Péclet 40 and 100 the meshes all have cells with cell Péclet number above one, and on all twelve of those operators the eigenvector peaks where the cell Péclet number is between 0.46 and 1.24 — within a factor of two of one on both sides, and on most of them between a half and four-fifths, just downstream of the crossing. At Péclet 10 no cell anywhere reaches one — the largest is 0.39, 0.67 and 0.92 at the three gradings — and the eigenvector peaks at cell Péclet numbers of 0.23 to 0.37, about where the cells are largest relative to what the grading has done to them. The account was that the edge lives where convection and diffusion are comparable; the measurement says it lives where they are as comparable as the mesh allows.

The reason the balance point is where the dissipation is weakest is the row sum the earlier essay found. Diffusion contributes a negative definite part whose size, relative to a cell’s own terms, grows as the cell shrinks; the convection stencil’s symmetric part contributes the positive grading term $(1/h_{i+1} - 1/h_i)/2$, which grows as the grading steepens. Upstream, where cells are wide, the grading term is small in absolute size. In the layer, where cells are narrowest, diffusion’s negative part grows as $1/h^2$ and swamps the grading term, which grows only as $1/h$. In between, where the cell Péclet number is near one, the two are of the same order, and that is where the positive part can win.

Not in the layer #

The natural guess, before drawing anything, is that a range edge produced by grading lives where the grading is steepest and the cells smallest: in the layer. It does not. On every operator the last five nodes hold under four per cent of the eigenvector’s weight — 3.6 per cent at most, on the least graded mesh at Péclet 100, and under one per cent on every mesh graded a hundred to one or more. The layer is where the solution changes fastest and where the mesh was graded to put its resolution; it is the most dissipative stretch of the operator, not the least.

That matters for the remedy the inner product the mesh already computed found. Weighting the inner product by cell size makes the range dissipative on every grading, and the place it changes the quadratic form most is where the cell sizes vary most against the nodal weights — which is not the layer either, where the cells are uniformly small, but the transition, where they are shrinking fastest relative to their size. The weight repairs the range exactly where the eigenvector shows the damage.

Can a one-sided stencil be dissipative? #

The second question was whether any consistent first-order convection stencil can be dissipative in nodal coordinates on such a mesh. Within the one-sided family — $-w_i(u_i - u_{i-1})$ at node $i$, a backward difference with some weight — the answer is a line of algebra. The stencil’s symmetric part has diagonal $-w_i$ and off-diagonal entries $w_i/2$ below and $w_{i+1}/2$ above, so an interior row sums to $(w_{i+1} - w_i)/2$. A row sum is the quadratic form at a constant vector, restricted to that row; if the weights increase downstream every interior row sum is positive and the constant vector, or something near it, puts the range into the right half plane. Dissipativity needs weights that do not increase downstream.

Consistency needs the opposite. For the stencil to approximate a derivative, $w_i$ must be one over the distance between node $i$ and node $i - 1$ — the width of the cell behind it — and on a mesh graded towards the outflow those widths shrink downstream, so the weights grow. The upwind stencil is exactly that choice. The two requirements cannot both be met.

The figure measures the three obvious weights on the convection term alone. With the cell behind — the consistent upwind stencil — the edge is 0.43 at a grading of three, 13.1 at a hundred and 109 at a thousand, rising roughly in proportion to the grading. With the cell ahead, the choice the earlier essay floated — “an upwind stencil that divided by the downstream width” — the edge is larger still, 15.3 at a hundred and 137 at a thousand, because the weights now grow a cell earlier. Only the constant weight, the stencil of a uniform mesh transplanted unchanged onto the graded one, is dissipative: its edge is $-0.16$ at every grading, the uniform mesh’s.

And it is not consistent. Applied to $u = x$ it should return $-1$ everywhere; the cell-behind stencil does, to rounding, at every grading. The cell-ahead stencil is wrong by 0.04 at a grading of three and 0.26 at a thousand. The constant weight is wrong by 0.58 at three and 4.1 at a thousand — an error four times the derivative it is meant to approximate. The one dissipative stencil in the family is the one that has stopped approximating the operator.

What this says about the remedy #

A certificate written in coordinates found that the numerical range is a property of the coordinates as much as of the operator, and the earlier essays on reduced stability chose a weight to repair it. The one-sided family shows the repair cannot be made inside the stencil. Any consistent backward difference on a mesh graded towards the outflow has weights growing downstream; any such stencil puts its nodal range into the right half plane; and the only way out is to change the inner product — which is what weighting by cell size does — or to leave the family. A stencil that is not one-sided, or a scheme that is not first-order, has more freedom, and whether any of them can be dissipative in nodal coordinates on a graded mesh is not settled by this argument.

There is one example in these essays of a stencil from outside the family that is exact on its problem. The diffusion that makes the answer exact found that adding a carefully chosen artificial diffusion, the coth-weighted fitting of the Iljin–Allen–Southwell scheme, makes the computed solution of the one-dimensional problem exact at every node. That stencil is three-point, not one-sided, and its weights depend on the local cell Péclet number through a function that tends to the centred stencil where cells are small and to the upwind stencil where they are large. On a graded mesh it would interpolate between the two exactly through the transition the eigenvector occupies, and whether that interpolation is dissipative in nodal coordinates is the cleanest single test of whether leaving the one-sided family helps at all. The row-sum argument does not apply to it directly, because its symmetric part has diffusion entries that vary from row to row, and a row sum then depends on how the diffusion weights change as well as the convection ones.

The algebra has a plainer reading too. A row sum of the symmetric part being positive means that a vector constant over a few neighbouring nodes grows under the operator, in the nodal inner product, faster than diffusion takes it away. A consistent stencil must transport such a vector downstream — that is what it means to approximate the derivative — and on a mesh whose cells shrink in that direction, transporting a constant into narrower cells concentrates it. In the nodal inner product, where each node counts the same whatever its cell, concentration reads as growth. In the cell-weighted inner product, where a node counts in proportion to the width it stands for, the same concentration conserves the integral and reads as nothing at all. The defect is not in the stencil; it is in asking the nodal coordinates to measure a quantity that the mesh has already said is not uniform.

The location result says where a cheaper repair could act. If the damage is concentrated in the transition, a weight that differs from the identity only there — a few nodes either side of where the cell Péclet number crosses one — might certify the range at a fraction of the full mass weighting’s departure from nodal coordinates. That is a prediction, not a measurement.

Half the conditions and a certificate and a model that cannot be run began the subject with reduced models that blow up although the full model is stable; on a graded mesh the place they blow up from now has an address.

What thirty nodes do not show #

Every mesh has thirty interior nodes, and the eigenvector’s peak is resolved to a node; at a thousand-to-one grading the nodes near the peak are a few thousandths apart, which is enough to place it but not to say how its shape scales with refinement. The cell Péclet number at a node is taken as the mean of the two cells beside it. The one-sided family is the whole of what the stencil argument covers; central and higher-order stencils are not touched by it. And the edge is a statement about the worst direction only: a reduced model fails if its basis has a component in that direction, and whether the bases the earlier essays’ interpolation points produced have such components where the eigenvector lives is a question the failure counts already answered without this picture.

Still open: a local weight, and the eigenvector under refinement #

A weight only in the transition. Weight the inner product by cell size over the nodes where the cell Péclet number is between a quarter and two, and by one elsewhere. The prediction with a sign is that on every grading at Péclet 40 and 100 this local weight makes the range dissipative, and that the Galerkin models built in it fail on none of the placements where the nodal ones failed — so that the full mass weighting’s success comes entirely from the transition the eigenvector occupies.

Refinement. On a mesh of 120 nodes with the same grading the transition is resolved by four times as many nodes. The prediction is that the eigenvector still peaks where the cell Péclet number is between a half and one, that its width in $x$ shrinks in proportion to the transition’s, and that the edge grows in proportion to the inverse width of the cells there — so that refinement makes the nodal range worse, at the place the eigenvector says.