Calculateur quantique: factorisation des entiers
Difficulté de la factorisation Exemple de factorisation par divisions successives Soit N Factoriser N c'est recherché tous les nombres premiers n diviseurs de N avec 1
Cours de Calcul Formel : R esum e
5 3 Algorithme de factorisation dans IZ p[X] factorisation avec degr es egaux des facteurs 20 On voit souvent un ordinateur comme un calculateur, c’est
Table des mati eres - Accueil du site de lUniversité
On dit qu’on a e ectu e une factorisation de Gauss ou factorisation LU de A Remarque 1 1 Il est aussi possible avec le m^eme algorithme d’obtenir la factorisation LU d’une matrice de M m(C), avec m n, si les pivots qui apparaissent sont non nuls 1 1 Cout^ de la m ethode d’ elimination de Gauss On estime le cout^ de l’ elimination
METHODES NUMERIQUES - Université de Genève
Matlab utilise des mots en double pr´ecision de 64 bits avec t = 52 le nombre de bits de la mantisse et e ∈[−1023,1024] les valeurs possibles pour l’exposant On a alors m ≈1 11 ×10−308 et M ≈1 67 ×10308 La fonction Matlab realmin et realmax produit m respectivement M
Journée HPC du LJLL - 30 novembre
Algorithme de calcul des valeurs propres d’une matrice (calcule toutes les valeurs propres et tous les vecteurs propres) Factorisation QR d’une matrice Mise en œuvre sur calculateur parallèle Premiers résultats sur hpc1 Généralisation Quelques références Pascal Joly (Laboratoire Jacques-Louis Lions) Journée HPC du LJLL décembre
Méthode QR Polytech’Paris-UPMC
Il existe différents moyens de décomposer une matrice quelconque L’une des plus utilisée est la décomposition QR Théorème Soit A une matrice quelconque de Mn,m(C) ∃Q ∈Mm,m une matrice orthogonale, ∃R ∈Mn,m(C) une matrice triangulaire supérieure telles que A = QR On peut utiliser cette décomposition pour résoudre le
I Propriétés fondamentales
II 3 Linéarisation et factorisation On déduit de la série précédente les formules de linéarisation d'un produit de cos ou sin cosacosb = 1 2 (cos(a b)+cos(a+b)) sinasinb = 1 2 (cos(a b) cos(a+b)) sinacosb = 1 2 (sin(a b)+sin(a+b)) En posant p= a bet q= a+ bdans les formules précédentes, on obtient les formules de factorisation de
MATLAB:Fonctions,polynoˆmesetorthonormalisation
Exercice 3 Comparer l’utilisation de polyfit avec la m´ethode d’interpolation de Lagrange 3 proc´edure de orthonormalisation de Gram-Schmidt Soit (X1,··· ,X m) une famille libre de vecteurs dans Rm On peut construire une base or-thonorm´e (U1,··· ,U m) a partir de (X1,··· ,X m) en suivant la proc´edure d
Les congruences Principe des congruences
Or 754 = donc donc le reste de 754 par 8 est 2 Exemple 2 Déterminer le reste dans la division euclidienne de par 7 On commence par calculer avec les congruences les puissances de 3 : Pourquoi prendre – 1 plutôt que 6 ? Parce que des puissances de – 1 sont plus faciles à calculer de tête que des puissances de 6
Cryptographie post-quantique: processus de standardisation du
Permet de faire des recherches sur des ensembles non structurés de taille N en O(p N) avec un espace en O(log(N)) Attaque AES, SHA Diminue de moitié la taille de la clef Algorithme de Harrow, Hassidim et Lloyd (2009) Permet de résoudre des systèmes linéaires creux de N variables en O(log(N)k2) où k est le conditionnement de la matrice
[PDF] exercice géothermie ts
[PDF] factoriser en ligne avec étapes
[PDF] sujet bac geothermie
[PDF] développer en ligne
[PDF] factorisation en ligne avec détails
[PDF] epices marocaine pour poulet
[PDF] les epices marocaine en arabe et francais
[PDF] tableau épices cuisine
[PDF] utilisation des epices et aromates
[PDF] bienfaits des épices et aromates
[PDF] quels sont les bienfaits des épices
[PDF] géothermie et propriétés thermiques de la terre cours
[PDF] controle svt terminale s géologie
[PDF] sujet bac corrigé svt géologie
- p. 1/21
Méthode QR
Polytech'Paris-UPMC
IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion
Introduction- p. 2/21
Introduction
IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 3/21
Décomposition QR
Il existe différents moyens de décomposer une matrice quelconque. L'une des plus utilisée est la décomposition QR.ThéorèmeSoitAune matrice quelconque deMn,m(C).
?Q? Mm,mune matrice orthogonale ?R? Mn,m(C)une matrice triangulaire supérieure telles que A=QRIntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 3/21
Décomposition QR
Il existe différents moyens de décomposer une matrice quelconque. L'une des plus utilisée est la décomposition QR.ThéorèmeSoitAune matrice quelconque deMn,m(C).
?Q? Mm,mune matrice orthogonale ?R? Mn,m(C)une matrice triangulaire supérieure telles que A=QR On peut utiliser cette décomposition pour résoudre le système linéaire Ax=bIntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 3/21
Décomposition QR
Il existe différents moyens de décomposer une matrice quelconque. L'une des plus utilisée est la décomposition QR.ThéorèmeSoitAune matrice quelconque deMn,m(C).
?Q? Mm,mune matrice orthogonale ?R? Mn,m(C)une matrice triangulaire supérieure telles que A=QR On peut utiliser cette décomposition pour résoudre le système linéaireAx=b?QRx=b
IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 3/21
Décomposition QR
Il existe différents moyens de décomposer une matrice quelconque. L'une des plus utilisée est la décomposition QR.ThéorèmeSoitAune matrice quelconque deMn,m(C).
?Q? Mm,mune matrice orthogonale ?R? Mn,m(C)une matrice triangulaire supérieure telles que A=QR On peut utiliser cette décomposition pour résoudre le système linéaireAx=b?QRx=b?Rx=tQb
IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 3/21
Décomposition QR
Il existe différents moyens de décomposer une matrice quelconque. L'une des plus utilisée est la décomposition QR.ThéorèmeSoitAune matrice quelconque deMn,m(C).
?Q? Mm,mune matrice orthogonale ?R? Mn,m(C)une matrice triangulaire supérieure telles que A=QR On peut utiliser cette décomposition pour résoudre le système linéaire Ax=b?QRx=b?Rx=tQbAn'est pas forcement carrée (système surdéterminé).IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 3/21
Décomposition QR
Il existe différents moyens de décomposer une matrice quelconque. L'une des plus utilisée est la décomposition QR.ThéorèmeSoitAune matrice quelconque deMn,m(C).
?Q? Mm,mune matrice orthogonale ?R? Mn,m(C)une matrice triangulaire supérieure telles que A=QR On peut utiliser cette décomposition pour résoudre le système linéaireAx=b?QRx=b?Rx=tQbAn'est pas forcement carrée (système surdéterminé).La décomposition n'est pas unique.
IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 4/21
Rappel
Définition
(Matrice orthogonales)On appelle matrice orthogonale une matrice dont les colonnes sont orthonorméesC'est à dire les matricesOtelles que :
t OO=I Les matrices orthogonales sont les matrices de changement debases orthogonales.SiOest orthogonale,det(O) =±1.Elles ne changent pas la norme associée au produit scalaire :?u?IRm
?Ou?=?u?Le produit de deux matrices orthogonales est une matriceorthogonale : t (OO?)OO?=tO?tOOO?=IIntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 5/21
Exemple
Par exemple :
Matrices de rotation,
A=? cosθ-sin(θ) sinθcos(θ)?Matrices de permutation,A=(((0 1 00 0 11 0 0)))Matrices de symétrie.
IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 6/21
Intéret
Comme la décomposition LU, cette décomposition transformeune matrice quelconque en produit de matrices plus simples. A=QRIntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 6/21
Intéret
Comme la décomposition LU, cette décomposition transformeune matrice quelconque en produit de matrices plus simples. A=QR Une matrice orthogonale est facile à inverser (tQ=Q-1). ?cela peut être utilisé pour la résolution d'équations linéaires : au lieu de résoudreAx=b, on résoutRx=tQbIntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 6/21
Intéret
Comme la décomposition LU, cette décomposition transformeune matrice quelconque en produit de matrices plus simples. A=QR Une matrice orthogonale est facile à inverser (tQ=Q-1). ?cela peut être utilisé pour la résolution d'équations linéaires : au lieu de résoudreAx=b, on résoutRx=tQbCela fonctionne pour les matrices rectangulaires ?résolution d'équations linéaires surdéterminés (avec plus d'équations que d'inconnues)IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 6/21
Intéret
Comme la décomposition LU, cette décomposition transformeune matrice quelconque en produit de matrices plus simples. A=QR Une matrice orthogonale est facile à inverser (tQ=Q-1). ?cela peut être utilisé pour la résolution d'équations linéaires : au lieu de résoudreAx=b, on résoutRx=tQbCela fonctionne pour les matrices rectangulaires ?résolution d'équations linéaires surdéterminés (avec plus d'équations que d'inconnues)Les matrices orthogonales ont de bonnes propriétés :IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 6/21
Intéret
Comme la décomposition LU, cette décomposition transformeune matrice quelconque en produit de matrices plus simples. A=QR Une matrice orthogonale est facile à inverser (tQ=Q-1). ?cela peut être utilisé pour la résolution d'équations linéaires : au lieu de résoudreAx=b, on résoutRx=tQbCela fonctionne pour les matrices rectangulaires ?résolution d'équations linéaires surdéterminés (avec plus d'équations que d'inconnues)Les matrices orthogonales ont de bonnes propriétés : le déterminant deAest égale à celui deR;IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 6/21
Intéret
Comme la décomposition LU, cette décomposition transformeune matrice quelconque en produit de matrices plus simples. A=QR Une matrice orthogonale est facile à inverser (tQ=Q-1). ?cela peut être utilisé pour la résolution d'équations linéaires : au lieu de résoudreAx=b, on résoutRx=tQbCela fonctionne pour les matrices rectangulaires ?résolution d'équations linéaires surdéterminés (avec plus d'équations que d'inconnues)Les matrices orthogonales ont de bonnes propriétés :le déterminant deAest égale à celui deR;multiplier par une matrice orthogonale ne change pas lanorme (Problème des moindres carrés);
IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 6/21
Intéret
Comme la décomposition LU, cette décomposition transformeune matrice quelconque en produit de matrices plus simples. A=QR Une matrice orthogonale est facile à inverser (tQ=Q-1). ?cela peut être utilisé pour la résolution d'équations linéaires : au lieu de résoudreAx=b, on résoutRx=tQbCela fonctionne pour les matrices rectangulaires ?résolution d'équations linéaires surdéterminés (avec plus d'équations que d'inconnues)Les matrices orthogonales ont de bonnes propriétés :le déterminant deAest égale à celui deR;multiplier par une matrice orthogonale ne change pas lanorme (Problème des moindres carrés);le conditionnement deAest égale à celui deR.
IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 6/21
Intéret
Comme la décomposition LU, cette décomposition transformeune matrice quelconque en produit de matrices plus simples. A=QR Une matrice orthogonale est facile à inverser (tQ=Q-1). ?cela peut être utilisé pour la résolution d'équations linéaires : au lieu de résoudreAx=b, on résoutRx=tQbCela fonctionne pour les matrices rectangulaires ?résolution d'équations linéaires surdéterminés (avec plus d'équations que d'inconnues)Les matrices orthogonales ont de bonnes propriétés :le déterminant deAest égale à celui deR;multiplier par une matrice orthogonale ne change pas lanorme (Problème des moindres carrés);le conditionnement deAest égale à celui deR.
Cette décomposition est aussi utilisée pour le calcul des valeurs propres d'une matrice (voir cours).IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 6/21
Intéret
Comme la décomposition LU, cette décomposition transformeune matrice quelconque en produit de matrices plus simples. A=QR Une matrice orthogonale est facile à inverser (tQ=Q-1). ?cela peut être utilisé pour la résolution d'équations linéaires : au lieu de résoudreAx=b, on résoutRx=tQbCela fonctionne pour les matrices rectangulaires ?résolution d'équations linéaires surdéterminés (avec plus d'équations que d'inconnues)Les matrices orthogonales ont de bonnes propriétés :le déterminant deAest égale à celui deR;multiplier par une matrice orthogonale ne change pas lanorme (Problème des moindres carrés);le conditionnement deAest égale à celui deR.
Cette décomposition est aussi utilisée pour le calcul des valeurs propres d'une matrice (voir cours)....IntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 7/21
Le problème
On dispose d'une matriceAque l'on veut décomposer enQ orthogonale etRtriangulaire supérieure :A=((((((((((()))))))))))
Q(((((((((((())))))))))))
RIntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 7/21
Le problème
On dispose d'une matriceAque l'on veut décomposer enQ orthogonale etRtriangulaire supérieure :A=((((((((((()))))))))))
Q(((((((((((())))))))))))
R Le problème est le même que de trouverHorthogonale telle que : HA=R carQ=tHIntroductionDécomposition QRRappelExempleIntéretLe problèmeDécompositionQRMatrices semblablesConclusion- p. 7/21