Shoutbox

LeSingeMalicieux

New member

Registered: 2015-03-03

Posts: 8

Matrices

Bonjour,

Avant tout, comme c'est mon tout premier message, je tenais à vous remercier pour cet excellent site sur lequel je m'éclate !

Je viens de valider (non sans mal) l'épreuve n°12 Matrices.
Cependant, lorsque je fais tourner mon programme avec les deux matrices données en exemple, je n'obtiens pas le résultat de l'exemple...

Pour rappel on a :
A = [[13,2,5,23][-2,0,1,3][-1,3,7,77]]
B = [[13,-2,1,7][2,3,3,77][99,13,0,777]]

Pour transposée(B) et A*transposée(B), j'obtiens les mêmes résultats que dans l'exemple.

Par contre, pour inverse(A*transposée(B)), j'obtiens :
[[-0.0016389,-0.0088499,0.0008419][-0.0021470,-0.0152358,0.0012328][0.0002284,0.0015965,-0.0001314]]

Suis-je dans l'erreur ? Auquel cas je m'interroge, mon programme semblant correct puisqu'il a validé l'épreuve, et ce à plusieurs reprises.

En vous remerciant.

Metatr0n

Administrator

Registered: 2011-04-24

Posts: 205

Re: Matrices

Bonjour,

tout d'abord merci pour tes encouragements, ça nous fait toujours très plaisir de voir que des gens s'amusent sur notre site ! Sans vous on aurait arrêté de développer µContest depuis longtemps

Après revérifications, je suis sûr que l'exemple de l'épreuve est juste.
Il y a une manière simple de le vérifier.
Si B est l'inverse de A, ça implique que A*B = Id (où Id est la matrice identité).
Appelons M la matrice qu'on doit inverser dans l'exemple, c'est à dire
M = A*transposée(B) = [[331,1818,19184][-4,230,2133][527,5957,59769]]
Jusque là on est tous d'accord.

Si je prends la matrice inverse résultat de l'exemple, sous matlab, quand je les multiplie j'obtiens :
M*[[0.0258444,0.1395566,-0.0132757][0.0338561,0.2402561,-0.0194409][-0.0036022,-0.0251761,0.0020714]] =
[[1,0,0][0,1,0][0,0,1]]
On obtient bien la matrice identité.

Si je prends ta matrice inverse résultat et que je fais la même chose :
M*[[-0.0016389,-0.0088499,0.0008419][-0.0021470,-0.0152358,0.0012328][0.0002284,0.0015965,-0.0001314]] =
[[-0.0641,-0.0007,-0.0009][-0.0001,-0.0635,-0.0001][-0.0021,-0.0023,-0.0662]]
On obtient pas la matrice identité.

Il y a donc un problème dans ton calcul

Metatr0n

Administrator

Registered: 2011-04-24

Posts: 205

Re: Matrices

Mais j'ajouterais que bizarrement la matrice qu'on obtient avec ta matrice résultat ressemble étrangement à la matrice identité. Les nombres sur la diagonale (qui devraient être des 1) sont significativement plus grands que les autres (qui devraient être des 0). C'est comme si ta matrice "marchotte" sans être parfaite.
Ca fait penser à des erreurs d'approximation dans tes calculs.

LeSingeMalicieux

New member

Registered: 2015-03-03

Posts: 8

Re: Matrices

Merci beaucoup pour ta réponse rapide.

En effet ça sent les erreurs d'approximation. Pour info j'ai développé ça en Java en utilisant des doubles pour les valeurs dans mes matrices.
Je vais me repencher là-dessus.

Metatr0n

Administrator

Registered: 2011-04-24

Posts: 205

Re: Matrices

tu as implémenté le pivot de Gauss ? Si oui je crois que c'est un algo très sensible aux erreurs d'approximation

LeSingeMalicieux

New member

Registered: 2015-03-03

Posts: 8

Re: Matrices

Je sais que je n'ai pas utilisé la méthode la plus optimisée, mais non je n'ai pas utilisé de pivot de Gauss.

Je multiplie l'inverse du déterminant par la transposée de la comatrice.
Et pour le calcul du déterminant, une récursivité sur les déterminants des sous-matrices.
Soit beaucoup de calculs, et encore plus de chance d'avoir des approximations.

Mais de toute façon je me rends compte que dans d'autres épreuves, je rencontre aussi des erreurs d'approximations.
Par exemple un résultat qui devrait être 0.5, mais qui est 0.500000001. Et j'avoue que je n'ai pas trop comment gérer ces erreurs (en même temps de ne découvre le Java que depuis trois semaines).

Pas grave, je m'amuse beaucoup quand même

Metatr0n

Administrator

Registered: 2011-04-24

Posts: 205

Re: Matrices

