salut tous,

j'ai une question à propos de la méthode de Gauss :

- j'ai lu que pour avoir des erreurs d'arrondies faibles il faut choisir le pivot le plus gros (en valeur absolue)

pourriez vous m'expliquez pour quoi s'il vous plait je ne comprends pas ...

merci d'avance

A+

il y a plusieurs niveau de réponse possible

La plus simple à saisir est que si tu choisis un pivot <math>\(p\)</math> petit (voir très petit et inférieur à 1) quand tu vas appliquer gauss, tu vas utiliser partout du <math>\(\frac{1}{p}\)</math> qui risque d'être très grand et très sensible à l'erreur sur <math>\(p\)</math> (regarde la courbe de la fonction inverse, quand on s'approche de 0, la moindre erreur fait grandement varier le résultat du fait de la verticalité de la courbe). D'où l'intérêt de prendre un grand pivot (là où la fonction inverse est presque plate).

Pour l'autre vision du problème, il faut considérer une modélisation du pivot de gauss par multiplication de matrice successive. Sans entrer dans les détails, les matrices sont très proche de l'identité mais avec des coefficients ailleurs que sur la diagonale proportionnels à l'inverse du pivot, or, multiplier par de telles matrices augmente beaucoup le nombre condition du problème si les termes hors de la diagonal sont éloignés de 0. Or plus le nombre condition est mauvais (grand) plus les erreurs sur les données de départ sont amplifiés.

merci beaucoup rushia pour ta reponse. J'ai bien compris à présent.

=> par contre pour la deuxieme partie je n'ai pas vraiment saisi car je ne connais pas la méthode matricielle dont tu parles. pourrais tu m'expliquer stp ?
je n"'arrive pas à construire une matrice qui permet de faire cette operation...

En fait, un système
<math>\(\left\{\begin{array}{ccc} a_{1,1}x_1+a_{1,2}x_2+...+a_{1,n}x_n & = & b_1 \\ a_{2,1}x_1+a_{2,2}x_2+...+a_{2,n}x_n & = & b_2 \\ ... & = & ... \\ a_{n,1}x_1+a_{n,2}x_2+...+a_{n,n}x_n & = & b_n \end{array}\)</math>
Peut s'écrire sous forme matricielle comme :
<math>\(\underbrace{\begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n}\end{pmatrix}}_{A_0}\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n\end{pmatrix}=\begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n\end{pmatrix}\)</math>
Et l'idée du pivot de Gauss est de triangulariser <math>\(A_0\)</math> colonne par colonne.
On passe alors de <math>\(A_0\)</math> à <math>\(A_1\)</math>, puis à <math>\(A_2\)</math>, puis .... à <math>\(A_{n-1}\)</math> qui est (sauf erreur d'indice de ma part ^^) triangulaire supérieure.
Or, pour passer de <math>\(A_0\)</math> à <math>\(A_1\)</math>, il suffit de multiplier <math>\(A_0\)</math> à gauche par <math>\(P_1 = \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \\ -\frac{a_{2,1}}{a_{1,1}} & 1 & 0 & \ddots & 0 \\ -\frac{a_{3,1}}{a_{1,1}} & 0 & 1 &\ddots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ -\frac{a_{n,1}}{a_{1,1}} & 0 & 0 & \cdots & 1 \\\end{pmatrix}\)</math> c'est-à-dire <math>\(A_1 = P_1A_0\)</math>.
Sur le même principe, on a <math>\(A_{k+1} = P_{k+1}A_k\)</math> avec des matrice <math>\(P_{k}\)</math> plus ou moins de la même forme.
On constate donc que d'un étape à l'autre on multiplie par une matrice qui ressemble beaucoup à l'identité, et d'autant plus que le pivot est grand.
Ce qu'il faut comprendre, c'est que plus la matrice qu'on applique "déforme" l'espace, plus les erreurs faites sur les données d'entrée sont amplifiées (par exemple, pour un problème très mal conditionné une erreur relative de <math>\(10^{-5}\)</math> sur une entrée peut donner une erreur relative de <math>\(10^{5}\)</math> à la sortie). Or la matrice qui tord le moins l'espace est incontestablement l'identité, donc pour ne pas trop aggraver le problème à chaque itération, il faut que les différentes matrices <math>\(P_k\)</math> soient le plus proche de l'identité possible et par conséquent que le pivot choisi soit le plus grand possible. On utilise pour cela des méthodes type pivot partiel (On choisit pour l'itération suivante le plus grand pivot de la colonne à "annuler") ou pivot total (On choisit le plus grand pivot dans toute la sous matrice restante, ce qui impose de modifier l'ordre des lignes, mais aussi des colonnes, et donc de l'ordre des variables <math>\(x_k\)</math>).

En espérant t'avoir éclairé.

Remarque : la méthode du pivot est très bien pour une résolution "à la main", mais pour la résolution numérique, on fait beaucoup plus robuste pour pas vraiment plus cher (décomposition <math>\(QR\)</math> par exemple, qui ressemble beaucoup au pivot sur le principe, mais pour laquelle toutes les matrices <math>\(P_k\)</math> sont orthogonales et donc ne dégrade pas du tout le problème).

merci enormement pour cette reponse très intéressante !!!!


=> pourrais tu me détailler deux choses s'il te plait, si possible : quel est le lien entre deformation de l'espace et propagation d'erreur, je n'arrive pas à lier les deux....

=> pour la decomposition QR, il n'y a pas de deformation cela est lié au fait que la norme de cette matrice est 1 où au fait que les vecteurs soient orthogonaux ? (en fait la réponse à cette question est liée à la précédente...)

merci de ton aide

Pour répondre à ta question je vais devoir introduire un peu de formalisme

Norme d'opérateur

Soit <math>\(M\)</math> un opérateur sur un espace <math>\(E\)</math> muni d'une norme <math>\(||.||_E\)</math>, on va définir sa norme par :
<math>\(||M|| = \sup_{x\neq0}\frac{||Mx||_E}{||x||_E}\)</math>
Si <math>\(M\)</math> est linéaire (si c'est une matrice ^^), cette norme peut s'écrire alors <math>\(||M|| = \sup_{||x||_E=1}||Mx||_E\)</math>

L'avantage de cette norme, c'est qu'on a <math>\(\forall x\in E, ||Mx||_E\leq||M||\times||x||_E\)</math> et que pour deux opérateurs <math>\(M_1\)</math> et <math>\(M_2\)</math>, <math>\(||M_1M_2||\leq||M_1||\times||M_2||\)</math> et <math>\(||M_1+M_2||\leq||M_1||+||M_2||\)</math>

Application à notre problème

On cherche à résoudre <math>\(Mx=b\)</math>, on va maintenant supposer qu'au lieu d'avoir b, on a accès à une mesure perturbé <math>\(b+\delta b\)</math> il en résulte qu'on va obtenir <math>\(x+\delta x\)</math> en sortie de notre algo, tel que <math>\(M(x+\delta x)=b+\delta b\)</math>.
On a donc (on suppose que M est inversible sinon on ne chercherait pas à résoudre le problème ^^) :
<math>\(Mx=b \Rightarrow ||Mx||_E=||b||_E \Rightarrow ||M||.||x||_E\geq||b||_E \Rightarrow \frac{1}{||x||_E}\leq\frac{||M||}{||b||_E}\)</math> (1)
<math>\(M\delta x=\delta b \Rightarrow \delta x = M^{-1}\delta b \Rightarrow ||\delta x||_E \leq ||M^{-1}||.||\delta b||_E\)</math> (2)

En multipliant (1) et (2) on obtient <math>\(\frac{||\delta x||_E}{||x||_E}\leq||M||.||M^{-1}||\frac{||\delta b||_E}{||b||_E}\)</math>.

Autrement dit on est capable de majorer l'erreur relative commise sur le résultat par une constante fois l'erreur relative commise sur les données d'entrée.
Ce nombre, c'est <math>\(\mathcal{N}_M = ||M||.||M^{-1}||\)</math> qu'on appelle nombre condition du problème. plus ce nombre est grand, plus le problème est dure à résoudre (on a beaucoup de chance de faire de grosses erreurs).
Au mieux, il vaut 1.

Je vais maintenant répondre à ta seconde question en premier


Un opérateur orthogonal à une norme de 1 (son inverse aussi) et donc son nombre condition vaut <math>\(1\)</math> et on n'aggrave pas le problème.

Nombre condition et déformation de l'espace

Décomposition en valeur singulières :
Un matrice <math>\(M\)</math> peut se mettre sous la forme <math>\(M=U\Sigma V^*\)</math> où <math>\(U\)</math> et <math>\(V\)</math> sont des matrices orthogonales (carrés) et où <math>\(\Sigma\)</math> à les mêmes dimensions que <math>\(M\)</math> et est de la forme suivante :
<math>\(\Sigma = \begin{pmatrix} \sigma_1 & 0 & 0 & \cdots & 0 \\ 0 & \sigma_2 & 0 & \cdots & 0 \\ 0 & 0 & \sigma_3 &\cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \sigma_n \\0 & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 & \cdots & 0\end{pmatrix}\)</math>

Les <math>\(\sigma_i\)</math> sont positifs et appelées les valeurs singulières de <math>\(M\)</math>.

Interprétation :
Les matrices <math>\(U\)</math> et <math>\(V\)</math> étant orthogonales, elles représentent seulement une succession de rotation et d'homothétie qui ne "tardent" par vraiment l'espace. Par contre, la matrice <math>\(\Sigma\)</math> montre de quelle façon notre matrice <math>\(M\)</math> modifie l'espace dans les différentes directions. Si les <math>\(\Sigma_i\)</math> sont très différentes, l'espace est complètement déformé (imagine une boule de pâte à modeler que tu tirerais plus ou moins dans chaque direction)

En fait, on peut montrer que le nombre condition de <math>\(M\)</math> peut s'écrire <math>\(\mathcal{N}_M=\frac{\sigma_{max}}{\sigma_{min}}\)</math>, ce qui est donc bien cohérent avec tout ce que je dis. Si la plus grande valeur singulière est plusieurs ordres de grandeur au dessus de la plus petite valeur singulière, le nombre condition explose.

Voila, j'espère t'avoir permis de comprendre.

Rushia, quelques remarque sur la première partie de ton message

- tout d'abord : merci beaucoup pour ton aide !!!!!!!!!!! j'ai beaucoup tes explications, elles sont très claires et à la fois très précises!

- j'ai bien compris l'idée, je le referai à tête reposé pour être certain d'avoir tous saisi
par contre tu dis que le meilleur conditionnement est 1, ça veut dire qu'un conditionnement < 1 ça existe pas ? (car ça serait encore mieux que 1 puisque l'erreur relative sur la solution serait encore plus faible ?)

- pour l'histoire des normes il me manque des bases mathematiques, je vais faire un sujet la dessus sur le forum afin de saisir ceci une bonne fois pour toute ;-) (j'espère que tu auras le temps d'y jeter un oeil)

- je ferais aussi un sujet sur la stabilité des methodes numeriques car je sais que c'est lié au conditionnement mais j'ai du mal à lier tous les morceaux (rayon spectral < 1, conditionnement, pas de discretisation temps vers 0 ...) => apparemment ça à un lien (theoreme de lax milgram? ) mais mon niveau mathematique n'est pas suffisant

Non, malheureusement, on ne peut pas faire mieux que 1 pour le nombre condition (cf la seconde partie de mon message que je viens de terminer : au mieux la plus petite valeur singulière et la plus grande valeur singulière sont égales)

merci beaucoup, à présent de nombreuses choses s’éclaircissent !!!!!!

ps: juste un truc : la matrice sigma est une matrice diagonale, hein ? (sur le message c pas evident je trouve)
en faite tu fais juste un changement de base entre le repere principale et le repère ou M n'est pas diagonale ? (ceci est vrai que si M est diagonalisable donc ?)

En fait, la décomposition en valeurs singulières peut être faite sur des matrices non carrés et donc la matrice <math>\(\Sigma\)</math> n'est pas forcement diagonale (il peut y avoir des colonnes ou des lignes entières de 0 selon la taille de <math>\(M\)</math>), bien sur, dans le cas qui nous intéresse (la résolution d'un système) <math>\(M\)</math> et <math>\(\Sigma\)</math> sont carré et donc <math>\(\Sigma\)</math> est bien diagonale.
Par contre, a priori, <math>\(U\)</math> et <math>\(V\)</math> ne sont pas égales et donc <math>\(V^*\)</math> n'est pas l'inverse de <math>\(U\)</math>, il ne s'agit donc pas d'une mise sous forme diagonale (mais ça y ressemble)

rushia, j'aime beaucoup tes explications !!!

-> décomposition en valeurs singulière je ne connaissais pas par contre, c'est en quelque sorte la généralisation de la diagonalisation d'une matrice ?

-> pour montrer que le rapport des valeurs propres min et max est le nombre de condition il suffit d'écrire l'expression des normes de M et M-1 et en retombe sur ce que tu m'as dis avec les valeurs propres ?

-> j'ai toujours entendu qu'une matrice mal conditionnée est une matrice dont les vecteurs colonnes qui la compose ont des ordres de grandeurs très différents. Ca veut donc dire qu'on trouve un rapport des valeurs propres grand si la matrice à des colonnes qui ont des ordres de grandeurs différents ?

-> dernier truc: d'après mes souvenirs un algo est stable si la sa plus grand valeur propre est inférieure en valeur absolue à "1". Il doit y avoir un lien avec le nombre de condition (matrice sigma) dont tu me parles ? mais je ne vois pas lequel... pour tant ça semble très proche mais il me manque un petit quelque chose pour saisir ça

-> On peut voir ça comme une généralisation si on veut, mais je pense pas que ce soit utilisé dans les mêmes conditions.

-> Je dois avouer que je ne connais pas vraiment la démo pour obtenir le nombre condition en fonction des valeurs singulière, mais l'idée doit être celle que tu donnes (pour une matrice inversible bien sur, sinon <math>\(||M^{-1}||\)</math> n'existe pas)

-> Surement encore une fois l'idée c'est que la déformation de l'espace n'est pas homogène dans toutes les directions (c'est juste plus simple à voir et à quantifier une fois la décomposition faite)

-> Si la matrice est diagonalisable <math>\(\mathcal{N}=\left|\frac{\lambda_{max}}{\lambda_{min}}\right|\)</math>, c'est le seul lien que je vois. On peut très bien avoir un nombre condition très grand avec des valeurs propres toutes inférieures à 1 en valeur absolue (la la plus grande vaut 0,5 mais que la plus petite vaut 0.00005) et à l'inverse avoir un nombre condition très faible et des valeurs propre très grandes (par exemple <math>\(1000I\)</math> avec <math>\(I\)</math> l'identité). D'ailleurs, on peut avoir le même nombre condition avec des matrices totalement différentes et donc des valeurs propres totalement différentes aussi.

re-salut Rushia,

1°) j'ai trouvé un document qui répond un peu près à toutes mes interrogations mais par contre il est sous la forme de TD sans la correction (apparemment la définition que tu m'as dis avec les valeurs propres n'est valable que si la matrice est symétrique) :
http://www.ann.jussieu.fr/~okutmustur/TD.NUM.pdf

2°) j'ai regardé ce que tu m'as écris plus haut mais ta définition du conditionnement repose sur une norme que je ne comprends pas...
pourrais tu m'en dire plus car je ne comprends pas grand chose à cette norme... d'ailleurs j'ai un peu de mal à comprendre qu'es ce que la norme d'une matrice... la norme d'un vecteur ça va mais d'une matrice...
=> pourrais tu me détailler ce passage stp ?

Re salut Rushia !

je te contact car je me suis posé plusieurs questions sur cette méthode de Gauss. On l'utilise car c'est trop long de calculer des déterminants numériquement et car inverser une matrice demande le calcul d'un déterminant, du coup :

=> comment calculer numériquement un déterminant ?
=> et donc comment calculer une matrice inverse ?

Pour calculer un déterminant, et pour éviter l'explosion calculatoire de la formule générale, on essaye généralement d'arriver à un problème équivalent avec une matrice pour laquelle le déterminant est calculable très facilement (par exemple une matrice triangulaire : il suffit de faire le produit des termes diagonaux).

Pour calculer l'inverse d'une matrice, on a plusieurs solutions, selon la situation. Le plus simple est de résoudre <math>\(Ax_i=e_i\)</math> où les <math>\(e_i\)</math> sont les colonnes de l'identité.
Une autre solution est de faire la décomposition en valeur singulière de la matrice, on a alors <math>\(A=U\Sigma V^t\)</math> et donc <math>\(A^{-1}=V\Sigma^{-1}U^t\)</math> (la matrice sigma est diagonale donc triviale à inverser et U et V sont orthogonales)

Merci Rushia

=> une autre question : il y a des méthodes qui demandent d'avoir une matrice définie positive du coup la seule façon de savoir est de diagonaliser la matrice et vérifier que les valeurs propres sont positive ?

du coup ça fait lourd comme calcul? on doit d'abord diagonaliser et ensuite résoudre le systeme ?

Non, il y a d'autres méthodes pour arriver à savoir si une matrice est bien symétrique définie positive. Parmi elles, on utilise une variante de la décomposition LU : une matrice symétrique définie positive admet une décomposition <math>\(LL^t\)</math> (on a donc <math>\(U=L^t\)</math>), si, au cours de cette décomposition on rencontre un problème, c'est que la matrice que l'on considere n'est pas définie positive.

Citation : rushia

Non, il y a d'autres méthodes pour arriver à savoir si une matrice est bien symétrique définie positive. Parmi elles, on utilise une variante de la décomposition LU : une matrice symétrique définie positive admet une décomposition <math>\(LL^t\)</math> (on a donc <math>\(U=L^t\)</math>), si, au cours de cette décomposition on rencontre un problème, c'est que la matrice que l'on considere n'est pas définie positive.

super merci !

encore quelques questions :
1°) lorsqu'on applique la méthode du pivot partiel et que l'on rencontre un pivot nul on dit que la la matrice n'est pas inversible mais pourquoi ? si on aurait fait une méthode du pivot total peut être que l'on aurait pas eu de pivot nul ?
2°) comment adapter l'algorithme de Gauss dans le cas où on a des nombres complexes ?
3°) si cet algorithme est sensible au conditionnement de la matrice (même dans le cas d'un pivot partiel?) quel type d'algorithme on utilise pour s'affranchir de ceci ? il en existe ?
4°) j'aimerai trouver l'inverse de la matrice P que tu m'a montré plus haut. En fait, j'aimerai démontrer que cette matrice <math>\(Pi=I-Hi\)</math> à pour inverse <math>\(P_i^{-1}=I+H_i\)</math> sur un cas particulier c'est facile mais pour le cas général je ne sais pas comment faire, pourrais tu me montrer stp ?


