Commentaires

En gros,cette méthode d'interpolation te permet d'approcher la perfection en terme d'interpolation....des courbes très progressives et naturellement belles...Celles qui permettent de conserver un max de vitesse dans la trajectoire

Il y a asservissement en boucle ouverte

Bonjour,

En résumé :

I. Sur le plan des maths et des applications, je montre dans les deux billets comment construire le polynôme d'interpolation à partir d'une série de points (issus par exemple d'une expérience). En gros, on estime les valeurs intermédiaires de celles données par l'expérience, les applications sont donc nombreuses, dans ce lien quelques exemples :

https://fr.wikipedia.org/wiki/Interp...e#Applications

Sous l'angle des vecteurs, on met aussi en évidence des propriétés et des opérations communes entre les polynômes d'interpolation et les vecteurs classiques (addition, multiplication par un scalaire, produit scalaire, etc.).

On fait également indirectement le lien entre une variable statistique (série de mesures statistiques..) et un vecteur défini par ses composantes.

II. Concernant la partie programmation et implémentation en Python, dans le 1er billet je montre comment créer une classe permettant de représenter des vecteurs définis dans une base, puis comment réaliser des opérations comme l'addition entre deux vecteurs à l'aide de la surcharge d'opérateur.

Dans le 2nd billet on propose d'ajouter à cette classe des opérations comme le produit scalaire (avec la surcharge d'opérateur) ou le calcul du coefficient de corrélation entre des vecteurs de même base orthonormée.

Tout ceci accompagné d'exemples de code en Python permettant de créer ces objets vecteurs et de réaliser des opérations entre eux.

Cordialement

Envoyé par User

Bonjour,

Plus simplement, le polynôme d'interpolation (de Lagrange) se construit ainsi :

L(X) = y₀.l₀(X) + y₁.l₁(X) + ... + y_n.l_n(X)

Dans le cas général, ce polynôme d'interpolation peut-être vu comme un vecteur de composantes (y₀, y₁, ..., y_n) de l'espace R_n[X].

Il est construit avec la famille de polynômes de Lagrange (l₀, l₁, ..., l_n) qui forme une base orthonormée de cette espace et ceux-ci peuvent donc être vus comme les vecteurs de cette base orthonormée.

Cordialement

Ce que j'ai vu,c'est qu'un vecteur est forcément orthonormé

Quelle est la plus intuitive façon de te servir des polynômes...Expliques le d'une façon simplifiée s'il te plaît...Sinon une personne lambda ne peut avoir envie d’être matheux si on ne lui dit pas a quoi cela sert

En gros,quelles sont les domaines d'utilisation?

Cordialement

Bonjour,

Plus simplement, le polynôme d'interpolation (de Lagrange) se construit ainsi :

L(X) = y₀.l₀(X) + y₁.l₁(X) + ... + y_n.l_n(X)

Dans le cas général, ce polynôme d'interpolation peut-être vu comme un vecteur de composantes (y₀, y₁, ..., y_n) de l'espace R_n[X].

Il est construit avec la famille de polynômes de Lagrange (l₀, l₁, ..., l_n) qui forme une base orthonormée de cette espace et ceux-ci peuvent donc être vus comme les vecteurs de cette base orthonormée.

Cordialement

les polynômes d'interpolation de Lagrange vus comme des vecteurs
polynômes de Lagrange vus comme les vecteurs d'une base orthonormée

Quelle est la différence?

Merci à vous pour ce message, je corrige la coquille

Bonjour, très instructif ce billet de blog. Merci à vous pour cet article.
J'aimerais souligner une petite erreur de frappe au niveau de l'équation avec x, y et z. Il y a eu une répétition du y dans la notation.
Merci bien à vous

Bonjour MPython Alaplancha,

Envoyé par MPython Alaplancha

...
Je n'ai que peu de culture mathématique, j'en ignore l'écriture et ses codes (par exemple j'ignore ce que le symbole sigma signifie).
La première question que je me suis posé c'est: à quoi ça sert?
Je suis donc allé voir les liens que tu mentionnes et là ç'a attisé ma curiosité et mon intérêt, notamment sur ses applications sur le traitement d'image. Je t'en remercie.

Merci pour ton message

Oui, j'ai surtout parlé de l'algorithme et de son implémentation en Python. Comme tu le mentionnes, j'ai aussi donné plusieurs liens dans lesquels il y a pas mal d'exemples d'application :

