cherche désespérément formule/algorithme

dike · 21-02-2017 11:21:14

Bonjour tout le monde :)

Je cherche svp une formule/algorithme pour résoudre un cas et je ne sais pas où me tourner, quelqu'un pourrait-il m'aider (si ce n'est qu'en m'indiquant où chercher) ?

Voici ce cas :

J'ai une série de valeurs >=0, que je nomme di (i : 1->n-1). Le problème est de trouver une autre série de valeurs, Ri >=0 (i : 1->n), telles que :

Ri + Ri+1 = di.

Et surtout rien de négatif dans l'histoire merci.

A+ j'espère

:) dike

Dernière modification par dike (21-02-2017 13:24:23)

yoshi · 21-02-2017 13:41:58

Bonjour,

Pour tenter de t'aider, il faudrait déjà éclaircir certains points...

Nous avons n valeurs valant initialement 0 : [tex]R_1=R_2=\cdots = R_n = 0[/tex]
Nous avons n-1 valeurs étant initialement >=0 (peuvent naturellement être différentes) :
[tex]d_1,\; d_2,\;\cdots,\; d_{n-1} \leqslant 0[/tex]
Il faudrait que j'annule tous ces [tex]d_i[/tex] de [tex]i = 1\text{ à } n-1[/tex] en employant la règle suivante :

Jusque-là, ça va...
Mais

Si je fais [tex]R_i = R_i + v (v>0)[/tex]

1. Qu'est-ce que ce v qui arrive là comme un cheveu sur la soupe ? Quel rapport a-t-il avec les $d_i$ et les $R_i$ ?
2. Que signifie[tex] v(v>0)[/tex] ? On fait [tex]R_i=R_i+v[/tex] si v > 0 ?
Déjà, pour i = 1, je vois pas pourquoi effectuer [tex]d_1=d_1-v[/tex] permet d'annuler [tex]d_1[/tex]. On en revient à : qu'est-ce que v ?...

Ensuite, tu souhaiterais un algorithme rédigé
* en "langage naturel"
* dans un langage de programmation précis ? Et lequel ?

@+

dike · 21-02-2017 14:50:35

Bonjour et merci de ta réponse.

J'ai entre-temps reformulé le problème, peut-être que cela n'était pas à jour dans ton navigateur. Voici donc :

J'ai une série de valeurs >=0, que je nomme di (i : 1->n-1). Le problème est de trouver une autre série de valeurs, Ri >=0 (i : 1->n), telles que :

Ri + Ri+1 = di.

Et surtout rien de négatif dans l'histoire merci.

En espérant que ce soit clair. Et en fait de langage, ma préférence serait le perl :)

A+, cordialement,

dike

Yassine · 21-02-2017 23:37:46

Bonsoir,
A partir de la relation $R_{i+1}=d_i - R_i$, on peut établir une formule qui donne $R_i$ en fonction des $d_{j}$ précédents et de $R_1$ :
$R_i=\sum_{j=1}^k (-1)^{j+1} d_{i-j} + (-1)^k R_{i-k}$, soit avec $k=i-1$, $R_i=\sum_{j=1}^{i-1} (-1)^{j+1} d_{i-j} + (-1)^{i-1} R_1$.
Soit encore (changement $k=i-j$) $R_i=\sum_{k=1}^{i-1} (-1)^{k-i+1} d_k + (-1)^{i-1} R_1$
et finalement $R_i = (-1)^i\left(\sum_{k=1}^{i-1} (-1)^{k+1} d_k - R_1 \right)$

La condition $R_i \ge 0$ va imposer une contrainte sur $R_1$ :
Si $i$ pair, alors $R_1 \le \sum_{k=1}^{i-1} (-1)^{k+1} d_k$
Si $i$ impair, alors $R_1 \ge \sum_{k=1}^{i-1} (-1)^{k+1} d_k$

Soit $\max_i \sum_{k=1}^{2i} (-1)^{k+1} d_k \le R_1 \le \min_i \sum_{k=1}^{2i+1} (-1)^{k+1} d_k$

dike · 22-02-2017 09:39:02

Merci beaucoup de cette brillante réponse Yassine,

Et le fait est que j'ai malheureusement omis de préciser quelque-chose, j'en suis navré :(

Je reformule svp :

Nous avons n valeurs valant initialement 0 : R1 .. Rn = 0
Nous avons n-1 valeurs étant initialement >=0 (peuvent naturellement être différentes) : d1 d2 .. dn-1 >=0.

Il faudrait que j'annule tous ces di (i : 1 .. n-1) en employant la règle suivante :

Une augmentation de x d'un Ri entraîne, en plus de la diminution de x de di, une pareille diminution de x de di-1.
Valable pour 1<i<n ; pour i=1 alors que le d1 diminue ; pour i=n alors que dn-1 diminue.

On peut encore signaler qu'en d'autres termes, Ri + Ri+1 = di est également valable.

Il faut qu'en finalité, les Ri soient >=0 (nombres réels)

Merci, A+

dike :-)

Yassine · 22-02-2017 10:53:47

