Algorithmique 2 : Séries Formelles

Séries Formelles

P ≝ \sum_{n \geq 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 $\exists Q$ tq $P Q = 1$ ?

Condition nécessaire : $p_{0}$ inversible : $p_{0}^{- 1} = q_{0}$

⟶ il faut satisfaire

\begin{matrix} p_{0} q_{n} + p_{1} q_{n - 1} + \dots + p_{n} q_{0} = 0 \\ ⟺ q_{n} = - q_{0} (p_{1} q_{n - 1} + \dots + p_{n} q_{0}) \end{matrix}

⟹ 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 = \underset{≝ \sum_{i < n / 2} p_{i} X^{i}}{\underset{⏟}{P_{0}}} + \underset{≝ \sum_{n / 2 \leq i < n} p_{i} X^{i}}{\underset{⏟}{P_{1}}} + P_{2}

Q = \underset{≝ \sum_{i < n / 2} q_{i} X^{i}}{\underset{⏟}{Q_{0}}} + \underset{≝ \sum_{n / 2 \leq i < n} q_{i} X^{i}}{\underset{⏟}{Q_{1}}} + Q_{2}

\begin{aligned} P Q_{0} + P Q_{1} + P Q_{2} = 1 \\ ⟺ P Q_{0} = 1 - P Q_{1} - P Q_{2} \\ ⟺ P Q_{0}^{2} = Q_{0} - P Q_{0} Q_{1} - P Q_{0} Q_{2} \\ ⟺ P Q_{0}^{2} = Q_{0} - (1 - P Q_{1} - P Q_{2}) Q_{1} - P Q_{0} Q_{2} \\ ⟺ P Q_{0}^{2} = Q_{0} - Q_{1} + P Q_{1}^{2} + P Q_{1} Q_{2} - P Q_{0} Q_{2} \end{aligned}

Q_{1} = Q_{0} + P Q_{1}^{2} + P Q_{1} Q_{2} - P Q_{0} Q_{2} - P Q_{0}^{2}

Soit,

pour les $n / 2$ premiers termes :
$Q_{1} = Q_{0} - P Q_{0}^{2}$
pour les termes entre $n / 2$ (large) et $n$ (strict) :
$Q_{1} = - P Q_{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)

\begin{matrix} T (n) \leq T (n / 2) + c n \log (n) \log \log n \\ \leq c n \log (n) \log \log n + c (n / 2) \log (n / 2) \log \log (n / 2) + . . . \\ \leq 2 c n \log (n) \log \log n \end{matrix}

Division Euclidienne

$P$ de degré $n$
$D$ de degré $m$ , $d_{m}$ inversible

P = Q D + 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_{i \leq n} p_{i} X^{i - n} = \sum_{i \leq 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$

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

Avec $\tilde{d_{0}} = d_{m}$

⟹ $\tilde{P} {\tilde{D}}^{- 1} = \underset{\deg \leq n - m}{\underset{⏟}{\tilde{Q}}} + \underset{coeff de degré supérieur à n - m + 1}{\underset{⏟}{\tilde{R} {\tilde{D}}^{- 1}}}$

⟶ On fait la division euclidienne en $O (n \log n \log \log n)$
$\tilde{Q} = \tilde{P} {\tilde{D}}^{- 1}$

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

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

Share on

Twitter Facebook Google+ LinkedIn

Séries Formelles

Inversion de série formelle

Division Euclidienne

Share on

Leave a comment