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 4ba73db..136beb6 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,50 +1,274 @@ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ - "# **Concept(s)-clé(s) et théorie**" + "# **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": null, + "execution_count": 1, "metadata": {}, - "outputs": [], + "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" + "from ipywidgets import interact_manual\n", + "import numpy as np" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Exercise 1\n", + "\n", + "Exercise on the elementary operations --> given a matrix, write down the expression of the matrices you need to multiply it by (pre and post) to get a target matrix (5 trials)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Exercise 2\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" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Exercise 3\n", + "\n", + "Exercise on the computation of the LU decomposition of a matrix (NO PIVOTING, neither partial nor full). Implement interactive method, simular to Gauss, but displaying at each iteration both temporary L and temporary U" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Vous allez échelonner la matrice A\n" + ] + }, + { + "data": { + "text/latex": [ + "$\\left[\\begin{array}{ccc} 2 & 0 & 1 \\\\0 & 6 & 4 \\\\2 & 2 & 1 \\end{array}\\right]$" + ], + "text/plain": [ + "" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Régler les paramètres et évaluer la cellule suivante\n", + "Répéter cela jusqu'à obtenir une forme échelonnée réduite\n" + ] + }, + { + "data": { + "application/vnd.jupyter.widget-view+json": { + "model_id": "c5f0545b5f714ea1b37244ca80a84861", + "version_major": 2, + "version_minor": 0 + }, + "text/plain": [ + "RadioButtons(description='Opération:', options=('Eij', 'Ei(alpha)', 'Eij(alpha)', 'Revert'), value='Eij')" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "data": { + "application/vnd.jupyter.widget-view+json": { + "model_id": "e108342e04b544998433448efffcb526", + "version_major": 2, + "version_minor": 0 + }, + "text/plain": [ + "BoundedIntText(value=1, description='Ligne i:', max=3, min=1)" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "data": { + "application/vnd.jupyter.widget-view+json": { + "model_id": "4f9e75674f314751b5c000ca74f88c4d", + "version_major": 2, + "version_minor": 0 + }, + "text/plain": [ + "BoundedIntText(value=1, description='Ligne j:', max=3, min=1)" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "data": { + "application/vnd.jupyter.widget-view+json": { + "model_id": "e5e6d1f746e14ceaa15c39d9cd8bbcdd", + "version_major": 2, + "version_minor": 0 + }, + "text/plain": [ + "Text(value='1', description='Coeff. alpha:')" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[1mExecutez la ligne suivante pour effectuer l'opération choisie \u001b[0m\n" + ] + } + ], + "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": 4, + "metadata": {}, + "outputs": [ + { + "data": { + "text/latex": [ + "\\begin{equation}\\begin{align}L &= \\left[\\begin{array}{ccc} 1 & 0 & 0 \\\\0 & 1 & 0 \\\\0 & 0 & 1 \\end{array}\\right]\\qquad & U &= \\left[\\begin{array}{ccc} 2 & 0 & 1 \\\\0 & 6 & 4 \\\\2 & 2 & 1 \\end{array}\\right] \\\\ L &= \\left[\\begin{array}{ccc} -1 & 0 & 0 \\\\0 & 1 & 0 \\\\0 & 0 & 1 \\end{array}\\right]\\qquad & U &= \\left[\\begin{array}{ccc} 4 & 0 & 2 \\\\0 & 6 & 4 \\\\2 & 2 & 1 \\end{array}\\right]\\end{align}\\end{equation}" + ], + "text/plain": [ + "" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "m=al.LU_interactive(i,j,r,alpha, LList, UList)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], - "source": [] + "source": [ + "L_ref, U_ref = al.LU_no_pivoting(A)" + ] } ], "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 }