1
$\begingroup$

I would like to know what are the necessary and sufficient tests one has to perform in order to show the convergence of the algorithm. I have not found a good reference to state for that as I am interested in the quantity $\|u_h-u\|$ in some discrete norm as $h\to 0$. $u_h$ denotes a numerical solution on a grid with spacing $h$ and $u$ denotes the true solution. Assume there is no exact solution to compare to. I don't want to "manufacture" the solution for the pde as it assumes that there is a strong solution of the pde, which I do not necessarily have. Bottom line, solution is not strong on the entire domain+the boundary. But I have a numerical algorithm that solves that equation and I can observe the results. What are my techniques to judge the accuracy for that equation with the used algorithm?

One of the ways I propose is ASSUME: $$\| u_h - u \| \leq Ch^2$$. Then $$\| u_{2h} - u_h \| \leq \| u_{2h} - u\| + \| u - u_h \| = 5Ch^2.$$ Similarly $$\| u_{4h} - u_{2h} \| \leq 20Ch^2$$ Thus, since all these solution live on different finite-dimensional spaces I project the finer solution on a coarser grid, that is $\| u_{2h} - u_h \|$ is measured on the grid space with spacing $2h$ and $\| u_{4h} - u_{2h} \| $ is measured on the grid spacing of $4h$. The ratio of these two quantities would give me $4$ for the second order method. However, I STARTED with an assumption that the method is second order and therefore to see $4$ as a ratio is only necessary, but not sufficient to claim that the algorithm in fact is of second order. Thus, what are my options to show that the rate of the algorithm is in fact second order in this case?

EDIT: the equation I am solving is $$u_t=u_{xx}+1_{\{x\geq K\}}u_y,\; x\in [0,2K], y\in [0,2], t\in [0,T]$$ with initial data: $$u(0,x,y)=x-K/2, x\in[K/2,2K], y \in [0,1]$$ and and everywhere else the value is $0$. So the initial data is "rough", lacking even continuity, the second dimension has no diffusion and the coefficient in pde is discontinuous, as a result, i do not obtain any regularity in $y$ dimension at all. And I don't see how I can manufacture a solution that would exhibit such a shape at $t=0$. For the manufactured solution idea, I have to come up with a function that has $u_t,u_{xx},u_y$ and is "very close" to the initial data, but since it will be smooth apriori in order to take derivative it is still not a good approximation of the real function.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I don't think its a good idea to begin by assuming a priori that your method is 2nd order accurate in order to prove it is so... Typically, you should assume a bound of the form $Ch^p$ where p is an unknown order. Then you derive the value of p by analysis. $\endgroup$ – Paul♦ Feb 7 '13 at 14:02
  • $\begingroup$ right, I carried the analysis and established that $p=2$, so now I want to verify that numerically. At least that it is at least as good as two. $\endgroup$ – Kamil Feb 8 '13 at 1:46
  • $\begingroup$ Do you have an exact expression for the solution $u$? $\endgroup$ – Paul♦ Feb 9 '13 at 3:18
  • $\begingroup$ If I did I could check the error directly by measuring $||u_h-u||$... $\endgroup$ – Kamil Feb 9 '13 at 14:05
  • $\begingroup$ I don't see why manufacturing a solution assumes that there's a strong solution. You can apply the Method of Manufactured solutions to the weak form of your equations just as easily as the strong form. Perhaps if you provided the equations you're trying to solve, we could be more helpful. $\endgroup$ – Bill Barth Feb 9 '13 at 16:59
2
$\begingroup$

However, I STARTED with an assumption that the method is second order and therefore to see 4 as a ratio is only necessary, but not sufficient to claim that the algorithm in fact is of second order.

I think the proof that a given discretization method is second-order accurate takes place on paper (assumptions, theorems and such). Numerical experiments then confirm and illustrate the proof. More importantly, they show whether the implementation of the method in a particular piece of software is correct (so-called Code Verification).

|cite|improve this answer
$\endgroup$
7
+25
$\begingroup$

Convergence is a statement about the asymptotic limit $h\to0$. Therefore, it's not possible to "prove" convergence by any finite number of computations. The best you can do with computations is motivate the belief that an algorithm does converge. To prove convergence, you need to...write a proof.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

The usual strategy for problems where you don't have and exact solution is to compute an "overkill" solution on an extremely fine mesh (as fine as you can reasonably run) and then compute a sequence of solutions on successively finer meshes leading up to that mesh. You can then plot the difference between the overkill solution and each of the others and compare to the expected asymptotic rate.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Downvoter care to comment? $\endgroup$ – Bill Barth Feb 12 '13 at 2:06
  • 1
    $\begingroup$ I don't think this is a reliable way to test the convergence for the following two reasons. First, this can be risky: the code can converge perfectly to the "wrong" solution. In fact, if there is any error in specification of the boundary condition you will never notice that. Second, consider very slow convergence, almost flat(that is the method is slower than linear convergence). Then you run it on a fine grid, the error is still large(the difference between the numerical solution and the true one) but you can easily obtain a high order of convergence taking that as a reference soln. $\endgroup$ – Kamil Feb 12 '13 at 3:02
  • $\begingroup$ In fact, even the method that I have proposed in the question itself would not be sufficient either as the second argument can be applied there as well. $\endgroup$ – Kamil Feb 12 '13 at 3:08
  • $\begingroup$ Sometimes, though, this method is the only choice you have. Have you tried it? Your first comment is wrong where you state that you can simultaneous have a slow convergence and appear to have fast convergence. You are correct that even your "overkill" solution may be far from the true solution, but if there is a second-order rate of decrease in difference between coarser grids and the fine grid, you have established the rate portion of the error bound. There's not much you can do about the constant unless you have an exact solution. $\endgroup$ – Bill Barth Feb 12 '13 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.