diff --git "a/Chapitre 2 - Algebre matricielle/2.10 D\303\251composition LU (applications aux syst\303\250mes lin\303\251aires).ipynb" "b/Chapitre 2 - Algebre matricielle/2.10 D\303\251composition LU (applications aux syst\303\250mes lin\303\251aires).ipynb"
index 1262f0a..77c1bff 100644
--- "a/Chapitre 2 - Algebre matricielle/2.10 D\303\251composition LU (applications aux syst\303\250mes lin\303\251aires).ipynb"
+++ "b/Chapitre 2 - Algebre matricielle/2.10 D\303\251composition LU (applications aux syst\303\250mes lin\303\251aires).ipynb"
@@ -1,351 +1,399 @@
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Concept(s)-clé(s) et théorie\n",
"\n",
"## APPLICATION DE LA DÉCOMPOSITION AUX SYSTÈMES LINÉAIRES \n",
- "Soit un système $Ax=b$ d'équations linéaires aux inconnues $x_1, \\dots, x_n$ et supposons que $A=LU$ où $L$ est triangulaire inférieure et $U$ triangulaire supérieure. Alors on résout le système de la manière suivante :\n",
+ "Soit un système d'équations linéaires aux inconnues $x_1, \\dots, x_n$, représenté sous forme matricielle $A\\vec{x}=\\vec{b}$. Supposons que $A=LU$ où $L$ est triangulaire inférieure et $U$ est un forme échelonnée. Alors on résout le système de la manière suivante.\n",
"\n",
- "1. Poser $Y = (y_1, y_2, \\dots, y_n)^T$\n",
- "2. Résoudre le système $LY=b$ avec la méthode de substitution en avant\n",
- "3. Résoudre le sytème $Ux=y$ avec la méthode de substitution en arrière"
+ "1. Poser $Y = (y_1, y_2, \\dots, y_n)^T$;\n",
+ "2. Résoudre le système $LY=b$ avec la méthode de substitution en avant;\n",
+ "3. Résoudre le sytème $Ux=y$ avec la méthode de substitution en arrière;"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
" \n",
" "
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
" \n",
" "
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import Librairie.AL_Fct as al\n",
"import Corrections.corrections as corrections\n",
"from ipywidgets import interact_manual\n",
"import numpy as np\n",
"import time\n",
"from scipy.linalg import solve_triangular\n",
"import matplotlib.pyplot as plt"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 1\n",
"\n",
"Considerez le système linéaire $Ax=b$, avec $A$ et $b$ donné par:\n",
"\n",
"\\begin{equation}\n",
"A =\n",
"\\begin{pmatrix}\n",
"1 & -1 & 0 \\\\\n",
"2 & 0 & 1 \\\\\n",
"1 & 1 & 1 \n",
"\\end{pmatrix}\n",
"\\qquad b = \n",
"\\begin{pmatrix}\n",
"2 \\\\\n",
"1 \\\\\n",
"-1 \n",
"\\end{pmatrix}\n",
"\\end{equation}\n",
"\n",
"**Sans calculer aucune décomposition LU ni résoudre explicitement le système**, lesquelles des affirmations suivantes sont clairement correctes? [Exécutez la cellule suivante]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"corrections.Ex1Chapitre2_10()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 2 \n",
"\n",
- "Considerez le système linéaire $Ax=b$ avec $A \\in \\mathcal{M}_{4 \\times 4}(\\mathbb{R})$ et $b \\in \\mathcal{M}_{4 \\times 1}(\\mathbb{R})$ donné par:\n",
+ "Considerez le système linéaire $Ax=b$ avec $A \\in \\mathcal{M}_{4 \\times 4}(\\mathbb{R})$ et $b \\in \\mathcal{M}_{4 \\times 1}(\\mathbb{R})$ donnés par:\n",
"\n",
"\\begin{equation}\n",
"A = \n",
"\\begin{pmatrix}\n",
"1 & 0 & -1 & -2 \\\\\n",
"0 & -2 & -2 & 1 \\\\\n",
"1 & 2 & 2 & 1 \\\\\n",
"0 & 1 & 1 & -1\n",
"\\end{pmatrix}\n",
"\\qquad b = \n",
"\\begin{pmatrix}\n",
"1 \\\\\n",
"-2 \\\\\n",
"1 \\\\\n",
"0\n",
- "\\end{pmatrix}\n",
+ "\\end{pmatrix}.\n",
"\\end{equation}\n",
"\n",
- "Profitant de la décomposition LU, résolvez, si possible, le système linéaire."
+ "En utilisation la décomposition LU de A, résolvez, si possible, le système linéaire."
]
},
{
"cell_type": "code",
- "execution_count": null,
+ "execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
+ "#Entrez les coefficients de A et b\n",
"A=[[1,0,-1,-2], [0,-2,-2,1], [1,2,2,1], [0,1,1,-1]]\n",
- "b = [[1], [-2], [1], [0]]\n",
+ "b = [[1], [-2], [1], [0]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Vous allez échelonner la matrice A\n"
+ ]
+ },
+ {
+ "ename": "NameError",
+ "evalue": "name 'al' is not defined",
+ "output_type": "error",
+ "traceback": [
+ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
+ "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)",
+ "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Vous allez échelonner la matrice A'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mal\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprintA\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mr\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0malpha\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m=\u001b[0m \u001b[0mal\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmanualEch\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0mLList\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mnp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0meye\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0mUList\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mnp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0marray\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mastype\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfloat\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
+ "\u001b[0;31mNameError\u001b[0m: name 'al' is not defined"
+ ]
+ }
+ ],
+ "source": [
"print('Vous allez échelonner la matrice A')\n",
"al.printA(A)\n",
"[i,j,r,alpha]= al.manualEch(A)\n",
"LList = [np.eye(4)]\n",
"UList=[np.array(A).astype(float)]\n",
- "print('\\033[1mExecutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')"
+ "print('\\033[1mExécutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"m=al.LU_interactive(i,j,r,alpha, LList, UList)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
- "**Insert the values of the temporary variable y and of the system solution x in the following cell**"
+ "**Entrez ci-dessous les coefficients de la variable temporaire y et de la solution x du système"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
- "y = [[1], [-2], [-2], [-1]] # temporary variable\n",
- "x = [[-5], [12], [-10], [2]] # system solution\n",
+ "y = [[1], [-2], [-2], [-1]] # variable temporaire\n",
+ "x = [[-5], [12], [-10], [2]] # solution du système\n",
"\n",
"corrections.Ex2Chapitre2_10(LList[-1], UList[-1], b, x, y)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 3\n",
"\n",
"Considerez le système linéaire $Ax=b$ avec $A \\in \\mathcal{M}_{3 \\times 4}(\\mathbb{R})$ et $b \\in \\mathcal{M}_{3 \\times 1}(\\mathbb{R})$ donné par:\n",
"\n",
"\\begin{equation}\n",
"A = \n",
"\\begin{pmatrix}\n",
"1 & 2 & 0 & -1 \\\\\n",
"-2 & -2 & -1 & 0 \\\\\n",
"0 & 2 & -2 & 1\n",
"\\end{pmatrix}\n",
"\\qquad b = \n",
"\\begin{pmatrix}\n",
"1 \\\\\n",
"-1 \\\\\n",
"2 \n",
"\\end{pmatrix}\n",
"\\end{equation}\n",
"\n",
"Profitant de la décomposition LU, résolvez, si possible, le système linéaire et marquez ceux des énoncés suivants qui sont corrects"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
+ "#Entrez les coefficients de A et b\n",
"A = [[1,2,0,-1], [-2,-2,-1,0], [0,2,-2,1]]\n",
- "b = [[1], [-1], [2]]\n",
+ "b = [[1], [-1], [2]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
"print('Vous allez échelonner la matrice A')\n",
"al.printA(A)\n",
"[i,j,r,alpha]= al.manualEch(A)\n",
"LList = [np.eye(3)]\n",
"UList=[np.array(A).astype(float)]\n",
- "print('\\033[1mExecutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')"
+ "print('\\033[1mExécutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"m=al.LU_interactive(i,j,r,alpha, LList, UList)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "0214334953bb438a8a6eb92790c5edac",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"interactive(children=(Checkbox(value=False, description='If L is such that all its diagonal elements equal 1, …"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"corrections.Ex3Chapitre2_10()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exemple 1\n",
"\n",
- "Il peut être difficile de comprendre pourquoi la décomposition LU est si importante. En effet il semble que ce ne soit rien de plus qu'une manière différente de mettre en œuvre la méthode d'élimination de Gauss, où au lieu d'impliquer le vecteur droit b dans la procédure de réduction, une matrice (L) codant toutes les opérations élémentaires effectuées sur les lignes de la matrice du système est construit.\n",
+ "Il peut être difficile de comprendre pourquoi la décomposition LU est si importante. En effet il semble que ce ne soit rien de plus qu'une manière différente de mettre en œuvre la méthode d'élimination de Gauss, où au lieu d'impliquer le vecteur b directement dans la procédure de réduction, on va construire une matrice (L) qui contient toutes les opérations élémentaires effectuées sur les lignes de la matrice du système.\n",
"\n",
- "En fin de compte, de toute façon, ce changement apparemment simple est la clé qui rend la décomposition LU (avec toutes ses variantes) très utile dans la pratique réelle; en effet, dans de nombreux cas d'utilisation, il est nécessaire de résoudre plusieurs systèmes linéaires (grands ou énormes), tous présentant la même matrice, mais différents vecteurs du côté droit. Dans de telles situations, il est très utile de s'appuyer sur la décomposition LU; en particulier, la décomposition LU de la matrice est calculée avant la résolution de tous les systèmes linéaires, puis chacun d'eux est rapidement résolu via des schémas de substitution avant / arrière (sur les matrices diagonales supérieure et inférieure L et U). Si la décomposition LU n'est pas utilisée, à chaque étape un système linéaire complet devrait être résolu, conduisant à une augmentation significative en termes de nombre d'opérations et de temps de calcul.\n",
+ "En fin de compte, ce changement apparemment simple est la clé qui rend la décomposition LU (avec toutes ses variantes) très utile dans la pratique réelle; en effet, dans de nombreuses utilisations, il est nécessaire de résoudre plusieurs systèmes linéaires (qui peuvent êtres avec un très grand nombre de variables!). Tous ces systèmes ont la même matrice (L ou U), mais différents vecteurs du côté droit. \n",
+ "Dans de telles situations, il est très utile d'utiliser la décomposition LU! D'abord, la décomposition LU de la matrice est calculée avant la résolution de tous les systèmes linéaires et on ne la calcule qu'une seule fois. En suite, chaque système est rapidement résolu via des schémas de substitution avant / arrière (sur les matrices L et U qui possèdent beaucoup de coefficients nuls). \n",
+ "Si la décomposition LU n'est pas utilisée, alors à chaque étape un système linéaire complet devrait être résolu, conduisant à une augmentation significative en termes de nombre d'opérations et de temps de calcul.\n",
"\n",
"Afin de le montrer, nous présentons ci-dessous comment le nombre d'opérations et le temps d'exécution se comparent si plusieurs grands systèmes linéaires (partageant tous la même matrice) sont résolus en s'appuyant ou non sur la décomposition LU.\n",
"\n",
"**Exécutez la cellule suivante et évaluez les différences de performances ... cela peut prendre quelques minutes**"
]
},
{
"cell_type": "code",
- "execution_count": null,
+ "execution_count": 3,
"metadata": {},
- "outputs": [],
+ "outputs": [
+ {
+ "ename": "SyntaxError",
+ "evalue": "EOL while scanning string literal (, line 29)",
+ "output_type": "error",
+ "traceback": [
+ "\u001b[0;36m File \u001b[0;32m\"\"\u001b[0;36m, line \u001b[0;32m29\u001b[0m\n\u001b[0;31m print(\"Avec décomposition LU: nombre d'opérations:% e, temps d'exécution:% f s %(n_op_lu, time_lu))\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m EOL while scanning string literal\n"
+ ]
+ }
+ ],
"source": [
"N = 1000 # dimension of the linear systems\n",
"Nt = 10000 # number of linear systems to be solved\n",
"A = np.random.rand(N, N);\n",
"start = time.time()\n",
"L, U = al.LU_no_pivoting(A)\n",
"time_lu = 0\n",
"n_op_lu = 2/3*(N**3 - N)\n",
"n_op_no_lu = 0\n",
"\n",
"# solve without using LU \n",
"start = time.time()\n",
"for cnt in range(Nt):\n",
" b = np.random.rand(N,1)\n",
" x = np.linalg.solve(A, b)\n",
" n_op_no_lu += N**3 # --> N^3 operations per cycle, according to Numpy/LAPACK documentation on benchmark cases\n",
"time_no_lu = time.time() - start\n",
"\n",
"# solve using LU\n",
"start = time.time()\n",
"for cnt in range(Nt):\n",
" b = np.random.rand(N,1)\n",
" y = solve_triangular(L, b)\n",
" n_op_lu += 2*N**2 - N # computational cost of forward substitution\n",
" x = solve_triangular(U, y)\n",
" n_op_lu += 2*N**2 - N # computational cost of backward substitution\n",
"time_lu += time.time() - start\n",
"\n",
"print(\"Sans décomposition LU: nombre d'opérations:% e, temps d'exécution:% f s\" %(n_op_no_lu, time_no_lu))\n",
"print(\"Avec décomposition LU: nombre d'opérations:% e, temps d'exécution:% f s %(n_op_lu, time_lu))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Vous pouvez comparer les temps d'exécution et le nombre d'opérations pour différentes tailles de matrice (c'est-à-dire changer le paramètre N) et pour un nombre différent de systèmes lineaires (c'est-à-dire changer le paramètre N_t)**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Passez au notebook 2.11: Décomposition en blocs](2.11%20Décomposition%20en%20blocs.ipynb)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
- "version": "3.7.4"
+ "version": "3.6.9"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
diff --git "a/Chapitre 2 - Algebre matricielle/2.6-2.7 Crit\303\250res d'inversibilit\303\251.ipynb" "b/Chapitre 2 - Algebre matricielle/2.6-2.7 Crit\303\250res d'inversibilit\303\251.ipynb"
index 70f1ddb..32a932a 100644
--- "a/Chapitre 2 - Algebre matricielle/2.6-2.7 Crit\303\250res d'inversibilit\303\251.ipynb"
+++ "b/Chapitre 2 - Algebre matricielle/2.6-2.7 Crit\303\250res d'inversibilit\303\251.ipynb"
@@ -1,309 +1,242 @@
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# **Concept(s)-clé(s) et théorie**\n",
"\n",
"## PREMIER CRITÈRE D'INVERSIBILITÉ \n",
"Une matrice $A \\in \\mathcal{M}_{n \\times n}(\\mathbb{R})$ est inversible si et seulement si le système homogène $Ax=0$ possède une solution unique, à savoir, la solution triviale.\n",
"\n",
"## COROLLAIRE DU PREMIER CRITÈRE D'INVERSIBILITÉ \n",
"Soit $A \\in \\mathcal{M}_{n \\times n}(\\mathbb{R})$ alors les deux affirmations suivantes sont vérifiées.\n",
"\n",
"1. La matrice $A$ est inversible si et seulement s'il existe $B \\in \\mathcal{M}_{n \\times n}(\\mathbb{R})$ telle que $BA = I_n$.\n",
"2. La matrice $A$ est inversible si et seulement s'il existe $C \\in \\mathcal{M}_{n \\times n}(\\mathbb{R})$ telle que $AC = I_n$.\n",
"\n",
"## RAPPEL: ALGORITHME POUR TROUVER L'INVERSE D'UNE MATRICE DONNÉE\n",
"Soit $A \\in \\mathcal{M}_{n \\times n}(\\mathbb{R})$ une matrice carrée. Afin de déterminer si $A$ est inversible et de calculer son inverse (lorsque c'est possible), on procède comme suit :\n",
"\n",
"1. Ecrire les matrices $A$ et $I_n$ l'une à côté de l'autre, formant ainsi une nouvelle matrice de taille $n \\times 2n$;\n",
"2. Faire des opérations élémentaires sur les lignes de cette nouvelle matrice, afin de réduire le côté gauche à $I_n$;\n",
"3. Si on y arrive, alors $A$ est inversible et son inverse $A^{-1}$ est donnée par la matrice à droite."
]
},
{
"cell_type": "code",
- "execution_count": 1,
+ "execution_count": null,
"metadata": {},
- "outputs": [
- {
- "data": {
- "text/html": [
- " \n",
- " "
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- },
- {
- "data": {
- "text/html": [
- " \n",
- " "
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- }
- ],
+ "outputs": [],
"source": [
"import Librairie.AL_Fct as al\n",
"import Corrections.corrections as corrections\n",
"from ipywidgets import interact_manual\n",
"import plotly as py\n",
"import plotly.graph_objs as go\n",
"from ipywidgets import interactive, HBox, VBox, widgets, interact, FloatSlider\n",
"import numpy as np"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### EXERCICE 1\n",
"Considérez le système linéaire quelconque $Ax=b$ avec $A \\in \\mathcal{M}_{n \\times n}(\\mathbb{R})$ et $b \\in \\mathcal{M}_{n \\times 1}(\\mathbb{R})$; cochez les déclarations suivantes qui pourraient être vraies pour certaines valeurs de $A$ et $b$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"corrections.Ex1Chapitre2_6_7()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## EXERCICE 2 ##\n",
"Cochez, parmi les matrices suivantes, celles qui sont inversibles.\n",
"\\begin{equation}\n",
"A_1 = \n",
"\\begin{pmatrix}\n",
"2 & 0 & 1\\\\\n",
"0 & 6 & 4 \\\\\n",
"2 & 2 & 1\n",
"\\end{pmatrix} \\qquad A_2 = \n",
"\\begin{pmatrix}\n",
"3 & -7 & 0\\\\\n",
"1 & 0 & 1\\\\\n",
"-5 & 35/3 & 0\n",
"\\end{pmatrix} \\qquad A_3 = \n",
"\\begin{pmatrix}\n",
"2 & 1 & -1\\\\\\\n",
"2 & -5 & 4\\\\\n",
"6 & -3 & 2\n",
"\\end{pmatrix}\n",
"\\end{equation}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"corrections.Ex2Chapitre2_6_7()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Vous pouvez vous aider à déterminer si les matrices suivantes sont inversibles ou non en exécutant les cellules suivantes et en calculant manuellement leurs inverses (éventuelles)**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#Entrez la matrice A\n",
"A=[[2,0,1], [0,6,4], [2,2,1]]\n",
"I=[[1,0,0],[0,1,0],[0,0,1]]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print('Vous allez échelonner la matrice augmenteé avec la matrice identité')\n",
"al.printA(A,I)\n",
"[i,j,r,alpha]= al.manualEch(A,I)\n",
"m=np.concatenate((A,I), axis=1)\n",
"MatriceList=[A]\n",
"RhSList=[I]\n",
"print('\\033[1mExecutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"m=al.echelonnage(i,j,r,alpha,A,m,MatriceList,RhSList)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## EXERCICE 3 ##\n",
"Considéz le système linéaire générique $Ax = b$, avec:\n",
"\\begin{equation}\n",
"A = \n",
"\\begin{pmatrix}\n",
"2 & -\\alpha\\\\\n",
"\\beta & -4 \\\\\n",
"\\end{pmatrix} \\qquad b = \n",
"\\begin{pmatrix}\n",
"1\\\\\n",
"-2\\\\\n",
"\\end{pmatrix}\n",
"\\end{equation}\n",
"Identifiez les valeurs des paramètres $\\alpha$ et $\\beta$ pour lesquels $A$ n'est pas inversible et cochez les déclarations suivantes qui sont correctes."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"corrections.Ex3Chapitre2_6_7()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**AIDE: vous pouvez exécuter la cellule interactive suivante pour mieux visualiser le système paramétré**"
]
},
{
"cell_type": "code",
- "execution_count": 2,
+ "execution_count": null,
"metadata": {},
- "outputs": [
- {
- "data": {
- "application/vnd.jupyter.widget-view+json": {
- "model_id": "e7de4db21060434087ae09c43ed222ad",
- "version_major": 2,
- "version_minor": 0
- },
- "text/plain": [
- "VBox(children=(FigureWidget({\n",
- " 'data': [{'name': 'd) Droite 1',\n",
- " 'type': 'scatter',\n",
- " …"
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- }
- ],
+ "outputs": [],
"source": [
"corrections.graphe_Ex3Chapitre2_6_7()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## EXERCICE 4\n",
"\n",
"Considérez les matrices suivantes:\n",
"\\begin{equation}\n",
"A = \n",
"\\begin{pmatrix}\n",
"0.5 & a & 1\\\\\n",
"0 & 2 & -1\\\\\n",
"-2 & 1 & b\n",
"\\end{pmatrix}; \\qquad B = \n",
"\\begin{pmatrix}\n",
"-6 & -2 & -2\\\\\n",
"4 & 2 & 1\\\\\n",
"8 & 3 & 2\n",
"\\end{pmatrix}\n",
"\\end{equation}\n",
"\n",
"Trouvez les valeurs des paramètres $a$ et $b$ pour lesquels $A$ et $B$ sont l'inverse l'une de l'autre."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"corrections.Ex4Chapitre2_6_7()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Passez au notebook 2.8-2.9: Décomposition LU (existance et algorithm)](2.8-2.9%20Décomposition%20LU%20(existance%20et%20algorithm).ipynb)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.9"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
diff --git "a/Chapitre 2 - Algebre matricielle/2.8-2.9 D\303\251composition LU (existance et algorithme).ipynb" "b/Chapitre 2 - Algebre matricielle/2.8-2.9 D\303\251composition LU (existance et algorithme).ipynb"
new file mode 100644
index 0000000..fa80955
--- /dev/null
+++ "b/Chapitre 2 - Algebre matricielle/2.8-2.9 D\303\251composition LU (existance et algorithme).ipynb"
@@ -0,0 +1,456 @@
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# **Concept(s)-clé(s) et théorie**\n",
+ "\n",
+ "## Propriété: Opérations élémentaires sur les colonnes d'une matrice\n",
+ "Soit $A \\in \\mathcal{M}_{m \\times n}(\\mathbb{R})$. Alors les affirmations suivantes sont vérifiées:\n",
+ "\n",
+ "* La matrice $AT_{ij}$ est obtenue en échangeant les colonnes $i$ et $j$ de $A$;\n",
+ "* La matrice $AD_{r}(\\lambda)$ est obtenue en multipliant la $r$-ème colonne de $A$ par $\\lambda$;\n",
+ "* La matrice $AL_{rs}(\\lambda)$ est obtenue en ajoutant $\\lambda$ fois la $r$-ème colonne de $A$ à la s-ème.\n",
+ "\n",
+ "**Remarque:** En multipliant une matrice $A$ par la gauche par une matrice élémentaire $E$ on modifie les lignes, et par la droite les colonnes. En général on a\n",
+ "\n",
+ "\\begin{align*}\n",
+ "&EA & &\\neq & &AE\\\\\n",
+ "\\nearrow& & & & &\\nwarrow\\\\\n",
+ "\\text{Opération sur les lignes}& & & & & \\text{Opérations sur les colonnes} \n",
+ "\\end{align*}\n",
+ "\n",
+ "## Théorème: Existance de la décomposition LU d'une matrice\n",
+ "Soit $A$ une matrice de taille $m \\times n$ et supposons qu'il soit possible de réduire $A$ à une forme échelonnée en n'utilisant que des opérations élémentaires de la forme $D_r(\\lambda), L_{rs}(\\lambda)$, avec $r>s$, sur les lignes de $A$. Alors il existe une matrice triangulaire inférieure $L$ ($n\\times n$) et une matrice échelonnée $U$ ($m\\times n$) telles que $A=LU$.\n",
+ "\n",
+ "## Algorithme: Trouver L et U dans la décomposition LU d'une matrice\n",
+ "Soit $A$ une matrice admettant une décomposition $LU$. Afin de déterminer les matrices $L$ et $U$ dans une telle décomposition, on procède comme suit:\n",
+ "\n",
+ "1. On applique successivement les opérations élémentaires de types **(II)** (i.e. $D_{r}(\\lambda)$ avec $\\lambda\\neq 0$) et **(III)** (i.e. $L_{rs}(\\lambda)$), avec matrices élémentaires correspondantes $E_1, E_2, \\dots, E_k$, aux lignes de la matrice $A$ afin de la rendre échelonnée.\n",
+ "2. On pose $U = E_k \\dots E_1A$, c'est-à-dire $U$ est la forme échelonnée de $A$ obtenue à l'aide des opérations élémentaires ci-dessus.\n",
+ "3. La matrice $L$ est alors obtenue en opérant sur les colonnes de $I_n$ par $E_1^{-1} \\dots E_k^{-1}$, dans cet ordre."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/html": [
+ " \n",
+ " "
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "data": {
+ "text/html": [
+ " \n",
+ " "
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "import Librairie.AL_Fct as al\n",
+ "import Corrections.corrections as corrections\n",
+ "from ipywidgets import interact_manual\n",
+ "import numpy as np"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Exercice 1\n",
+ "\n",
+ "Considérez la matrice suivante:\n",
+ "\n",
+ "\\begin{equation}\n",
+ "A = \n",
+ "\\begin{pmatrix}\n",
+ "2 & 0 & 4 & 2 \\\\\n",
+ "3 & 0 & -1 & 0 \\\\\n",
+ "0 & 2 & -2 & 1 \\\\\n",
+ "1 & 1 & 0 & -2\n",
+ "\\end{pmatrix}\n",
+ "\\end{equation}\n",
+ "\n",
+ "Insérez les valeurs des matrices élémentaires par lesquelles $A$ doit être multipliée à gauche et à droite afin d'obtenir chacune des matrices suivantes.\n",
+ "\n",
+ "\\begin{equation}\n",
+ "A_1 = \n",
+ "\\begin{pmatrix}\n",
+ "4 & 0 & 4 & 2 \\\\\n",
+ "3 & 0 & -1 & 0 \\\\\n",
+ "1 & 2 & -2 & 1 \\\\\n",
+ "-1 & 1 & 0 & -2\n",
+ "\\end{pmatrix}\n",
+ "\\quad A_2 = \n",
+ "\\begin{pmatrix}\n",
+ "2 & 0 & 2 & -2 \\\\\n",
+ "0 & 2 & -1 & -1 \\\\\n",
+ "3 & 0 & -0.5 & 0 \\\\\n",
+ "1 & 1 & 0 & 2\n",
+ "\\end{pmatrix}\n",
+ "\\quad A_3 = \n",
+ "\\begin{pmatrix}\n",
+ "2 & 0 & 4 & -6 \\\\\n",
+ "3 & 0 & -1 & 2 \\\\\n",
+ "0 & 2 & -2 & 5 \\\\\n",
+ "-1 & -1 & 0 & 2\n",
+ "\\end{pmatrix}\n",
+ "\\quad A_4 = \n",
+ "\\begin{pmatrix}\n",
+ "1 & 0 & 2 & -1 \\\\\n",
+ "3 & 0 & -1 & 0 \\\\\n",
+ "0 & 2 & 0 & -1 \\\\\n",
+ "1 & 1 & 1 & 2\n",
+ "\\end{pmatrix}\n",
+ "\\end{equation}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# MATRICE A1\n",
+ "E_gauche_1 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]\n",
+ "E_droite_1 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]\n",
+ "\n",
+ "# MATRICE A2\n",
+ "E_gauche_2 = [[1,0,0,0], [0,0,1,0], [0,1,0,0], [0,0,0,1]]\n",
+ "E_droite_2 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]\n",
+ "\n",
+ "# MATRICe A3\n",
+ "E_gauche_3 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]\n",
+ "E_droite_3 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]\n",
+ "\n",
+ "# MATRICE A4\n",
+ "E_gauche_4 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]\n",
+ "E_droite_4 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/latex": [
+ "Corrects: {}"
+ ],
+ "text/plain": [
+ ""
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ },
+ {
+ "data": {
+ "text/latex": [
+ "Manqué: {1, 2, 3, 4}"
+ ],
+ "text/plain": [
+ ""
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "corrections.Ex1Chapitre2_8_9([E_gauche_1, E_droite_1],\n",
+ " [E_gauche_2, E_droite_2], \n",
+ " [E_gauche_3, E_droite_3], \n",
+ " [E_gauche_4, E_droite_4])"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Exercice 2\n",
+ "\n",
+ "Pour chacune des matrices suivantes appartenant à $\\mathcal{M}_{4 \\times 4}(\\mathbb{R})$, déterminez si elles admettent ou non une décomposition LU.\n",
+ "\n",
+ "\\begin{equation}\n",
+ "A_1 = \n",
+ "\\begin{pmatrix}\n",
+ "2 & -1 & -4 & 0 \\\\\n",
+ "-1 & 2 & 0 & 3 \\\\\n",
+ "3 & 1 & -3 & 5 \\\\\n",
+ "1 & -3 & -5 & -5\n",
+ "\\end{pmatrix}\n",
+ "\\quad A_2 = \n",
+ "\\begin{pmatrix}\n",
+ "3 & 2 & 1 & -1 \\\\\n",
+ "0 & -1 & 1 & -2 \\\\\n",
+ "2 & -3 & 2 & 0 \\\\\n",
+ "1 & 0 & 0 & -1 \n",
+ "\\end{pmatrix}\n",
+ "\\quad A_3 = \n",
+ "\\begin{pmatrix}\n",
+ "1 & 0 & -1 & 2 \\\\\n",
+ "0 & 2 & -1 & 1 \\\\\n",
+ "0 & -4 & 2 & 3 \\\\\n",
+ "2 & 3 & -1 & -1\n",
+ "\\end{pmatrix}\n",
+ "\\end{equation}\n",
+ "\n",
+ "\n",
+ "**Exécutez les cellules suivantes pour effectuer la méthode d'élimination de Gauss sur les 3 matrices**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "#Entrez les coefficients de la matrice A\n",
+ "A=[[2,-1,-4,0], [-1,2,0,3], [3,1,-3,5], [1, -3,-5,-5]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "print('Vous allez échelonner la matrice A')\n",
+ "[i,j,r,alpha]= al.manualEch(A)\n",
+ "m=np.array(A)\n",
+ "MatriceList=[A]\n",
+ "print('\\033[1mExécutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "m=al.echelonnage(i,j,r,alpha,A,m,MatriceList)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "corrections.Ex3Chapitre2_8_9()"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Exercice 3\n",
+ "\n",
+ "Considérez la matrice carrée $A \\in \\mathcal{M}_{3 \\times 3}(\\mathbb{R})$ suivante:\n",
+ "\n",
+ "\\begin{equation}\n",
+ "A = \n",
+ "\\begin{pmatrix}\n",
+ "2 & 0 & 1 \\\\\n",
+ "0 & 6 & 4 \\\\\n",
+ "2 & 2 & 1\n",
+ "\\end{pmatrix}.\n",
+ "\\end{equation}\n",
+ "\n",
+ "En utilisant la la méthode d'élimination de Gauss, calculez, si possible, la décomposition LU de $A$. Profitez des cellules interactives suivantes et comprenez, à chaque passage, comment ont été dérivées $L$ et $U$."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "#Entrez les coefficients de la matrice A\n",
+ "A=[[2,0,1], [0,6,4], [2,2,1]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "print('Vous allez échelonner la matrice A')\n",
+ "al.printA(A)\n",
+ "[i,j,r,alpha]= al.manualEch(A)\n",
+ "LList = [np.eye(3)]\n",
+ "UList=[np.array(A).astype(float)]\n",
+ "print('\\033[1mExécutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "m=al.LU_interactive(i,j,r,alpha, LList, UList)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "**Exécutez la cellule suivante pour calculer les valeurs corrects de $ L $ et $ U $ et comparez-les à celles que vous venez de dériver**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "L_ref, U_ref = al.LU_no_pivoting(A)\n",
+ "al.printA(L_ref, name='L')\n",
+ "al.printA(U_ref, name='U')"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Exercice 4\n",
+ "\n",
+ "Considérez la matrice rectangulaire $B \\in \\mathcal{M}_{3 \\times 4}(\\mathbb{R})$ (représentant un système linéaire sous-déterminé) suivante:\n",
+ "\n",
+ "\\begin{equation}\n",
+ "B = \n",
+ "\\begin{pmatrix}\n",
+ "-1 & 2 & 0 & 3 \\\\\n",
+ "-1 & 0 & 2 & 4 \\\\\n",
+ "0 & -2 & 1 & 1\n",
+ "\\end{pmatrix}.\n",
+ "\\end{equation}\n",
+ "\n",
+ "En utilisant la la méthode d'élimination de Gauss, calculez, si possible, la décomposition LU de $A$. Profitez des cellules interactives suivantes et comprenez, à chaque passage, comment ont été dérivées $L$ et $U$."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "#Entrez les coefficients de la matrice B\n",
+ "B=[[-1,2,0,3], [-1,0,2,4], [0,-2,1,1]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "print('Vous allez échelonner la matrice A')\n",
+ "al.printA(B)\n",
+ "[i,j,r,alpha]= al.manualEch(B)\n",
+ "LList = [np.eye(3)]\n",
+ "UList=[np.array(B).astype(float)]\n",
+ "print('\\033[1mExecutez la ligne suivante pour effectuer l\\'opération choisie \\033[0m')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "m=al.LU_interactive(i,j,r,alpha, LList, UList)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "**Exécutez la cellule suivante pour calculer les valeurs corrects de $ L $ et $ U $ et comparez-les à celles que vous venez de dériver**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "L_ref, U_ref = al.LU_no_pivoting(B)\n",
+ "al.printA(L_ref, name='L')\n",
+ "al.printA(U_ref, name='U')"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "[Passez au notebook 2.10: Décomposition LU (applications au systèmes linéaires)](2.10%20Décomposition%20LU%20(applications%20aux%20systèmes%20linéaires).ipynb)"
+ ]
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Python 3",
+ "language": "python",
+ "name": "python3"
+ },
+ "language_info": {
+ "codemirror_mode": {
+ "name": "ipython",
+ "version": 3
+ },
+ "file_extension": ".py",
+ "mimetype": "text/x-python",
+ "name": "python",
+ "nbconvert_exporter": "python",
+ "pygments_lexer": "ipython3",
+ "version": "3.6.9"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 4
+}