Apprendre Maple

[hd5hiero]

Algorithme de Prepata et Sarwate
C'est la version amélioré de l'agorithme de Csanky
Entrée: matrice carrée A
Sortie: polyn. caract(A), Adj(A), Inverse(A)
_________________
Salut, je suis quelqu'un de trÃf¨s passionnÃfé aux maths sur
les methodes de calcul sur ordinateur et c'est Ãf cause de Ãf§a que je visite frequemment votre site ............

[hd5hiero]

Algorithme de Preparata et Sarwate
on utilise les memes hypothses que pour Le Verrier. Soit A une matrice carrée n*n.
L'amélioration apportée par Preparata et Sarwate à Csanky provient du fait que pour
calculer les traces s[k]=Tr(A^k) 1<=k<=n, on a pas besion de calculer toutes les puissances de A. Il suffit, si on pose p=ceil(sqrt(n)), de disposer des 2p matrices : In, A, A^2, ... ,A^(p-1) et A^p=B, ..., A^(p^2) .
Ce qui revient à calculer les 2p-2 puissances de de matrices n*n au lieu de n-1 puissance de A .IL fait appel pour cela à 2 procédure recursives notées Powers(A,r) et Superpowers(A,r) permettant de calculer les puissances successives d'une matrice A jusqu' à l'ordre r.
Les traces seront obtenue en considerant les matrices Uj 1<=j<=n definies par:
Uj=LjCj ou Lj est la matrice formée des j-ème lignes des p matrices In, A, ..., A^(p-1)et Cj la matrice formée des j-ème colonnes des autres matrices A^p, A^2P, ..., A^(p^2).
Les matrices Uj sont des matrices carrées d'ordre p dont les p^2 coefficients ne sont autres que les j-èmes éléments diagonaux des matrices A^p, A^2P, ..., A^(p^2).
Plus précisement l' élément U_kl^[j] qui est en position (k,l) dans Uj et qui est obtenue par multiplication de la j-ème ligne de la matrice A^(k-1) par la j-ème colonne de A^pl est donc le j-ème élément diagonaux du produit A^k-1*A^pl =A^(pl+k-1) c-à-d
U_kl^[j] = a_jj^[j] pour 1<=k,l<=p.
Si on désigne par a_rs^[m] l'élément en position (r,s) de A^m .En posant m= pl+k-1 , on obtient avec les notations ci-dessus et pour
p<=m<=p^2+p-1, Tr(A^m) = sum_j=1..n a_jj^[m] = Sum_j=1 à n U_kl^[j].
(ou l et k-1 sont resp. le quotient et le reste de la division de m par p)
Comme A, ..., A^(p-1) sont déjà disponible , cela nous donne en fin de compte les traces de toutes les puissances A, ..., A^(p-1),A^p, A^2P, ..., A^(p^2) donc celles de toutes les puissances A,..., A^n puisque p^2+ p -1>=n +sqrt(n)-1>=n.
D'ou l'algorithme de Preparata & Sarwate.
avant de donner l'algorithme on va voir les sous procedures utilisées dans ce algorithme .Il s'agit de Powers et Superpowers qui sont definies de manière recursive.Chacune des sous procedure prend en entrée une matrice A etr un entier p>1 et donne en sortie la matrice rectangulaire n*np formée desz p puissances de A.

Superpowers(A, p)

s:=floor(p/r); q:=p-rs;
[A|...|A^s]=powers(A,s);
pour kde 1 à r-1 faire A^sr*powers(A,s);
Powers(A,s) pour k de 1 à q faire A^sr*[A|...|A^q]:
m:=ceil(s/2);
[A|...|A^m]=Powers(A,m);
pour i de m+1 à s faire A^i:=A^floor(i/2)*A^ceil(i/2):

Entrée: une matrice A
Sortie: le vecteur c des coefficient du polynome caracteristique de A
Les étapes de calcul avec p= ceil(sqrt(n))
1. calculer les puissances A,..,A^p en appelant Superpowers(A,p);
2. calculer les puissances A^p,...,A^(p^2) en appelant Superpowers(A^p,p);
3.calculer en parallèle les n produits Uj=LjCj , 1<=j<=n;
4. Former le vecteur s et la matrice triangulaire S en calculant en parallèle , à partir des matrices Uj= (u_kl^[j] obtenues à
l'étaoe précédente, les n traces s_m=sum_j=1àn u_kl^[j] 1<= m <= n .On prendra , pour chaque valeur m , l=floor(m/p)
et k= m+1-lp;
5. calculer S^-1 ;
6. calculer le produit S^-1vect(s)= vect(c);


Si avez d'autre chose à me demander , n'hesitez pas, encore Merci.
_________________
Salut, je suis quelqu'un de trÃf¨s passionnÃfé aux maths sur
les methodes de calcul sur ordinateur et c'est Ãf cause de Ãf§a que je visite frequemment votre site ............

[hd5hiero]

Merci AMI
merci encore
:lol:



---

Découvre la liste des meilleurs casinos cashlib : https://www.critiquejeu.info/paiement-casino-cashlib/
_________________
Salut, je suis quelqu'un de trÃf¨s passionnÃfé aux maths sur
les methodes de calcul sur ordinateur et c'est Ãf cause de Ãf§a que je visite frequemment votre site ............