Ein Löser für 2-2-Bandmatrizen

Quoi?

Le calcul de courbes de spline demande la solution de systèmes d'équations linéaires avec un nombre d'équations proche du nombre de points à interpoler. Pour des splines cubiques, les matrices des systèmes d'équations correspondants ne contiennent que la diagonale et une sous-diagonale de chaque côté. Pour ces systèmes, des solutions sont connues et répandues.

Pour des fonctions d'ordre supérieur ou d'autres problèmes il peut être utile de pouvoir résoudre des systèmes sous forme 2-2-sous-diagonales. Une solution est dérivée et démontrée dans la suite.

Décomposition LU

La solution du système d'équation repose sur la décomposition LU et le fait - la preuve étant omise - que la décoposition d'une matrice de forme 2-2 diagonale est également dans la même forme.

Partons de la matrice initiale A de structure 2-2 diagonale et considérons les deux premiers pas de la décomposition LU:

Pas 1

Pas 1 transforme la matrice A = A⁽¹⁾ en matrice A⁽²⁾

Quels éléments sont modifiés?

• Ligne 1 reste inaltérée
• Colonne 1 dès ligne 2 résulte par division des éléments a₂₁...a_n1 par a₁₁. Pour cause de la structure en ruban, a₂₁ et a₃₁ seuls sont importants, le reste est zéro
• La sous-matrice a⁽²⁾₂₂ à a⁽²⁾₃₃ est obtenue par soustraction du produit dyadique de vecteurs [a⁽²⁾₂₁, a⁽²⁾₃₁]^T mit [a⁽¹⁾₁₂, a⁽¹⁾₁₃] de [[a⁽¹⁾₂₂, a⁽¹⁾₂₃], [a⁽¹⁾₃₂, a⁽¹⁾₃₃]]
  a⁽²⁾₂₂ = a⁽¹⁾₂₂ – (a⁽¹⁾₁₂a⁽¹⁾₂₁)/a⁽¹⁾₁₁ etc.
• Colonne 4, colorée en orange dans le tableau ci-haut est également obtenue par soustraction du produit du vecteur en colonne 1 par ligne 1. Cette dernière contient zéro dès a₁₄, laissant colonne 4 et les suivantes inaltérée.
• Par analogie, ligne 4, colorée en jaune et les suivantes jusqu'à n restent inaltérées.

En tout, seuls les éléments de la sous-matrice A⁽¹⁾_2..3,1..3 subissent des modifications.

Pas 2

Pas 2 transforme matrice A⁽²⁾ en matrice A⁽³⁾ et, comme pour pas 1, seul un bloc 2x3 subit une modification.

Quels éléments sont modifiés et comment?

• Ligne 2 reste sans modification
• En colonne 2, les éléments a⁽³⁾₃₂ et a⁽³⁾₄₂ sont produits depuis a⁽²⁾₃₂ et a⁽²⁾₄₂ par division avec a⁽²⁾₂₂ du pas 1. Faute de valeurs intermédiaires, ces deux opérations doivent etre contenues dans une formule: a⁽³⁾₃₂ = (a⁽¹⁾₃₂ – (a⁽²⁾₁₂a⁽²⁾₃₁)/a⁽²⁾₁₁)/a⁽²⁾₂₂) etc.
• La sous-matrice a⁽³⁾₃₃ bis a⁽³⁾₄₄ est produite par soustraction du produit de vecteurs dyadique des vecteurs [a⁽³⁾₃₂, a⁽³⁾₄₂]^T et [a⁽²⁾₂₃, a⁽²⁾₂₄] de [[a⁽²⁾₃₃, a⁽²⁾₃₄], [a⁽²⁾₄₃, a⁽²⁾₄₄]]
  Elément a⁽³⁾₃₃ mérit mention, étant obtenu depuis a⁽²⁾₃₃. Puisqu'élémentt a⁽²⁾₃₃ n'est pas stocké en intermédiaire, rendant nécéssaire d'inclure également le pas 1 de a⁽¹⁾₃₃ vers a⁽²⁾₃₃ dans la formule. Pour le calcul des éléments des colonnes et lignes 4, les valeurs sont disponibles à partir de la matrice originale

Pour les pas suivants k, toutes les valeurs d'entrée des calculs sont disponibles soit dpuis dans la plage des calculs A^(k-1), ou depuis la matric initiale A.

Exemple

Système d'équations linéaire Ax - b = 0

Matrice A  et vecteur de conditions b

Le schéma de calcul implémenté peut traiter jusqu'à 20 équations, également moins. Les éléments pivot ne sont pas cherchés. Dans la plage d'entrée de A les colonnes a₂ et a₁ correpsondent aux diagonales secondaires inférieures, colonnes c₁ et c₂ aux supérieures.

Décomposition LU et vecteur y

La décomposition LR de A en un format économique en mémoirein contient les deux matrices L et U de façon imbriquée. La matrice L (désignée par M ) possède une diagonale pleine de 1 qui ne sont pas stockés mais directement contenus dans les formules de calcul.

Vecteur de solutions x

La solution du système d'équations.