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