H∞ norm: Sturm-Habicht method

For a transfer matrix $G \in \mathbb{R}(s)^{u \times v}$ without pole on the imaginary axis,

\[\|G\|_\infty = \sup_{\omega \in \mathbb{R}} \sigma_{\max}(G(i\omega)),\]

where $\sigma_{\max}$ is the largest singular value. With $\Phi_\gamma(s) = \gamma^2 I_v - G^T(-s) G(s)$, write

\[\det \Phi_\gamma(i\omega) = \frac{n(\omega, \gamma)}{d(\omega)}, \qquad n \in \mathbb{R}[\omega, \gamma],\ d \in \mathbb{R}[\omega] \text{ coprime}.\]

The norm is the largest $\gamma$ among the projections of the real critical points of the curve $n(\omega, \gamma) = 0$ in the $\omega$ direction and the real roots of its leading coefficient in $\omega$.

Hinf_StHa computes it by the Sturm-Habicht method of Bouzidi, Quadrat, Rouillier and Younes:

  1. compute the principal Sturm-Habicht coefficients of $n$ and $\partial n / \partial \omega$ with respect to $\omega$ (LACE.biv_psc), the one of index 0 being $\mathrm{Sres}_0$;
  2. isolate the real roots $y_1 < \dots < y_m$ of $\mathrm{Sres}_0$;
  3. from the largest, return the first $y_k$ that is a root of the leading coefficient of $n$, or at which the principal Sturm-Habicht coefficients have a positive number of sign variations.

The result is an isolating interval of the norm, at the precision starting_precision (in bits) or finer.

From a transfer matrix

The entries of G belong to a rational function field in two variables; the first one stands for $\gamma$, the second one is $s$.

using PaceControl, AbstractAlgebra

S, (y, s) = rational_function_field(AbstractAlgebra.QQ, [:y, :s])
G = [s//(s+1) -s//(s+1); -s//(s+1) 1//(s+1)]

Hinf_StHa(G)                                    # encloses (1 + sqrt(5))/2
Hinf_StHa(G, starting_precision = Int32(10))

From the polynomial n(ω, γ)

using PaceControl, Nemo

S, γ = polynomial_ring(QQ, "γ")
S2, ω = polynomial_ring(S, "ω")
P = (4γ - 1)*(4γ + 1)*ω^4 - 4*(2γ - 1)*(2γ + 1)*ω^2 + 16*(γ - 1)*(γ + 1)

Hinf_StHa(P)                                    # encloses sqrt((5 + sqrt(21))/8)

The notebook Infinity Norm Computation runs these examples.

Reference: Y. Bouzidi, A. Quadrat, F. Rouillier, G. Younes, Computation of the $\mathcal{L}_\infty$-norm of finite-dimensional linear systems, Mathematical Software - ICMS 2021, Springer, 2021.