Pour la décomposition LU avec pivot partiel:
j'ai regardé comment fonctionne la méthode de Gauss avec Pivot partiel et je bloque un peu pour la factorisation, pourrais tu vérifier stp ce que j'ai mis plus bas :
on a notre matrice finale (supérieur triangle) U qui est donnée par :

<math>\(U=(G_n.P_n*G_{n-1}.P_{n-1}*...*G_1.P_1).A\)</math>
donc si je veux avoir la factorisation A=LU j'ai :
<math>\(A=(P_1^{T}.G_1^{-1}*...*P_{n-1}^{T}.G_{n-1}^{-1}*P_n^{T}.G_n^{-1}).U\)</math>
Gi est la matrice de Gauss du pivot i, Pi est la matrice de permutation du pivot i (qui peut être identité)
on peut donc réecrire:
<math>\(A=(P_1^{T}*..*P_{n-1}^{T}*P_n^{T})(G_1^{-1}*...*G_{n-1}^{-1}*G_n^{-1}).U\)</math>
et donc on a :
<math>\(Permutation.A=L.U\)</math>
avec :
<math>\(Permutation=P_n*P_{n-1}*..*P_1\)</math> et L qui est <math>\(L=I=H1+H2+H3...+Hn\)</math> ?
es ce bien ceci ?? la permutation obtenu est bien la même que celle qui servira à permuter le second membre ?

