Devoir

Essayez de bien rédiger vos réponses, sans vous reporter ni au cours, ni au corrigé. Si vous souhaitez vous évaluer, donnez-vous deux heures ; puis comparez vos réponses avec le corrigé et comptez un point pour chaque question à laquelle vous aurez correctement répondu.

Questions de cours : On désigne par $f$ la fonction qui à $x\in\mathbb{R}$ associe $x\sin(1/x)$ (prolongée par continuité en 0). Le but de l'exercice est d'en obtenir une représentation graphique sur un intervalle contenant 0, qui puisse être agrandie par zoom au voisinage de 0.

1. Expliquer les raisons pour lesquelles les lignes de commandes suivantes ne conviennent pas, quelle que soit la valeur de n.

   x=linspace(-1,1,n); y=x*sin(1/x);
   plot2d(x,y)
   

2. On note $\lfloor x\rfloor$ la partie entière du nombre réel $x$. Soit $h$ un paramètre réel strictement positif. Définir le vecteur x de valeurs allant de $\pi\lfloor 1/(h\pi)\rfloor +\pi/10$ à $\pi\lfloor 1000/(h\pi)\rfloor+\pi$ par pas de $\pi/10$. Définir le vecteur X des inverses des valeurs de x, puis le vecteur Y, produit des valeurs de $X$ par les sinus de celles de x. Expliquer en quoi la commande plot2d(X,Y) constitue une représentation graphique satisfaisante de $f$, et préciser l'intervalle de représentation.
3. Comment en déduire une représentation satisfaisante sur $[-h,0[$ ?
4. On souhaite utiliser ce qui précède pour obtenir une représentation sur $[-h,h]$. Donner les limites du cadre graphique.
5. Écrire une fonction qui prend en entrée un paramètre $h$ strictement positif, qui retourne en sortie $f(h)$ et représente la fonction $f$ sur l'intervalle $[-h,h]$.

Exercice 1 : Soient $x=(x(i))_{i=1,\ldots,n}$ et $y=(y(i))_{i=1,\ldots,n}$ deux vecteurs. On appelle suite des différences divisées de $x$ par $y$ la suite de vecteurs $d=(d_i)_{i=1,\ldots,n}$, définie par $d_1=y$, et pour $i=1,\ldots,n\!-\!1$,

$$\forall j = 1,\ldots n-i ,\; d_{i+1}(j) = \frac{d_i(j+1)-d_i(j)}{x(j+i)-x(j)}\;.$$

1. Définir la fonction differences_divisees, qui prend en entrée deux vecteurs lignes x et y de même taille, et qui retourne en sortie la matrice $D$, triangulaire inférieure dont les lignes sont les vecteurs de différences $d_i$, complétés par des zéros.
2. Soit $P$ un polynôme de degré $k\leqslant n-2$. On pose $y=(P(x(i)))_{i=1,\ldots,n}$. Vérifiez expérimentalement que le vecteur $d_i$ est constant pour $i=k+1$, et nul pour $i=k+2,\ldots, n$.
3. Définir la fonction Newton, qui prend en entrée deux vecteurs lignes x et y de même taille, et qui retourne en sortie le polynôme $P$, de degré $n\!-\!1$, défini par :
   $$P(X)=d_1(1)+d_2(1)(X-x(1))+\cdots+d_n(1)(X-x(1))\cdots(X-x(n\!-\!1))\;.$$

4. Vérifiez expérimentalement que $P$ est le polynôme interpolateur de Lagrange des ordonnées $y(i)$ aux abscisses $x(i)$ :
   $$\forall i=1,\ldots,n\;,\quad P(x(i))=y(i)\;.$$

5. Le polynôme interpolateur de Lagrange $P$ peut se calculer aussi par la formule suivante :
   $$P(X) = \sum_{i=1}^n y_i\prod_{j\neq i} \frac{X-x_j}{x_i-x_j}\;.$$
   Définir la fonction Lagrange, analogue à la fonction Newton, mais utilisant la nouvelle formule.
6. Vérifiez expérimentalement que Lagrange est à la fois plus lente et plus instable numériquement que Newton.

Exercice 2 : Étant donnée une matrice symétrique définie positive $A=(a_{i,j})_{i,j=1,\ldots,n}$, sa décomposition de Cholesky consiste à écrire $A= L {^t\! L}$, où $L$ est une matrice triangulaire inférieure. Pour obtenir la matrice $L=(l_{i,j})$, on définit d'abord sa première colonne :

$$l_{1,1}=\sqrt{a_{1,1}}\;,\quad \forall i=2,\ldots,n ,\; l_{i,1}= \frac{a_{i,1}}{l_{1,1}}\;.$$

Pour $j=2,\ldots,n$, la $j$-ième colonne est définie à partir des précédentes :

$$l_{i,j} = \left\{\begin{array}{ll} 0 &\forall i=1,\ldots,j\!-\!1... ...^{j-1}l_{i,k}l_{j,k}}{l_{i,i}} } &\forall i=j+1,\ldots,n\;. \end{array}\right.$$

1. Définir une fonction Lt qui prend en entrée un entier strictement positif $n$ et retourne en sortie la matrice L de taille $n\times n$ dont le coefficient d'ordre $(i,j)$ est nul si $i<j$, égal à $i-j+1$ sinon.
2. Définir une fonction Lr qui prend en entrée un entier strictement positif $n$ et retourne en sortie la matrice L de taille $n\times n$ dont le coefficient d'ordre $(i,j)$ est nul si $i<j$, égal à un nombre au hasard entre 0 et $1$ sinon.
3. Pour L=Lt(n) et L=Lr(n), calculer la matrice A égale au produit de L par sa transposée, puis la norme matricielle de la différence entre L' et chol(A). Noter le temps d'exécution de la commande chol(A). Effectuez des essais pour différentes valeurs de n et notez vos observations.
4. Définir la fonction Cholesky3, qui prend en entrée une matrice symétrique A, et qui retourne en sortie la matrice triangulaire inférieure L, en utilisant 3 boucles emboîtées : la première pour l'indice de colonne, la seconde pour l'indice de ligne, la troisième pour calculer la somme définissant le numérateur de $l_{i,j}$.
5. Répéter les expériences de la question 3 en remplaçant la fonction Scilab chol par Cholesky3.
6. Modifier la fonction Cholesky3 en Cholesky2 et remplacer la troisième boucle par un calcul utilisant sum.
7. Répéter les expériences de la question 3 en renplaçant chol par Cholesky2.
8. Modifier la fonction Cholesky2 en Cholesky1 et remplacer la deuxième boucle par un calcul direct de la $j$-ième colonne.
9. Répéter les expériences de la question 3 en renplaçant chol par Cholesky1.