Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
151 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Gram-Schmidt et calcul d'inverse: complexité
l’an passé
avatar
Soit $M\in GL_n(\mathbb{R})$. Si $R$ est la matrice des vecteurs obtenus en appliquant Gram-Schmidt sur les colonnes de $M$, on a $M=PR^{-1}$, où $P$ est une matrice orthogonale.

En particulier, on a $M^{-1}=RR^t M^t$.

Du coup, on obtient un algorithme pour calculer $M^{-1}$ à partir de $M.$

Quelle est sa complexité en fonction de $n$ ? J'imagine que cela doit être équivalent (voire pire) que la complexité des algos connus, mais je suis curieux (et nul en complexité !)

Merci!



Edité 3 fois. La dernière correction date de l’an passé et a été effectuée par jacquot.
Re: Gram Schmidt et calcul d'inverse: complexité
l’an passé
Le calcul d'un produit scalaire est en O($n$) et il y en a environ $n^2/2$ à calculer ; on est donc en O($n^3$), tout comme les algo du genre pivot. Cela dit, la décomposition ci-dessus me semble avoir plus un intérêt théorique que réellement algorithmique.

Cdlt, Hicham
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 138 291, Messages: 1 342 360, Utilisateurs: 24 786.
Notre dernier utilisateur inscrit Ariste.


Ce forum
Discussions: 17 456, Messages: 169 295.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page