pour revenir sur le calcul d'une matrice inverse :
1°) la première méthode nécessite le calcul d'autant de systemes que la taille de la matrice ?
2°) la deuxieme methode fonctionne que si la matrice de passage est orthogonale, c'est à dire si la matrice de depart est symétrique..

1) On aurait certes pu trouver un pivot non nul, mais cela ne fait que repousser le problème : au final il arrivera une étape où on ne trouvera plus de pivot non nul. La raison, c'est que si on ne trouve pas de pivot non nul dans la colonne, alors cette colonne est une combinaison linéaire des colonnes précédentes et la matrice ne peut pas être inversible(déterminant nul).

2) Dans le cas complexe, j'imagine qu'on fait exactement pareil que dans le cas réel (on choisit le pivot avec le plus grand module). Je ne vois pas vraiment ce qui pourrait poser problème.

3) J'en ai déjà cité plus haut, la décomposition <math>\(QR\)</math> a l'avantage de ne pas changer le conditionnement du problème car <math>\(Q\)</math> est orthogonale.

4) <math>\(P_i(I+H_i) = (I-H_i)(I+H_i) = I + H_i - H_i - H_i^2 = I-H_i^2\)</math> et par construction <math>\(H_i\)</math> est nulle partout sauf une partie de colonne située strictement sous la diagonale, une tel matrice possède un carré nul (ça peut se voir facilement)
Une autre façon de voir et de regarder ce que l'on fait quand on veut "annuler" la manipulation faite à l'étape précédente : si on retire la première ligne fois un certain coef, il suffit d'ajouter la première ligne multipliée par ce même coefficient.

