Dans cette section, nous mettrons au point des fonctions permettant de créer des matrices et de les afficher sous un format lisible.
Définir la fonction make_matrix : int -> int -> float array array telle que make_matrix n p retourne un tableau de n tableaux à p éléments contenant des 0., par exemple :
# make_matrix 3 4;; - : float array array = [|[|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]|]
Notez bien qu’en caml light, Array est remplacé par vect.
Définir les fonctions nb_lines : ’a array -> int et nb_columns : ’a array array -> int retournant respectivement le nombre de lignes et de colonnes de la matrice passée en paramètre.
Définir la fonction fill_matrix : ’a array array -> (int * int -> ’a) -> unit telle que fill_matrix m f place dans la matrice m les images de ses coordonnées par f, ainsi on aura mij = f(i, j). Par exemple :
# let m = make_matrix 3 4;; val m : float array array = [|[|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]|] # fill_matrix m (function i,j -> float_of_int (i + j + 1));; - : unit = () # m;; - : float array array = [|[|1.; 2.; 3.; 4.|]; [|2.; 3.; 4.; 5.|]; [|3.; 4.; 5.; 6.|]|]
Définir la fonction identity : int -> float array array telle que identity n retourne la matrice identité d’ordre n.
Définir la fonction copy_matrix : float array array -> float array array telle que copy_matrix retourne une copie de la matrice m.
Définir la fonction integers : int -> float array array telle que integers n retourne la matrice ligne (1 2 3 … n).
Définir la fonction str_of_matrix : float array array -> string retournant une représentation en chaîne de caractères de la matrice passée en paramètre. Par exemple :
# print_string (str_of_matrix (identity 4));; 1. 0. 0. 0. 0. 1. 0. 0. 0. 0. 1. 0. 0. 0. 0. 1. - : unit = ()
Définir la fonction print_matrix : float array array -> unit affichant la matrice passée en paramètre. Par exemple :
# print_matrix (identity 4);; 1. 0. 0. 0. 0. 1. 0. 0. 0. 0. 1. 0. 0. 0. 0. 1. - : unit = ()
Définir la fonction matrix_of_list : float list -> float array array retournant une matrice ligne contenant les éléments de la liste passée en paramètre. Par exemple,
# matrix_of_list [1.;2.;4.;3.;5.;6.];; - : float array array = [|[|1.; 2.; 4.; 3.; 5.; 6.|]|]
Définir la fonction list_of_vector : ’a array -> ’a list retournant une liste contenant les éléments de la matrice passée en paramètre. Par exemple,
# list_of_vector [|1;2;3|];; - : int list = [1; 2; 3]
Définir la fonction list_of_matrix : ’a array array -> ’a list list retournant une liste de liste contenant les éléments de la matrice passée en paramètre. Par exemple,
# list_of_matrix [|[|1;2;3|]; [|4;5;6|]|];; - : int list list = [[1; 2; 3]; [4; 5; 6]]
Nous allons maintenant implémenter les opérations les plus courantes sur les matrices : somme, produit, transposition, etc.
Définir la fonction transpose : float array array -> float array array retournant la transposée de la matrice passée en paramètre.
Définir la fonction rotation : float array array -> float array array retournant une copie de la matrice passée en paramètre transformée de la façon suivante :
# rotation [|[|1. ; 2. ; 3.|] ; [|4. ; 5. ; 6. |]; [|7. ; 8. ; 9. |]; [|10. ; 11. ; 12. |]|];; - : float array array = [|[|12.; 11.; 10.|]; [|9.; 8.; 7.|]; [|6.; 5.; 4.|]; [|3.; 2.; 1.|]|]
Définir la fonction add_matrix : float array array -> float array array -> float array array retournant la somme des matrices passées en paramètre. Vous créerez l’exception Dimensions_mismatch et l’utiliserez dans cette fonction si les deux matrices ne peuvent être additionnées..
Définir la fonction trace : float array array -> float retournant la trace de la matrice passée en paramètre. Vous lèverez l’exception Dimensions_mismatch si la matrice n’est pas carrée.
Définir la fonction mult_matrix_const : float array array -> float -> float array array telle que mult_matrix_const m k retourne le produit de la matrice m par la constante k.
Définir la fonction mult_matrix : float array array -> float array array -> float array array retournant le produit des matrices passées en paramètre. Vous contrôlerez les dimensions des deux matrices.
Définir la fonction exp_matrix : float array array -> int -> float array array telle que exp_matrix m n retourne m élevée à la puissance n.
Nous allons maintenant nous intéresser à une opération davantage subtile, l’inversion de matrice. Bien qu’il existe de nombreux algorithmes très performants pour ce faire, nous allons implémenter celui que vous connaissez déjà. Pour inverser une matrice m, on appliquera le pivot de Gauss sur m jusqu’à obtenir la matrice identité, on appliquant simultanément ces opérations sur la matrice identité, on obtiendra à la fin l’inverse de m.
Pour des raisons de simplicité, les indices que nous utiliserons ici ne seront pas les indices mathématiques (commençant à 1), mais les indices telles qu’ils sont utilisés en caml, en comptant à partir de 0.
Définir la fonction add_linear_combination : float array array -> int * float -> int * float -> unit telle que add_linear_combination m (lg, wg) (ld, wd) effectue l’opération Llg ← wgLlg + wdLld sur la matrice m. Cette opération consiste à remplacer la ligne d’indice lg par la combinaison linéaire obtenue en additionnant les lignes d’indices lg et ld pondérées par les réels wd et wd.
Définir la fonction pivot : float array array -> float array array -> int * int -> unit. pivot m inv (a, b) effectue sur m une itération de l’algorithme du pivot de Gauss en utilisant mab comme pivot. Les 0 se trouvant dans les b−1 premières colonnes de m ne doivent pas être éliminés par l’exécution de la fonction, et les coefficients de trouvant en dessous du pivot doivent passer à 0.
La matrice m ne doit pas être recopiée mais modifiée, les opérations effectuées sur les lignes de m doivent être répercutées sur la matrice inv.
Par exemple, l’appel de pivot m inv (0, 0) sur les matrices
| m= | ⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ | et inv= | ⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ |
transforme les variable m et inv de la façon suivante :
| m= | ⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ | et inv= | ⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ |
Ce qui donne
val m : float array array = [|[|2.; 5.; 8.|]; [|4.; 7.; 0.|]; [|1.; 9.; 3.|]|] val inv : float array array = [|[|1.; 0.; 0.|]; [|0.; 1.; 0.|]; [|0.; 0.; 1.|]|] # pivot m inv (0, 0);; - : unit = () # m;; - : float array array = [|[|2.; 5.; 8.|]; [|0.; -6.; -32.|]; [|0.; 13.; -2.|]|] # inv;; - : float array array = [|[|1.; 0.; 0.|]; [|-4.; 2.; 0.|]; [|-1.; 0.; 2.|]|]
Il n’est possible d’utiliser mab comme pivot que s’il est est non nul. Si mab = 0, il convient de permuter la ligne d’indice a avec une ligne k (vérifiant k > a) de sorte que le pivot soit non nul. Définir la fonction find_pivot : float array array -> int -> int telle que find_pivot m i recherche un pivot dans la colonne d’indice i, et retourne l’indice de la ligne k telle que mki ≠ 0 et k ≥ i. Par exemple,
# find_pivot [|[|0.; 5.; 8.|]; [|0.; 7.; 0.|]; [|1.; 9.; 3.|]|] 0;; - : int = 2
Si un tel k n’existe pas, alors la matrice n’est pas inversible, et vous lèverez l’exception Singular_matrix.
Définir la fonction swap_items : ’a array array -> int * int -> int * int -> unit telle que swap_items m (l1, c1) (l2, c2) permute dans la matrice m les éléments ml1,c1 et ml2,c2.
Définir la fonction swap_lines : ’a array array -> int -> int -> unit telle que swap_lines m i k permute dans la matrice m les lignes d’indices i et k.
Définir la fonction iteration_pivot : float array array -> float array array -> int -> unit telle que iteration_pivot m inv i recherche dans la colonne i de la matrice m un pivot, l’amène en mii (en permutant éventuellement la ligne i avec une autre ligne), et annule tous les mij (i < j) avec des opérations sur les lignes de m.
Toutes les opérations sur les lignes de m seront répercutées sur la matrice inv.
Définir la fonction reduce_diagonal : float array array -> float array array -> unit telle que si m est une matrice diagonale, alors reduce_diagonal m inv amène tous les coefficients diagonaux à 1 avec des opérations sur les lignes de m. Toutes ces opérations sur les lignes de m doivent être répercutées sur inv.
Définir la fonction apply_function : (’a -> ’a) -> ’a -> int -> ’a telle que apply_function f x n retourne l’image de x par la fonction obtenue en composant f avec elle-même n fois. Par exemple, apply_function f x 3 retourne f3(x)= f(f(f(x))). On considérera que f0 est la fonction identité.
Définir la fonction inverse_matrice : float array array -> float array array telle que inverse_matrice m retourne la matrice inverse de m. Attention, inverse_matrice ne doit pas produire d’effet de bord.
Définir la fonction solve_system : float array array -> float array array -> float array array tel que solve_system a y retourne la solution x de l’équation Ax = y.