Analyse

Les fonctions lipschitziennes

Une fonction qui ne peut jamais amplifier un écart plus de k fois : cette simple promesse borne toutes les pentes, garantit qu'une suite converge, qu'une équation différentielle n'a qu'une solution, et permet même de trouver un minimum avec certitude.

L'idée en une phrase

Mesurez une grandeur x avec une petite erreur, puis calculez f(x) : de combien se trompe-t-on sur le résultat ? Si f est lipschitzienne de constante k, l'erreur sur f(x) ne dépasse jamais k fois l'erreur sur x, et cela partout, quelle que soit la taille de l'erreur.

Définition. Une fonction f définie sur un intervalle I est k-lipschitzienne (k ≥ 0) si, pour tous x et y de I,

|f(x) − f(y)| ≤ k · |x − y|.

Le plus petit k qui convient s'appelle la constante de Lipschitz de f. Le mot vient du mathématicien allemand Rudolf Lipschitz (1832-1903).

Lecture géométrique. Si x ≠ y, on peut diviser par |x − y| : le quotient (f(x) − f(y))/(x − y) est la pente de la corde qui joint deux points du graphe. Être k-lipschitzienne, c'est donc avoir toutes les cordes de pente comprise entre −k et k. Aucune corde ne peut être plus raide que k, ni près, ni loin.

Lien avec la dérivée. Par le théorème des accroissements finis, une corde a toujours la pente d'une tangente quelque part entre ses deux extrémités. Une fonction dérivable dont la dérivée vérifie |f′| ≤ k est donc k-lipschitzienne, et sa constante est exactement sup |f′|. Mais la notion ne demande pas de dérivée : |x| est 1-lipschitzienne alors qu'elle a un angle en 0.

dérivable, f′ bornée⟹ lipschitzienne⟹ höldérienne⟹ uniformément continue⟹ continue

Les cinq planches parcourent cette chaîne : le sablier qui visualise la définition, ce qui se passe quand une fonction est « plus raide que toute droite », puis trois grands usages — les contractions et leur point fixe, l'unicité des solutions d'une équation différentielle, et la recherche d'un minimum garanti.

Planche 1

Le sablier : toutes les cordes sous contrôle

Fixons un point a du graphe. L'inégalité |f(x) − f(a)| ≤ k|x − a| dit que le point (x ; f(x)) reste entre les deux droites de pentes +k et −k qui passent par (a ; f(a)) : c'est une région en forme de sablier (en vert). La fonction est k-lipschitzienne si le graphe reste dans le sablier quel que soit le point a où on le pose. Déplacez a, diminuez k : les morceaux de graphe qui sortent passent au rouge.

Intervalle [−3 ; 3]. Sablier vert : |y − f(a)| ≤ k|x − a|. Graphe bleu dans le sablier, rouge en dehors. Corde orange : la plus raide de toutes les cordes partant de a.
plus grande pente de corde (grille de 100 001 points)—
sup |f′| exact sur [−3 ; 3]—
écart mesure − exact—
corde la plus raide depuis a—
part du graphe hors du sablier—
verdict—

Mesure de la constante sur des grilles de plus en plus fines (plus grande pente entre deux points voisins de la grille) :

À retenir. Une astuce rend la mesure facile : la pente d'une corde entre deux points éloignés est une moyenne des pentes des petites cordes intermédiaires, donc elle ne peut pas dépasser la plus grande d'entre elles. Il suffit de regarder les points voisins. Pour les fonctions lipschitziennes, la mesure se stabilise sur sup |f′| (même pour |x| − 1, sans dérivée en 0) ; pour √|x|, elle est multipliée par environ 3,16 = √10 à chaque fois que la grille devient dix fois plus fine : aucune constante ne convient.
Planche 2

Plus raide que toute droite : la famille xα

Prenons f(x) = xα sur [0 ; 1]. Pour savoir si f est lipschitzienne, on mesure, pour chaque écart h, la plus grande variation ω(h) = max |f(x + h) − f(x)| (le module de continuité) puis le rapport ω(h)/h, qui est la plus grande pente des cordes de longueur h. Lipschitzienne veut dire : ω(h)/h reste borné quand h tend vers 0. La loupe de gauche grossit le voisinage de 0 autant horizontalement que verticalement : une fonction lipschitzienne garde des pentes raisonnables à tout grossissement, les autres se redressent jusqu'à la verticale.

Loupe sur [0 ; h] × [0 ; h], échelles égales. Bleu : y = xα. Pointillé gris : pente 1. Rouge : corde de 0 à h.
Échelles logarithmiques : ω(h)/h en fonction de h (bleu), droite de régression sur h ∈ [10⁻⁶ ; 10⁻³] (rouge pointillé), h actuel (point orange).
ω(h)/h au h actuel—
pente mesurée en log-log—
pente prévue : min(α − 1 ; 0)—
δ garantissant ε = 10⁻³—
contrôle : ω(δ) mesuré—
verdict—
À retenir. Pour α < 1, la corde de 0 à h a pour pente hα−1, qui explose quand h → 0 : la fonction n'est pas lipschitzienne. Elle reste pourtant höldérienne d'exposant α : |f(x) − f(y)| ≤ |x − y|α. La différence se voit sur le δ qui assure une précision ε : δ = ε/k pour une fonction lipschitzienne (proportionnel à ε), mais δ = ε1/α pour xα — avec α = 0,1, il faut δ = 10⁻³⁰ pour obtenir ε = 10⁻³. Les deux sont uniformément continues, mais pas au même prix.
Planche 3

Les contractions et leur point fixe

Une contraction est une fonction k-lipschitzienne avec k < 1 : elle rapproche toujours deux points d'un facteur au moins k. Le théorème du point fixe de Banach (1922) affirme alors qu'il existe un unique x* tel que g(x*) = x*, et que la suite xn+1 = g(xn) y converge depuis n'importe quel départ, l'erreur étant multipliée par k au moins à chaque pas. On l'éprouve sur g(x) = k·cos x, dont la constante de Lipschitz sur ℝ est exactement k (puisque |g′(x)| = k|sin x| atteint k).

Diagramme en toile d'araignée : on monte jusqu'à la courbe y = g(x) (bleu), on revient horizontalement à la diagonale y = x (gris), et l'on recommence. Point vert : x* calculé par dichotomie.
Erreur |xn − x*| en échelle logarithmique (points bleus), borne de Banach kⁿ|x₁ − x₀|/(1 − k) (rouge, seulement si k < 1), décroissance prévue en |g′(x*)|ⁿ (violet).
point fixe x* (dichotomie)—
|g′(x*)| = k·sin x*—
rapport mesuré en/en−1—
erreur |xₙ − x*|—
borne a priori de Banach—
itérations pour 10⁻¹⁰ : borne / réel—
verdict—
À retenir. Avec k < 1, la convergence est garantie d'avance et la borne kⁿ|x₁ − x₀|/(1 − k) n'est jamais dépassée : on sait combien d'itérations faire avant de calculer. Le rapport mesuré se cale sur |g′(x*)|, plus petit que k : la borne est prudente. Entre k = 1 et k ≈ 1,319, g n'est plus une contraction sur ℝ et pourtant la suite converge encore : le théorème donne une condition suffisante, pas nécessaire. Au-delà, |g′(x*)| > 1 : le point fixe repousse, la suite s'installe sur un cycle de deux valeurs.
Planche 4

Une seule solution : le théorème de Cauchy-Lipschitz

Pour une équation différentielle y′ = f(t, y) avec une condition initiale y(0) = y₀, la seule continuité de f assure qu'une solution existe (Peano). Si de plus f est lipschitzienne en y, la solution est unique, et deux solutions parties de points voisins ne s'écartent pas plus vite qu'une exponentielle : |Δ(t)| ≤ |Δ(0)|·ekt (lemme de Grönwall). Sans la condition de Lipschitz, l'unicité peut disparaître.