"L'algorithme des k-moyennes peut être utilisé pour réduire le nombre de couleurs d'une image sans que cela ne nuise trop à sa qualité...
ce peut être utile à des fins de compression ou pour permettre l'affichage optimal d'une image sur un écran ou une imprimante n'offrant pas une grande variété de couleurs."

Je voulais pas trop rajouter d'infos et me concentrer sur l'algorithme, mais ta remarque me fait penser que je devrais l'ajouter dans le billet..

Envoyé par MPython Alaplancha

Sinon, juste pour dire qu'il existe une implémentation probablement optimisée de l'algo KMeans dans le module scikit-learn (ce qui n'enlève rien à ton travail)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

from sklearn.cluster import KMeans

https://scikit-learn.org/stable/modu...g.html#k-means

Concernant le module scikit-learn je le mentionne aussi à la fin du billet mais merci pour le lien et l'exemple.

En fait de nos jours on installe une librairie pour utiliser une fonction optimisée qui va faire tout le travail. Comme tu peux l'imaginer, cela ne veut pas dire qu'on ne s'intéresse pas à la compréhension du code et donc à l'algorithmique et à la programmation

D'ailleurs, comme je l'indique ma fonction comporte certaines instructions print() permettant de mieux suivre et de mieux comprendre le déroulement du code.

Bon week-end

Bonjour.
Je n'ai que peu de culture mathématique, j'en ignore l'écriture et ses codes (par exemple j'ignore ce que le symbole sigma signifie).
La première question que je me suis posé c'est: à quoi ça sert?
Je suis donc allé voir les liens que tu mentionnes et là ç'a attisé ma curiosité et mon intérêt, notamment sur ses applications sur le traitement d'image. Je t'en remercie.
Sinon, juste pour dire qu'il existe une implémentation probablement optimisée de l'algo KMeans dans le module scikit-learn (ce qui n'enlève rien à ton travail)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

from sklearn.cluster import KMeans

https://scikit-learn.org/stable/modu...g.html#k-means

Merci pour cette précision, je vais ajouter son nom.

S'il est vrai que von Neumann a travaillé sur la méthode "Monté Carlo", les travaux initiaux sont le plus souvent attribués à Stanislaw Ulam, un des ses éminents collègues mathématiciens du projet Manhattan, certes moins célèbre.

Petite mise à jour des tableaux

Bonjour,

Oui la bonne curiosité merci pour ces précisions.

En fait concernant l'optimisation l'objectif était surtout ensuite d'économiser de la mémoire (2nde version).

Cdlt,

Bonjour,

Merci pour votre réponse.

Expert, je ne sais pas, curieux, volontiers.

Oui la lisibilité en a pris un coup pour supprimer les divisions et modulos.
Le manque de commentaire n'y aide pas et la relecture me fait penser
que ce n'est pas une implémentation optimale.

Mais il n'y a vraiment rien de spécial la dedans, la série produite présente
des cas particuliers pour faire pivoter les valeurs.
L'algo s'appuie la dessus. (4, 1) (3, 1, 1) (2, 1, 1, 1) etc

Bonne journée.

Bonjour et merci pour votre message,

Tout ce qu'on apprend en maths ou dans d'autres matières n'a pas toujours une application directe, mais déjà avoir la satisfaction de comprendre les choses, en rendant accessible un sujet pas forcément simple de prime abord ça peut être sympa..

Concernant le code, l'objectif était surtout d'écrire du code le plus lisible possible, sans chercher forcément la performance, car le billet ne s'adresse pas à des experts en programmation En tout cas chercher le meilleur compromis entre les deux.

Je voulais aussi proposer quelque chose de différent de ce qu'on trouve habituellement sur les forums, autre chose par exemple que les fonctions récursives..

En tout cas merci pour le code, je ne connais pas Go

Cordialement,

Bonjour,

Merci pour la ressource, intéressant ! Question annexe, ça sert à quel genre d'applications ces calculs ?

Par curiosité j'ai porté votre bout de code en Go, on fait x2.
C'est pas mal pour un portage sans douleur.

Code Go :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func partition_suivante(a []int, k, N int) ([]int, int, int) {
	// # Construit la partition b qui suit la partition a dans la liste des partitions.
	// # a : liste des entiers représentant la partition passée en argument
	// # k : rang du dernier entier dans a strictement supérieur à 1
	// # N : nombre d'entiers qui valent 1 dans la liste a
 
	b := make([]int, 0, k+3)
	b = append(b[:0], a[:k]...)
 
	// # pour tout j < k, on définit b[j] = a[j] : a = [2, 2, 1] -> b = [2]
	// b := a[:k]
 
	// # On ajoute (a[k] - 1) à la liste b : b[k] = a[k] - 1 : a = [2, 2, 1] -> b = [2, 1]
	b = append(b, a[k]-1)
 
	// # En notant N+1 = b[k]*q + r la division euclidienne de N+1 par b[k]
	// # On obtient le quotient q et le reste r de cette division.
	q := int(math. Floor(float64(N+1) / float64(b[k])))
	r := (N + 1) % b[k]
 
	// # On évalue ensuite les entiers b[j] = b[k] pour k < j < k + q + 1 : a = [2, 2, 1] -> b = [2, 1] + 2*[1] = [2, 1, 1, 1]
	for e := 0; e < q; e++ {
		b = append(b, b[k])
	}
 
	// # Si le reste r est non nul.
	if r != 0 {
		// # On ajoute l'entier r à la liste b : b[k+q+1] = r
		b = append(b, r)
	}
 
	// # calcul des valeurs de k et N pour la nouvelle partition b
	for b[k] != 1 {
		k++
		if k == len(b) {
			break
		}
	}
 
	// # renvoi de la partition b suivant la partition a, du rang k dans b, et du nombre N d'entiers valant 1 dans b
	return b, k - 1, len(b) - k
}

Si on pousse l'optimisation un petit peu on fait encore 2x, mais si on est vraiment motivé je crois qu'on peut faire beaucoup mieux en généralisant cette ébauche.
Ici, seul les 1 sont optimisés, on peut généraliser cela et gagner sur les durées d'allocations.

Code Go :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
type partition struct {
	a    []int
	n    int
	ones int
}
 
func (p partition) is_last() bool {
	return len(p.a) < 1 || p.a[0] == 1
}
 
func (p partition) len() int {
	return len(p.a) + p.ones
}
 
func (p partition) slice() []int {
	out := make([]int, p.len())
	copy(out, p.a)
	for i := 0; i < p.ones; i++ {
		out[len(p.a)+i] = 1
	}
	return out
}
 
func partition_from_slice(s []int) partition {
 
	n := 0
	i := 0
	for ; i < len(s); i++ {
		if s[i] == 1 {
			break
		}
		n += s[i]
	}
	ones := len(s) - i
 
	return partition{
		a:    s[:i],
		n:    n + ones,
		ones: ones,
	}
}
 
func gen_part(p partition) partition {
 
	if p.is_last() {
		return p
	}
 
	n := p.a[len(p.a)-1]
 
	if n == 2 {
		np := partition{
			a:    make([]int, len(p.a)-1),
			n:    p.n,
			ones: p.ones + 2,
		}
		copy(np.a, p.a)
		return np
	}
 
	if len(p.a) == 1 {
		np := partition{
			a:    make([]int, 0, 10),
			n:    p.n,
			ones: 0,
		}
		j := 0
		m := n - 1
		for {
			if j+m > np.n {
				break
			}
			np.a = append(np.a, m)
			j += m
		}
		if u := np.n - j; u > 1 {
			np.a = append(np.a, u)
		} else if u > 0 {
			np.ones++
		}
		return np
	}
 
	if p.ones < 1 {
		np := partition{
			a:    make([]int, len(p.a)),
			n:    p.n,
			ones: 1,
		}
		copy(np.a, p.a)
		np.a[len(p.a)-1]--
		return np
	}
 
	np := partition{
		a:    make([]int, len(p.a)+1),
		n:    p.n,
		ones: 0,
	}
	copy(np.a, p.a)
	n--
	ones := p.ones + 1
	np.a[len(p.a)-1] = n
	if n > ones {
		np.a[len(p.a)] = ones
	} else {
		np.a[len(p.a)] = n
		o := 0
		for _, j := range np.a {
			o += j
		}
		for o < p.n {
			r := p.n - o
			if r >= n {
				np.a = append(np.a, n)
			} else if r > 1 {
				np.a = append(np.a, r)
			} else {
				np.ones++
				break
			}
			o += n
		}
	}
	return np
}

Quelques cas de tests pour montrer l'utilisation.

Code Go :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package main
 
import (
	"fmt"
	"reflect"
	"testing"
)
 
func TestGenPart(t *testing.T) {
 
	type tcase struct {
		input      []int
		expect     []int
		expect_end bool
	}
 
	cases := []tcase{
		{
			input:  []int{15},
			expect: []int{14, 1},
		},
		{
			input:  []int{10, 5},
			expect: []int{10, 4, 1},
		},
		{
			input:  []int{7, 1, 1, 1, 1, 1, 1, 1, 1},
			expect: []int{6, 6, 3},
		},
		{
			input:  []int{4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			expect: []int{3, 3, 3, 3, 3},
		},
		{
			input:  []int{6, 6, 3},
			expect: []int{6, 6, 2, 1},
		},
		{
			input:      []int{1},
			expect:     []int{1},
			expect_end: true,
		},
		{
			input:      []int{1, 1, 1},
			expect:     []int{1, 1, 1},
			expect_end: true,
		},
		{
			input:      []int{2, 1, 1},
			expect:     []int{1, 1, 1, 1},
			expect_end: true,
		},
		{
			input:      []int{2, 1, 1, 1, 1, 1, 1},
			expect:     []int{1, 1, 1, 1, 1, 1, 1, 1},
			expect_end: true,
		},
		{
			input:  []int{3, 3, 3, 3, 3},
			expect: []int{3, 3, 3, 3, 2, 1},
		},
		{
			input:  []int{3, 2, 1},
			expect: []int{3, 1, 1, 1},
		},
		{
			input:  []int{4, 4},
			expect: []int{4, 3, 1},
		},
		{
			input:  []int{5, 3},
			expect: []int{5, 2, 1},
		},
		{
			input:  []int{18, 2},
			expect: []int{18, 1, 1},
		},
		{
			input:  []int{18, 1, 1},
			expect: []int{17, 3},
		},
		{
			input:  []int{6, 6, 6, 1, 1},
			expect: []int{6, 6, 5, 3},
		},
		{
			input:  []int{14, 3, 1, 1, 1},
			expect: []int{14, 2, 2, 2},
		},
		{
			input:  []int{15, 3, 1, 1},
			expect: []int{15, 2, 2, 1},
		},
		{
			input:  []int{12, 4, 1, 1, 1, 1},
			expect: []int{12, 3, 3, 2},
		},
	}
 
	for i, c := range cases {
		p := partition_from_slice(c.input)
		res := gen_part(p)
 
		if !reflect.DeepEqual(res.slice(), c.expect) {
			fmt.Printf("%#v\n", p)
			fmt.Printf("%#v\n", res)
			t.Fatalf(`invalid result at #%v
		expected    %#v
		result      %#v`, i, c.expect, res.slice())
		}
		if c.expect_end != res.is_last() {
			t.Fatalf(`invalid result at #%v
		expected    %#v
		result      %#v`, i, c.expect_end, res.is_last())
		}
	}
}

Évidemment, si on pouvait trouver à répartir les de calculs sur plusieurs fils d'exécution on gagnerait d'autant plus, mais la répartition de la charge n'est pas évidente.

Bref, des babioles sans conséquence.

Bonne journée.

Envoyé par User

Merci Fabien

Mais tu as en partie raison, comme je l'indique plus il y a de billes sur la planche et plus ça ralenti, d'où l'utilité du bouton finaliser qui donne le résultat de la simulation

Oui oui, mais vu la lenteur avec peu de billes alors que ça fonctionne très bien dans une VM Linux sur la même machine, j'ai vraiment un problème pas normal sous Windows

Merci Fabien

Mais tu as en partie raison, comme je l'indique plus il y a de billes sur la planche et plus ça ralenti, d'où l'utilité du bouton finaliser qui donne le résultat de la simulation

Marrant Par contre, l'animation ralentit sérieusement chez moi au fur et à mesure de l'apparition des billes. Bizarre...


Edit : Programme qui fonctionne très bien dans une VM sous Linux, j'ai donc une m#@! à résoudre sous Windows

Ah ouais en effet très didactique pour les débutants

Merci Fabien pour ce complément