Décomposition <math>\(LU\)</math> :
Je n'ai pas tout vérifié, mais le passage de la ligne 2 à 3 me parait suspect : je ne vois aucune raison permettant de dire que les matrices <math>\(P^T\)</math> et <math>\(G^{-1}\)</math> commutent.

Il y a beaucoup plus simple pour calculer la décomposition <math>\(LU\)</math> :
En posant <math>\(L=\begin{pmatrix} 1 & 0 & \cdots & 0 \\ l_{2,1} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{n,1} & l_{n,2} & \cdots & 1\end{pmatrix}\)</math> et <math>\(U=\begin{pmatrix} u_{1,1} & u_{1,2} & \cdots & u_{1,n}\\ 0 & u_{2,2} & \cdots & u_{2,n}\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{n,n}\end{pmatrix}\)</math> et en écrivant <math>\(A=LU\)</math>, on obtient un système très simple permettant d'identifier les coefficients <math>\(l_{i,j}\)</math> et <math>\(u_{i,j}\)</math> par propagation de solution.
Exemple 3x3 (pour saisir le principe) :
<math>\(\begin{pmatrix} 1 & 0 & 0 \\ l_{2,1} & 1 & 0 \\ l_{3,1} & l_{3,2} & 1\end{pmatrix}\begin{pmatrix} u_{1,1} & u_{1,2} & u_{1,3}\\ 0 & u_{2,2} & u_{2,3}\\ 0 & 0 & u_{3,3}\end{pmatrix}=\begin{pmatrix} \special{color rgb 1.0 0.0 0.0}u_{1,1}& u_{1,2}& u_{1,3}\\ u_{1,1}\special{color rgb 1.0 0.5 0.0}l_{2,1} & \special{color rgb 1.0 0.0 0.0}u_{1,2}\special{color rgb 1.0 0.5 0.0}l_{2,1} \special{color rgb 0.0 0.0 1.0}+ u_{2,2}& \special{color rgb 1.0 0.0 0.0}u_{1,3}\special{color rgb 1.0 0.5 0.0}l_{2,1} \special{color rgb 0.0 0.0 1.0}+ u_{2,3}\\ \special{color rgb 1.0 0.0 0.0}u_{1,1}\special{color rgb 1.0 0.5 0.0}l_{3,1} & \special{color rgb 1.0 0.0 0.0}u_{1,2}\special{color rgb 1.0 0.5 0.0}l_{3,1} \special{color rgb 0.0 0.0 1.0}+ u_{2,2}\special{color rgb 1.0 0.0 1.0}l_{3,2} & \special{color rgb 1.0 0.0 0.0}u_{1,3}\special{color rgb 1.0 0.5 0.0}l_{3,1} \special{color rgb 0.0 0.0 1.0}+ u_{2,3}\special{color rgb 1.0 0.0 1.0}l_{3,2} \special{color rgb 0.0 0.0 0.0}+ u_{3,3}\end{pmatrix}\)</math>
En rouge : ce que l'on identifie immédiatement
En orange : ce que l'on déduit une fois qu'on a trouvé les rouges
En bleu : ce que l'on déduit une fois les rouges et les oranges trouvés
En rose et en noir : je pense que tu as compris

