diff --git "a/Chapitre 2 - Algebre matricielle/2.8-2.9 D\303\251composition LU (existance et algorithm).ipynb" "b/Chapitre 2 - Algebre matricielle/2.8-2.9 D\303\251composition LU (existance et algorithm).ipynb" index a8740bb..72922af 100644 --- "a/Chapitre 2 - Algebre matricielle/2.8-2.9 D\303\251composition LU (existance et algorithm).ipynb" +++ "b/Chapitre 2 - Algebre matricielle/2.8-2.9 D\303\251composition LU (existance et algorithm).ipynb" @@ -1,284 +1,285 @@ { "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 \\mathbb{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", "## Theoré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$ et une matrice triangulaire supérieure $U$ 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)$) 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, + "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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ - "## Exercise 1\n", + "## Exercice 1\n", "\n", "Considérez la matrice suivante:\n", "\n", "\\begin{equation}\n", "A = \n", "\\begin{bmatrix}\n", "2 & 0 & 4 & 2 \\\\\n", "3 & 0 & -1 & 0 \\\\\n", "0 & 2 & -2 & 1 \\\\\n", "1 & 1 & 0 & 2\n", "\\end{bmatrix}\n", "\\end{equation}\n", "\n", "Insérez les valeurs des matrices élémentaires par lesquelles $A$ doit être pré et post multiplié afin d'obtenir chacune des matrices suivantes.\n", "\n", "\\begin{equation}\n", "A_1 = \n", "\\begin{bmatrix}\n", "4 & 0 & 4 & 2 \\\\\n", "3 & 0 & -1 & 0 \\\\\n", "1 & 2 & -2 & 1 \\\\\n", "-1 & 1 & 0 & 2\n", "\\end{bmatrix}\n", "\\quad A_2 = \n", "\\begin{bmatrix}\n", "2 & 0 & 2 & -2 \\\\\n", "0 & 2 & -1 & -1 \\\\\n", "3 & 2 & -0.5 & 0 \\\\\n", "1 & 1 & 0 & 2\n", "\\end{bmatrix}\n", "\\quad A_3 = \n", "\\begin{bmatrix}\n", "2 & 0 & 4 & -6 \\\\\n", "3 & 0 & -1 & 1 \\\\\n", "0 & 2 & -2 & 1 \\\\\n", "1 & 1 & 0 & 2\n", "\\end{bmatrix}\n", "\\quad A_4 = \n", "\\begin{bmatrix}\n", "1 & 0 & 2 & -1 \\\\\n", "3 & 0 & -1 & 0 \\\\\n", "0 & 2 & 0 & -1 \\\\\n", "1 & 1 & 1 & 2\n", "\\end{bmatrix}\n", "\\end{equation}" ] }, { "cell_type": "code", - "execution_count": 4, + "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# MATRIX A1\n", "E_pre_1 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]\n", "E_post_1 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [-1,0,0,1]]\n", "\n", "# MATRIX A2\n", "E_pre_2 = [[1,0,0,0], [0,0,1,0], [0,1,0,0], [0,0,0,1]]\n", "E_post_2 = [[1,0,0,0], [0,1,0,0], [0,0,1/2,0], [0,0,0,1]]\n", "\n", "# MATRIX A3\n", "E_pre_3 = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]\n", "E_post_3 = [[1,0,0,0], [0,1,0,0], [0,0,1,-1], [0,0,0,1]]\n", "\n", "# MATRIX A4\n", "E_pre_4 = [[1/2,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]\n", "E_post_4 = [[1,0,0,0], [0,1,1,0], [0,0,1,0], [0,0,0,1]]" ] }, { "cell_type": "code", - "execution_count": 5, + "execution_count": null, "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "Corrects: {1, 2, 3}\n", - "Manqué: {4}\n" - ] - } - ], + "outputs": [], "source": [ "corrections.Ex1Chapitre2_8_9([E_pre_1, E_post_1],\n", " [E_pre_2, E_post_2], \n", " [E_pre_3, E_post_3], \n", " [E_pre_4, E_post_4])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ - "## Exercise 2\n", + "## Exercice 2\n", + "\n", + "Pour chacune des matrices suivantes appartenant à $\\mathbb{R}^{4 \\times 4}$, déterminez si elles admettent ou non une décomposition LU.\n", + "\n", + "\\begin{equation}\n", + "A_1 = \n", + "\\begin{bmatrix}\n", + "2 & -1 & -4 & 0 \\\\\n", + "-1 & 2 & 0 & 3 \\\\\n", + "3 & 1 & -3 & 5 \\\\\n", + "1 & -3 & -5 & -5\n", + "\\end{bmatrix}\n", + "\\quad A_2 = \n", + "\\begin{bmatrix}\n", + "3 & 2 & 1 & -1 \\\\\n", + "0 & -1 & 1 & -2 \\\\\n", + "2 & -3 & 2 & 0 \\\\\n", + "1 & 0 & 0 & -1 \n", + "\\end{bmatrix}\n", + "\\quad A_3 = \n", + "\\begin{bmatrix}\n", + "1 & 0 & -1 & 2 \\\\\n", + "0 & 2 & -1 & 1 \\\\\n", + "0 & -4 & 2 & 3 \\\\\n", + "2 & 3 & -1 & -1\n", + "\\end{bmatrix}\n", + "\\end{equation}\n", + "\n", "\n", - "Exercise on the existance of the LU decomposition of a matrix --> give 3 matrices and ask which of those admits a LU decomposition (1 yes, 1 no because it is singular, 1 no because it needs permutation)\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": [ + "A=[[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]] # INSERT HERE THE VALUE OF THE MATRIX!!\n", + "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[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)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "corrections.Ex3Chapitre2_8_9()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ - "## Exercise 3\n", + "## Exercice 3\n", "\n", "Considérez la matrice suivante:\n", "\n", "\\begin{equation}\n", "A = \n", "\\begin{bmatrix}\n", "2 & 0 & 1 \\\\\n", "0 & 6 & 4 \\\\\n", "2 & 2 & 1\n", "\\end{bmatrix}\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": [ "A=[[2,0,1], [0,6,4], [2,2,1]]\n", "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')" ] }, { "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": "code", - "execution_count": null, + "cell_type": "markdown", "metadata": {}, - "outputs": [], - "source": [] + "source": [ + "[Passez au notebook 2.10: Décomposition LU (applications au systèmes linéaires)](2.10%20Décomposition%20LU%20(applications%aux%systèmes%liné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.7.4" + "version": "3.6.9" } }, "nbformat": 4, "nbformat_minor": 4 }