\documentclass{article}

\textheight 23cm
%\textwidth 16.5cm \columnsep 10pt \columnseprule 0pt

%\usepackage[pdftex]{hyperref}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{amsmath,amsfonts,amssymb}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}

\textheight=23.5cm
\textwidth=17.5cm
\topmargin=-7mm
\oddsidemargin=-10mm
\begin{document}
\newtheorem{rem}{Remarque}
\newcommand{\on}{\framebox{ON}}
\newcommand{\tr}{\mbox{trace }}
\newcommand{\enter}{\framebox{ENTER}}
\newcommand{\haut}{\framebox{$\uparrow$}}
\newcommand{\bas}{\framebox{$\downarrow$}}
\newcommand{\droit}{\framebox{$\rightarrow$}}
\newcommand{\gauche}{\framebox{$\leftarrow$}}
\def\fb{\framebox}
\def\ls{shift gauche }
\def\rs{shift droit }
\newcommand{\atan}{\mbox{atan\,}}

\title{TP6: algèbre linéaire}
%\maketitle

\noindent Mat249 \hfill Alg\`ebre lin\'eaire \hfill TP6

\section{Logiciels} \label{sec:expe}

\subsection{Rappels MuPAD/maple/xcas} \label{sec:mupad}
Ne pas oublier de taper \verb|export(linalg)| (\verb|MuPAD|)
ou {\tt with(linalg)} (maple) dans votre session.

Quelques instructions d'alg\`ebre lin\'eaire données dans l'ordre MuPAD, 
maple si les noms de commande diffèrent, xcas accepte généralement 
les 2 syntaxe~:
\begin{enumerate}
\item {\tt charpoly(A,x)}: polyn\^ome caract\'eristique
\item {\tt det(A)}: d\'eterminant d'une matrice $A$,
\item {\tt scalarProduct(A,B)}/{\tt dotprod(A,B)}: 
produit scalaire des deux vecteurs $A$ et $B$,
\item {\tt eigenvalues(A)}/{\tt eigenvals(A)}: 
valeurs propres de la matrice $A$. Si vous voulez
des valeurs num\'eriques (et si $A$ est \`a valeurs num\'eriques) 
\'ecrivez au moins un des coefficients de $A$ comme nombre r\'eel ou complexe.
\item {\tt eigenvectors(A)}/{\tt eigenvects(A)}: vecteurs propres de $A$,
\item {\tt matlinsolve(A,b)}/{\tt linsolve(A,b)}: 
r\'esout l'\'equation lin\'eaire $Ax=b$,
\item {\tt f:=(i,j)->(1/(i+j-1));matrix(2,2,f)}:
pour cr\'eer une matrice (ici de Hilbert).
\item \verb|(i,j) -> if i=j then 1; else 0; end_if;|: utile pour cr\'eer
la matrice identit\'e.
\item \verb|ncols(A)|/\verb|coldim(A)|: nombre de colonnes d'une matrice,
\item \verb|normalize(v)|: renvoie $v/||v||$
\item \verb|trace(A)|: trace de $A$
\item {\tt transpose(A)}: transpos\'ee de $A$
\item {\tt ludecomp(A)} ou {\tt lu(A)}: donne la d\'ecomposition $LU$ de $A$.
\item \verb|?linalg| pour la liste des commandes d'alg\`ebre lin\'eaire
\end{enumerate}

Attention en maple, les matrices sont stockées par référence et non
par valeur, si vous affectez {\tt A:=matrix(...)} puis {\tt B:=A},
toute modification de {\tt A} est automatiquement reflétée sur {\tt B}.
De plus, il est souvent nécessaire d'effectuer {\tt evalm} pour
effectuer un calcul matriciel ou renvoyer une valeur.

\subsection{Calculatrices} \label{sec:calc}

\subsubsection{Commandes de la HP49} \label{sec:erable}
Pour entrer une matrices $A$ vous pouvez utiliser le MatrixWriter 
(\verb|MTRW| sur le clavier) ou directement le clavier
(par exemple \verb|[[1,2],[3,4]]|). On peut aussi cr\'eer une matrice
dont l'\'el\'ement $m_{i,j}$ est donn\'e par une fonction
$(i,j) \rightarrow m_{i,j}$ \`a l'aide de \verb|LC2M|.

Commandes utiles~:
\begin{itemize}
\item \verb|EGV|, \verb|EGVL|~: vecteurs propres et valeurs propres
d'une matrice
\item \verb|IDN(n)|, (resp. \verb|RANM(n,m)|)~: crée une matrice identité
(resp. matrice aléatoire)
\item \verb|JORDAN|~: réduction sous forme de Jordan d'une matrice
\item \verb|LU|~: factorisation LU d'une matrice (numérique uniquement)
\item \verb|RREF|~: réduction sous forme échelonnée
\end{itemize}

\subsubsection{TI92/89, Casio Classpad} \label{sec:ti}
Pour entrer une matrice, on peut utiliser l'éditeur statistique
ou directement au clavier (par exemple \verb|[[1,2][3,4]]|).

Commandes utiles~:
\begin{itemize}
\item  \verb|egv| (non disponible sur la 92)~: 
valeurs propres/vecteurs propres. Attention, le calcul est num\'erique 
uniquement.
\item \verb|identity(n)| et \verb|randmat(n,m)| pour cr\'eer 
des matrices identit\'e et al\'eatoire
\item \verb|lu|, décomposition LU
\item  \verb|rref| : r\'eduction de Gau\ss\
\item Sur tous les mod\`eles on peut bien sur calculer le polynome
caract\'eristique avec \verb|det(A-xI)| ou $I$ d\'esigne la matrice
identit\'e, puis factoriser avec \verb|factor| et calculer les vecteurs
propres \`a la main en r\'esolvant le syst\`eme.
\end{itemize}


\section{Exercices}

\subsection{Méthode du pivot}
\begin{itemize}
\item Choisissez 5 vecteurs aléatoires exacts dans $\R^4$,
trouvez une relation linéaire entre ces 5 vecteurs en calculant
le noyau d'une application linéaire.

\item Déterminez le temps mis par votre logiciel pour résoudre
un système linéaire de $n$ équations à $n$ inconnues 
à coefficients aléatoires numériques puis exacts
de taille $n=5,10,20,40$. Commentez.

\item \'Ecrire une fonction {\tt gaussinv} qui prend en argument une 
matrice carrée,
lui accolle à droite la matrice identité de m\^eme taille puis applique
la fonction de réduction sous forme échelonnée, et renvoie la partie
droite de la matrice réduite. Testez votre fonction avec une matrice
aléatoire $M$ de taille 3 à coefficients entiers, 
calculer en particulier {\tt M * gaussinv(M)}.
Faites le m\^eme test avec la matrice $H$ de coefficient $m_{ij}=1/(i+j)$
en taille 5, puis avec la m\^eme matrice mais évaluée
numériquement. Calculez le conditionnement de $H$ et expliquez
les résultats.

\end{itemize}

\subsection{Réduction exacte des endomorphismes.} 
\begin{itemize}
\item Polyn\^ome minimal par une méthode probabiliste \\
On prend un vecteur aléatoire $v$, et on cherche
une relation linéaire entre 
$v$, $Av$, ..., $A^nv$. On trouve alors un polynôme
minimal $P$ relatif à $v$, c'est-à-dire que $P(A)v=0$. 
Si le degré de $P$ est $n$, 
$P$ est à la fois le polynôme caractéristique et le polynôme minimal
(en particulier cette méthode permet de trouver efficacement le polynôme
caractéristique de ``presque'' toutes les matrices). Sinon, 
on essaie alors un autre
vecteur aléatoire. On prend le PPCM des polynômes obtenus. Si le degré
du PPCM est $n$, alors on a le polynôme minimal et caractéristique.
S'il reste de degré plus petit que $n$, on réessaie encore un ou 2 vecteurs.
Si le degré est identique (et strictement inférieur à $n$) 
pour 2 vecteurs de suite, on peut tester si $P(A)=0$ pour \^etre sur
(ou peut aussi renvoyer $P$ qui sera alors probablement le polyn\^ome
minimal pour éviter le test qui est couteux en temps~: $O(n^4)$ opérations).
Donnez les détails des calculs par cette méthode
pour une matrice aléatoire de taille 4.
(Bonus) \'Ecrire une fonction effectuant ce calcul. Déterminez
empiriquement le temps nécessaire à calculer le polyn\^ome minimal
pour une matrice aléatoire numérique de taille $n$.

\item Polyn\^ome caractéristique par interpolation\\
\'Ecrire une fonction qui calcule le polyn\^ome caractéristique
d'une matrice par interpolation de Lagrange (on calcule 
$\det(A-\lambda I)$ pour $\lambda=0,...,n$).
Factorisez le polyn\^ome, puis comparez avec les valeurs
propres numériques de $A=B \ ^t B $ (obtenues par la fonction
de calcul de valeurs propres du logiciel) pour $B$ une matrice
aléatoire numérique de taille 10, 20, 40.

\end{itemize}

\subsection{Réduction numérique des endomorphismes}
\begin{itemize}
\item \'Ecrire un programme mettant en oeuvre la méthode de la
puissance.  Utilisez ce programme pour trouver une valeur approch\'ee 
de la valeur propre de norme maximale par la m\'ethode
de la puissance de $B \ ^t B$ où $B$ est une matrice aléatoire.

\item
En utilisant la méthode des itérations inverses,
trouvez la plus petite valeur propre de la matrice précédente.

\item
Pour trouver les autres valeurs propres/vecteurs propres,
on \'elimine la valeur propre trouv\'ee en remplaçant
$A$ par $A'=A-\lambda_1 w_1 \ ^t w_1$. Une fois une valeur
propre de $A'$ trouvée, on peut améliorer
la précision en utilisant des itérations inverses sur 
la matrice $A$.
Trouvez toutes les valeurs propres de la matrice~:
\[D= \left(\begin{array}{rrr}
 9 & -1 & 2  \\
 -1 & 5 & -2  \\
 2 & -2 & -7 
\end{array}\right) \]

\item Couple de complexe conjugu\'e de module maximal\\
Trouver le couple de valeurs propres de plus grand module de la matrice~:
\[E= \left(\begin{array}{rrrr}
 -3 & -8 & -3 & 4  \\
 7 & 8 & 6 & 5  \\
 -1 & 4 & -4 & 1 \\
7  & -4 & -5 & 7 
\end{array}\right) \]
Faites de m\^eme pour le couple de plus petit module.
\end{itemize}

\end{document}