Livre_silo 30 août 2013 16:32 Page 8
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
VIII
Informatique pour tous
6.2 Structure de tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.2.1 Construction d’un tableau . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.2.2 Accès aux éléments d’un tableau . . . . . . . . . . . . . . . . . . . . . . 151
6.2.3 Parcours de tous les éléments d’un tableau . . . . . . . . . . . . . . . . . . 153
6.3 Recherche dans un tableau . . . . . . . . . . . . . . . . . . . . . . . . . 155
6.3.1 Recherche séquentielle . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6.3.2 Recherche dichotomique dans un tableau trié . . . . . . . . . . . . . . . . 156
6.4 Recherche d’un mot dans un texte . . . . . . . . . . . . . . . . . . . . . . 158
6.5 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
6.5.1 Création . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.5.2 Copie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.5.3 Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
6.5.4 Transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
6.5.5 Produit matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.6 Mode de passage des tableaux . . . . . . . . . . . . . . . . . . . . . . . . 166
6.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
T
Ingénierie numérique et simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
C
Pivot de Gauss et résolution de systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
7.1 Résolution de AX = Y : principe du pivot . . . . . . . . . . . . . . . . . . 175
7.1.1 Le cas des systèmes triangulaires . . . . . . . . . . . . . . . . . . . . . . 175
7.1.2 Les transvections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.1.3 Le problème de la comparaison à zéro . . . . . . . . . . . . . . . . . . . 177
7.1.4 Formalisation de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . 179
7.1.5 Le formalisme matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7.2 Mise en œuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.2.1 Découper le travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.2.2 Recoller les morceaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.2.3 Comparaison avec numpy . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.3.1 Mise sous forme triangulaire . . . . . . . . . . . . . . . . . . . . . . . . 187
7.3.2 Phase de remontée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
7.3.3 Peut-on faire mieux que n
3 ? . . . . . . . . . . . . . . . . . . . . . . . . 188
7.4 Conditionnement d’une matrice . . . . . . . . . . . . . . . . . . . . . . 191
7.4.1 Mesurer les propagations d’erreurs . . . . . . . . . . . . . . . . . . . . . 191
7.4.2 Le conditionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.4.3 Quelques exemples caractéristiques . . . . . . . . . . . . . . . . . . . . . 192
7.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
VIII
Informatique pour tous
6.2 Structure de tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.2.1 Construction d’un tableau . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.2.2 Accès aux éléments d’un tableau . . . . . . . . . . . . . . . . . . . . . . 151
6.2.3 Parcours de tous les éléments d’un tableau . . . . . . . . . . . . . . . . . . 153
6.3 Recherche dans un tableau . . . . . . . . . . . . . . . . . . . . . . . . . 155
6.3.1 Recherche séquentielle . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6.3.2 Recherche dichotomique dans un tableau trié . . . . . . . . . . . . . . . . 156
6.4 Recherche d’un mot dans un texte . . . . . . . . . . . . . . . . . . . . . . 158
6.5 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
6.5.1 Création . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.5.2 Copie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.5.3 Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
6.5.4 Transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
6.5.5 Produit matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.6 Mode de passage des tableaux . . . . . . . . . . . . . . . . . . . . . . . . 166
6.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
T
Ingénierie numérique et simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
C
Pivot de Gauss et résolution de systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
7.1 Résolution de AX = Y : principe du pivot . . . . . . . . . . . . . . . . . . 175
7.1.1 Le cas des systèmes triangulaires . . . . . . . . . . . . . . . . . . . . . . 175
7.1.2 Les transvections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.1.3 Le problème de la comparaison à zéro . . . . . . . . . . . . . . . . . . . 177
7.1.4 Formalisation de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . 179
7.1.5 Le formalisme matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7.2 Mise en œuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.2.1 Découper le travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.2.2 Recoller les morceaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.2.3 Comparaison avec numpy . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.3.1 Mise sous forme triangulaire . . . . . . . . . . . . . . . . . . . . . . . . 187
7.3.2 Phase de remontée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
7.3.3 Peut-on faire mieux que n
3 ? . . . . . . . . . . . . . . . . . . . . . . . . 188
7.4 Conditionnement d’une matrice . . . . . . . . . . . . . . . . . . . . . . 191
7.4.1 Mesurer les propagations d’erreurs . . . . . . . . . . . . . . . . . . . . . 191
7.4.2 Le conditionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.4.3 Quelques exemples caractéristiques . . . . . . . . . . . . . . . . . . . . . 192
7.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194