Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 19-07-2019 12:51:58

Eric_40
Invité

Calculs de coefficients dans Z

Bonjour,

Je cherche à trouver des coefficients entiers signés ki pour une équation de la forme

Y = k1.Val1 + k2.Val2 + ... + kn.Valn

Je dispose des valeurs Val1 à Valn, je connais Y
et je cherche à déterminer tous les ki dans Z répondant à la formule ci-dessus.

J'ai trouvé à résoudre ce problème mais de façon laborieuse, existerait-il des algorithmes ou procédures pour trouver facilement ces coefficients et éventuellement ceux ayant les plus petites valeurs ?

Par exemple, pour Y=371 et Val=(108,102,65,-38), je trouve plusieurs solutions k [tex] \in [/tex] {(7,-1,7,15),  (7,-6,-5,5), (6,-5,-9,-2), (6,-11,1,-1), (5,-5,-5,2), (4,-5(-1(6), (3,-4,-5,-1), (2,-4,-1,3), (0,-3,-1,0)}

Je privilégie le dernier quartet car il contient un maximum de 0 et les coefficients sont de taille la plus petite possible;
J'ai donc 371 = (-3) x 102 + (-1) x 65

n peut avoir jusqu'à 20 valeurs
certaines valeurs peuvent être identiques (en valeur absolue), on peut n'en garder qu'une, ce qui simplifie les recherches.

Le but étant de créer une fonction sous excel VBA qui me retournerait ces coefficients.

J'ai cherché sur le net, on trouve facilement la décomposition en facteurs premiers ou le calcul de PGCD, mais pas ce que je recherche.

Je suis grand ouvert à toute proposition pour la résolution de ce problème et de préférence avec les explications car j'aime bien tout comprendre.

Merci à celles et ceux qui m'accorderont un peu de leur temps pour m'éclairer.
Bonne journée

#2 19-07-2019 13:23:29

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : Calculs de coefficients dans Z

Salut,

il n'y a pas de méthode parfaite, sauf à programmer un outil de calcul, car du fait qu'il y a moins de contraintes que coefficients entiers relatifs à chercher, tu as un nombre conséquent de solutions. C'est ce qu'on appelle le nombre de degrés de liberté, qui est grand dans ton cas.

Notre modérateur yoshi peut te faire ça sous Python je pense, s'il en a le temps et surtout l'envie :-)

C'est un sujet pour un informaticien, pas pour un algébriste.
Bon courage !


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#3 19-07-2019 13:29:14

Eric-40
Membre
Inscription : 19-07-2019
Messages : 5

Re : Calculs de coefficients dans Z

Merci Freddy,

Effectivement, il y a plusieurs possibilités, je cherche les plus petits coefficients
Et effectivement aussi, c'est pour de la programmation

Je me demandais s'il n'y avait pas de l'euclide ou autre par là, ce serait bien leur genre ;)

Python ou un algo m'iraient, j'adapterai en conséquence.

En tout cas, merci d'avoir répondu si vite
Agréable journée

(En même temps, je découvre Latex, c'est sympa ...)

Dernière modification par Eric-40 (19-07-2019 13:30:23)

Hors ligne

#4 21-07-2019 15:26:49

Maenwe
Invité

Re : Calculs de coefficients dans Z

Bonjour,
Je fais juste une petite remarque avant de continuer : J'ai vérifié tes 2 première solutions (j'ai eu la flemme de faire les autres) et la 1ère est fausse et la 2ème bonne.

J'ai fais un programme python pour obtenir des solutions du problème posé, voilà quelques solutions obtenues :
[-7, 1, 7, -15], [-7, 6, 5, -5], [-7, 7, -3, -16], [-6, 0, 11, -8], [-6, 6, 1, -9], [-5, -1, 15, -1], [-5, 0, 7, -12], [-5, 5, 5, -2], [-5, 6, -3, -13], [-4, -1, 11, -5], [-4, 0, 3, -16], [-4, 5, 1, -6], [-4, 6, -7, -17], [-3, -1, 7, -9], [-3, 5, -3, -10], [-2, -2, 11, -2], [-2, -1, 3, -13], [-2, 4, 1, -3], [-2, 5, -7, -14], [-1, -2, 7, -6], [-1, -1, -1, -17], [-1, 4, -3, -7], [0, -2, 3, -10], [0, 3, 1, 0], [1, -8, 9, -13], [1, -3, 7, -3], [1, -2, -1, -14], [2, -9, 13, -6], [2, -8, 5, -17], [2, -3, 3, -7], [2, -2, -5, -18], [3, -9, 9, -10], [3, -4, 7, 0], [3, -3, -1, -11].

Et voici le programme (qui mériterait peut-être d'être optimisé ^^) :


#### Remarque ###
#### Pour augmenter le nombre de solutions obtenues il faut augmenter la valeur de nb_sol
################
   
def verif(S, Coef, y): # Pour vérifier les n_uplet obtenus
    somme = 0
    for i in range(len(Coef)-1) :
        somme = somme + S[i]*Coef[i+1]
    if somme==y:
        return True
    return False
   
y = 371
Coef = [108, 102, 65, -38] #Coeffficient voulu
nb_sol = 11


Coef = [0] + Coef
n = len(Coef) - 1

L = [[[0, y]]] + [[[0,0] for _ in range(nb_sol**(i+1))] for i in range(n)] #[0,1] 0 le quotient 1 le reste
Soustracteur = [-i for i in range(nb_sol)]

for i in range(1, n+1) :
    for k in range(len(L[i])) :
        L[i][k][0] = L[i-1][k//nb_sol][1]//Coef[i] + Soustracteur[k%nb_sol] # On soustrait au quotient obtenu une certaine valeur
        L[i][k][1] = L[i-1][k//nb_sol][1]%Coef[i] - Soustracteur[k%nb_sol]*Coef[i] # On compense ce que l'on a enlevé dans le quotient


V = L[-1]
K = []
for k in range(len(V)) : #On cherche toutes les opérations qui donnent un reste nul
    if V[k][1]==0 :
        K.append([k,V[k][0]])  
   
S = []
for i in range(len(K)):
    k = K[i][0]
    S = [[L[i][k//nb_sol**((n-i))][0] for i in range(1,n+1)]] + S
   
print(S)
 

#5 21-07-2019 15:54:50

Maenwe
Invité

Re : Calculs de coefficients dans Z

J'ai oublié d'expliquer un peu le programme :
Je me suis basé sur l'algorithme d'Euclide pour calculer le PGCD. Normalement lorsque l'on utilise cette algorithme on obtient à la fin un reste qui est égale à 0, ors dans le problème posé ici on a déjà posé ce qui serait normalement la valeur du PGCD, on a donc aucune assurance que "y" soit le PGCD des valeurs dans "Val", j'ai donc créé une liste où j'ai "modifié" le quotient obtenu (c'est le rôle le la liste appelé Soustracteur) pour le premier quotient obtenu et enregistré le couple  "quotient modifié" avec le reste de la division elle aussi "modifiée" en conséquence, et j'ai fait de même pour la deuxième division euclidienne dans l'algorithme d'Euclide, et ainsi de suite.
"nb_sol" est le nombre de modifications que j'applique au 1er quotient obtenu (d'où la remarque en début de programme).

Voici un petit exemple pour aider à comprendre comprendre :
On sait que le 4-uplet : (-7,6,5,-5)* est solution du cas particulier proposé.
En faisant la division euclidienne de 371 par 108 on a :
371 = 3*108 + 47
Sauf que l'on veut que le quotient soit égale à -7 on ajoute donc -10 à 3 :
371 = -7*108 + 47 + 10*108
le nouveau "reste" obtenu est alors 47 + 10*108 = 1127
On répète l'opération en faisant la division de 1127 par 102 :
1127 = 11*102 + 5
Or on veut avoir 6 devant 102, on ajoute donc -5 à 11 :
1127 = 6*102 + 5 + 5*102
le nouveau "reste" obtenu est alors 5 + 5*102 = 515
On répète l'opération en faisant la division de 515 par 65 :
515 = 7*65 + 60
Or on veut avoir 5 devant 65, on ajoute donc -2 à 7 :
515 = 5*65 + 60 + 2*65
le nouveau "reste" obtenu est alors 60 + 2*65 = 190
On répète l'opération en faisant la division de 190 par -38 :
190 = -5*(-38) + 0
Et voilà ! J'espère que vous avez compris la mécanique.

Par curiosité, d'où vient ce problème ?

*NB : Je me suis un peu trompé quand j'ai dit que le 2ème exemple était vraie, en fait il est fait mais au signe près.

#6 21-07-2019 16:24:33

Eric-40
Membre
Inscription : 19-07-2019
Messages : 5

Re : Calculs de coefficients dans Z

Bonjour et merci Maenwe,
effectivement la première solution est fausse : erreur de recopie, le 2ème 7 est en fait -7 soit  (7, -1, -7, 15)

Le viens d'essayer ton programme python, trop trop bien, tu es un chef, il faudra juste que je prenne en compte d'inverser tous les signes.

je vais essayer de le comprendre et ajouter un test de la meilleure solution (celle qui contiendra le maximum de 0, puis dont la somme des coefficients sera au minimum) ou alors, à la place du append :
S'il y a davantage de 0 que dans la dernière solution retenue ou si la somme des coefs est plus petite que la dernière solution retenue, alors on la prend en compte

Après, je rajouterai une nouvelle boucle car le problème complet est de trouver
le 1er nombre en fonction du 2ème au dernier
puis le 2ème en fonction du 3ème au dernier
puis le 3ième en fonction du 4ème au dernier
etc, ... jusqu'à ce que ça bloque, en général, soit ça ne bloque pas, soit ce sont les deux dernières valeurs qui ne sont pas multiple l'une de l'autre, dans ce cas, au lieu de a = kb, je fais k1.a = k2.b, avec k1 = b/pgcd(a,b) et k2 = a/pgcd(a,b)

ceci me sert pour réduire des matrices de grande dimension en vue de calculer leur déterminant rapidement et le plus juste possible, plus d'autres calculs après avoir trouvé le déterminant.
Je tente de faire du VBA car les matrices sont sous excel.

Merci encore et bonne fin de dimanche

Hors ligne

#7 21-07-2019 16:36:48

Maenwe
Invité

Re : Calculs de coefficients dans Z

La deuxième solution que tu as donné est bonne si tu inverses les signes de chaque valeurs : (-7,6,5,-5) fonctionne et normalement (j'ai utilisé une petite fonction, que j'ai mise avec le programme, pour vérifier mes solutions) tu n'as pas besoin d'inverser les signes des solutions que te donne le programme que j'ai écris ;)

Merci, bon weekend à toi aussi.

#8 22-07-2019 15:52:55

Eric-40
Membre
Inscription : 19-07-2019
Messages : 5

Re : Calculs de coefficients dans Z

Bonjour,
Si si, il faut l'inverser car c'est la somme de tout qui doit faire 0 : Y + K1.Val1 + K2.Val2 + … + Kn.Val(n) = 0
Mea culpa, j'ai écrit Y = K1.Val(1) …

J'ai modifié légèrement le python en ajoutant un while, reste à choisir la bonne solution lorsqu'il y en a plusieurs, celle dont la somme des valeur absolue de tous les coefficients est la plus petite.
[0, 3, 0, 3, -2, 1, 0] qui donne 9 dans l'exemple cité


#### Remarque ###
#### Pour augmenter le nombre de solutions obtenues il faut augmenter la valeur de nb_sol
################
     
def verif(S, Coef, y): # Pour vérifier les n_uplet obtenus
     somme = y
     for i in range(len(Coef)-1) :
         somme += S[i]*Coef[i+1]
     if somme==0:
         return True
     return False

S = []
y = -72
Coef = [-44, 35, 30, -26, -16, 13, 4] #Coeffficient voulu

Coef = [0] + Coef
n = len(Coef) - 1
nb_sol = 0

while S == [] :
    nb_sol += 1

    L = [[[0, y]]] + [[[0,0] for _ in range(nb_sol**(i+1))] for i in range(n)] #[0,1] 0 le quotient 1 le reste
    Soustracteur = [-i for i in range(nb_sol)]

    for i in range(1, n+1) :
        for k in range(len(L[i])) :
            L[i][k][0] = L[i-1][k//nb_sol][1]//Coef[i] + Soustracteur[k%nb_sol] # On soustrait au quotient obtenu une certaine valeur
            L[i][k][1] = L[i-1][k//nb_sol][1]%Coef[i] - Soustracteur[k%nb_sol]*Coef[i] # On compense ce que l'on a enlevé dans le quotient

    V = L[-1]
    K = []
    for k in range(len(V)) : #On cherche toutes les opérations qui donnent un reste nul
        if V[k][1]==0 :
            K.append([k,V[k][0]])
         
    S = []
    for i in range(len(K)):
        k = K[i][0]
        S = [[-L[i][k//nb_sol**((n-i))][0] for i in range(1,n+1)]] + S

print(nb_sol)
print(S)
 

Hors ligne

#9 22-07-2019 18:10:21

Maenwe
Invité

Re : Calculs de coefficients dans Z

Bonjour,
Oh d'accord ! Je comprends la correction alors :)
Je n'ai pas pu m'empêcher de faire un nouveau code (par ailleurs bien vue pour le while) :


#### Remarque ###
#### Pour augmenter le nombre de solutions obtenues il faut augmenter la valeur de nb_sol
################
     
def verif(S, Coef, y): # Pour vérifier les n_uplet obtenus
     somme = y
     for i in range(len(Coef)-1) :
         somme += S[i]*Coef[i+1]
     if somme==0:
         return True
     return False

S = []
y = -72
Coef = [-44, 35, 30, -26, -16, 13, 4] #Coeffficient voulu

Coef = [0] + Coef
n = len(Coef) - 1
nb_sol = 0

while S == [] :
    nb_sol += 1

    L = [[[0, y]]] + [[[0,0] for _ in range(nb_sol**(i+1))] for i in range(n)] #[0,1] 0 le quotient 1 le reste
    Soustracteur = [i-nb_sol//2 for i in range(nb_sol)]

    for i in range(1, n+1) :
        for k in range(len(L[i])) :
            L[i][k][0] = L[i-1][k//nb_sol][1]//Coef[i] + Soustracteur[k%nb_sol] # On soustrait au quotient obtenu une certaine valeur
            L[i][k][1] = L[i-1][k//nb_sol][1]%Coef[i] - Soustracteur[k%nb_sol]*Coef[i] # On compense ce que l'on a enlevé dans le quotient

    V = L[-1]
    K = []
    for k in range(len(V)) : #On cherche toutes les opérations qui donnent un reste nul
        if V[k][1]==0 :
            K.append([k,V[k][0]])
         
    S = []
    for i in range(len(K)):
        k = K[i][0]
        S = [[-L[i][k//nb_sol**((n-i))][0] for i in range(1,n+1)]] + S

print(nb_sol)
print(S)
Min = -1
k_min = -1
for i in range(len(S)):
    somme = 0
    for j in range(len(S[i])):
        somme = somme + abs(S[i][j])
    if somme < Min :
        Min = somme
        k_min = i
print("")
print("Minimum en valeur absolue : {} des solutions proposées".format(S[k_min]))
 

J'ai modifié le Soustracteur pour éventuellement accepter plus de solutions et rajouté du code pour trouver le minimum.
J'ai eu une autre idée pour trouver un minimum ""idéal"" voici l'algorithme :


#### Remarque ###
#### Pour augmenter le nombre de solutions obtenues il faut augmenter la valeur de nb_sol
################
     
def verif(S, Coef, y): # Pour vérifier les n_uplet obtenus
     somme = y
     for i in range(len(Coef)-1) :
         somme += S[i]*Coef[i+1]
     if somme==0:
         return True
     return False
 
def find(S):
    somme = 0
    for j in range(len(S[0])):
        somme = somme + abs(S[0][j])    
    Min = somme
    k_min = 0
    for i in range(len(S)):
        somme = 0
        for j in range(len(S[i])):
            somme = somme + abs(S[i][j])
        if somme < Min :
            Min = somme
            k_min = i  
    return S[k_min]

S = []
y = -72
Coef = [-44, 35, 30, -26, -16, 13, 4] #Coeffficient voulu

Coef = [0] + Coef
n = len(Coef) - 1
nb_sol = 0
Sol_prec = Sol = 0
ind = True
repet = 0
while S == [] or  nb_sol-repet < 5:
    nb_sol += 1

    L = [[[0, y]]] + [[[0,0] for _ in range(nb_sol**(i+1))] for i in range(n)] #[0,1] 0 le quotient 1 le reste
    Soustracteur = [i-nb_sol//2 for i in range(nb_sol)]

    for i in range(1, n+1) :
        for k in range(len(L[i])) :
            L[i][k][0] = L[i-1][k//nb_sol][1]//Coef[i] + Soustracteur[k%nb_sol] # On soustrait au quotient obtenu une certaine valeur
            L[i][k][1] = L[i-1][k//nb_sol][1]%Coef[i] - Soustracteur[k%nb_sol]*Coef[i] # On compense ce que l'on a enlevé dans le quotient

    V = L[-1]
    K = []
    for k in range(len(V)) : #On cherche toutes les opérations qui donnent un reste nul
        if V[k][1]==0 :
            K.append([k,V[k][0]])
         
    S = []
    for i in range(len(K)):
        k = K[i][0]
        S = [[-L[i][k//nb_sol**((n-i))][0] for i in range(1,n+1)]] + S
       
    if S != []:
        if ind :
            Sol = find(S)
            ind = False
        else :
            Sol_prec = Sol
            Sol = find(S)
    else:
        repet = repet + 1

print("Minimum en valeur absolue : {} des solutions proposées.".format(Sol_prec))
 

Pied de page des forums