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

Réponses

  • Bonjour.

    Tu n'as pas dit comment tu vas pratiquer ce calcul, quel algorithme tu utilises ...

    Cordialement.
  • En toute honnêteté, j'en ai aucune idée. La seule chose que je vois c'est l'élimination de Gauss, mais comment déterminer le nombre d'opérations, aucune idée. J'espère que quelqu'un saura m'aider.
  • Eh bien, si tu procèdes ainsi, regarde sur un ou deux exemples simples les opérations que tu as faites, puis généralise. C'est ton exercice, c'est à toi de le faire.

    Bon travail personnel !
  • Tu auras du mal à montrer que ça prend $n^3$ opérations pour deux raisons :
    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.
  • Ma vraie question? ::o

    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!
  • Non tu ne l'es pas.

    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é.
  • Je ne suis pas sur de comprendre la question.
    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.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Même pour la multiplication de matrice, ça dépend de l'algorithme utilisé. Mais au moins la définition donne en soi un algorithme puisqu'elle est constructive, même si ce n'est pas la meilleure complexité.
  • Chalk écrivait : http://www.les-mathematiques.net/phorum/read.php?15,2124260,2124358#msg-2124358
    [Inutile de recopier un message présent sur le forum. Un lien suffit. AD]

    B-) super pertinent !
  • lourrran écrivait : http://www.les-mathematiques.net/phorum/read.php?15,2124260,2124366#msg-2124366
    [Inutile de recopier un message présent sur le forum. Un lien suffit. AD]

    Merci d'avoir pris le temps de répondre (:P)
  • Quelle hypocrisie, si tu as quelque chose à dire dis le ici plutôt que de m'invectiver par MP.

    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.
Connectez-vous ou Inscrivez-vous pour répondre.