--- /tmp/giac-1.6.0.41+dfsg1-1pdkxsfep/debian/giac-doc_1.6.0.41+dfsg1-1_all.deb +++ giac-doc_1.6.0.41+dfsg1-1_all.deb ├── file list │ @@ -1,3 +1,3 @@ │ -rw-r--r-- 0 0 0 4 2020-12-19 14:42:07.000000 debian-binary │ --rw-r--r-- 0 0 0 43812 2020-12-19 14:42:07.000000 control.tar.xz │ --rw-r--r-- 0 0 0 10568568 2020-12-19 14:42:07.000000 data.tar.xz │ +-rw-r--r-- 0 0 0 43852 2020-12-19 14:42:07.000000 control.tar.xz │ +-rw-r--r-- 0 0 0 10565732 2020-12-19 14:42:07.000000 data.tar.xz ├── control.tar.xz │ ├── control.tar │ │ ├── ./md5sums │ │ │ ├── ./md5sums │ │ │ │┄ Files differ ├── data.tar.xz │ ├── data.tar │ │ ├── file list │ │ │ @@ -1915,15 +1915,15 @@ │ │ │ -rw-r--r-- 0 root (0) root (0) 0 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/es/html_mtt │ │ │ -rw-r--r-- 0 root (0) root (0) 0 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/es/html_vall │ │ │ -rw-r--r-- 0 root (0) root (0) 5223 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/es/keywords │ │ │ -rw-r--r-- 0 root (0) root (0) 2267 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/es/xcasex │ │ │ -rw-r--r-- 0 root (0) root (0) 33039 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/es/xcasmenu │ │ │ drwxr-xr-x 0 root (0) root (0) 0 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/fr/ │ │ │ -rw-r--r-- 0 root (0) root (0) 1314973 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/fr/algo.html │ │ │ --rw-r--r-- 0 root (0) root (0) 1625569 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/fr/algo.pdf │ │ │ +-rw-r--r-- 0 root (0) root (0) 1625608 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/fr/algo.pdf │ │ │ -rw-r--r-- 0 root (0) root (0) 5341 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/fr/keywords │ │ │ -rw-r--r-- 0 root (0) root (0) 929 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/giac.js │ │ │ -rw-r--r-- 0 root (0) root (0) 42616 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/giac.tex │ │ │ -rw-r--r-- 0 root (0) root (0) 42678 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/giacfr.tex │ │ │ -rw-r--r-- 0 root (0) root (0) 1072 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/giacworker.js │ │ │ -rw-r--r-- 0 root (0) root (0) 2113587 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/graphtheory-user_manual.pdf │ │ │ -rw-r--r-- 0 root (0) root (0) 3058 2020-12-19 14:42:07.000000 ./usr/share/giac/doc/hevea.sty │ │ ├── ./usr/share/giac/doc/en/cas.ps │ │ │ @@ -11,15 +11,15 @@ │ │ │ %%EndComments │ │ │ %%BeginDefaults │ │ │ %%ViewingOrientation: 1 0 0 1 │ │ │ %%EndDefaults │ │ │ %DVIPSWebPage: (www.radicaleye.com) │ │ │ %DVIPSCommandLine: /usr/bin/dvips -o cas.ps cas.dvi │ │ │ %DVIPSParameters: dpi=600 │ │ │ -%DVIPSSource: TeX output 2020.12.19:2230 │ │ │ +%DVIPSSource: TeX output 2021.10.08:0746 │ │ │ %%BeginProcSet: tex.pro 0 0 │ │ │ %! │ │ │ /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S │ │ │ N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 │ │ │ mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 │ │ │ 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ │ │ │ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize │ │ ├── ./usr/share/giac/doc/en/cascmd_en.ps │ │ │ @@ -10,15 +10,15 @@ │ │ │ %%+ NimbusRomNo9L-ReguItal MSAM10 NimbusMonL-ReguObli CMSY10 CMEX10 │ │ │ %%+ CMMI12 CMR12 CMMI6 CMSY6 CMR6 CMTT10 CMTT8 CMBX10 CMMI7 │ │ │ %%DocumentPaperSizes: a4 │ │ │ %%EndComments │ │ │ %DVIPSWebPage: (www.radicaleye.com) │ │ │ %DVIPSCommandLine: /usr/bin/dvips -o cascmd_en.ps cascmd_en.dvi │ │ │ %DVIPSParameters: dpi=600 │ │ │ -%DVIPSSource: TeX output 2020.12.19:2230 │ │ │ +%DVIPSSource: TeX output 2021.10.08:0747 │ │ │ %%BeginProcSet: tex.pro 0 0 │ │ │ %! │ │ │ /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S │ │ │ N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 │ │ │ mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 │ │ │ 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ │ │ │ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize │ │ ├── ./usr/share/giac/doc/en/casinter.ps │ │ │ @@ -8,15 +8,15 @@ │ │ │ %%DocumentFonts: NimbusRomNo9L-Regu NimbusMonL-Regu NimbusRomNo9L-Medi │ │ │ %%+ CMEX10 CMMI10 CMR10 CMSY10 CMR7 CMSY7 CMMI7 CMMI5 │ │ │ %%DocumentPaperSizes: Letter │ │ │ %%EndComments │ │ │ %DVIPSWebPage: (www.radicaleye.com) │ │ │ %DVIPSCommandLine: /usr/bin/dvips -o casinter.ps casinter.dvi │ │ │ %DVIPSParameters: dpi=600 │ │ │ -%DVIPSSource: TeX output 2020.12.19:2230 │ │ │ +%DVIPSSource: TeX output 2021.10.08:0746 │ │ │ %%BeginProcSet: tex.pro 0 0 │ │ │ %! │ │ │ /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S │ │ │ N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 │ │ │ mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 │ │ │ 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ │ │ │ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize │ │ ├── ./usr/share/giac/doc/fr/algo.pdf │ │ │ ├── pdftotext {} - │ │ │ │┄ error from `pdftotext {} -`: │ │ │ │┄ Syntax Error (161): Unknown operator 'pagesize' │ │ │ │┄ Syntax Error (163): Unknown operator 'width' │ │ │ │┄ Syntax Error (173): Unknown operator 'pt' │ │ │ │┄ Syntax Error (175): Unknown operator 'height' │ │ │ │┄ Syntax Error (179): Unknown operator 'pt' │ │ │ │ @@ -3009,29 +3009,29 @@ │ │ │ │ 55 │ │ │ │ │ │ │ │ Comment générer des clefs │ │ │ │ On choisit p et q en utilisant le test de Miller-Rabin. Par exemple │ │ │ │ p:=nextprime(randint(10^150));q:=nextprime │ │ │ │ (randint(10^200));n:=p*q; │ │ │ │ │ │ │ │ -32680114071606089895466849701303309044548735763911639642130205789349281147446408086430685435 │ │ │ │ +16932044877036119983681387315247557484773054609265621845910656594250284499272203148318747404 │ │ │ │ On choisit un couple de clefs privée-publique en utilisant l’identité de Bézout │ │ │ │ (ou inverse modulaire). Par exemple │ │ │ │ E:=65537; gcd(E,(p-1)*(q-1));d:=iegcd(E, │ │ │ │ (p-1)*(q-1))[0]; │ │ │ │ │ │ │ │ -65537, 1, 1127063409638154232941852219900354544081358422783234881547872127227478018657507209057 │ │ │ │ +65537, 1, −73764558059876810203424982230698358333063228491254610624863782620638544019848548845 │ │ │ │ Ici, on a pris E de sorte que l’exponentiation modulaire rapide à la puissance E │ │ │ │ nécessite peu d’opérations arithmétiques (17), comparé au calcul de la puissance │ │ │ │ d, ceci permet de faire l’opération “publique” plus rapidement (encodage ou vérification d’une signature) si le microprocesseur a peu de ressources (par exemple │ │ │ │ puce d’une carte bancaire). │ │ │ │ a:=randint(123456789);b:=powmod(a,E,n);c:=powmod │ │ │ │ (b,d,n); │ │ │ │ │ │ │ │ -11098824, 349574293562667294264352525164308887476692793255027460300941491988027601668782385110 │ │ │ │ +28393849, 413915650639749916890274720192472978734854576164770928132714680605034408050656368195 │ │ │ │ Sur quoi repose la sécurité de RSA. │ │ │ │ — Difficulté de factoriser n. │ │ │ │ Si on arrive à factoriser n, tous les autres calculs se font en temps polynomial en ln(n) donc la clef est compromise. Il faut bien choisir p et q pour │ │ │ │ que certains algorithmes de factorisation ne puissent pas s’appliquer. Par │ │ │ │ exemple choisir │ │ │ │ │ │ │ │ p:=nextprime(10^100):;q:=nextprime(10^101 │ │ │ │ @@ -3279,23 +3279,23 @@ │ │ │ │ 1. À quelle vitesse votre logiciel multiplie-t-il des grands entiers (en fonction │ │ │ │ du nombre de chiffres) ? On pourra tester le temps de calcul du produit de │ │ │ │ a(a + 1) où a = 10000!, a = 15000!, etc. . Même question pour des polynômes en une variable (à générer par exemple avec symb2poly(randpoly(n)) │ │ │ │ ou avec poly1[op(ranm(.))]). │ │ │ │ n:=100; p:=symb2poly(randpoly(n)):; time(p*p); │ │ │ │  │ │ │ │  │ │ │ │ -100, "Done", 3.4 × 10−5 , 3.31563164 × 10−5 │ │ │ │ +100, "Done", 3.2 × 10−5 , 7.71846932 × 10−5 │ │ │ │ 2. Comparer le temps de calcul de an (mod m) par la fonction powmod et │ │ │ │ la méthode prendre le reste modulo m après avoir calculé an . │ │ │ │ a:=123; n:=456; m:=789; time(powmod(a,n,m │ │ │ │ )); time(irem(a^n,m)); │ │ │ │  │ │ │ │   │ │ │ │  │ │ │ │ -123, 456, 789, 1.0 × 10−6 , 9.8877751999999 × 10−7 , 6.0 × 10−6 , 5.7094609 × 10−6 │ │ │ │ +123, 456, 789, 9.0 × 10−7 , 2.08490218 × 10−6 , 5.0 × 10−6 , 1.204636732 × 10−5 │ │ │ │ Programmez la méthode rapide et la méthode lente. Refaites la comparaison. Pour la méthode rapide, programmer aussi la version itérative utilisant │ │ │ │ la décomposition en base 2 de l’exposant : on stocke dans une variable │ │ │ │ 0 │ │ │ │ 1 │ │ │ │ k │ │ │ │ locale b les puissances successives a2 (mod m), a2 (mod m), ..., a2 │ │ │ │ (mod m), ..., on forme an (mod n) en prenant le produit modulo m de │ │ │ │ @@ -3326,15 +3326,15 @@ │ │ │ │ (c) l’inverse modulaire en ne calculant que ce qui est nécessaire dans l’algorithme de Bézout │ │ │ │ (d) les restes chinois │ │ │ │ 6. Construire un corps fini de cardinal 128 (GF), puis factoriser le polynôme │ │ │ │ x2 − y où y est un élément quelconque du corps fini. Comparer avec la │ │ │ │ √ │ │ │ │ valeur de y. │ │ │ │ GF(2,7); │ │ │ │ -GF (2, k 7 + k 6 + 1, [k, K, g] , undef) │ │ │ │ +GF (2, k 7 + k 3 + 1, [k, K, g] , undef) │ │ │ │ 7. Utiliser la commande type ou whattype ou équivalent pour déterminer │ │ │ │ la représentation utilisée par le logiciel pour représenter une fraction, un │ │ │ │ nombre complexe, un flottant en précision machine, un flottant avec 100 │ │ │ │ décimales, la variable x, l’expression sin(x) + 2, la fonction x->sin(x), │ │ │ │ une liste, une séquence, un vecteur, une matrice. Essayez d’accéder aux │ │ │ │ parties de l’objet pour les objets composites (en utilisant op par exemple). │ │ │ │ a:=sin(x)+2; type(a); a[0]; a[1] │ │ │ │ @@ -3408,15 +3408,15 @@ │ │ │ │ 3.14. EXERCICES SUR TYPES, CALCUL EXACT ET APPROCHÉ, ALGORITHMES DE BASES63 │ │ │ │ 14. Que se passe-t-il si on essaie d’appliquer l’algorithme de la puissance rapide pour calculer (x + y + z + 1)k par exemple pour k = 64 ? Calculer le │ │ │ │ nombre de termes dans le développement de (x + y + z + 1)n et expliquez. │ │ │ │ │ │ │ │ time(normal((x+y+z+1)^30)); a:=normal((x+y+z+1 │ │ │ │ )^15):; time(normal(a*a)); │ │ │ │ │ │ │ │ -[0.0052, 0.00496315308] , "Done", [0.015, 0.0153119585] │ │ │ │ +[0.0062, 0.01551417428] , "Done", [0.023, 0.0527491635] │ │ │ │ │ │ │ │ 15. Programmation de la méthode de Horner │ │ │ │ Il s’agit d’évaluer efficacement un polynôme │ │ │ │ │ │ │ │ P (X) = an X n + ... + a0 │ │ │ │ │ │ │ │ en un point. On pose b0 = P (α) et on écrit : │ │ │ │ @@ -5729,21 +5729,24 @@ │ │ │ │ approchée. On a alors au moins une racine de Q dans le disque de centre │ │ │ │ z et de rayon degre(Q)/m, Si les disques obtenus sont disjoints, on a ainsi │ │ │ │ une localisation certifiée des racines complexes. │ │ │ │ Q:=randpoly(5); M:=companion(Q); P,S:=schur(M):; S │ │ │ │  │ │ │ │  │ │ │ │  │ │ │ │ +x +78x +85x +59x −71x−18,  │ │ │ │ + │ │ │ │ + │ │ │ │ 5 │ │ │ │ + │ │ │ │ 4 │ │ │ │ + │ │ │ │ 3 │ │ │ │ + │ │ │ │ 2 │ │ │ │ -x +85x +97x −84x −97x−17,  │ │ │ │ - │ │ │ │ - │ │ │ │ │ │ │ │ 0 │ │ │ │ 1 │ │ │ │ 0 │ │ │ │ 0 │ │ │ │ 0 │ │ │ │ │ │ │ │ @@ -5755,38 +5758,36 @@ │ │ │ │ │ │ │ │ 0 │ │ │ │ 0 │ │ │ │ 0 │ │ │ │ 1 │ │ │ │ 0 │ │ │ │ │ │ │ │ -0 17 │ │ │ │ -0 97 │ │ │ │ -0 84 │ │ │ │ -0 −97 │ │ │ │ -1 −85 │ │ │ │ - │ │ │ │ - │ │ │ │ - │ │ │ │  │ │ │ │ - │ │ │ │ -1.0375968548166 │ │ │ │ - −4.0657581468206 × 10−20 │ │ │ │ - │ │ │ │ + │ │ │ │ +0.65902447382653 │ │ │ │ +0 │ │ │ │ +0 18 │ │ │ │ + −2.168404344971 × 10−19 │ │ │ │ +− │ │ │ │ +0 71  │ │ │ │  │ │ │ │  │ │ │ │ - , "Done",  │ │ │ │ -0.0 │ │ │ │ -−1. │ │ │ │ + 7.457906640952 × 10−16 −3.3 │ │ │ │ +0 −59  │ │ │ │ +, │ │ │ │ +"Done", │ │ │ │  │ │ │ │  │ │ │ │  │ │ │ │  │ │ │ │ 0.0 │ │ │ │ -2.1139773926638 × 10−26 −5. │ │ │ │ +0 −85 │ │ │ │ +1 −78 │ │ │ │ +1.3527197513304 × 10−19 −6.0 │ │ │ │ │ │ │ │ P*S*trn(P); P*trn(P); │ │ │ │ 1. cela se fait par une méthode itérative appelée algorithme de Francis. On pose A0 , la forme de │ │ │ │ Hessenberg de M , puis on factorise An = QR par des symétries de Householder ou des rotations │ │ │ │ de Givens et on définit An+1 = RQ, le calcul de An+1 en fonction de An se fait sans expliciter la │ │ │ │ factorisation QR │ │ │ │ │ │ │ │ @@ -5797,35 +5798,35 @@ │ │ │ │  │ │ │ │  │ │ │ │  │ │ │ │  │ │ │ │  │ │ │ │  │ │ │ │ │ │ │ │ -1.4003728901577 × 10−15 −8.7079391549068 × 10−16 4.3454823073219 × 10−16 │ │ │ │ +−4.7923535968872 × 10−17 −1.2412759622243 × 10−16 1.9905951886834 × 10−16 │ │ │ │ 0.99999999999999 │ │ │ │ -−9.3292886436946 × 10−16 4.0245584642662 × 10−16 │ │ │ │ -3.3248605454397 × 10−16 │ │ │ │ +4.7961309403155 × 10−15 −9.6277152916713 × 10−16 │ │ │ │ +9.9248946836331 × 10−16 │ │ │ │ +0.99999999999999 │ │ │ │ +−1.568190022283 × 10−15 │ │ │ │ +−16 │ │ │ │ +−16 │ │ │ │ +−1.4727277150616 × 10 │ │ │ │ +−1.1793409131211 × 10 │ │ │ │ 0.99999999999999 │ │ │ │ -2.2291196666302 × 10−15 │ │ │ │ -−15 │ │ │ │ -−15 │ │ │ │ -−1.881321162224 × 10 │ │ │ │ -2.4300765393004 × 10 │ │ │ │ -0.99999999999998 │ │ │ │ −17 │ │ │ │ −17 │ │ │ │ -−5.7359377122167 × 10 │ │ │ │ -1.5531196120855 × 10 │ │ │ │ -−1.9949319973733 × 10−16 │ │ │ │ +−4.1237799037076 × 10 │ │ │ │ +4.336808689942 × 10 │ │ │ │ +−1.1102230246252 × 10−16 │ │ │ │ │ │ │ │ l:=proot(Q); z:=exact(l[0]); evalf(degree │ │ │ │ (Q)*Q(x=z)/Q’(x=z),20) │ │ │ │ │ │ │ │ -[−83.831123372906, −1.3497016952198, −0.62513851727829, −0.23163326941174, 1.03759 │ │ │ │ +[−76.904869696324, −0.76567241057147 − 1.0038548259169i, −0.76567241057147 + 1.003 │ │ │ │ │ │ │ │ On peut aussi utiliser l’arithmétique d’intervalles pour essayer de trouver │ │ │ │ un petit rectangle autour d’une racine approchée qui est conservé par la │ │ │ │ méthode de Newton g(x) = x − f (x)/f 0 (x), le théorème du point fixe de │ │ │ │ Brouwer assure alors qu’il admet un point fixe qui n’est autre qu’une racine │ │ │ │ de g. │ │ │ │ │ │ │ │ @@ -16373,15 +16374,15 @@ │ │ │ │ f(t):=exp(-t^2); n:=1000; a:=0; b:=2.0;l:=ranv │ │ │ │ (n,uniformd,a,b):; │ │ │ │ 2 │ │ │ │ │ │ │ │ t 7→ e−t , 1000, 0, 2.0, "Done" │ │ │ │ │ │ │ │ (b-a)*sum(apply(f,l))/n; int(f(t),t,a,b); │ │ │ │ -0.874646157016, 0.882081390762 │ │ │ │ +0.900474573238, 0.882081390762 │ │ │ │ La convergence en fonction de n est assez lente, on peut l’observer en faisant plusieurs estimations : │ │ │ │ │ │ │ │ I:=seq(2*sum(apply(f,ranv(n,uniformd,a,b │ │ │ │ )))/n,500); │ │ │ │ │ │ │ │ 20.11. MÉTHODES PROBABILISTES. │ │ │ │ │ │ │ │ @@ -16416,15 +16417,15 @@ │ │ │ │ │ │ │ │ 2 │ │ │ │ │ │ │ │ par exemple ici │ │ │ │ │ │ │ │ 2*sqrt(int(f(t)^2,t,0,2.)/2-(1/2*int(f(t │ │ │ │ ),t,0,2.))^2)/sqrt(n); stddevp(I); │ │ │ │ -0.0217983295084, 0.0220781375885 │ │ │ │ +0.0217983295084, 0.0221303061801 │ │ │ │ mais on ne fait pas ce calcul en pratique (puisqu’il faudrait calculer une intégrale), │ │ │ │ √ │ │ │ │ on estime l’écart-type σ/ n de la loi normale par l’écart-type de l’échantillon des │ │ │ │ estimations stddevp(I). │ │ │ │ │ │ │ │ histogram(I,0,0.01); plot(normald(mean(I │ │ │ │ ),stddevp(I),x),x=0.8..1) │ │ │ │ @@ -16438,15 +16439,15 @@ │ │ │ │ │ │ │ │ 2 │ │ │ │ │ │ │ │ t 7→ e−t , 1000, 0, 2.0, "Done" │ │ │ │ │ │ │ │ fl:=apply(f,l):;m:=(b-a)*mean(fl);s:=(b-a │ │ │ │ )*stddevp(fl)/sqrt(n);[m-2s,m+2s] │ │ │ │ -"Done", 0.877948916887, 0.021764410809, [0.834420095269, 0.921477738505] │ │ │ │ +"Done", 0.8941582054, 0.0221163205609, [0.849925564278, 0.938390846522] │ │ │ │ Cette méthode converge donc beaucoup moins vite que les quadratures, en dimension 1. Mais elle se généralise très facilement en dimension plus grande en │ │ │ │ conservant la même vitesse de convergence alors que le travail nécessaire pour une │ │ │ │ méthode de quadrature croit comme une puissance de la dimension, et ne nécessite pas de paramétrer des domaines d’intégration compliqués (il suffit par exemple │ │ │ │ d’utiliser la méthode du rejet pour avoir un générateur uniforme dans un domaine │ │ │ │ inclus dans un cube). │ │ │ │ │ │ │ │ 264 │ │ │ │ @@ -20396,25 +20397,25 @@ │ │ │ │ On retrouve ce cas pour une petite perturbation d’une matrice diagonale, par exemple │ │ │ │ │ │ │ │ n:=500;A:=2*idn(n)+1e-4*ranm(n,n,uniformd,-1,1 │ │ │ │ ):;b:=seq(1,n):; │ │ │ │ 500, "Done", "Done" │ │ │ │ │ │ │ │ time(c:=linsolve(A,b)); │ │ │ │ -[0.2, 0.188203432] │ │ │ │ +[0.22, 0.584925606] │ │ │ │ │ │ │ │ time(d:=jacobi(A,b,1e-12,50)); │ │ │ │ -[0.12, 0.119125765] │ │ │ │ +[0.17, 0.415211889] │ │ │ │ │ │ │ │ 318 │ │ │ │ │ │ │ │ CHAPITRE 22. ALGÈBRE LINÉAIRE │ │ │ │ │ │ │ │ maxnorm(d-c) │ │ │ │ -7.95807864051 × 10−13 │ │ │ │ +7.81597009336 × 10−13 │ │ │ │ Pour n assez grand, la méthode de Jacobi devient plus rapide. Cela se vérifie encore │ │ │ │ plus vite si A est une matrice creuse. │ │ │ │ Pour Gauss-Seidel, le calcul de M −1 n’est pas effectué, on résoud directement │ │ │ │ le système triangulaire M xn+1 = b + N xn soit │ │ │ │ (D + L)xn+1 = b − U xn │ │ │ │ Gauss-Seidel est moins adapté à la parallélisation que Jacobi. On adapte le programme précédent │ │ │ │ seidel(A,b,N,eps):={ │ │ │ │ @@ -23473,26 +23474,25 @@ │ │ │ │ │ │ │ │ exp(a); │ │ │ │ 1 + h + h8 order_size (h) │ │ │ │ Pour travailler avec un autre corps de base, il suffit de donner des coefficients dans │ │ │ │ ce corps. Si la caractéristique du corps est assez grande, les fonctions usuelles sont │ │ │ │ aussi applicables. │ │ │ │ GF(11,3); │ │ │ │ -GF (11, k 3 − 2k 2 + k + 5, [k, K, g] , undef) │ │ │ │ +GF (11, k 3 − 5k + 3, [k, K, g] , undef) │ │ │ │ │ │ │ │ 24.8. SÉRIES FORMELLES. │ │ │ │ │ │ │ │ 363 │ │ │ │ │ │ │ │ a:=ln(1+g*h+O(h^6)); │ │ │ │  │ │ │ │  │ │ │ │  │ │ │ │ - │ │ │ │ -(g) h+ 5 · g 2 h2 + (−3 · g 2 − 4 · g + 2) h3 + (2 · g 2 − g − 3) h4 + (2 · g 2 + 4 · g − 3) h5 +h6 order_size (h) │ │ │ │ +(g) h+ 5 · g 2 h2 +((−2 · g − 1)) h3 + (−4 · g 2 − 2 · g) h4 + (−5 · g 2 + 5 · g − 3) h5 +h6 order_size (h) │ │ │ │ exp(a); │ │ │ │ 1 + (g) h + h6 order_size (h) │ │ │ │ Les opérations sur les séries sont implémentées sans optimisation particulière, │ │ │ │ leur utilisation principale dans Xcas étant le calcul de développement de Taylor ou │ │ │ │ asymptotique sur Q. │ │ │ │ │ │ │ │ 364CHAPITRE 24. DÉVELOPPEMENT DE TAYLOR, ASYMPTOTIQUES, SÉRIES ENTIÈRES, FON │ │ │ │ @@ -23930,32 +23930,32 @@ │ │ │ │ g;r:=powmod(g,7,p); │ │ │ │ 3, 2187 │ │ │ │ puis en prenant la puissance 2n−k -ième de r on obtient une racine 2k -ième de 1 qui │ │ │ │ permettra de multiplier deux polynômes dont la somme des degrés est strictement │ │ │ │ inférieure à 2k , par exemple pour a et b de degrés 5 et 7, on prendra k = 4 │ │ │ │ a:=randpoly(5,[]); b:=randpoly(7,[]);w:=powmod │ │ │ │ (r,2^16,p); │ │ │ │ -[1, −14, 38, −28, 96, −96] , [1, 97, −65, 85, −22, −99, 91, −46] , 5712452 │ │ │ │ +[1, 0, −93, 35, −79, −98] , [1, 43, −84, −34, 98, 79, 9, −40] , 5712452 │ │ │ │ on allonge a et b avec des 0 pour les amener à la taille 16 = 2k │ │ │ │ ar:=[op(a),op(seq(0,(16-size(a))))];br:= │ │ │ │ [op(b),op(seq(0,(16-size(b))))] │ │ │ │ -[1, −14, 38, −28, 96, −96, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] , [1, 97, −65, 85, −22, −99, 91, −46, 0, 0, 0, 0, 0, 0, 0, 0] │ │ │ │ +[1, 0, −93, 35, −79, −98, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] , [1, 43, −84, −34, 98, 79, 9, −40, 0, 0, 0, 0, 0, 0, 0, 0] │ │ │ │ on calcule les transformées de Fourier rapide de a et b │ │ │ │ A:=fft(ar,w,p); B:=fft(br,w,p); │ │ │ │ │ │ │ │ -[7340030, 4380647, 6100180, 6080168, 5614030, 2346479, 4068379, 1733441, 273, 3081597, 2123327, 5662520, 1 │ │ │ │ +[7339799, 1795432, 1840634, 6821055, 5793636, 528284, 2408018, 2910213, 7339925, 6604888, 1405320, 113316 │ │ │ │ puis on fait le produit terme à terme et on applique la transformée de Fourier inverse │ │ │ │ C:=irem(A.*B,p); c:=ifft(C,w,p); │ │ │ │ │ │ │ │ -[7339907, 389037, 808605, 6685908, 839818, 341352, 478949, 2922772, 7331297, 3889216, 5733913, 4237644, 64 │ │ │ │ +[7323185, 6401837, 3071106, 965285, 4267383, 7316521, 1875101, 5416276, 2592, 5962322, 435997, 5123979, 31 │ │ │ │ On peut comparer avec le produit calculé par Xcas │ │ │ │ a*b; │ │ │ │ -[1, 83, −1385, 4653, −6302, 14475, −17291, 9934, −3398, −11688, 19528, −13152, 4416] │ │ │ │ +[1, 43, −177, −3998, 9336, −3194, −7873, 6961, −2482, −11810, −9853, 2278, 3920] │ │ │ │ smod(c,p); │ │ │ │ -[1, 83, −1385, 4653, −6302, 14475, −17291, 9934, −3398, −11688, 19528, −13152, 4416, 0, 0, 0] │ │ │ │ +[1, 43, −177, −3998, 9336, −3194, −7873, 6961, −2482, −11810, −9853, 2278, 3920, 0, 0, 0] │ │ │ │ Bien entendu les tailles de a et b prises ici en exemple sont trop petites pour que │ │ │ │ l’algorithme soit efficace. │ │ │ │ │ │ │ │ 370 │ │ │ │ │ │ │ │ CHAPITRE 25. LA TRANSFORMÉE DE FOURIER DISCRÈTE.