stečkin

$ \newcommand{\R}{\mathbb{R}} \newcommand{\complex}{\mathbb{C}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\maxmod}[1]{\norm{#1}_\infty} $

Le lemme de S.B. Stečkin porte sur le comportement d’un polynôme trigonométrique près de son maximum. Pour être précis, si le polynôme $$ f(t) = \sum_{\abs{n}\leq N}\alpha_{n}e^{int} \quad (\alpha_{n}\in\complex) $$ est à valeurs réelles et $t_{0}\in [0,2\pi]$ est tel que $$ f(t_{0}) = \maxmod{f} = \max\left\{\abs{f(t)}\;:\; t\in [0, 2\pi]\right\}, $$ puis $$ f(t_{0}+s) \geq \maxmod{f}\cos Ns \quad (\abs{s}\leq \pi/N). $$ En d’autres termes, le polynôme décroît pas plus vite que $\cos Ns$ à proximité d’un maximum, sans aucune référence à sa dérivées. Ce lemme et ses généralisations peuvent être utilisés pour construire des algorithmes « subdiviser et à rejeter » pour l’optimisation globale des objectifs non convexes.

maxmod

L’algorithme maxmod calcule le module maximum d’un polynôme complexe sur le disque unité suivre une méthode de sectionnement répétée de $[0,2\pi]$ et de rejet des sous-intervalles non-maximiser. Une description détaillée de l’algorithme et de son exécution peut être trouvée ici.

L’algorithme a été employé par Gregory Janks dans une démonstration numérique que l’ensemble de Mandelbrot est relié simplement au point de Feigenbaum.

maxmodnd

Gabriel De La Chevrotière (Université McGill) a généralisé le lemme de Stečkin au cas multivarié et en tire alors une méthode pour trouver le module maximum d’un polynôme multivarié sur le polydisque. L’article, publié en SIURO, peut être téléchargé ici.

S. B. Stečkin
S. B. Stečkin (С. Б. Стечкину)

opnorm

S. W. Drury (Université McGill) a demonstré un estimation de genre de Stečkin pour les opérations sur espaces vectoriels réels de dimension finie avec la p-norme, aux espaces de Banach avec les normes facilement calculés. Cela lui permet de inventer le premier algorithme général calculer les normes $\ell_p \rightarrow \ell_q$ des matrices (quoique ceux avec un petit nombre de colonnes), et permet donc lui trouver un contre-exemple à une conjecture de longue date de Matsaev.

  • L’article de S.W. Drury dans Linear Algebra and its Applications (abonnement requis) et sa page web sur l’algorithme, y compris les implémentations pour Visual C++ et Maple.
  • Le paquetage opnorm réalisée en C99 (manuel) multithreadé et ciblée sur les systèmes Unix avec les liaisons pour Matlab, Octave et Python.

Comme on peut le voir dans le tableau, l’algorithme semble requérir de temps qui est exponentielle dans l’ordre de la matrice (en fait, dans le nombre de colonnes), ainsi seules les matrices de moins que 10 colonnes sont réalisables. Mais c’est à prévoir, car Julien M. Hendrickx et Alex Olshevsky ont démontré (SIAM J. Matrix Anal. Appl. 01/2010; 31:2802–2812, DOI, arXiv) que ce problème est NP-difficile.

Performances thread d'opnorm pour les matrices d'ordre $n \times n$, sur un quad-core Intel® Core™ i7-4700MQ 2.5 GHz et hyperthreading activée (8 processeurs virtuels). Chronométrage en millisecondes pour la 4-norme en moyenne de 128 matrices aléatoires (gaussienne).
threads
order 1 2 4 8
2 0.163 0.113 0.132 0.143
3 0.949 0.530 0.349 0.383
4 6.490 3.689 2.082 1.911
5 49.962 27.154 15.061 12.445
6 412.647 220.077 120.219 95.550
7 3270.566 1746.786 946.903 740.649