L’algorithme d’Euclide étendu consiste à calculer la suite de relations
où
dont on tire la relation de Bezout
en prenant \(n\) tel que \(r_n>0\) et \(r_{n+1}=0\).
iquo
et irem
.Sur \(\k[x]\), les fonctions de quotient et reste deviennent quo
et rem
.
En outre, le pgcd n’est défini qu’à un inversible près, et il est préférable de
choisir à chaque étape \(r_k\) unitaire.
L’algorithme s’écrit alors
euclideetendu(a,b):={
local la,lb,uk1,uk,vk1,vk,rk1,rk,qk,r,l;
la:=lcoeff(a); lb:=lcoeff(b);
uk1:=1/la; vk1:=0; rk1:=a/la;
uk:=0; vk:=1/lb; rk:=b/lb;
while(rk!=0) {
qk := normal(quo(rk1,rk));
r := normal(rk1 - qk * rk);
l := lcoeff(r);
if(r==0) {l:=1;}
uk1, uk := uk, (uk1 - qk * uk)/l;
vk1, vk := vk, (vk1 - qk * vk)/l;
rk1, rk := rk, r/l;
};
return(normal([uk1,vk1,rk1]));
}:;
Modifier l’algorithme en ajoutant un troisième argument \(t\) qui fasse retourner le triplet \((u_k,v_k,r_k)\) au dernier rang \(k\) tel que \(\deg(v_k)\leq t\) (avec un déroulement normal si \(t>=deg(a)\)).
euclideetendu(a,b,t):={
local la,lb,uk1,uk,vk1,vk,rk1,rk,qk,r,l;
la:=lcoeff(a); lb:=lcoeff(b);
uk1:=1/la; vk1:=0; rk1:=a/la;
uk:=0; vk:=1/lb; rk:=b/lb;
while(rk!=0 and degree(vk)<=t) {
qk := normal(quo(rk1,rk));
r := normal(rk1 - qk * rk);
l := lcoeff(r);
if(r==0) {l:=1;}
uk1, uk := uk, (uk1 - qk * uk)/l;
vk1, vk := vk, (vk1 - qk * vk)/l;
rk1, rk := rk, r/l;
//print( normal([uk,vk,rk]), normal(rk/vk) );
};
return(normal([uk1,vk1,rk1]));
}:;
Soit \(b(x)=\sum_{k\geq 0} b_k x^k\) une série entière. L’approximant de Padé d’ordre \((m,n)\) de \(b\) est la fraction rationnelle \(r/v\) vérifiant
avec \(r,v\) de degrés \(m\) et \(n\).
Calculer le développement en série entière \(b(x)\) de \(\tan(x)\) au voisinage de \(0\) à l’ordre 9, et le convertir en polynôme (de degré 9).
b := series(tan(x),x,0,10);
b := convert(b,polynom);
Représenter graphiquement \(b(x)\) et \(\tan(x)\) sur \(]-3/2,2[\).
plot([b,tan(x)],x=-3/2..2);
Écrire l’algorithme d’Euclide étendu entre \(x^{10}\) et \(b(x)\), et récupérer tous les couples \(v_k,r_k\) issus de l’algorithme.
v := euclideetendu(x^10,b,1):; normal(v[2]/v[1]);
v := euclideetendu(x^10,b,2):; normal(v[2]/v[1]);
v := euclideetendu(x^10,b,3):; normal(v[2]/v[1]);
v := euclideetendu(x^10,b,4):; normal(v[2]/v[1]);
v := euclideetendu(x^10,b,5):; normal(v[2]/v[1]);
v := euclideetendu(x^10,b,6):; normal(v[2]/v[1]);
v := euclideetendu(x^10,b,7):; normal(v[2]/v[1]);
v := euclideetendu(x^10,b,8):; normal(v[2]/v[1]);
Pour chaque fraction \(r_k/v_k\), tracer la courbe représentative. Que dire de la qualité d’approximation de \(\tan(x)\), comparé à la formule de Taylor ?
Écrire une fonction approx_pade(b,n,m)
qui calcule le \((n,m)\)
approximant de Padé de la série \(b\). Comparer avec la fonction
correspondante xcas.
pade(tan(x),x,9,3);
pade(tan(x),x,9,5);
pade(tan(x),x,9,6);
On considère le corps fini muni d’une racine primitive de l’unité.
>>> Fq := GF(16,'a')
On pose pour l’instant les paramètres
>>> n:= 15; t := 3
Construire un polynôme générateur \(g(x)\) d’un code MDS \(t\)-correcteur.
>>> g = prod(x-a^i for i in range(1,2*t+1))
Écrire une fonction syndrome(y)
qui calcule le syndrome du mot reçu
\(y(x)\).
def syndrome(y):
return sum( y(x=a^l)*x^(l-1) for l in range(1,2*t+1) )
Écrire une fonction pade(B,n,k)
qui, pour un polynôme \(B\) de degré
inférieur à \(n\) retourne un couple R,V
tel que
\(VB\equiv R\bmod x^{n+1}\) avec \(\deg(V)\leq n-k\), \(\deg(R)\leq k\).
def pade(B,n,k):
assert(B.degree()<=n)
x, = B.variables()
A = x^(n+1)
""" extended euclidean algorithm """
u1, u = 1, 0
v1, v = 0, 1
r1, r = A, B
while r.degree() > k:
q, rr = r1.quo_rem(r)
l = rr.leading_coefficient()
r1, r = r, rr/l
u1, u = u, (u1 - q*u)/l
v1, v = v, (v1 - q*v)/l
return r, v
Écrire une fonction corrige(y)
qui corrige le mot reçu \(y\in E\).
def corrige(y):
S = syndrome(y)
if S == 0: return y
R,E = pade(S,2*t-1,t)
T = [ i for i in range(1,n) if E(x=a^(-i))==0 ]
Ep = E.derivative()
e = sum( - R(x=a^(-i))/Ep(x=a^(-i)) * x^i for i in T )
return y+e