# Why do structured and unstructured discretizations give different errors?

It is necessary for me to solve a Poisson problem with a numerical method on a square domain with two types of triangular mesh: uniform triangular mesh (using uniform distribution nodes on square) and nonuniform triangular mesh using pdetool in MATLAB.

The first one leads to a banded matrix and the second one leads to a sparse matrix but not banded. This is the only different between two method. It should be noted that the sparsity of two matrices are the same. Also the condition numbers of those are nearlly equal.

But the result by using uniform triangular mesh is much better than the second one. Is there anyone who know about this problem?

Also, I should say the quality of two meshes are same. • Does the non-uniform mesh have any particularly thin elements? What metric are you using to evaluate the quality of the meshes?
– Paul
Feb 18 '15 at 19:44
• Not really, in the uniform mesh, the mesh quality of each element is 0.86 using pdetriq MATLAB command, so the avarege is 0.86. but for non-uniform the min qulity is 0.7 for a few triangles but the average is about 0.9.
– Rosa
Feb 18 '15 at 19:51
• Also, what metric are you using to evaluate the "size" of the finite elements in each mesh?
– Paul
Feb 18 '15 at 20:01
• Assuming at least one of linear solvers used is iterative (banded solver could be exact), are the convergence tolerances the same for both solvers? Feb 19 '15 at 6:09
• How do you compute the errors? Do you really compute the L2 error of the exact vs the discrete solution or of the discrete solution to an interpolant? In the latter case there exist superconvergence and supercloseness results on structured meshes. Jun 24 '15 at 19:17

There are two sources of error, and each of them will be different for your two discretizations.

1. Truncation error, also referred to as discretization error. This results from the fact that you approximate the Laplacian by a discrete stencil. This error will remain even if you solve the linear system exactly; the only way to reduce it is to use a finer or more accurate discretization. Since you haven't specified precisely the discretization you are using in each case, it is impossible to say by how much the discretization errors differ.

2. Error in the linear solver. Since you are computing in finite precision arithmetic, you will not obtain an exact solution to the linear algebraic system given by your discretization. As you are aware, the influence of roundoff errors will be amplified by the conditioning of the problem, and also by the stability of the algorithm you use. MATLAB's backslash operator uses a variety of algorithms, depending on the structure of the matrix in question. It is possible that it is able to use an algorithm with better stability for the banded matrix, thus leading to a smaller error (even though the matrices have similar condition numbers).

It seems most likely that the difference you see is due to #1, but #2 cannot be ruled out based on what you have written. Also, it may be helpful to consider a third possibility: that there is a bug in the unstructured grid code (which is necessarily more complicated than the structured-grid code). It would be useful to quantify what you mean by "much better". If both solutions appear to converge to the same thing upon refinement, a bug is less likely.

This has nothing to do with banded/non-banded matrices: since you use the \ operator to solve your system, you will always obtain an exact solution to your discretized problem (up to roundoff effects). The question is therefore how well the solution of the discrete problem approximates the exact solution.

I assume that you use a standard FEM with Courant elements (piecewise linear and continuous). We know, by Céa's Lemma, that the discrete solution will be quasi-optimal in the sense that it is only by a constant factor worse than the best possible approximation of the solution that your discretization space allows.

So what you really have to ask is how good the approximation properties of your discretization space are. The typical approximation properties derived for the FEM usually assume that the mesh is quasi-uniform and shape-regular. In other words, the elements are roughly the same size and none of them are extremely stretched in one dimension. If this assumption is violated, then we must expect a degradation of the approximation quality.

I recommend you to read up on these topics in any standard textbook or lecture notes on numerical methods for elliptic PDEs. Please ask if you need pointers on particular sources.

A practical concern is also if the two discretizations you use have the same or at least comparable number of degrees of freedom.

• I don't think you should say that the backslash is exact up to roundoff. Certainly, the errors in the solution of the linear system will almost always be much larger than roundoff (since most matrices are not perfectly conditioned). Apr 24 '15 at 8:00
• @DavidKetcheson: You are right, of course. I should probably say "up to roundoff and conditioning effects". However, in my experience, I have never seen this error dominate the discretization error, and certainly not on such a simple, small FEM example.
– cfh
Apr 24 '15 at 8:05
• You're still leaving out the amplification of error due to stability of the algorithm. But I agree that for a small mesh and simple problem, the issue is almost certainly either a bug or the discretization. Apr 24 '15 at 8:07