Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 21-02-2017 10:21:14
- dike
- Membre
- Inscription : 22-04-2016
- Messages : 29
cherche désespérément formule/algorithme
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 12:24:23)
Hors ligne
#2 21-02-2017 12:41:58
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 402
Re : cherche désespérément formule/algorithme
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 ?
@+
Hors ligne
#3 21-02-2017 13:50:35
- dike
- Membre
- Inscription : 22-04-2016
- Messages : 29
Re : cherche désespérément formule/algorithme
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
Hors ligne
#4 21-02-2017 22:37:46
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : cherche désespérément formule/algorithme
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$
Hors ligne
#5 22-02-2017 08:39:02
- dike
- Membre
- Inscription : 22-04-2016
- Messages : 29
Re : cherche désespérément formule/algorithme
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 :-)
Hors ligne
#6 22-02-2017 09:53:47
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : cherche désespérément formule/algorithme
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 !
Hors ligne
#7 22-02-2017 11:37:10
- dike
- Membre
- Inscription : 22-04-2016
- Messages : 29
Re : cherche désespérément formule/algorithme
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 :-)
Hors ligne
#8 22-02-2017 11:50:45
- dike
- Membre
- Inscription : 22-04-2016
- Messages : 29
Re : cherche désespérément formule/algorithme
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.
Hors ligne
#9 22-02-2017 12:41:08
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : cherche désespérément formule/algorithme
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 22:03:25)
Hors ligne
#11 23-02-2017 09:27:47
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : cherche désespérément formule/algorithme
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 ?
Hors ligne
#13 24-02-2017 09:05:54
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : cherche désespérément formule/algorithme
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 09:09:21)
Hors ligne
#14 24-02-2017 09:52:18
- dike
- Membre
- Inscription : 22-04-2016
- Messages : 29
Re : cherche désespérément formule/algorithme
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+ :)
Hors ligne
#15 24-02-2017 11:18:49
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : cherche désespérément formule/algorithme
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).
Hors ligne