Ici f(y) = c·sin y a pour constante de Lipschitz c, puisque |∂f/∂y| = c|cos y| ≤ c. La solution exacte est connue : y(t) = 2 arctan(tan(y₀/2)·ect). On lance deux solutions séparées de δ et l'on suit leur écart.

Faisceau de solutions (gris), les deux solutions suivies (bleu et orange), équilibres y = 0 et y = ±π (pointillés). Les courbes ne se croisent jamais.
Rapport |Δ(t)|/δ en échelle logarithmique (bleu) et borne de Grönwall ect (rouge pointillé).
|Δ(4)|/δ mesuré—
borne de Grönwall e4c—
plus grand rapport (mesure/borne) sur [0 ; 4]—
contrôle : Runge-Kutta 4 contre formule exacte—
À retenir. L'écart reste toujours sous la borne ect. Près de l'équilibre instable y = 0, où f′(0) = c, il la suit presque exactement : la borne de Grönwall ne peut pas être améliorée. Près de ±π, équilibres stables, les solutions se rapprochent au contraire. Dans les deux cas, deux solutions distinctes ne peuvent jamais se rejoindre en temps fini : c'est l'unicité.

Ici f(y) = 2√|y| n'est pas lipschitzienne en 0 : le rapport |f(y) − f(0)|/|y| = 2/√|y| devient infini. Toutes les fonctions « nulles jusqu'à l'instant c, puis (t − c)² » sont des solutions issues de y(0) = 0 : une infinité de solutions pour une seule condition initiale. C'est le pinceau de Peano.

Pinceau de solutions issues de (0 ; 0) en gris, solution choisie en bleu, solution d'Euler partie de 0 (points orange, collée à l'axe), solution exacte partie de y₀ = 10⁻⁸ (vert pointillé).
rapport 2/√|y| en y = 10⁻⁸—
résidu |y′ − 2√|y|| de la solution bleue (différences finies)—
Euler depuis y₀ = 0, valeur en t = 4—
depuis y₀ = 10⁻⁸ : exact / Euler en t = 4—
À retenir. Un écart initial de 10⁻⁸ produit un écart de 16 à l'instant 4 : avec une constante de Lipschitz, Grönwall l'aurait borné par 10⁻⁸·e4k, minuscule. Et la méthode d'Euler partie de 0 reste bloquée sur la solution nulle sans jamais signaler les autres. Sans condition de Lipschitz, ni l'unicité ni la confiance dans le calcul numérique ne sont garanties.
Planche 5 · signature

Savoir sans tout voir

Voici le pouvoir le plus étonnant de la constante de Lipschitz : connaître f en quelques points et connaître k suffit à encadrer f partout. Chaque point mesuré (xi ; fi) interdit à f de sortir de son sablier, donc f est coincée entre deux enveloppes en dents de scie. On en tire un procédé qui trouve le minimum global d'une fonction avec un certificat : une preuve chiffrée que l'on ne s'est pas trompé. Fonction étudiée : f(x) = sin x + sin(10x/3) sur [2,7 ; 7,5], un banc d'essai classique de l'optimisation globale, avec plusieurs creux trompeurs.

Enveloppe haute U(x) = mini (fi + k|x − xi|), enveloppe basse L(x) = maxi (fi − k|x − xi|). Toute fonction k-lipschitzienne passant par les points mesurés est comprise entre L et U, et U, L sont elles-mêmes k-lipschitziennes : c'est le prolongement de McShane et Whitney (1934).

