diff --git a/4 Systemes lineaires.ipynb b/4 Systemes lineaires.ipynb deleted file mode 100644 index eb36cd5..0000000 --- a/4 Systemes lineaires.ipynb +++ /dev/null @@ -1,391 +0,0 @@ -{ - "cells": [ - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "# Résolution de systèmes linéaires " - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "D'abord quelques exemples d'utilisations de la factorisation LU et de Choleski, ensuite on passe aux methodes itéreatives\n", - "\n", - "## Méthodes Directes" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "### Exercice \n", - "\n", - "On considère le système linéaire $A\\mathbf{x} = \\mathbf{b}$ où :\n", - "\n", - "$$A = \\left(\n", - " \\begin{array}{ccc}\n", - " 3 & 6 & 7 \\\\[0.5em]\n", - " 1 & 1 & 4 \\\\[0.5em]\n", - " 2 & 4 & 8\n", - " \\end{array} \\right), \\quad\n", - " \\mathbf{b} = \\left( \\begin{array}{c} 4 \\\\[0.5em] 5 \\\\[0.5em] 6 \\end{array} \n", - "\\right) \\, .$$\n", - " \n", - "1. Calculer la factorisation $LU$ de la matrice $A$ avec Python:\n", - "\n", - "2. Résoudre le système linéaire $A \\mathbf{x} = \\mathbf{b}$ en utilisant la factorisation trouvée au point\n", - "précédent (Ne plus utiliser Python. Mais ici on va le faire)\n", - "\n", - "3. Calculer le déterminant de la matrice $A$ en utilisant sa factorisation $LU$." - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "# importing libraries used in this book\n", - "import numpy as np\n", - "import scipy.linalg as linalg\n", - "import pprint" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "#### Partie 1" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "A = np.array([[3, 6, 7],\n", - " [1, 1, 4],\n", - " [2, 4, 8] ])\n", - "\n", - "# LU factorisation with pivoting\n", - "P, L, U = linalg.lu(A)\n", - "\n", - "print(\"A = P L U\")\n", - "pprint.pprint(P.dot(L.dot(U)) )\n", - "\n", - "print(\"P:\")\n", - "pprint.pprint(P)\n", - "\n", - "print (\"L:\")\n", - "pprint.pprint(L)\n", - "\n", - "print (\"U:\")\n", - "pprint.pprint(U)\n" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "#### Partie 2\n", - "\n", - "Si $P$ est l'identité, $A = LU$.\n", - "\n", - "1. résoudre pour $\\mathbf y$ tel que $L \\mathbf y = \\mathbf{b}$ par substitution progressive\n", - "\n", - "2. résoudre pour $\\mathbf x$ tel que $U \\mathbf x = \\mathbf{y}$ par substitution retrograde\n", - "\n", - "Si $P$ n'est pas l'identité, $A = PLU$. \n", - "\n", - "Attention, une matrice de permutation est une matrice orthogonale car les colonnes sont orthonormée.\n", - "Donc $P^{-1} = P^T$. Du coup : $P^TA = LU$ et \n", - "$$A\\mathbf x = \\mathbf b \\Leftrightarrow P^TA\\mathbf x = P^T \\mathbf b\\Leftrightarrow LU\\mathbf x = P^T \\mathbf b.$$\n", - "Alors il faut modifier les calculs précedants comme suit:\n", - "\n", - "1. résoudre pour $\\mathbf y$ tel que $L \\mathbf y = P^T\\mathbf{b}$ par substitution progressive\n", - "\n", - "2. résoudre pour $\\mathbf x$ tel que $U \\mathbf x = \\mathbf{y}$ par substitution retrograde\n" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "b = np.array([4,5, 6])\n", - "\n", - "y = np.linalg.solve(L,P.T.dot(b))\n", - "x = np.linalg.solve(U,y)\n", - "# Here useless since P is the identity\n", - "\n", - "print(x)\n", - "\n", - "# check the residual of the equation\n", - "print(b - A.dot(x))" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "#### Partie 3\n", - "\n", - "$$\\det A = \\det P \\, \\det L \\, \\det U$$" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "linalg.det(P)*linalg.det(L)*linalg.det(U)" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "*Les mineurs principaux** d'une matrice $A \\in \\mathbb{R}^{n \\times n}$ \n", - "sont les déterminants des matrices $A_p = (a_{i,j})_{1 \\leq i, j \\leq p}$, $p = 1, ..., n$.\n", - "\n", - "**Critère de Sylvester:** une matrice symétrique $A \\in \\mathbb{R}^{n\\times n}$ \n", - "est définie positive si et seulement si les mineurs\n", - "principaux de $A$ sont tous positifs." - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "### Exercice \n", - "\n", - "On considère le système linéaire $A\\mathbf{x} = \\mathbf{b}$\n", - "où\n", - "\n", - "$$A = \\left(\n", - " \\begin{array}{ccc}\n", - " \\varepsilon & 1 & 2\\\\\n", - " 1 & 3 & 1 \\\\\n", - " 2 & 1 & 3 \\\\\n", - " \\end{array}\n", - " \\right).$$\n", - " \n", - "1. Déterminer pour quelles valeurs du paramètre réel\n", - "$\\varepsilon \\in \\mathbb{R}$, la matrice $A$ est symétrique\n", - "définie positive \n", - "\n", - "2. Soit maintenant $\\varepsilon=0$. On veut résoudre le système\n", - "$A\\mathbf{x}=\\mathbf{b}$ par une méthode directe; quelle\n", - "factorisation de la matrice $A$ envisageriez-vous? Justifier\n", - "votre réponse.\n", - "\n", - "3. En considérant $\\varepsilon = 2$, vérifier que dans ce cas la\n", - "matrice $A$ est définie positive et calculer sa\n", - "factorisation de Cholesky $A = L L^T$.\n", - "\n", - "4. En supposant que $\\mathbf{b} = (1,1,1)^T$, résoudre le\n", - "système linéaire $A \\mathbf{x} = \\mathbf{b}$ en utilisant la\n", - "factorisation de Cholesky calculée au point c).\n", - "\n", - "Reference Python pour la factorisation de Cholesky :\n", - "[scipy.linalg.cholesky](https://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.linalg.cholesky.html)" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "#### Partie 1 t 2\n", - "\n", - "cf corrigé" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "#### Partie 3" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "epsilon = 2\n", - "A = np.array([[epsilon, 1, 2],\n", - " [1, 3, 1],\n", - " [2, 1, 3] ])\n", - "\n", - "# Is A symmetric ?\n", - "print(f'max(abs(A-AT)) = {np.max(np.abs(A-A.T))} ')\n", - "\n", - "# What are the eigenvlues of $A$ ? (usually, use linalg.eig, but here A is symmetric, we can use eigh )\n", - "lk, v = linalg.eigh(A)\n", - "print(f'The eigenvalues of A are {lk}')\n", - "\n", - "# Cholesky factorisation: lower : return lower-triangular matrix, A = L^T L\n", - "L = linalg.cholesky(A, lower=True) \n", - "print(f\"\\n A = L^T L = {L.dot(L)}\\n\")\n", - "\n", - "print (f\"L = {L}\")\n", - "\n" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "#### Partie 4" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "b = np.array([1,1, 1])\n", - "\n", - "y = np.linalg.solve(L,b)\n", - "x = np.linalg.solve(L.T,y)\n", - "\n", - "print(x)\n", - "\n", - "# check the residual of the equation\n", - "print(b - A.dot(x))" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "## Méthodes itératives" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "### Exemple\n", - "\n", - "$$A=\\begin{pmatrix}\n", - "1 & 2 & 3 & 4 \\\\\n", - "5 & 6 & 7 & 8\\\\\n", - "9 & 10 & 11 & 12\\\\\n", - "13 & 14 & 15 & 16\n", - "\\end{pmatrix}.$$\n", - "\n", - "On a alors\n", - "$$D=\\begin{pmatrix}\n", - "1 & 0 & 0 & 0 \\\\\n", - "0 & 6 & 0 & 0\\\\\n", - "0 & 0 & 11 & 0\\\\\n", - "0 & 0 & 0 & 16\n", - "\\end{pmatrix};$$\n", - "la matrice d'itération de la méthode de Jacobi est\n", - "$$B_J = D ^{-1}(D - A) = I - D^{-1}A =\n", - "\\begin{pmatrix}\n", - "0 & -2 & -3 & -4 \\\\\n", - "-5/6 & 0 & -7/6 & -4/3\\\\\n", - "-9/11 & -10/11 & 0 & -12/11\\\\\n", - "-13/16 & -14/16 & -15/16 & 0\n", - "\\end{pmatrix}.$$" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "A = np.array([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]])" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "# Jacobi\n", - "# first diag extract the diagonal of A, the second builds a diagonal matrix starting from a vector\n", - "D = np.diag(np.diag(A)) \n", - "\n", - "Bj = np.linalg.solve(D,(D-A))\n", - "# What are the eigenvlues of $A$ ? \n", - "lk, v = linalg.eig(Bj)\n", - "print(f'The eigenvalues of Bj are {lk}\\n')\n", - "print(f'The spectral radius of Bj is {np.max(np.abs(lk)):.4f} > 1, therefore Jacobi does not converge')\n" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "# Gauss-Seidel\n", - "# Return a copy of an array with elements above the k-th diagonal zeroed. \n", - "Pgs = np.tril(A,k=0)\n", - "\n", - "Bgs = np.linalg.solve(Pgs,(Pgs-A))\n", - "# What are the eigenvlues of $A$ ? \n", - "lk, v = linalg.eig(Bgs)\n", - "print(f'The eigenvalues of Bgs are {lk}\\n')\n", - "print(f'The spectral radius of Bgs is {np.max(np.abs(lk)):.4f} > 1, therefore Gauss-Seidel does not converge')\n", - "\n" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [ - "Bgs" - ] - }, - { - "cell_type": "code", - "execution_count": null, - "metadata": {}, - "outputs": [], - "source": [] - } - ], - "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.6" - } - }, - "nbformat": 4, - "nbformat_minor": 4 -}