Bonjour,
Je ne suis pas sûr de comprendre alors.
Pourrais-tu adopter une autre notation. Si tu décris un processus itératif, il faudrait avoir deux indices, un pour la dimension ($d_1$ à $d_n$) et un autre pour l'itération. Donc $R_i^0$ indiquera la valeur de $R_i$ au début, à savoir $R_i^0 = 0$.
Exprime alors tes contraintes avec ces nouvelles notations.
Par contre, un passage en Latex me semble indispensable, sinon, on (je) ne va (is) rien comprendre !

dike · 22-02-2017 12:37:10

OK, alors :

Nous avons n valeurs valant initialement 0 : $R_1^0$, $R_2^0$.. $R_n^0$ = 0
Nous avons n-1 autres valeurs étant initialement >=0 (et peuvent être différentes les unes des autres) : $d_1^0$, $d_2^0$ .. $d_{n-1}^0$ >=0.

Il faudrait que - par une formule, un algorithme ou n'importe quel moyen - j'annule toute cette dernière série de valeurs, c'est-à-dire que (disons après l’itération p) : $d_1^p$ = $d_2^p$ = .. = $d_{n-1}^p$ =0.

Je dois à ce sujet respecter/employer la règle suivante (pour une itération k quelconque) :

Si $R_i^{k+1}$ = $R_i^k$ + x (avec x réel, >=0)

Alors $d_i^{k+1}$ = $d_i^k$ - x et $d_{i-1}^{k+1}$ = $d_{i-1}^k$ - x ; valable pour 1<i<n
Pour i=1 : $d_1^{k+1}$ = $d_1^k$ - x
Pour i=n : $d_{n-1}^{k+1}$ = $d_{n-1}^k$ - x

Nous travaillons avec des nombres réels positifs ou nuls que ce soit les valeurs R ou d merci bien :-)

dike · 22-02-2017 12:50:45

En d'autre termes, augmenter un R diminue les deux d disons voisins, cf. la représentation ci-dessous.

R1..........R2..........R3..........R4..........R5
........d1.........d2...........d3..........d4

C'est le seul et unique moyen d'annuler les d.

Yassine · 22-02-2017 13:41:08

Il y a encore un point à préciser.

On note $x_i^k = R_i^{k+1}-R_i^k$ l'augmentation de $R_i$ à la $k$-ième étape, avec $x_i^k \ge 0$. Il y a $n$ valeurs.

Ensuite, tu dis que $d_i^{k+1}=d_i^k - x_i^k$. Ici, on n'a que $n-1$ valeurs de $d_i^k$. A quoi sert $x_n^k$ ?

--EDIT--
Je rectifie ma question, je pense qu'il faut préciser comment sont modifiés les $d_i$
Prenons $d_2$ entre l'étape $1$ et $2$. Il peut bouger parce que $R_2$ a bougé :$R_2^2 = R_2^1 + x$, ou parce que $R_3$ a bougé $R_3^2 = R_3^1 + y$
Que vaut $d_2^2$, est-ce $d_2^2=d_2^2-x$ (application de la première partie de ta règle avec $i=2$) ou est-ce $d_2^2=d_2^2-y$ (application de la deuxième partie de ta règle avec $i=3$)

Dernière modification par Yassine (22-02-2017 23:03:25)

dike · 23-02-2017 09:24:39

Bonjour

Les d cumulent, c'est-à-dire que pour ton exemple : $d_2^2$ = $d_2^1$ - x - y

Voilà :)

Yassine · 23-02-2017 10:27:47

Donc, en résumé :
$d_i^{k+1} = d_i^{k} - (R_{i+1}^{k+1}-R_{i+1}^k) - (R_{i}^{k+1}-R_{i}^k)$ Pour $2 \le i \le n-2$
$d_1^{k+1} = d_1^{k} - (R_{1}^{k+1}-R_{1}^k)$
$d_{n-1}^{k+1} = d_{n-1}^{k} - (R_{n}^{k+1}-R_{n}^k)$

C'est ça ?

dike · 23-02-2017 10:59:24

Oui, c'est bien ça.

Yassine · 24-02-2017 10:05:54

Je propose donc une notation qui permettra de simplifier l'écriture du problème, et donc aider à le résoudre.
Je passe en notation vectorielle.
Je pose $R^k = (R_1^k, \cdots,R_n^k)^T$ le vecteurs des $R_i$ et note également $X^k = R^{k}-R^{k-1}$ l'innovation qui donne l'étape $k$.
Je noté également $D^k = (d_1^k, \cdots,d_{n-1}^k, 0)$ le vecteur des $d_i$, que j'ai complété à $0$ pour avoir la même dimension que $R^k$.

Je définis ensuite les matrices $A_1$, $A_2$, $A_3$ et $A_4$ comme suit :
$A_1$ : matrice avec une diagonale de $1$ juste au dessus de la diagonale principale. Elle "décale" un vecteur vers le haut : $A_1(x_1,\cdots,x_n)^T = (x_2,\cdots,x_n,0)^T$.

$A_2$ : Matrice identité à laquelle on enlève le dernier $1$ en bas à droite. Elle met à zéro l'entrée $n$ d'un vecteur.

$A_3$ : Matrice telle que $A_3(x_1,\cdots,x_n)^T = (x_2,0,\cdots,0)^T$ ($(A_3)_{1,2}=1$, et $(A_3)_{i,j}=0$ autrement).

$A_4$ : Matrice telle que $A_4(x_1,\cdots,x_n)^T = (0,\cdots,x_{n-1},0)^T$ ($(A_4)_{n-1,n-1}=1$, et $(A_4)_{i,j}=0$ autrement).

Alors, les trois relations précédentes peuvent s'écrire comme :
$D^{k+1} = D^{k} - A_1X^{k+1} - A_2X^{k+1} + (A_3+A_4)X^{k+1}$

Soit encore, si on pose $A = A_1 + A_2 - (A_3+A_4)$, la relation
$D^{k+1} = D^{k} - AX^{k+1}$

Donc, si $D^p=0$, on aurait alors $0 = D^1-A\sum_{i=1}^{p-1}X^{i+1}=D^1 - AR^{p}$

Il faut donc regarder si la matrice $A$ est inversible (chaque étape est réversible).
Je n'ai pas encore eu le temps de vérifier.

Dernière modification par Yassine (24-02-2017 10:09:21)

dike · 24-02-2017 10:52:18

Merci Yassine, je pense que le problème tel que posé est solvable comme tu le proposes.

Ceci dit, il y a un membre d'un autre forum qui me l'a reformulé d'une façon intéressante :

"Il s'agit donc juste d'un système d'équations linéaires $d_i=x_i+x_{i+1}$ pour $i=1,\ldots,n-1$ de rang $n-1$ à $n$ inconnues (les $x_i$) dont on se demande s'il a une solution à composantes toutes positives ou nulles."

Ce qui déjà me rappelle aussi l'algorithme d'élimination de Gauss. Cette personne ajoute :

"Il est très facile d'exprimer les solutions en fonction de la variable libre $x_1$, par exemple, et on trouve la condition nécessaire et suffisante suivante : Soit $m=\max(0, d_1-d_2, d_1-d_2+d_3-d_4,\ldots)$ et $M=\min(d_1, d_1-d_2+d_3,d_1-d_2+d_3-d_4+d_5,\ldots)$. Il existe une solution du système à composantes toutes positives ou nulles si et seulement si $m\leq M$, et dans ce cas on peut prendre la solution déterminée par $x_1=(m+M)/2$."

Je n'ai pas réussi à comprendre comment - en l'occurrence l'algèbre linéaire - a permis d'en arriver là. Je n'ai pas de réponse comment traiter les cas de nombre pair/impair de $d_i$.

De plus, je risque bien de subir une complexification du problème ; nous avons p.ex. $x_1, x_2, x_3, x_4, x_5, x_6, x_7,x_8, x_9$ et nous imposons encore des règles égalant certains $x$, du genre :
$x_2=x_3=x_9$
et $x_1=x_5$
les autres $x$ restant libres.

A vue de nez, l'algorithme d'élimination de Gauss pourrait résoudre ça, qu'en penses-tu ? Mais au hic près qu'il me faut à tout prix des $x >= 0$...

A+ :)

Yassine · 24-02-2017 12:18:49

Bon bah, ...
Difficile de t'aider si le problème change à chaque fois.
Le réponse de l'autre personne ne semble pas correspondre au problème actuel (où est l'indice $k$ qui représente l'étape ?). ça semble proche de ce que j'avais compris au tout début (pas de notion d'étapes).

dike · 24-02-2017 12:55:24

OK, je comprends.

Merci encore pour ta précieuse aide et bon week-end !

dike :)

Forum de mathématiques - Bibm@th.net

#1 21-02-2017 11:21:14

cherche désespérément formule/algorithme

#2 21-02-2017 13:41:58

Re : cherche désespérément formule/algorithme

#3 21-02-2017 14:50:35

Re : cherche désespérément formule/algorithme

#4 21-02-2017 23:37:46

Re : cherche désespérément formule/algorithme

#5 22-02-2017 09:39:02

Re : cherche désespérément formule/algorithme

#6 22-02-2017 10:53:47

Re : cherche désespérément formule/algorithme

#7 22-02-2017 12:37:10

Re : cherche désespérément formule/algorithme

#8 22-02-2017 12:50:45

Re : cherche désespérément formule/algorithme

#9 22-02-2017 13:41:08

Re : cherche désespérément formule/algorithme

#10 23-02-2017 09:24:39

Re : cherche désespérément formule/algorithme

#11 23-02-2017 10:27:47

Re : cherche désespérément formule/algorithme

#12 23-02-2017 10:59:24

Re : cherche désespérément formule/algorithme

#13 24-02-2017 10:05:54

Re : cherche désespérément formule/algorithme

#14 24-02-2017 10:52:18

Re : cherche désespérément formule/algorithme

#15 24-02-2017 12:18:49

Re : cherche désespérément formule/algorithme

#16 24-02-2017 12:55:24

Re : cherche désespérément formule/algorithme

Réponse rapide

Pied de page des forums