Tube des possibles (bleu clair) entre L et U, points mesurés (bleu foncé), vraie fonction (vert pointillé). En rouge : là où la vraie fonction sort du tube, ou là où les données elles-mêmes contredisent k.
vraie constante sup |f′| sur [2,7 ; 7,5]—
pente maximale entre points mesurés—
aire du tube (intégrale numérique)—
aire par la formule des losanges—
pente log-log de l'aire en fonction de n—
vraie fonction dans le tube ?—
À retenir. Entre deux points voisins, le tube est un losange d'aire (k²h² − Δf²)/(2k) ; avec des points réguliers, l'aire totale décroît comme 1/n (pente mesurée −1). Si k est trop petit, deux choses peuvent arriver : la vraie fonction s'échappe du tube sans que rien ne le signale, ou bien les données elles-mêmes deviennent incompatibles (U passe sous L) — c'est alors la mesure qui réfute la constante supposée.

Algorithme de Piyavskii (1972) et Shubert (1972) : on mesure f aux deux bouts, on trace l'enveloppe basse en dents de scie, on évalue f là où cette enveloppe est la plus basse, et l'on recommence. À chaque étape, le minimum cherché est encadré entre le plus bas sommet des dents de scie (borne basse) et la plus petite valeur mesurée (borne haute).

Vraie fonction (bleu clair, inconnue de l'algorithme), points mesurés (bleu), enveloppe basse en dents de scie (violet), prochain point à évaluer (orange), meilleure valeur trouvée (vert), borne basse garantie (rouge pointillé).
évaluations de f—
borne haute (meilleure valeur, en x)—
borne basse garantie—
écart garanti—
vrai minimum (10⁶ points puis section dorée)—
évaluations pour un écart 10⁻⁴ : Piyavskii / grille uniforme—
certificat—
À retenir. Sans hypothèse, aucun nombre fini de mesures ne permet d'affirmer qu'on a trouvé le minimum : la fonction pourrait plonger entre deux points. La constante de Lipschitz interdit ces plongées et transforme une recherche à l'aveugle en preuve. L'algorithme concentre ses mesures autour des creux prometteurs et atteint l'écart 10⁻⁴ en un peu plus de quatre cents évaluations (avec k = 4,5), quand une grille uniforme offrant la même garantie en demanderait plus de cent mille. Mais la preuve ne vaut que si k est juste : réglez k sous la vraie constante, et le certificat peut devenir faux.

Repères historiques

Synthèse

Une pente bornée

Lipschitzienne de constante k : toutes les cordes ont une pente entre −k et k. Pour une fonction dérivable, k = sup |f′|. Mais une dérivée n'est pas nécessaire, et √x montre qu'une fonction continue peut être plus raide que toute droite.

Un écart maîtrisé

Une erreur e sur x donne au plus k·e sur f(x). Itérée avec k < 1, cette maîtrise devient convergence (Banach) ; intégrée dans le temps, elle devient l'inégalité de Grönwall et l'unicité de Cauchy-Lipschitz.

Une connaissance globale

Avec k et quelques mesures, la fonction est encadrée partout. On peut alors certifier un minimum, borner une intégrale ou interpoler sans surprise — à condition que k soit juste.

Pour aller plus loin

Plusieurs variables. La définition s'écrit ‖f(x) − f(y)‖ ≤ k‖x − y‖ avec des normes ; pour une fonction différentiable, k est la plus grande norme de la matrice jacobienne. En apprentissage automatique, on contrôle la constante de Lipschitz d'un réseau de neurones pour qu'une petite perturbation de l'image ne change pas la réponse.

Théorème de Rademacher. Une fonction lipschitzienne est dérivable partout sauf sur un ensemble de longueur nulle : |x| n'a qu'un angle, mais on ne peut pas faire pire qu'un ensemble négligeable d'angles.

Lipschitzienne locale. x² n'est pas lipschitzienne sur ℝ (la corde entre x et x + 1 a pour pente 2x + 1), mais elle l'est sur tout intervalle borné. C'est cette version locale qui suffit pour le théorème de Cauchy-Lipschitz, au prix de solutions qui peuvent exploser en temps fini, comme y′ = y².

Contraction et calcul. La méthode de Newton, la résolution itérative des systèmes linéaires (Jacobi, Gauss-Seidel) ou le calcul du classement PageRank sont des itérations de contractions ; la constante k règle directement la vitesse.