Cette structure se généralisant à la taille <math>\(n\)</math>, on en déduit tous les coefficients étape par étape (propagation), bien sur, il y a un petit problème si on tombe sur une solution nulle, il faut alors faire intervenir des permutations (après je suis pas non plus un expert du calcul de décomposition ^^).

Matrice inverse :
1) tout à fait, ça fait donc <math>\(n\)</math> systèmes à résoudre et comme la résolution d'un système est généralement en <math>\(O(n^3)\)</math>, ça fait une complexité en <math>\(O(n^4)\)</math> (en utilisant certaines méthodes, et dans la mesure où la matrice ne change pas, on peut résoudre les <math>\((n-1)\)</math> derniers systèmes en <math>\(O(n^2)\)</math> au lieu de <math>\(O(n^3)\)</math> d'où une complexité d'inversion en <math>\(O(n^3)\)</math>) à comparer au <math>\(O\left((n+1)!\right)\)</math> pour une inversion par formule de la comatrice.

2) Non, la seconde méthode utilise la décomposition en valeurs singulières et non la diagonalisation, elle est donc valable pour toute matrice inversible.

merci Rushia de prendre le temps de repondre à toutes mes questions

Citation : rushia

1) On aurait certes pu trouver un pivot non nul, mais cela ne fait que repousser le problème : au final il arrivera une étape où on ne trouvera plus de pivot non nul. La raison, c'est que si on ne trouve pas de pivot non nul dans la colonne, alors cette colonne est une combinaison linéaire des colonnes précédentes et la matrice ne peut pas être inversible(déterminant nul).

