THE NASH-MOSER ITERATION SCHEME

TERENCE TAO

Abstract. Some notes on the Nash-Moser iteration scheme.

1. Finite dimensions

The Nash-Moser iteration scheme is an advanced form of the Newton fixed point method which can work in certain “tame” Frechet spaces. Before we review that scheme, let us first look at what happens in finite dimensions.

1.1. The Picard and Newton iteration schemes. Let X be a finite-dimensional Banach space with a norm ∥∥_{X}. Suppose we are given a differentiable (hence continuous) but nonlinear map Φ : X → X and want to find a solution u ∈ X to the equation

Φ(u) = 0.  (1)

Suppose we are also given an initial guess u_{0} ∈ X for the solution, for which the error

ε_{0} := ∥Φ(u_{0})∥_{X}

is small. An iteration scheme is a recursive algorithm that uses the initial guess u_{0} to construct a sequence u_{1}, u_{2}, u_{3}, … of improved guesses u_{n} ∈ X. Let us say that the scheme works if

• The guesses u_{n} should converge to a limiting value x as n → ∞; and

• The errors

ε_{n} := ∥Φ(u_{n})∥_{X}  (2)

converge to zero as n → ∞. Since Φ is continuous, we see that if an iteration scheme works, then the limiting value x solves (1) as desired. So it is of interest to construct schemes which have a chance of working.

We consider two examples of iteration schemes:

• (i) The Picard iteration scheme, which sets

u_{n+1} := u_{n} − Φ(u_{n});  (3)

• (ii) The Newton iteration scheme, which sets

u_{n+1} := u_{n} − Φ′(u_{n})^{−1}Φ(u_{n}).

Here Φ′(u_{n}) : X → X is the derivative operator of Φ at u_{n} (identifying the tangent space of X at u_{n} with X in the usual manner).

The Newton scheme is very general and should work for all sufficiently regular and non-degenerate Φ and sufficiently good initial guesses u_{0}. Note that the Picard scheme is very similar to the Newton scheme, except that the derivative map Φ′ has been replaced by the identity. We expect the Picard scheme to work well when Φ (and thus Φ′) is close to the identity. The Picard iteration scheme is based on viewing (1) as a fixed point of the map x ↦ x − Φ(x), which is then solved by iteration. The Newton iteration scheme is based on the fact that if x does indeed solve (1) and u_{n} is close to x, then by Newton approximation

Φ(u_{n}) ≈ Φ′(u_{n})(x − u_{n})

and thus

x ≈ u_{n} − Φ′(u_{n})^{−1}Φ(u_{n}).

1.2. Error analysis. Let us first analyse the Picard scheme. For simplicity let us work on the unit ball

B := {u ∈ X : ∥u∥_{X} ≤ 1}

and its dilate

5B := {u ∈ X : ∥u∥_{X} ≤ 5}.

Let us make the following assumptions:

• (Initial boundedness) We have u_{0}, Φ(u_{0}) ∈ B.

• (Lipschitz condition) For any u, v ∈ 5B, we have

∥[u − Φ(u)] − [v − Φ(v)]∥_{X} ≤ \frac{1}{2}∥u − v∥_{X}.  (4)

Setting u = u_{0} in (4) and using the triangle inequality repeatedly, we see that if x ∈ 5B then x − Φ(x) ∈ 5B also. Thus u_{n}, Φ(u_{n}) ∈ 5B for all n. Furthermore we have

∥u_{n+2} − u_{n+1}∥_{X} ≤ \frac{1}{2}∥u_{n+1} − u_{n}∥_{X}

for all n, and thus by (3) we have

ε_{n+1} ≤ \frac{1}{2}ε_{n}.

Thus this scheme converges exponentially fast: ε_{n} = O(2^{−n}). On the other hand, it requires Φ to be close to the identity in the sense of (4).

Now we analyse the Newton scheme. Again we work on B and 5B. Now we make the following assumptions:

