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 9fd0dd8..accab3a 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,372 +1,311 @@ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ - "###### Concept(s)-clé(s) et théorie\n", + "# Concept(s)-clé(s) et théorie\n", "\n", "## APPLICATION DE LA DÉCOMPOSITION AUX SYSTÈMES LINÉAIRES \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;" ] }, { "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 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é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{equation}\n", "\n", "En utilisation la décomposition LU de A, résolvez, si possible, le système linéaire." ] }, { "cell_type": "code", "execution_count": null, "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]]" ] }, { "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(4)]\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": [ "**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]] # 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]]" ] }, { "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": "code", "execution_count": null, "metadata": {}, "outputs": [], "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 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, 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 secondes**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "----------------------------Décomposition LU--------------------------------\n", - "Nombre d'opérations élémentaires (I, II, III): 499500\n", - "Coût de la décomposition LU (nombre total d'additions, soustractions, multiplications et divisions): 667166500\n", - "Temps d'exécution: 2.385104 s\n", - "\n", - "---------------------Résolution du système linéaire-------------------------\n" - ] - } - ], + "outputs": [], "source": [ "N = 1000 # dimension of the linear systems\n", "Nt = 5000 # number of linear systems to be solved\n", "A = np.random.rand(N, N);\n", - "start = time.time()\n", + "\n", "print(\"----------------------------Décomposition LU--------------------------------\")\n", + "start = time.time()\n", "L, U = al.LU_no_pivoting(A)\n", "time_lu = time.time() - start\n", "n_op_lu = 2/3*(N**3 - N)\n", "n_op_no_lu = 0\n", "print(\"Temps d'exécution: % f s\" %(time_lu))\n", "\n", "print(\"\\n---------------------Résolution du système linéaire-------------------------\")\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", "print(\"Sans décomposition LU: coût computationnelle: % e, temps d'exécution: % f s\" %(n_op_no_lu, time_no_lu))\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(\"Avec décomposition LU: coût computationnelle: % 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" } }, "nbformat": 4, "nbformat_minor": 4 }