d'accord, merci.

Citation : rushia

2) Dans le cas complexe, j'imagine qu'on fait exactement pareil que dans le cas réel (on choisit le pivot avec le plus grand module). Je ne vois pas vraiment ce qui pourrait poser problème.

En fait avec Gauss quand on fait Aij=Aij-AikAkj/pivot les Aij sont en fait des valeurs à deux composantes (une réelle et une complexe) on prend ceci comme si les Aii sont des vecteurs ?

Citation : rushia

3) J'en ai déjà cité plus haut, la décomposition <math>\(QR\)</math> a l'avantage de ne pas changer le conditionnement du problème car <math>\(Q\)</math> est orthogonale.

en fait je me suis mal exprimé :
- on a une matrice A mal conditionnée, donc Gauss plante là dessus ( et Gauss partiel aussi ??? )
- si on choisit la méthode QR on va pas changer le conditionnement de A mais si A est mal conditionné alors on va toujours garder une solution pourrie ?
=> je voudrais savoir si un algorithme est capable de trouver une solution correcte si la matrice est mal conditionnée ? Le pivot partiel permet il ceci ?

Citation : rushia

4) <math>\(P_i(I+H_i) = (I-H_i)(I+H_i) = I + H_i - H_i - H_i^2 = I-H_i^2\)</math> et par construction <math>\(H_i\)</math> est nulle partout sauf une partie de colonne située strictement sous la diagonale, une tel matrice possède un carré nul (ça peut se voir facilement)
Une autre façon de voir et de regarder ce que l'on fait quand on veut "annuler" la manipulation faite à l'étape précédente : si on retire la première ligne fois un certain coef, il suffit d'ajouter la première ligne multipliée par ce même coefficient.