• (Initial boundedness) We have u_{0}, Φ(u_{0}) ∈ B.

• (C^{1,1} condition) For any u, u + v ∈ 5B, we have
∥Φ(u + v) − Φ(u) − Φ′(u)v∥_{X} ≲ ∥h∥_{X}^{2}.  (5)

• (Invertibility of derivative) For any u ∈ 5B and v ∈ X, the map Φ′(u) is invertible and we have

∥Φ′(u)^{−1}v∥_{X} ≲ ∥v∥_{X}.  (6)

Here as usual we use A ≲ B to denote the estimate A ≤ CB for an absolute constant C.

Suppose that u_{n} ∈ 5B. Then by (6) we have

∥Φ′(u_{n})^{−1}u_{n}∥_{X} ≲ ε_{n}

and thus

∥u_{n+1} − u_{n}∥_{X} ≲ ε_{n}.

Thus the convergence of u_{n} will be tied to the decay of ε_{n}. Also, if ε_{n} is sufficiently small, we conclude from (5) (with x := u_{n} and h := −Φ′(u_{n})^{−1}u_{n}) that

∥Φ(u_{n+1})∥_{X} ≲ ∥Φ′(u_{n})^{−1}u_{n}∥_{X}^{2}

and thus

ε_{n+1} ≲ ε_{n}^{2}.  (7)

Thus if ε_{0} is sufficiently small, we can see inductively that ε_{n} converges super-exponentially (in fact ε_{n} ≤ (Cε_{0})^{2^{n}}/C for some large constant C) and that u_{n} is convergent in 5B, so the scheme will work in this case.

To summarise, the Newton scheme converges much faster than the Picard scheme, and does not require Φ to be close to the identity. On the other hand, it requires the initial guess to be very accurate, and also requires some reasonably strong differentiability and non-degeneracy conditions on Φ.

2. Infinite dimensions

The above discussion extends without difficulty to the case where X is an infinite-dimensional Banach space, since we did not actually use the finite-dimensional hypothesis anywhere. The Picard scheme in this case is used quite frequently, especially in nonlinear dispersive or parabolic equations, to construct solutions to Cauchy problems; this is a well-studied topic and will not be discussed further here.

However, in nonlinear PDE a frequent problem arises, namely that the map Φ arising in (1) does not map any Banach space X to itself, but instead “loses regularity”, for instance mapping a Sobolev space H^{s}(R^{d}) to H^{s−10}(R^{d}) for all sufficiently large s. Such a loss is quite fatal to the Picard iteration scheme. It is however a remarkable fact that the Newton scheme (with one additional tweak) can still survive such a derivative loss. Basically, this is because the superexponential improvement (7) in the error estimate can, in certain cases, overcome the loss of derivatives.

To keep things simple we shall work with the Sobolev scale H^{s}(R^{d}), abbreviating ∥u∥_{H^{s}(R^{d})} = ∥u∥_{s}, although we will not actually use many properties of this particular scale and could easily work in a more abstract setting if desired. We select a large initial regularity k and work in the ball

B := {u : ∥u∥_{k} ≤ 1},

as well as the dilate 5B. Now suppose that instead of the estimates (5), (6), we have estimates which lose derivatives (say 10 derivatives at a time, for sake of concreteness). More precisely, assume for sake of argument the following properties:

• (Initial boundedness) We have u_{0}, Φ(u_{0}) ∈ B.

• (C^{1,1} condition) For any u, u + v ∈ 5B and k ≤ s ≤ 1.1k, we have

∥Φ(u + v) − Φ(u) − Φ′(u)v∥_{s−10} ≲_{s} ∥v∥_{s}^{2}.  (8)

Here we subscript the ≲ notation by s to indicate that the implied constant can depend on s.

• (Invertibility of derivative) For any u ∈ 5B and v ∈ H^{s}, and k ≤ s ≤ 1.1k, the map Φ′(u) is invertible and we have