En effet ce n'est pas la méthode la plus optimisée mais j'aurais fait pareil, c'est probablement la plus simple à implémenter.
Mais oui ça fait beaucoup de calculs qui peuvent potentiellement mener à des erreurs.

Pour ce qui est du 0.5 approximé en 0.500000001, c'est tout à fait normal et ce sera le cas dans beaucoup de langages.
Il faut savoir qu'un double est codé en mémoire sur 64 bits, répartis en 1 bit de signe, 52 bits de mantisse et 11 bits d'exposant.
Le nombre correspondant s'obtient avec la formule : n = (-1)^exposant*mantisse*2^(exposant - 1023).
Sur un nombre fini de bits, on peut de manière évidente ne représenter qu'un nombre fini de nombres réels. Beaucoup de nombres ne sont pas représentables avec ce système et c'est le cas de 0.5, qui serra stocké en fait en mémoire par son approximation la plus proche représentable, 0.500000001.

Pour plus d'info tu peux lire cet article :
dans lequel on peut lire :

0.2 : ceci est un exemple d'un des nombreux nombres décimaux qui ne peuvent pas être représentés précisément avec un format binaire en virgule flottante. La mantisse devrait répéter  C à l'infini ;

Bref la plupart du temps ces erreurs sont complètement négligeables

Etoiline

New member

Registered: 2012-05-11

Posts: 2

Re: Matrices

Bonjour,

Tout d'abord bravo pour ce site. Il est beaucoup axé programmation et j'aime bien ça.

J'ai un petit problème avec cette épreuve. Je l'ai codée en python avec la bibliothèque numpy (qui permet de faire des opérations sur les matrices entre autre).
Quand je teste avec l'exemple donné je tombe sur le bon résultat aucun problème mais si je lance avec des données récupérées je tombe sur un "wrong" à chaque fois !

Je regarde depuis un moment et je n'arrive pas à voir ce qui ne va pas.... si quelqu'un pouvait m'indiquer d'où vient l'erreur ou ce qui ne va pas dans mon raisonnement.

Metatr0n

Administrator

Registered: 2011-04-24

Posts: 205

Re: Matrices

Bonjour Etoiline,

merci beaucoup de tes encouragements on apprécie beaucoup .

J'ai consulté les log de tes essais, et j'ai pris au hasard ton dernier.
Les variables étaient les suivantes :

A : [[-5,4,-1,4,5,0,2,-4][-1,3,2,-4,5,-5,-1,-4][-4,5,0,4,-2,0,-2,-4][3,-4,-1,3,-2,4,-1,-3]]
B : [[1,0,-1,-2,0,-5,-5,-4][-4,-1,0,-2,-5,0,1,0][-5,0,4,-1,-2,-5,2,3][4,0,-3,-2,4,2,5,0]]

M attendue : [[-0.023081746869005,0.017796796333997,-0.00081547629690745,0.0069420852182309][-0.066009517508793,-0.005599135607897,-0.0083910403612873,-0.0013946752016021][0.0071068408052334,-0.00088699810211781,-0.0012152321010297,-0.020978239490765][-0.02430528060814,0.0043813491566813,-0.026394739060357,-4.9171241082125E-5]]

M que tu as envoyé : [[0.0192823,-0.0056219,-0.0130199,0.0009605][-0.0056219,0.0174341,0.0019256,0.0108404][-0.0130199,0.0019256,0.0213679,-0.0015853][0.0009605,0.0108404,-0.0015853,0.0232735]]

J'ai utilisé Wolfram Alpha pour vérifier les calculs.
Quand on commence par faire  on obtient :
[[-6, -15, -1, 5][51, -17, 18, 3][14, 11, 4, -42][-5, -5, -49, 4]]

Et quand on en prend l':
[[-0.023082, 0.017797, -0.00081548, 0.0069421][-0.066010, -0.0055991, -0.0083910, -0.0013947][0.0071068, -0.00088700, -0.0012152, -0.020978][-0.024305, 0.0043813, -0.026395, -0.000049171]]

Ceci me laisse penser qu'il y a un soucis avec ta manière de calculer la réponse, car µContest (en tout cas pour cette tentative là) calcule la bonne matrice.

Etoiline

New member

Registered: 2012-05-11

Posts: 2

Re: Matrices

Bonjour Metatron,
merci de ta réponse. Je vais tout reprendre avec l'exemple que tu as donné ça fera une deuxième possibilité de test.

J'y retourne ^^

edit : Oh l'erreur !!!!!!!  En parsant les données récupérées pour les mettre dans un tableau j'ai inversé a et b...... donc forcément quand je rentrais des matrices ça marchait puisque je les mettais directement sous la forme que je voulais.

Last edited by Etoiline (2015-06-14 16:30:14)

Metatr0n

Administrator

Registered: 2011-04-24

Posts: 205

Re: Matrices

Content de voir que tu t'en es sortie !
Félicitations