OK, merci.

Citation : rushia

Décomposition <math>\(LU\)</math> :
Je n'ai pas tout vérifié, mais le passage de la ligne 2 à 3 me parait suspect : je ne vois aucune raison permettant de dire que les matrices <math>\(P^T\)</math> et <math>\(G^{-1}\)</math> commutent.

en fait j'ai juste inversé la relation et comme <math>\((A*B*C)^{-1}=C^{-1}.B^{-1}.A^{-1}\)</math> alors j'en déduit la relation que j'ai mis (mais il faut se souvenir aussi pour cela que la matrice de permutation est orthogonale).
Par contre dans la suite je me suis planté quand j'ai regroupé les termes et je ne vois pas trop comment faire pour cette decomposition LU avec strategie du pivot partiel

Citation : rushia

Il y a beaucoup plus simple pour calculer la décomposition <math>\(LU\)</math> :
En posant <math>\(L=\begin{pmatrix} 1 & 0 & \cdots & 0 \\ l_{2,1} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{n,1} & l_{n,2} & \cdots & 1\end{pmatrix}\)</math> et <math>\(U=\begin{pmatrix} u_{1,1} & u_{1,2} & \cdots & u_{1,n}\\ 0 & u_{2,2} & \cdots & u_{2,n}\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{n,n}\end{pmatrix}\)</math> et en écrivant <math>\(A=LU\)</math>, on obtient un système très simple permettant d'identifier les coefficients <math>\(l_{i,j}\)</math> et <math>\(u_{i,j}\)</math> par propagation de solution.
Exemple 3x3 (pour saisir le principe) :
<math>\(\begin{pmatrix} 1 & 0 & 0 \\ l_{2,1} & 1 & 0 \\ l_{3,1} & l_{3,2} & 1\end{pmatrix}\begin{pmatrix} u_{1,1} & u_{1,2} & u_{1,3}\\ 0 & u_{2,2} & u_{2,3}\\ 0 & 0 & u_{3,3}\end{pmatrix}=\begin{pmatrix} \special{color rgb 1.0 0.0 0.0}u_{1,1}& u_{1,2}& u_{1,3}\\ u_{1,1}\special{color rgb 1.0 0.5 0.0}l_{2,1} & \special{color rgb 1.0 0.0 0.0}u_{1,2}\special{color rgb 1.0 0.5 0.0}l_{2,1} \special{color rgb 0.0 0.0 1.0}+ u_{2,2}& \special{color rgb 1.0 0.0 0.0}u_{1,3}\special{color rgb 1.0 0.5 0.0}l_{2,1} \special{color rgb 0.0 0.0 1.0}+ u_{2,3}\\ \special{color rgb 1.0 0.0 0.0}u_{1,1}\special{color rgb 1.0 0.5 0.0}l_{3,1} & \special{color rgb 1.0 0.0 0.0}u_{1,2}\special{color rgb 1.0 0.5 0.0}l_{3,1} \special{color rgb 0.0 0.0 1.0}+ u_{2,2}\special{color rgb 1.0 0.0 1.0}l_{3,2} & \special{color rgb 1.0 0.0 0.0}u_{1,3}\special{color rgb 1.0 0.5 0.0}l_{3,1} \special{color rgb 0.0 0.0 1.0}+ u_{2,3}\special{color rgb 1.0 0.0 1.0}l_{3,2} \special{color rgb 0.0 0.0 0.0}+ u_{3,3}\end{pmatrix}\)</math>
En rouge : ce que l'on identifie immédiatement
En orange : ce que l'on déduit une fois qu'on a trouvé les rouges
En bleu : ce que l'on déduit une fois les rouges et les oranges trouvés
En rose et en noir : je pense que tu as compris

