Lalgèbre linéaire numérique, aussi appelée algèbre linéaire appliquée, consiste en l'étude de la mise en application des opérations matricielles afin de créer des algorithmes informatiques qui fournissent de façon efficace et précise des réponses approchées à des problèmes de mathématiques continues. C'est ainsi un sous-domaine de l'analyse numérique, mais aussi une branche de l'algèbre linéaire. Les ordinateurs utilisent l'arithmétique à virgule flottante et ne peuvent représenter exactement les données irrationnelles. Par conséquent, lorsqu'un algorithme est appliqué à une matrice de données, l'écart entre la valeur estimé et la valeur exacte peut s'accroître. L'algèbre linéaire numérique exploite les propriétés des vecteurs et des matrices pour développer des algorithmes minimisant l'erreur introduite par l'ordinateur, tout en veillant à leur efficacité maximale.
L'algèbre linéaire numérique vise à résoudre des problèmes de mathématiques continues à l'aide d'ordinateurs à précision finie. Ses applications aux sciences naturelles et sociales sont donc aussi larges que celles des mathématiques continues. Elle constitue souvent un élément fondamental des problèmes apparaissant dans l'ingénierie et le calcul scientifique, tels que le traitement d'images et de signaux, les télécommunications, les mathématiques financières, les simulations en science des matériaux, la biologie structurale, l'exploration de données, la bio-informatique, la dynamique des fluides et les statistiques. Les méthodes matricielles sont particulièrement utilisées dans les méthodes des différences finies, des éléments finis et plus généralement la modélisation des équations différentielles. Soulignant l'étendue des applications de l'algèbre linéaire numérique, Lloyd N. Trefethen et David Bau III affirment qu'elle est « aussi fondamentale pour les sciences mathématiques que le calcul différentiel et intégral et les équations différentielles » , même s'il s'agit d'un domaine relativement restreint. Étant donné que de nombreuses propriétés des matrices et des vecteurs s'appliquent également aux fonctions et aux opérateurs, l'algèbre linéaire numérique peut aussi être considérée comme une branche d'analyse fonctionnelle qui met plus particulièrement l'accent sur les algorithmes pratiques.
En algèbre linéaire numérique, on rencontre fréquemment des problèmes tels que l'obtention de décompositions matricielles ( décomposition en valeurs singulières, factorisation QR, factorisation LU ou décomposition spectrale ), qui permettent de résoudre des problèmes d'algèbre linéaire usuels, comme la résolution de systèmes d'équations linéaires, la recherche de valeurs propres ou l'optimisation par moindres carrés. L'objectif principal de l'algèbre linéaire numérique est de développer des algorithmes qui n'introduisent pas d'erreurs lorsqu'ils sont appliqués à des données réelles sur un ordinateur à précision finie. Pour ce faire, on privilégie souvent les méthodes itératives aux méthodes directes.
Histoire L'algèbre linéaire numérique a été développée par des mathématiciens pionniers de l'informatique comme John von Neumann, Alan Turing, James H. Wilkinson, Alston Scott Householder, George Forsythe et Heinz Rutishauser, afin d'utiliser les premiers ordinateurs dans la résolution de problèmes de mathématiques continues, comme les problèmes de balistique et les systèmes d'équations aux dérivées partielles. La première tentative sérieuse de minimiser les erreurs informatiques lors de l'application d'algorithmes à des données réelles est celle de John von Neumann et Herman Goldstine en 1947. Ce domaine s'est développé à mesure que la technologie a permis aux chercheurs de résoudre des problèmes complexes sur des matrices de très grande taille et de haute précision, et certains algorithmes numériques ont acquis une importance croissante grâce à des technologies comme le calcul parallèle qui en ont fait des approches pratiques pour la résolution de problèmes scientifiques.
Décompositions matricielles
Matrices partitionnées Pour de nombreux problèmes d'algèbre linéaire appliquée, il est utile de considérer une matrice comme une concaténation de vecteurs colonnes. Par exemple, lors de la résolution du système linéaire , plutôt que de comprendre x comme le produit de la matrice inverse avec le vecteur b, il est utile de considérer x comme le vecteur des coefficients du développement linéaire de b dans la base formée par les colonnes de A. Considérer les matrices comme une concaténation de colonnes est également une approche pratique pour les algorithmes matriciels. En effet, ces algorithmes contiennent fréquemment deux boucles imbriquées : l’une parcourant les colonnes d’une matrice A, et l’autre ses lignes. Par exemple, pour les matrices et les vecteurs et , on peut utiliser la perspective de partitionnement en colonnes pour calculer comme
for q = 1:n for p = 1:m y(p) = A(p,q)*x(q) + y(p) end end
Décomposition en valeurs singulières La décomposition en valeurs singulières d'une matrice consiste à trouver la forme où U et V sont unitaires, et est diagonale. Les éléments diagonaux de sont appelées les valeurs singulières de A. Parce que les valeurs singulières sont les racines carrées des valeurs propres de , il existe un lien étroit entre la décomposition en valeurs singulières et la décomposition en valeurs propres. Cela signifie que la plupart des méthodes de calcul de la décomposition en valeurs singulières sont similaires aux méthodes de calcul des valeurs propres. La méthode peut-être la plus courante utilise les transformations de Householder.
Factorisation QR La factorisation QR d'une matrice est le produit d'une matrice et d'une matrice de sorte que A = QR, où Q est orthogonal et R est triangulaire supérieure. Les deux principaux algorithmes de calcul des factorisations QR sont le procédé de Gram-Schmidt et la transformation de Householder. La factorisation QR est souvent utilisée pour résoudre les problèmes de moindres carrés linéaires et les problèmes de valeurs propres (via l'algorithme QR itératif).
Factorisation LU La factorisation LU d'une matrice A consiste à construire une matrice triangulaire inférieure L et une matrice triangulaire supérieure U, telles que A = LU. La matrice U est obtenue par une procédure de triangularisation supérieure qui consiste à multiplier à gauche A par une série de matrices pour former le produit , de sorte que de manière équivalente .
Diagonalisation La diagonalisation d'une matrice est , où les colonnes de X sont les vecteurs propres de A, et est une matrice diagonale dont les éléments diagonaux sont les valeurs propres correspondantes de A. Il n'existe pas de méthode directe pour trouver la décomposition en valeurs propres d'une matrice quelconque. Comme il est impossible d'écrire un programme qui trouve les racines exactes d'un polynôme quelconque en temps fini, tout solveur de valeurs propres général doit nécessairement être itératif.
Algorithmes
Pivot de Gauss Du point de vue de l'algèbre linéaire numérique, l'élimination de Gauss est une procédure permettant de factoriser une matrice A en sa factorisation LU, ce que l'élimination de Gauss accomplit en multipliant à gauche A par une suite de matrices jusqu'à ce que U soit triangulaire supérieure et L triangulaire inférieure, où . Les programmes naïfs d'élimination gaussienne sont connus pour leur grande instabilité et produisent des erreurs considérables lorsqu'ils sont appliqués à des matrices comportant de nombreux chiffres significatifs. La solution la plus simple consiste à introduire le pivot, ce qui permet d'obtenir un algorithme d'élimination de Gauss modifié et stable .
Résolution des systèmes linéaires L'algèbre linéaire numérique considère généralement les matrices comme une concaténation de vecteurs colonnes. Afin de résoudre le système linéaire , l'approche algébrique traditionnelle consiste à considérer x comme le produit de avec b. L'algèbre linéaire numérique interprète plutôt x comme le vecteur des coefficients de la décomposition de b dans la base formée par les colonnes de A.
De nombreuses décompositions différentes peuvent être utilisées pour résoudre le problème linéaire, en fonction des caractéristiques de la matrice A et des vecteurs x et b, ce qui peut rendre une factorisation beaucoup plus facile à obtenir que d'autres. Si A = QR est une factorisation QR de A, alors de manière équivalente on a . Cela se calcule aussi facilement qu'une factorisation matricielle . Si est une décomposition spectrale A, et on cherche à trouver b tel que b = Ax, avec et , alors on a . Ceci est étroitement lié à la résolution du système linéaire par décomposition en valeurs singulières, car les valeurs singulières d'une matrice sont les valeurs absolues de ses valeurs propres, qui sont également équivalentes aux racines carrées des valeurs absolues des valeurs propres de la matrice de Gram . Et si A = LU est une factorisation LU de A, alors Ax = b peut être résolu par un algorithme de descente-remontée à l'aide des matrices triangulaires Ly = b et Ux = y .
Optimisation par moindres carrés Les décompositions matricielles suggèrent plusieurs façons de résoudre le système linéaire r = b − Ax, où l'on cherche à minimiser r, comme dans le problème de régression. L'algorithme QR résout ce problème en calculant la factorisation QR réduite de A et en la réarrangeant pour obtenir . Ce système triangulaire supérieur peut alors être résolu pour x. La décomposition en valeurs singulières (SVD) propose également un algorithme pour obtenir la solution du problème exprimé comme un problème de moindres carrés linéaires. En calculant la décomposition SVD réduite puis en calculant le vecteur , on ramène le problème des moindres carrés à un système diagonal simple. Le fait que les factorisations QR et la SVD permettent d'obtenir des solutions par moindres carrés signifie qu'en plus de la méthode classique des équations normales pour résoudre les problèmes de moindres carrés, ces problèmes peuvent également être résolus par des méthodes incluant l'algorithme de Gram-Schmidt et les méthodes de Householder.
Conditionnement et stabilité On considère un problème sous forme d'une fonction , où X est un espace vectoriel normé de données et Y est un espace vectoriel normé de solutions. Pour un certain point de données . On dit que le problème est mal conditionné si une petite perturbation de x entraîne une grande variation de la valeur de f ( x ). On peut quantifier cela en définissant un nombre de conditionnement qui mesure la qualité du conditionnement du problème, défini par