Komputeralgebrai algoritmusok
J\303\241rai Antal
Ezek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak.
1. T\303\266rt\303\251net
3. Norm\303\241l form\303\241k, reprezent\303\241ci\303\263
5. K\303\255nai marad\303\251kol\303\241s
6. Newton-iter\303\241ci\303\263, Hensel-felemel\303\251s
7. Legnagyobb k\303\266z\303\266s oszt\303\263
8. Faktoriz\303\241l\303\241s
10. Gr\303\266bner-b\303\241zisok
11. Racion\303\241lis t\303\266rtf\303\274ggv\303\251nyek integr\303\241l\303\241sa
restart;
A 11.1. Algoritmus.
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
SquareFree:=proc(a,x) local i,out,b,c,y,z,w;
i:=1; out:=[]; b:=diff(a,x);
c:=gcd(a,b); w:=quo(a,c,x);
while c<>1 do
y:=gcd(w,c);
z:=quo(w,y,x);
out:=[op(out),z];
i:=i+1;
w:=y; c:=quo(c,y,x);
od; out:=[op(out),w]; end;
SquareFree((-12*x^3+9*x+3)/(-12),x);
sqrfree(-12*x^3+9*x+3);
PolynomialDiophant:=proc(a,b,r,x) local y,z,q;
gcdex(a,b,x,'y','z'); q:=quo(y*r,b,x);
[expand(y*r-q*b),expand(z*r+q*a)] end;
PartialFractions1:=proc(r,L,x) local a,b,l,i,c;
l:=nops(L); if l<2 then return([[r,L[1]]]) fi;
a:=1; for i to l-1 do a:=a*L[i]^i od; b:=L[l]^l;
c:=PolynomialDiophant(a,b,r,x);
[op(PartialFractions1(c[2],L[1..l-1],x)),[c[1],L[l]]];
end;
PartialFractions2:=proc(r,q,e,x) local a,b,l,i,u,v;
if e<2 then return([r]) fi;
u:=quo(r,q,x,v);
[op(PartialFractions2(u,q,e-1,x)),v];
end;
PartialFractions:=proc(r,L,x) local i,LL,LLL;
LL:=PartialFractions1(r,L,x); LLL:=[];
for i to nops(LL) do
LLL:=[op(LLL),[LL[i][2],PartialFractions2(LL[i][1],LL[i][2],i,x)]];
od; end;
HermiteReduction:=proc(p,q,x) local pp,rp,r,qq,ip,i,qi,ri,n,c;
pp:=quo(p,q,x); r:=rem(p,q,x);
qq:=SquareFree(q,x);
r:=PartialFractions(r,qq,x);
rp:=0; ip:=0;
for i to nops(r) do
qi:=r[i][1]; ri:=r[i][2]; n:=i;
while n>1 do
if ri[n]<>0 then
c:=PolynomialDiophant(qi,diff(qi,x),ri[n],x);
rp:=rp-c[2]/(n-1)/qi^(n-1);
ri[n-1]:=ri[n-1]+c[1]+diff(c[2],x)/(n-1);
fi; n:=n-1;
od;
ip:=ip+ri[1]/qi;
od; rp+int(pp,x)+Int(ip,x); end;
E 11.4. P\303\251lda.
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
fp:=441*x^7+780*x^6-2861*x^5+4085*x^4+7695*x^3+3713*x^2-43253*x+24500;
fq:=9*x^6+6*x^5-65*x^4+20*x^3+135*x^2-154*x+49;
fp:=fp/9; fq:=fq/9; fr:=rem(fp,fq,x); f:=fp/fq;
qq:=SquareFree(fq,x);
PartialFractions1(fr,qq,x);
PartialFractions2(392+441*x^2-882*x,x-1,4,x);
PartialFractions(fr,qq,x);
convert(f,parfrac,x,sqrfree);
PolynomialDiophant(x+7/3,1,294,x);
int(294/(x+7/3)^2,x);
int(441/(x-1)^2-49/(x-1)^4,x);
HermiteReduction(fp,fq,x);
A 11.2. Algoritmus.
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
HorowitzReduction:=proc(p,q,x) local pop,pp,d,b,m,n,a,aa,c,cc,r,i,j,e,s;
pop:=quo(p,q,x); pp:=rem(p,q,x);
d:=gcd(q,diff(q,x)); b:=quo(q,d,x);
m:=degree(b); n:=degree(d);
aa:=sum(a[i]*x^i,i=0..m-1);
cc:=sum(c[i]*x^i,i=0..n-1);
r:=expand(b*diff(cc,x)-cc*quo(b*diff(d,x),d,x)+d*aa);
for i from 0 to m+n-1 do e[i]:=coeff(pp,x,i)=coeff(r,x,i); od;
s:=solve([e[j]$j=0..m+n-1],[a[j]$j=0..m-1,c[j]$j=0..n-1]);
aa:=sum(a[j]*x^j,j=0..m-1); aa:=subs(op(s),aa);
cc:=sum(c[j]*x^j,j=0..n-1); cc:=subs(op(s),cc);
cc/d+Int(pop,x)+Int(aa/b,x);
end;
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn