Décomposition LU pour les matrices tridiagonales (Java)

Question

Je crée une classe pour représenter les matrices tridiagonales. Ce sont des matrices carrées qui ont un ensemble de valeurs non nulles sur la diagonale, et des valeurs non nulles sur les diagonales supérieures et inférieures, puis des zéros partout ailleurs.

Pour les stocker, j'utilise trois tableaux 1D: un pour chaque diagonale.

Voici un exemple:

d_0 u_0 0  0 
l_0 d_1 u_1 0 
0 l_1 d_2 u_2 
0  0 l_2 d_3 

Donc il y a un tableau pour le a_i, un pour le u_i et un pour le l_i. Les zéros ne sont pas stockés.

J'ai besoin d'un algorithme pour effectuer une décomposition LU. LU décomposition serait généralement donné les deux matrices suivantes:

1  0  0 0 
a_0 1  0 0 
0 a_1 1 0 
0  0 a_2 1 


b_0 c_0 0  0 
0 b_1 c_1 0 
0  0 b_2 c_2 
0  0  0 b_3 

Cependant, les 1 de sont inutiles comme les zéros, ils ont juste l'espace des déchets je rechercherai donc l'algorithme de retour de la matrice tridiagonal suivante pour agir comme la décomposition LU:

b_0 c_0 0  0 
a_0 b_1 c_1 0 
0  a_1 b_2 c_2 
0  0 a_2 b_3 

J'ai réussi à obtenir les équations suivantes:

c_i = u_i for all i 

b_0=d_0 

l_i = a_i * b_i for all i 

d_(i+1) = a_i * c_i + b(i+1) for i>=1 

Mais je ne suis pas sûr de savoir comment trouver une formule générale pour tous les a_i, b_i et c _i c'est ce dont j'ai besoin.

Est-ce que quelqu'un sait d'un bon algorithme, facile à programmer pour faire cela pour moi. Je ne cherche rien d'efficace, juste le plus facile à programmer.

Merci beaucoup d'avance.

Answer 1

Est-ce un devoir? Pourquoi réinventer la roue? Utilisez ce lien sur la décomposition de LU avec C#. Désolé, vous devez traduire Java

http://msdn.microsoft.com/en-us/magazine/jj863137.aspx

static double[][] MatrixDecompose(double[][] matrix, 
    out int[] perm, out int toggle) { 
    ... 
}