Comptage d'opérations, calcul de $A^{-1}$
Salut! (:P)
Voici la situation qui me pose problème. :-S
Assumons que nous voulons calculer l'inverse de $A,\ AX=I$ auquel cas $A^{-1} = X$.
Comment démontrer que ce calcul va me prendre $n^3$ multiplications/divisions et $n^3-n^2$ additions/soustractions ? (À noter que la factorisation est connue ; ne
pas tenir compte de la structure particulière du membre de droite $I $).
Merci de m'aider, je galère de fouu :-D
Voici la situation qui me pose problème. :-S
Assumons que nous voulons calculer l'inverse de $A,\ AX=I$ auquel cas $A^{-1} = X$.
Comment démontrer que ce calcul va me prendre $n^3$ multiplications/divisions et $n^3-n^2$ additions/soustractions ? (À noter que la factorisation est connue ; ne
pas tenir compte de la structure particulière du membre de droite $I $).
Merci de m'aider, je galère de fouu :-D
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Tu n'as pas dit comment tu vas pratiquer ce calcul, quel algorithme tu utilises ...
Cordialement.
Bon travail personnel !
1) la complexité dépend de l'algorithme utilisé
2) la meilleure complexité possible n'est pas connue mais on peut la majorer par $O(n^{2,4})$
Du coup il faut que tu précises quelle est ta "vraie" question.
Quand tu parles de l'algorithme utilisé, par exemple factorisation LU? Si c'est ça, oui il en est question dans le cours en question liée à ma question.
Désolé si je ne suis pas claire!
On te dit que le nombre d'opérations dépend de l'algorithme (car non ce n'est pas toujours proportionnel à $n^3$). Donc si tu ne précises pas exactement l'algorithme utilisé (et pas juste "oui mon cours parle vaguement d'un truc qui ressemble de loin à une partie d'un algorithme pouvant éventuellement être utilisée pour inverser une matrice), ta question n'a pas de sens. Sachant qu'en plus tu veux pas juste la complexité, tu veux carrément les nombre exact d'opérations de chaque type, il faut vraiment le détail.
Comme ta question n'a pas de sens, elle n'obtient pas de réponse.
Si c'est un exercice, la question n'est sûrement pas "Calculer le nombre d'opérations nécessaires pour inverser une matrice" sans aucun contexte.
Si c'est une question personnelle, comme je te disais la complexité dépend de l'algorithme utilisé.
Oublions l'inversion de matrice.
Tu as 2 matrices carrées A et X, de dimension n toutes les 2.
Tu veux calculer le produit de ces 2 matrices P = A *X
Combien de multiplications ,et d'addition pour ce calcul ?
On va décomposer en trois étapes :
- P est une matrice de quelle taille ?
- Pour chaque élément de P combien d'opérations sont nécessaires ?
- Conclure.
[Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
B-) super pertinent !
[Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
Merci d'avoir pris le temps de répondre (:P)
Au passage on est quand même trois à t'avoir dit que ta question n'est pas claire, aide toi toi-même avant d'attendre des autres qu'ils comprennent magiquement ta question.
Et personne ne te doit rien sur ce forum, on n'est pas payé pour répondre aux questions, on donne déjà suffisamment de notre temps, on a encore le droit de ne pas passer du temps sur une question mal écrite.