Je fais face à un problème qui me paraît particulièrement difficile. J'ai essayé tout ce que je pouvais depuis près d'une cinquentaine d'heures sans jamais réussir à le résoudre.
Je travaille sur le livre "Introduction à l'algorithmique", voici ce qu'on y lit à la page 70 :
J'ai voulût entreprendre la démonstration de la validité de cette méthode, autrement dit que la division de deux matrices carrées en blocs de tailles moindres mais identiques entre elles puis le calcul du produit de ces blocs entre eux permettait ensuite d'obtenir le produit matriciel des matrices d'origine ( après quelques additions ).
Je souhaite le faire en procédant de la manière suivante. Comme première étape je me fixe deux coordonnées i,j avec 1 <= i,j <= n et ci,j un élément de la matrice produit C = A*B. Je souhaite ensuite montrer que les calculs indiqués par la méthode vont donner la bonne valeur dans ci,j.
Voici mon raisonnement, j'aimerai que vous me disiez si vous voyez une erreur, je considère également des découpages quelconques c'est à dire qu'on peut couper nos matrices de tailles n en k² matrices de tailles n/k ( je ne me limite pas au cas k = 2 comme dans le livre car je veux faire une démonstration générale ).
Je commence par remarquer que, peu importe les valeurs de i et de j, si on note C' le bloc dans lequel ci,j se trouve, alors les coordonnées de ci,j dans C' sont simplement i modulo n/k, j modulo n/k, puis voici ce que j'en tire :
( Je suis désolé si les photos sont un peu floues j'ai essayé plusieurs fois mais mon matériel me limite, je n'ai pas réussi à faire mieux j'espère que ça ira quand-même )
PS : Je sais que ma méthode de preuve a l'air très compliquée et qu'il y a des façons plus simples de le faire mais je tiens énormément à mener cette démonstration au bout et à réussir à démontrer cette propriété par moi-même même si j'ai besoin d'un peu d'aide pour ça, merci à vous
Je suis bloqué à la fin mais je ne sais même pas si mon raisonnement est correct en lui même, est-ce que vous pourriez m'aider s'il vous plaît ? Est-ce que ça vous semble juste ? Est-ce qu'on peut prouver la dernière étape ?
- Edité par RyanTalbi2 15 août 2022 à 5:48:48
Tentative preuve du produit de matrices en blocs
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
