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 791ccd2..9b5abf7 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,396 +1,347 @@ { "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", "## 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": [ "## 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 pré et post multiplié 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": 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], [0,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,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,0], [0,0,0,1]]\n", "\n", "# MATRIX A4\n", "E_pre_4 = [[1,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,0,0], [0,0,1,0], [0,0,0,1]]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "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": [ "## 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": [ "A=[[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]] # INSEREZ ICI LA VALEUR DE LA MATRICE!!\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": [ "## 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": [ "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": "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": [ "B=[[-1,2,0,3], [-1,0,2,4], [0,-2,1,1]]\n", "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.7.4" } }, "nbformat": 4, "nbformat_minor": 4 }