CCP Maths 2 PSI 2000

Thème de l'épreuve Étude des courbes de Bézier ; application à l'interpolation
Principaux outils utilisés barycentres, algèbre linéaire, fonctions de plusieurs variables

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Énoncé obtenu par reconnaissance optique des caractères


SESSION 2000 PSIOO7 A CONCOURS (0MHUNS POlYTECIINIOIIES ÉPREUVE SPÉCIFIOUE-FILIÈRE PSI MATHÉMATIQUES z DURÉE : 4 heures Les calculatrices programmables et alphanumériques sont autorisées, sous réserve des conditions définies dans la circulaire n° 99--018 du 01.02.99. Une feuille de papier millimètré devra être distribuée avec le sujet. Le problème est consacré à l'étude des courbes dites "courbes de Bézier", du nom de l'ingénieur français Bézier, l'un des créateurs, dans les années 1960, de cet outil très répandu aujourd'hui dans l'industrie automobile et plus généralement dans le vaste domaine d'applications que constitue la conception assistée par ordinateurs (CAO). Notations utilisées dans le problème et quelques rappels N désigne l'ensemble des entiers naturels, R le corps des réels. Les notations usuelles en découlent pour les ensembles construits à partir de ceux-là. Par exemple, N* désigne l'ensemble des entiers naturels non nuls, R+ l'ensemble des réels positifs ou nuls, etc. Dans tout le problème, le plan vectoriel réel R2 est muni de la base canonique (i, ;) : {? = (1,0) Î = (0,1) Chaque vecteur u e R2 s'identifie ainsi au couple de ses coordonnées dans la base canonique. Un point de vue différent mais cohérent avec ce qui précède permet que les éléments de R2 soient parfois appelés points, l'ensemble R2 étant alors muni de sa structure de plan affine et repéré par le repère canonique (0,Î, Î), où 0 = (0.0). Tout point du plan s'identifie alors au couple de ses coordonnées dans ce repère. On pourra ainsi écrire simplement : M = (x, y) pour exprimer que les coordonnées du point M dans le repère canonique sont (x, y). Etant donné deux points M et N, on posera N --M : MN . Cette écriture est cohérente avec les conventions précédentes, comme le montre la relation existante entre les coordonnées du vecteur MN et celles des points M et N. De façon équivalente, on pourra écrire : N=M+MN. Tournez la page S.V.P. ]. 1002 Plus généralement, si n désigne un entier naturel non nul, (M,...,À,,) une famille de n scalaires et (Pl,...,Pn) une famille de n points, l'expression MP] + À2 P2 +...+À,, P,, désignera le point (ou, selon le contexte, le vecteur) dont les coordonnées sont données conformément à cette expression. n En particulier, si le n--uplet (M,... .,À,,) vérifie E Àk : 1 , l'expression MP] + À2 P2 +.. . +À,, P,, k=l désigne le barycentre des points (P] ,...,P") affectés respectivement des poids (À... .,À,,). Le candidat remarquera qu'avec ces conventions, la propriété d'associativité du barycerytre s'exprime d'une façon très simple et naturelle. Pour tout entier n, on note L ,, l'ensemble des n-uplets de points du plan. Autrement dit, L,, = (RZÏ' . On ne fera pas de différence entre L] et le plan R2 . Par ailleurs, on note A l'ensemble des courbes paramétrées c de la forme c .- [0,1] --> R2 t l-> (x(tl y(t)) avec x et y fonctions continues du paramètre t e [O, 1]. On définit par récurrence une suite (B,l )neN d'applications en posant : l) Bo est l'application de L1 dans A qui à tout point P EUR L1 associe la courbe paramétrée constante (de trajectoire réduite à un point) BO (P) .- [0,1]-> R2 t ----> P 2) Pour tout n 2 1, B,! est l'unique application de l'ensemble L,... dans l'ensemble A qui satisfasse la relation V(P0,Pl,...,Pn)e L,...Vte [0,11 En (P0'Pl""'Pn Xt) : (1 _t)Bn--l (PO'Pl ""'Pn--l Xt)+tBn--l (P] ""'Pn )(t) L'arc paramétré B,,(P......,P,,): [0,1]--9 R2 n-> B,(Po,...,Pn )(t) est appelé la courbe de Bézier associée aux (n +1) pôles P0, P1, , P,,. Afin d'alléger la notation, pour toute famille Fe L,..., la courbe de Bézier associée aux (n +1) pôles F sera le plus souvent notée B,, F ou même BF. De façon générale, et sauf mention explicite du contraire dans l'énoncé, on ne fera pas appel aux coordonnées des points. PARTIE I [.Il Cas n = 1. Soit F: (PO,P,)e L2, 1.1.1/ Exprimer, en fonction du paramètre t et des points PO et P] , le point courant de la courbe de Bézier associée àla famille F, c'est-à--dire le point BF(t) : Bt. F(t). 1.1.2] Quelle est la trajectoire de l'arc paramétré BF ? I.2/ Cas n = 2. Soit F: (PO,PI,P2)eL3. 1 1.2.1/ Soit, pour ie {0,1}, Q,- le milieu de P,-- et P.... Montrer que BF(5) est le milieu de Q0 et Q1 . I.2.2/ Déterminer BF(O) et BF(I). I.2.3/ Exprimer en fonction de t le point courant B,,--(t) comme barycentre des trois pôles Po , P] et P2 , avec des coefficients dont la somme fait l. I.2.4/ On suppose P0 = (1,0), P] = (0,0) et P2 = (0,1). d 2 B t I.2.4.1/ Calculer _(dtî--(l) ; en déduire la nature de la trajectoire de l'arc paramétré B,. I.2.4.2/ Tracer la trajectoire de B,, (on prendra (O,Î,Î) orthonormé avec une unité de longueur de 4 cm). PARTIE II II.1/ On rappelle qu'une partie non vide K du plan est convexe si et seulement si ' V(M,N)e K2,VÀe [0,1] ,(1--À)M+ÀNE K. II.1.1/ Montrer qu'une partie non vide K du plan est convexe si et seulement si n n Vn e N*,V(Ml,...,Mn)e K",V(Àl,...,Àn)e (R,)", ZA,, = 1=> EMM, e K. k=l k=l II.1.2/ Soit E une paflie non vide du plan, et soit W un ensemble non vide de parties convexes du plan contenant E. Montrer que l'intersection de tous les convexes appartenant à W, c'est-à-dire (] K , est un convexe contenant E. KeW Dans la suite, pour toute partie non vide E du plan, on note C(E) l'enveloppe convexe de E, c'est--à-dire l'intersection de toutes les parties convexes du plan contenant E. II.].3/ Soit E une partie non vide du plan. Montrer l'équivalence E convexe (=> E = C(E). 11.1.4/ Soient G et H deux parties non vides du plan. Prouver l'implication (G G H)=> (C(G)c C(H)). Tournez la page S.V.P. II.1.5/ Soit E une partie non vide du plan. Montrer que { _ n n ] 605) = {lM ER2,3n & N*,3(Ml,...,Mn)e E",3(Àl,...,Àn)e (R+ )",Exk = 1 et M = EkkMkJ} k=l k=l Dans la suite, pour tout entier naturel n et toute famille de points F G L ,, , on notera encore C(F ) l'enveloppe convexe des points formant la famille F. Il.l.6/ Démontrer, par récurrence sur n, que pour tout entier naturel n et toute famille F E L la trajectoire de B", ,.-- est incluse dans C(F ) n+l* II.2/ Il.2.l/ Soit (p une transformation affine du plan. Démontrer, par récurrence sur n, que pour tout entier naturel n et toute famille F E L ,..., on a Vt EUR [011], (p(BMF(t))= Bn,(p(F)(t)' où (p(F ) désigne la famille obtenue en appliquant (p à chacun des points de la famille F. [1.2.2] Soit un triangle quelconque P0P|Pz, non aplati; en s'aidant de la question 1.2.4, tracer à main levée la courbe de Bézier associée, et justifier le tracé. Déduire également de la question 1 .2.4 la nature de cette courbe. PARTIE III III.1/ Fonctions de mélange. III.1.1/ Démontrer, par récurrence sur n, que pour tout entier naturel n il existe n +1 fonctions polynômes bmk:[0,I]-->[O,l], de degré inférieur ou égal à n, telles que, pour toute famille P: (P...... Pn)e Ln+1 , on ait On ne cherchera pas dans cette question 111.1.1 à exprimer explicitement les fonctions bn, k ( appelées fonctions de mélange). Au cours de la démonstration demandée, le candidat mettra en évidence la relation entre bn+l,k)bn,k et b,L k_1 vérifiée lorsque 15 k 5 n, ainsi que la relation entre b,..._0 et b,... et celle qui a lieu entre b,,+Ln+l et b,.... Ill.l.2l Pour cette seule question, on prend n = 3. Déterminer les polynômes b3,k (t) pour k & {0,...,3}. Ill.l.3/ n désigne à nouveau un entier naturel non nul quelconque. Déterminer, pour tout k E {O, n}, une formule simple exprimant b,,_ k(t) en fonction de t, de n et de k. l Pour tout k EUR {0,..., n}, on pose In,k : Ib,"EUR (t)dt. 0 n 111.1.4/ Déterminer 2 1,1, ,, . k=0 III.l.5/ Déterminer, en fonction de n et k, la valeur de [M (on pourra faire une intégration par parties). III.2/ Soit n eN* et F : (Po,... P,,)eL,.... On note Ë la famille obtenue à partir de F en inversant l'ordre des pôles : F" = (Pn, Pn_1,. Po) E L,... . III.2.1/ Quelle relation a--t--on entre B" F et En, F ? III.2.2/ Comparer les trajectoires respectives de B" F et de B", F. PARTIE IV IV.1/ Soit n eN* et F: (Po,...,Pn)eLn+l. Soit V l'espace vectoriel réel des polynômes à deux variables notées S et T, de degrés partiels inférieurs ou égaux à n. n n Autrement dit, les éléments de V sont de la forme 2 EOLÜSiTÏ , avec on,-]-- E R pour tout i=0 j=0 (i, j)e {o... .,n}2. Les monômes de la forme S iTj constituent une base de V, dite base canonique de V. A tout t EUR [0,1], on associe l'application linéaire 'P,:V -----> R2 caractérisée par l'image des vecteurs de la base canonique : V(i, j)e {O,...,n}2,'--I',(SiTÏ)= HP,. Par ailleurs, pour tout couple d'entiers naturels (i, j) te] Que _i+ j S n, on pose : C... = B,(P,,P,,,,....,gJ IV.1.1/ Trouver un polynôme Z & V, dont on donnera l'expression en fonction de S et T, tel que pour tout couple d'entiers naturels (i, j) tel que i+ j S n, on ait : Ci,j(t)= 'P, (215! ) On pourra faire une démonstration par récurrence sur i. ' IV.1.2/ Utiliser le résultat précédent pour retrouver la formule de la question III.1.3. IV.1.3/ Déterminer B,:(O) et BF(l). . . d (BW) IV.l.4/S tWGV.V' fe --'P W ='P -- . 01 en 1 rque dt ,( ) '\ ôT ' d IV.1.5/ Exprimer le vecteur dérivé :1Ï Bm F(t) à l'aide des points C,,_L0 (t) et C,,-... (t). IV.1.6/ On suppose les pôles P,- deux à deux distincts. Déterminer la droite tangente à la trajectoire de Bp au point de paramètre t = 0 ; même question en t = l. IV.1.7/ Dérivée k--ième. IV.1.7.1/ Z désignant le polynôme introduit à la question IV.1.1, déterminer, pour tout k n k EUR l,...,n , la dérivée artielle flZ--) . On laissera l'expression demandée sous forme p ôT" factorisée. IV.1.7.2/ Pour tout k & {l,..., n}, exprimer en fonction des pôles le vecteur dérivé k-ième de B", ,-- en t = 0, c'est-à--dire le vecteur B,,_ F(k)(0). Constater que ce vecteur ne dépend que des k +1 premiers pôles de la famille F. IV.2/ Dans cette question, on prend n = 3, PO : (--1,0), P] = (0,2), P2 : (O,--2) et P3 = (1,0). Montrer que la courbe de Bézier associée à cette famille de pôles est symétrique par rapport à 0 (on pourra exploiter le résultat de la question II.2.1), puis tracer cette courbe. On travaillera sur papier millimètré, avec une unité de 5 cm. Le tracé s'appuiera en particulier sur \ - \ l les tangentes a la courbe aux pomts de parametres t e {O, 5,1} . PARTIE V Soit q EURN*, (M,,M2,...,Mq) une famille de q points du plan et (l',...,tq) une famille de q réels deux à deux distincts pris dans l'intervalle ]O,l[. Pour tout ke {l,...,q} les coordonnées de Mk seront notées (ak ,B,, ). Par ailleurs, soit n e N*. La présente partie V vise à aborder le problème de la détermination d'une famille de pôles FE L,... telle que la courbe de Bézier BF s'approche au mieux des points Mk. Plus précisément, on pose g:L,... --)R G l-----> Ê[d(Mk,Ba(tk ))]2 où d désigne la distance euclidienne canonique sur R2 , et l'on cherche F tel que : F= ' G. g() aZËÎ,,g<) Afin de travailler avec une fonction de plusieurs variables réelles, on identifie L ,... et R2" +2 grâce àla bijection : Y ., R2n+2 _) Ln+l (x0'y0'""xn'yn)H ((x0'y0)""'(xn'yn» et la recherche d'un minimum pour g revient à celle d'un minimum def, où l'on a posé : f=g°r V.1/ Montrer que f est une application de classe C1 sur R2"+2 . ä' V.2/ Exprimer la dérivée partielle 8_ en fonction des variables (x0,...,xn, yo,..., y,,), de l'indice xi ie {O,...,n,}, des données du problème et des fonctions de mélange (voir question 111.1). Donner de même l'expression de (,Î--f . Yi ' + e r ] (i,j)e{0,...,n}2 dordre n 1, un vect u co orme U : (ui)os:'5n et un vecteur colonne V : (vi)OsiSn tel que si F = ((x... Yo ),...,,(xn y,1 )) minimise la V.3/ Déterminer une matrice carrée non nulle A = ai]- x0 yo fonction g, alors les vecteurs colonnes X = 3 et Y = 3 vérifient les systèmes linéaires xn yn AX : U AY : V Bien entendu, l'expression de A, U et Vne doit faire intervenir ni les x j ni les y j . CONCLUSION Dans le cas où A est inversible, on dispose ainsi d'un procédé pour déterminer la famille F cherchée, car on peut alors démontrer par un argument topologique que cette famille F minimise effectivement la fonction g. En praticzue, les choses sont en fait un peu plus complexes, car on ne dispose généralement que des points M , ,M 2,...,Mq) mais pas des valeurs (tl ,...,tq ).

