# history of the contraction mapping technique

If $|f(x)-f(y)| \leq k|x-y|$ for all $x,y$ then $f$ is Lipschitz with constant $k$, if $k<1$ then $f$ is called a contraction mapping. The beautiful result that a fixed point is associated to a contraction mapping on a metric space is attributed to Banach see here.

The proofs of many interesting theorems of basic analysis or advanced calculus are in part driven by the contraction mapping technique.The usual story:

1. identify an equation you want to solve,
2. replace the real solution with an affine approximation based on derivative data,
3. propose a mapping whose fixed point provides a solution to the equation, this map is inspired by the approximation
4. show the mapping is a contraction mapping and use the theorem associated to the context which provides the existence of the fixed point as a limit of a sequence of approximate functions.

I hope this gives you a ball-park idea of what I intend by saying contraction mapping technique. In Edwards Advanced Calculus text he uses this scheme to prove the multivariate mean value theorem and the inverse mapping theorem. I know a similar arguments can be used to prove existence theorems for ODEs.

Question: what is the history of the scheme above. Is it due to Banach? Is it due to Lipschitz? Is there a clear history of who first proposed the 4-step process I sketch above?

I hope the spirit of the question is clear if the words are not. In any event, I thank the MSE community in advance for its useful insights on this matter!

• If turns out that the answer is appropiate to post here, please do. – Git Gud Jun 10 '13 at 22:41
• @GitGud thanks for the suggestion, of course, it could be that Banach is responsible for the generalization of the scheme I mention. Sometimes we just refer to the generalization. I'm hoping the answer here is not just something like Newton or Euler. But, the odds are against me. – James S. Cook Jun 10 '13 at 22:45

The answer depends on what you mean by the "scheme". In your step 4 you mentioned: "the theorem". If you mean by it the general form of the theorem due to Banach, then there cannot be someone earlier than he who can implement the scheme (by definition). The Banach fixed point theorem is first stated as Theorem 6 on pg 330 of this printing of his doctoral dissertation. Unfortunately, despite its suggestive title, the dissertation does not in fact contain an application of using the fixed point theorem to solve integral equations.

But if you relax the meaning of "the theorem", and refer not so much to the abstract version stated and proved by Banach, but to the general idea that "contraction mappings contain fixed points", then Banach is not even close to the first person to make use of the scheme you outlined.

The scheme you outlined, in its general form (even more general than the exact four step scheme you described), is called the method of successive approximations. The earliest of its uses in the Western world is likely (though I am not entirely certain about this) due to I. Newton in his namesake method for finding roots of functions. The convergence in the case of a contraction mapping (since we are now talking about function $f:\mathbb{R}\to\mathbb{R}$) follows easily from the convergence of the geometric series and the comparison test for series convergence, and is nothing special to remark about. One of the more well-known uses of the method of successive approximations is Picard's original proof of the existence and uniqueness of solutions to ordinary differential equations. Despite the modern presentations which almost always pass through Banach's fixed point theorem, Picard "brute-forced" the construction. (Lindelof's improvement on Picard's original theorem was published in 1894, 25 years before Banach even formulated his fixed-point theorem).

But I said "Western world" before. In fact, a form of the method of successive approximations was known to the Babylonians for finding the square root of a positive number, which is very similar to applying Newton's method to the quadratic equation $x^2 - a = 0$. There's a nice blog post by John Baez and Richard Elwes about that.

But back to the method of successive approximations. Using the method to solve problems certainly has a long history. And it is recognized early on that a necessary condition for convergence is that the error term decreases to zero. The problem is that if we don't know about convergence, we don't have a candidate "limit object" to which we can measure the error! So one of the big steps in the development of this method is surely due to Bolzano and Cauchy who recognized the importance of Cauchy sequences. Ignoring the issue of convergence of Cauchy sequences (which is treated by the completeness of metric spaces), the method of successive approximations can be applied with success provided that the iterates form a Cauchy sequence.

Cast in this historical light, perhaps one should think of the development of the Banach fixed point theorem not as inspiring others to solve problems using the method of approximations, but as providing an important, sufficiently general criterion for when the method of approximations can be applied.

• Thanks! However, doesn't providing such a criterion encourage the practice. The fact that the contraction mapping comes with an error estimate attached makes the process of iterating so much more interesting. I mean, if you iterate without any idea of the verity of your latest iterate then it doesn't seem as interesting. Sort of like calculus one when we tell students the tangent line is the best linear approximation but fail to quantify this claim in a meaningful manner. Great answer! – James S. Cook Jun 13 '13 at 0:45
• @JamesS.Cook: I do not mean to disparage the contribution of Stefan Banach! Much of the development of mathematics hinges on these kinds of breakthroughs, where previously ad hoc constructions are formalized into a blackbox apparatus. One may say that is the difference between a hodgepodge of problem-solving techniques and a bona fide theory. – Willie Wong Jun 13 '13 at 11:49