Cette structure se généralisant à la taille <math>\(n\)</math>, on en déduit tous les coefficients étape par étape (propagation), bien sur, il y a un petit problème si on tombe sur une solution nulle, il faut alors faire intervenir des permutations (après je suis pas non plus un expert du calcul de décomposition ^^).

en fait ce que j'ai essayé de faire plus haut ce n'est pas la méthode LU (car j'y arrive bien) mais la méthode avec permutation de ligne (la matrice que j'appel P est une matrice de permutation de lignes) j'essai en fait de trouver l'alogo sous forme matricielle d'une decomposition LU avec pivot partiel mais ce n'est pas trivial

Citation : rushia

Matrice inverse :
1) tout à fait, ça fait donc <math>\(n\)</math> systèmes à résoudre et comme la résolution d'un système est généralement en <math>\(O(n^3)\)</math>, ça fait une complexité en <math>\(O(n^4)\)</math> (en utilisant certaines méthodes, et dans la mesure où la matrice ne change pas, on peut résoudre les <math>\((n-1)\)</math> derniers systèmes en <math>\(O(n^2)\)</math> au lieu de <math>\(O(n^3)\)</math> d'où une complexité d'inversion en <math>\(O(n^3)\)</math>) à comparer au <math>\(O\left(n(n!)^2\right)\)</math> pour une inversion par formule de la comatrice.

OK, super !!!

Citation : rushia

2) Non, la seconde méthode utilise la décomposition en valeurs singulières et non la diagonalisation, elle est donc valable pour toute matrice inversible.

</citation>

d'accord merci

Au fait dernière question :
=> quel est l'intérêt des méthode itaratives par rapport aux méthodes directes ??