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.

• maxmod.m pour Octave/Matlab
• maxmod.py pour Python
• le réalisation en C99 — voyez également le manuel
• le réalisation pour C++11 utilisant les templates

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.

• maxmodnd.m (qui utilise polyvaln.m) pour Octave/Matlab
• Une version de l’algorithme est inclus dans le paquetage mvpoly

maxmodnb

J'ai un code expérimental pour calculer le module maximal d'un polynôme complexe multivarié sur la balle unitaire. Les chercheurs intéressés sont invités à me contacter pour une version préliminaire du code.

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.