Extrait du corrigé obtenu par reconnaissance optique des caractères


 CCP Maths 2 PSI 2000 -- Corrigé Ce corrigé est proposé par Gilles Radenne (ENS Ulm) ; il a été relu par Pascal Delanoe (Mines de Paris) et Cyril Niboyet (Mines de Paris). L'épreuve se compose de cinq parties ; à chaque fois, un ou deux résultats seront utiles dans les parties suivantes. ­ Le sujet porte sur les courbes de Bézier, que la première partie étudie dans des cas simples, avec deux ou trois points. ­ On s'intéresse ensuite à la notion de convexité, qu'on utilise pour préciser l'étendue de ces courbes, et on regarde également l'effet d'une transformation affine sur ces courbes. ­ La troisième partie est consacrée à l'étude du cas général avec n points par l'intermédiaire des coefficients barycentriques. ­ La partie suivante définit les courbes de Bézier comme images de polynômes par une famille de morphismes, et on en déduit les dérivées successives de la trajectoire. ­ Enfin la dernière partie s'intéresse à l'interpolation d'une famille de points par une courbe de Bézier l'approchant au mieux. Cette épreuve est relativement longue, et très fortement calculatoire, mais ne requiert principalement que des connaissances en algèbre linéaire et en géométrie, avec cependant quelques dérivations partielles simples dans la dernière partie. Indications I.2.1 Exprimer Qi en fonction des Bj . II.1.1 Pour la réciproque, procéder par récurrence sur n. II.1.3 Utiliser la question II.1.2 pour montrer que C(E) est le plus petit ensemble convexe contenant E. II.1.5 Montrer que l'ensemble donné dans l'énoncé est le plus petit ensemble convexe contenant E. S II.1.6 Déterminer la relation existant entre l'enveloppe convexe de A B et celles de A et B. II.2.2 Appliquer le résultat de la question II.2.1 à la question I.2.4 . III.1.3 Penser à la formule du binôme de Newton, à ce que doit valoir la somme des bn,k , et généraliser les expressions de b3,k obtenues à la question III.1.2 . III.2.1 Comparer bn,k et bn,n-k . IV.1.1 Commencer par déterminer Z avec i = 1, puis démontrer le résultat par récurrence en utilisant la valeur de Z trouvée. IV.1.4 Montrer d'abord l'égalité sur les monômes de W, puis utiliser la linéarité de et des opérateurs dérivation. IV.1.5 Exprimer Bn,F comme un Ci,j puis appliquer les résultats des questions IV.1.1 et IV.1.4 . IV.2 Utiliser aussi le résultat de la question III.2.1. V.I Décomposer f en somme de carrés. V.2 Exprimer explicitement f en fonction des variables (xi et yi ) et des données du problème (Mk et tk ). V.3 Construire les matrices A, U et V à l'aide des relations affines obtenues dans la question V.2. Partie I I.1.1 En appliquant la définition de BF : BF (t) = (1 - t)B0 (P0 )(t) + tB0 (P1 )(t) = (1 - t)P0 + tP1 I.1.2 Ainsi, quand t parcourt [ 0 ; 1 ], BF (t) se déplace de P0 à P1 , donc : La trajectoire de l'arc paramétré BF est le segment [P0 P1 ]. 1 1 1 1 1 = B1 (P0 , P1 ) + B1 (P1 , P2 ) I.2.1 BF 2 2 2 2 2 1 1 1 D'après la question I.1.1, B1 (M, N) = M + N, donc B1 (M, N) est le milieu 2 2 2 1 de [MN] ; par suite B1 (Pi , Pi+1 ) = Qi , ce qui entraîne : 2 1 BF est le milieu du segment [Q0 Q1 ]. 2 I.2.2 On a : BF (0) = B1 (P0 , P1 )(0) = P0 BF (1) = B1 (P1 , P2 )(1) = P2 I.2.3 BF (t) = (1 - t)B1 (P0 , P1 )(t) + tB1 (P1 , P2 )(t) = (1 - t)((1 - t)P0 + tP1 ) + t((1 - t)P1 + tP2 ) BF (t) = (1 - t)2 P0 + 2t(1 - t)P1 + t2 P2 Et on a bien (1 - t)2 + 2t(1 - t) + t2 = (1 - t + t)2 = 1 Par conséquent, BF (t) est le barycentre des points (P0 , P1 , P2 ) affectés des coefficients ((1 - t)2 , 2t(1 - t), t2 ). I.2.4.1 BF (t) = (1 - t)2 , t2 dBF (t) = (2(t - 1), 2t) dt d2 BF (t) = (2, 2) dt2 La trajectoire de l'arc paramétré BF ayant une « accéleration constante », c'est un 1 1 1 morceau de parabole d'extremités P0 et P2 , et passant par BF = , . 2 4 4 I.2.4.2 L'étude précédente permet de tracer le graphe suivant : P2 Q1 P1 Q0 P0 Graphe de BF , pour n = 2. Partie II II.1.1 Pour un ensemble non vide K, on note () la propriété définie dans l'énoncé. Montrons que cette propriété () est équivalente à la propriété servant à définir la convexité. Soit K une partie non vide du plan vérifiant (). Appliquons cette propriété pour n=2: (M, N) K2 , (1 , 2 ) (R+ )2 1 + 2 = 1 = 1 M + 2 N K ce qui revient strictement à la définition de la convexité. Inversement, supposons que K est convexe, et montrons par récurrence que K vérifie (). ­ Pour n = 1 la propriété est immédiate, et pour n = 2 on vient de démontrer que cela revenait à la définition de la convexité. ­ Supposons () vérifiée par K pour n fixé. Soient (M1 , . . . , Mn+1 ) Kn+1 des points de K, (1 , . . . , n+1 ) [ 0 ; 1 ] des coefficients de somme égale à 1, et n+1 P montrons que k Mk K. k=1 On peut supposer n P k 6= 0, sinon en utilisant le fait que les i sont positifs, k=1 on a 1 = . . . = n = 0, ce qui entraîne est évidente. n+1 P k Mk = Mn+1 K et la propriété k=1