∥Φ′(u)^{−1}v∥_{s−10} ≲_{s} ∥v∥_{s}.  (9)

If we use the same Newton iteration scheme as before, we run into trouble (even if we set k to be very large). Indeed if we try to measure the error

ε_{n} := ∥Φ(u_{n})∥_{k}

recursively, and even if we already know somehow that all the u_{n} lie in 5B, we see from (8) (setting u := u_{n} and v := −Φ′(u_{n})^{−1}Φ(u_{n})) that

ε_{n+1} ≲_{k} ∥Φ′(u_{n})^{−1}Φ(u_{n})∥_{k+10}^{2}

and hence by (9)

ε_{n+1} ≲_{k} ∥Φ(u_{n})∥_{k+20}^{2}.

The loss of 20 derivatives here prevents us from obtaining an inequality such as (7) and thus closing the iteration.

However, we can analyse things further. Let us suppose informally that each u_{n} has “frequency” N_{n} in the sense that

∥u_{n}∥_{k+t} ≲_{k,t} N_{n}^{t}∥u_{n}∥_{k}.  (10)

If Φ is reasonably smooth, we expect the same type of bound to then be true for Φ(u_{n}) as well:

∥Φ(u_{n})∥_{k+t} ≲_{k,t} N_{n}^{t}∥Φ(u_{n})∥_{k}.

Then we can continue the previous analysis and obtain a recursive inequality for ε_{n}:

ε_{n+1} ≲_{k} N_{n}^{20}ε_{n}^{2}.  (11)

In order to use this, we of course need to know what N_{n} behaves like. If we have the initial condition

N_{0} = O(1)

and if we have some sort of subquadratic frequency growth estimate

N_{n+1} ≲ N_{n}^{2−κ}  (12)

for some κ > 0, then the quantities ε_{n} in (11) will still go to zero. The point is that while the N_{n} are growing reasonably fast - of the order of exp(O((2 − κ)^{n})) - the inherent decay of (11) is even faster than this; indeed one can show inductively that ε_{n} ≤ c^{2^{n}+1} if c is sufficiently small, and then ε_{0} is chosen even smaller.

Note that (12) is a remarkably mild condition; it is because the decay in (7) is so strong that one can get away with even quite a dramatic cascade from low to high frequencies in this scheme.

The above analysis was not rigorous because we did not pin down exactly what it meant for a function to have a certain frequency. Now let us give a formal version.

Theorem 2.1 (Nash-Moser-Hamilton inverse function theorem). Let k be a large number, and let B, 5B be as above. Let Φ be a nonlinear map with the following properties:

• (C^{1,1} condition) For any u, u + v ∈ 5B, we have

∥Φ(u + v) − Φ(u) − Φ′(u)v∥_{k−10} ≲_{k} ∥v∥_{k}^{2}.  (13)

• (C^{1} condition) For any u ∈ 5B and any v ∈ H^{k}, we have

∥Φ′(u)v∥_{k−10} ≲_{k} ∥v∥_{k}.  (14)

• (C^{0} condition) For any u ∈ 5B, and any k ≤ s ≤ 1.1k, we have

∥Φ(u)∥_{s} ≲_{k} ∥u∥_{s+10}.  (15)

• (Invertibility of derivative) For any u ∈ 5B, and k ≤ s ≤ 1.1k, the map Φ′(u) is invertible and we have

∥Φ′(u)^{−1}Φ(u)∥_{s} ≲_{s} ∥Φ(u)∥_{s+10} + ∥u∥_{s+10}^{2−κ}∥Φ(u)∥_{k+10}.  (16)

for some 0 < κ < 1. Then if k is sufficiently large depending on κ, and u_{0} ∈ H^{1.1k} obeys the initial boundedness condition

∥u_{0}∥_{1.1k} ≤ 1

and ε_{0} := ∥Φ(u_{0})∥_{k−10} is sufficiently small, then there exists a solution u ∈ 5B to (1).

