Algorithmique 2 : Séries Formelles

Séries Formelles

P ≝ \sum\limits_{n≥0}p_n X^n

où :

  • on a expression explicite de $p_n$, du genre $p_n ≝ n^2$
  • OU : on a une équation de récurrence, du genre $p_{n+1} = f(p_n, p_{n-1})$

Question : Est-ce que $∃Q$ tq $PQ = 1$ ?

Condition nécessaire : $p_0$ inversible : $p_0^{-1} = q_0$

⟶ il faut satisfaire

p_0 q_n + p_1 q_{n-1} + ⋯ + p_n q_0 = 0 \\ ⟺ q_n = - q_0 (p_1 q_{n-1} + ⋯ + p_n q_0)

⟹ Condition nécessaire et suffisante que $p_0^{-1} = q_0$

  • Algo naïf en $O(n^2)$ pour le calcul des $n$ premiers termes.

⟶ on va pour faire en $O(n \log n \log \log n)$


$n$ puissance de $2$.

P = \underbrace{P_0}_{ ≝ \sum\limits_{ i < n/2 } p_i X^i} + \underbrace{P_1}_{ ≝ \sum\limits_{ n/2 ≤ i < n } p_i X^i} + P_2

et

Q = \underbrace{Q_0}_{ ≝ \sum\limits_{ i < n/2 } q_i X^i} + \underbrace{Q_1}_{ ≝ \sum\limits_{ n/2 ≤ i < n } q_i X^i} + Q_2
\begin{align*} & PQ_0 + PQ_1 + PQ_2 = 1 \\ &⟺ PQ_0 = 1 - PQ_1 - PQ_2 \\ &⟺ PQ_0^2 = Q_0 - PQ_0Q_1 - PQ_0Q_2 \\ &⟺ PQ_0^2 = Q_0 - (1 - PQ_1 - PQ_2 ) Q_1 - PQ_0Q_2 \\ &⟺ PQ_0^2 = Q_0 - Q_1 + PQ_1^2 + PQ_1Q_2 - PQ_0Q_2 \\ \end{align*}
Q_1 = Q_0 + PQ_1^2 + PQ_1Q_2 - PQ_0Q_2 - PQ_0^2

Soit,

  • pour les $n/2$ premiers termes :

    Q_1 = Q_0 - PQ_0^2
  • pour les termes entre $n/2$ (large) et $n$ (strict) :

    Q_1 = - PQ_0^2

Soit, pour les $n$ premiers termes :

Q_1 = -(P_0 + P_1)Q_0^2

NB : l’intuition vient de $q_1 = -p_1 q_0^2$

Inversion de série formelle

def Inverse(P,n):
  if n==1:
    renvoyer P_0^{-1}
  else:
    Q_0 = Inverse(P, n//2)
    R = Produit(Q_0, Q_0, n//2)
    return Produit(-(P_0 + P_1), R)
T(n) ≤ T(n/2) + cn \log(n) \log\log n \\ ≤ cn \log(n) \log\log n + c(n/2) \log(n/2) \log\log(n/2) + ...\\ ≤ 2cn \log(n) \log\log n

Division Euclidienne

  • $P$ de degré $n$
  • $D$ de degré $m$, $d_m$ inversible
P = QD + R

Algo naïf en $O((n-m+1)m)$

Si $m = n/2$ : quadratique !

⟶ on peut faire mieux


On introduit une autre indéterminée :

T ≝ \frac 1 X

\frac{P}{X^n} = \frac{Q}{X^n}\frac{D}{X^n} + \frac{R}{X^n}
\frac{P}{X^n} = \sum\limits_{ i≤n } p_i X^{i-n} = \sum\limits_{ i≤n } p_{n-i} T^{i}

Donc

  • $\frac{P}{X^n}$ : polynôme en $T$ de degré $n$

  • $\frac{Q}{X^n}$ : polynôme en $T$ de degré $n-m$

  • $\frac{D}{X^n}$ : polynôme en $T$ de degré $m$

  • $\frac{R}{X^n}$ : polynôme en $T$ de degré $n$

\widetilde{P} = \widetilde{Q} \widetilde{D} + \widetilde{R}

Avec $\widetilde{d_0} = d_m$

\widetilde{P}\widetilde{D}^{-1} = \underbrace{\widetilde{Q}}_{\deg ≤ n-m} + \underbrace{\widetilde{R}\widetilde{D}^{-1}}_{\text{ coeff de degré supérieur à } n-m+1}

⟶ On fait la division euclidienne en $O(n \log n \log \log n)$

\widetilde{Q} =\widetilde{P}\widetilde{D}^{-1}

réduit aux $n-m+1$ premiers termes

Puis : une fois qu’on a $Q$ à partir de $\widetilde{Q}$, on retrouve $R = P - QD$

Leave a Comment