“For his groundbreaking contributions to the theory and application of partial differential equations and to the computation of their solutions.” — Citation for the 2005 Abel Prize awarded to Peter D. Lax.

This post focuses on one of Peter Lax’s pivotal contributions. Lax was one of the greatest mathematicians of the 20th century, and his work shaped many fields. None, more deeply than computational science. Winner of the Abel Prize in 2005. He died about a year ago at 99.

His career was shaped by the defining event of that century. He emigrated from Hungary with his family in late 1941. He was drafted into the U.S. Army at 18, and was assigned in 1945–46 to the Manhattan Project at Los Alamos. He was a brilliant high school graduate, but known to top scientists already. He returned to Los Alamos with a PhD as a staff member in 1949-50 and spent most summers there through the 1960s. There he witnessed the beginnings of computational science, and its power. Then he contributed to it mightily.

For my interests, Lax’s contributions sit primarily in hyperbolic conservation laws, where he developed much of the essential theory. These underpin both the mathematical and the numerical solution of these equations. My focus here is the equivalence theorem (Lax and Richtmyer 1956). It is sometimes called the Fundamental Theorem of Numerical Analysis (by Gil Strang). It states that for a well-posed linear initial-value problem, a consistent finite-difference method is convergent if and only if it is stable. The theorem applies rigorously to linear PDEs. This linearity restriction has long been used as the excuse for not placing it in a more central role in the practice and justification of code verification. I believe that excuse is wrong-headed and short-sighted, and I will make the case in what follows.

I write this with two things in mind. The first is the beauty and importance of mathematical foundations. This has utility in giving us confidence in what we do as computational scientists. The second is the recognition that the physical laws to which we apply mathematics are themselves only approximate too. Mathematics is the way we drag the physical world into order so that it can be understood and, with luck, mastered. We keep in mind that mathematical descriptions always fall short of the real thing. This falling-short does not diminish their importance. They are precisely what we lash ourselves to: the proverbial mast in the storm. Diminishing the power of this theorem only lessons our ability to withstand the waves.

“It was the experience of being part of a scientific team — not just of mathematicians, but people with different outlooks — with the aim being not a theorem, but a product. One cannot learn that from books, one must be a participant… It was there — that was in the 1950s — that I became imbued with the utter importance of computing for science and mathematics.” — Peter D. Lax

The Case for the Theorem

I believe strongly that Lax equivalence theorem is the foundation of verification. I will make the case for why. I will start by why the standard objection to it misses the point.

If one consults the canonical V&V references, Roache (1998), or Oberkampf and Roy (2010) you find a curiously dismissive attitude toward the theorem. The reason is always the same: strictly and rigorously, it applies only to linear partial differential equations. We all know that almost everything interesting in science is governed by nonlinear equations. In both books the theorem is mentioned exactly once, and in both it is dismissed almost as fast as it is raised.

I think that is short-sighted.

The theorem captures is the essence of what we ask of any computation: more computational effort will produce a more accuracy. It ties together the two properties that make this possible. These are consistency and numerical stability. It states that, for a well-posed linear problem, the two together are equivalent to convergence. That is the whole game. We design consistency and stability into a method. This carries the expectation of convergence. Verification is the discipline of checking whether the method actually delivers what the theory promises.

“Physics is like sex: sure, it may give some practical results, but that’s not why we do it.”― Richard P. Feynman

Yes, the rigorous statement is restricted to linear equations. But the objection loses the forest for the trees. Most of the nonlinear equations we actually care about are contractive. A contractive equation is close to a linear one in terms of what we expect from it. This is what is witnessed in our daily work. The genuine danger the linear caveat points at is real. Nonlinear equations can produce ill-behaved structures and solutions that do not converge the way linear ones do. Even linear equations do as witnessed by the fractional convergence of linear advection. That danger is the exception we should watch for, not the rule that should make us throw the framework away. The theorem tells us what to do. It defines the practice we must embrace.

The forest is this: Lax’s theorem expresses a fundamental, almost axiomatic belief about computing. It encapsulates precisely why verification is worth doing at all. The theorem is useful ammunition in a practice that is resisted commonly.

“The mathematical formulation of the physicist’s often crude experience leads in an uncanny number of cases to an amazingly accurate description of a large class of phenomena.” — Eugene P. Wigner

A Practitioner’s View

“There are many hypotheses in science that are wrong. That’s perfectly alright; it’s the aperture to finding out what’s right. Science is a self-correcting process. To be accepted, new ideas must survive the most rigorous standards of evidence and scrutiny.” ― Carl Sagan

Let me put it personally. Over a career spent designing methods, the two conditions I come back to every time are consistency, and stability. Consistency is where accuracy lives and gets defined. Stability is essential and must always be checked at design. The accuracy or stability of a technique matters more than the technique itself. I check the code, I look at how it converges on simplie problems. Then I go to more real problems. With observed convergence I confirm that the overall recipe I designed is a good. Evidence that I actually implemented what I intended to design. I have done this many times, and every single time, the result still lines up with the conditions of the equivalence theorem. It is disturbing to me that the community does not more widely recognize this simple pair of conditions as the foundational contribution it is. It is the cornerstone of the practice of the computational scientist.

There is more foundation to build here, not less. Extending it to specific classes of nonlinear equations would be valuable work. The Lax–Wendroff theorem already shows part of the way. For a consistent, conservative scheme, a convergent solution is guaranteed. A weak solution of the conservation law if you have conservation form. This has a technicality that you still need an entropy condition to pick out the physically correct weak solution.

So does the equivalence theorem hold for nonlinear equations all the time? No. Does it hold most of the time? Empirically, yes. There is the heart of my complaint: why reject something that holds most of the time? We should of course be careful, precisely because we cannot claim it always holds. Rejecting it outright is short-sighted. This is especially true given the power of the underlying concept. It has driven the growth of computational power in the decades since the Second World War. Its precepts hold for the vast majority of important work. When it does not hold, we have a crisis.

I would rather be tethered to something that does not rigorously apply than to nothing at all. This theorem supplies most of the practice we rely on during verification. That alone is reason to embrace it. Pure mathematics may not regard it as ironclad for the nonlinear problems we actually run. That is an important caveat to make clear. Still it contains very nearly the entirety of our well-founded beliefs about what these computations are doing, and it holds up empirically. That is exactly what makes it the right thing to stand on.

“I heartily recommend that all young mathematicians try their skill in some branch of applied mathematics. It is a gold mine of deep problems whose solutions await conceptual as well as technical breakthroughs.” — Peter D. Lax

References

Lax, P. D., and R. D. Richtmyer (1956). “Survey of the Stability of Linear Finite Difference Equations.” Communications on Pure and Applied Mathematics 9 (2): 267–293. DOI: 10.1002/cpa.3160090206.

Oberkampf, W. L., and C. J. Roy (2010). Verification and Validation in Scientific Computing. Cambridge University Press, Cambridge. ISBN 978-0-521-11360-1.

Roache, P. J. (1998). Verification and Validation in Computational Science and Engineering. Hermosa Publishers, Albuquerque, NM. ISBN 978-0-913478-08-0.