Remark 2.2. Of course, one can replace the parameters 10 and 1.1 with other values. One can also reduce the C^{1,1} condition (13) to a C^{1,α} condition for some 0 < α < 1 (thus replacing the 2 exponent on the right-hand side with 1+α, but then one must reduce the exponent 2−κ in (16) with α − κ. The conditions (13), (14), (15) are an expression that the map Φ and its first few derivatives are “tame”; basically, this means that if u has frequency O(N) then Φ(u) does also, thus Φ and its derivatives do not cause dramatic low-to-high cascades. However, the inverse map Φ′(u)^{−1} is allowed to increase frequencies from N to N^{2−κ} (this is morally apparent from the second term in (16), as can be seen by comparing the exponents in s here against (10). As one might imagine, in applications it is the estimate (16) which is hardest to prove. There are of course many generalisations and abstractions of this result but we will not pursue them here. The Nash-Moser scheme is most effective in highly nonlinear situations in which one expects quite substantial frequency cascades; when one does not expect frequencies to rapidly move from low frequencies to high then simpler approaches such as the Picard iteration scheme are likely to work (and will convey more information, such as stability and persistence of regularity even for quite rough data). Proof. In order to formalise the notion of “having frequency N” we shall utilise Littlewood-Paley projections. Specifically, let φ(ξ) be a smooth bump supported in the ball |ξ| ≤ 2 and equalling one on the ball |ξ| ≤ 1. For each N > 1 we define the Littlewood-Paley operators

{ \atop P_{≤N}f}(ξ) := φ(ξ/N)f̂(ξ),

{ \atop P_{>N}f}(ξ) := (1 − φ(ξ/N))f̂(ξ).f̂(ξ).

Let 2 = N_{0} < N_{1} < N_{2} < … be a sequence of (rapidly growing) frequency ranges to be chosen later. We shall modify the Newton iteration scheme as follows. For n = 0, 1, 2, … set

v_{n} := −Φ′(u_{n})^{−1}Φ(u_{n})
u_{n+1} = u_{n} + P_{≤N_{n+1}}v_{n}

and

ε_{n} := ∥Φ(u_{n})∥_{k−10}.

Note that if all the N_{n} were infinite then this would just be the Newton scheme. Thus the Nash-Moser scheme is a “regularised Newton iteration method”, where at the n^{th} stage we are truncating in frequency so that u_{n} has frequency O(N_{n}).

Suppose for now that u_{1}, …, u_{n+1} ∈ 5B. Then from the identity

Φ(u_{n+1}) = Φ(u_{n} + P_{≤N_{n+1}}v_{n})

= [Φ(u_{n} + P_{≤N_{n+1}}v_{n}) − Φ(u_{n}) − Φ′(u_{n})P_{≤N_{n+1}}v_{n}] + Φ(u_{n}) + Φ′(u_{n})P_{≤N_{n+1}}v_{n} = [Φ(u_{n} + P_{≤N_{n+1}}v_{n}) − Φ(u_{n}) − Φ′(u_{n})P_{≤N_{n+1}}v_{n}] − Φ′(u_{n})P_{<N_{n+1}}v_{n}

and the triangle inequality followed by (13), (5), we have

ε_{n+1} ≤ ∥Φ(u_{n} + P_{≤N_{n+1}}v_{n}) − Φ(u_{n}) − Φ′(u_{n})P_{≤N_{n+1}}v_{n}∥_{k−10} + ∥Φ′(u_{n})P_{>N_{n+1}}v_{n}∥_{k−10}
≲_{k} ∥P_{≤N_{n+1}}v_{n}∥_{k}^{2} + ∥P_{>N_{n+1}}v_{n}∥_{k}
≲_{k,t} ∥v_{n}∥_{k}^{2} + N_{n+1}^{−t}∥v_{n}∥_{k+t}

where 0 ≤ t ≤ 0.1k will be chosen later. Now from (16) we have

∥v_{n}∥_{k} ≲_{k} (1 + ∥u_{n}∥_{k+10}^{2−κ})∥Φ(u_{n})∥_{k+10}  (17)

and

∥v_{n}∥_{k+t} ≲_{k,t} ∥Φ(u_{n})∥_{k+t+10} + ∥u_{n}∥_{k+t+10}^{2−κ}∥Φ(u_{n})∥_{k+10}

and thus

ε_{n+1} ≲_{k,t} (1 + ∥u_{n}∥_{k+10}^{2−κ})^{2}∥Φ(u_{n})∥_{k+10}^{2}
+ N_{n+1}^{−t}(∥Φ(u_{n})∥_{k+t+10} + ∥u_{n}∥_{k+t+10}^{2−κ}∥Φ(u_{n})∥_{k+10}).

Now we need to close the argument and control the right-hand side in terms of ε_{n}. This requires a recovery of the derivative loss, which shall be accomplished using the Littlewood-Paley projection operators.

First we obseve from construction and induction that the Fourier transform u_{n} − u_{0} is supported on the ball {ξ = O(N_{n})}. In particular this implies that

∥u_{n} − u_{0}∥_{k+t} ≲_{k,t} N_{n}^{t}∥u_{n} − u_{0}∥_{k} ≲_{k,t} N_{n}^{t}

and hence by the triangle inequality and initial boundedness condition we have

∥u_{n}∥_{k+t} ≲_{k,t} N_{n}^{t} for all t ≤ 0.1k.

From (15) we conclude

∥Φ(u_{n})∥_{k+t} ≲_{k,t} N_{n}^{t+10} for all t ≤ 0.1k − 10.

On the other hand, by definition we have

∥Φ(u_{n})∥_{k−10} = ε_{n}.

If we let 0 < δ < 1 be a small exponent to be chosen later, we thus see by interpolation that if k is sufficiently large depending on δ, then

∥Φ(u_{n})∥_{k+t+10} ≲_{k} N_{n}^{t+20}ε_{n}^{1−O(δ)} for all t ≤ δk.  (18)

We thus obtain the recursive inequality

ε_{n+1} ≲_{k,t} N_{n}^{100}[ε_{n}^{2} + N_{n+1}^{−t}N_{n}^{t}ε_{n} + N_{n+1}^{−t}N_{n}^{(2−κ)t}ε_{n}].

Since κ ≤ 1 we can absorb the second term into the third, thus

ε_{n+1} ≲_{k,t} N_{n}^{100}[ε_{n}^{2} + N_{n+1}^{−t}N_{n}^{(2−κ)t}ε_{n}].

We now choose N_{n} recursively by

N_{n+1} := N_{n}^{2−κ/2}

and obtain

ε_{n+1} ≲_{k,t} N_{n}^{100}[ε_{n}^{2} + N_{n}^{−κt/2}ε_{n}].

If we then choose t large enough depending on κ, we can arrange matters so that

ε_{n+1} ≲_{k,t} N_{n}^{100}ε_{n}^{2} + N_{n}^{−300}ε_{n}.

If ε_{0} is sufficiently small, we can then recursively verify the estimate

ε_{n} ≤ cN_{n}^{−200}

for all n. Thus the ε_{n} are quite rapidly convergent. Applying (18) we see that ∥Φ(u_{n})∥_{k+10} is also rapidly convergent, and then applying (17) we conclude that the ∥v_{n}∥_{k} are absolutely convergent, and so the u_{n} are a Cauchy sequence. Taking limits we obtain the desired fixed point. □

References

[1] R. Hamilton, The inverse function theorem of Nash and Moser. Bulletin of the Amer. Math. Soc., vol. 7 (1982) 65–222.

[2] J. Moser, A new technique for the construction of solution of non-linear differential equations. Proc. Nat. Acad. Sci. 47, 11 (1961), 1824–1831.

Department of Mathematics, UCLA, Los Angeles, CA 90024

 E-mail address: tao@@math.ucla.edu