《线性代数及其应用》笔记16.矩阵分解-LU分解.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# LU分解\n",
    "$\\quad$分解要求：矩阵各列线性无关。  \n",
    "## 1.介绍\n",
    "$\\quad$矩阵的因式分解是把A表示为两个或更多矩阵的乘积，矩阵乘法是数据的综合（把两个或更多线性变换的作用结合成一个矩阵），矩阵的因式分解是数据的分解，把数据组成两个或者更多，这种结构可能更有用，或者更便于计算。  \n",
    "$\\quad$在工业与商业问题中，$LU$分解是常见的一种矩阵因式分解算法，用途在于解一系列具有相同系数矩阵中的线性方程：\n",
    "\n",
    "<img src=\"./_image/16_1.png\" width=\"250\" height=\"200\" />  \n",
    "\n",
    "$\\quad$我们假设$m\\times n$矩阵$A$可以行化简为阶梯型矩阵而**不必进行行变换**（可对比$LUP$分解），则$A$可以写成形式$A=LU$，$L$是$m\\times n$下三角矩阵（可逆），主对角线元素全是1；$U$是$A$的一个等价的$m\\times n$阶梯型矩阵，如下图所示：\n",
    "\n",
    "<img src=\"./_image/16_2.png\" width=\"250\" height=\"200\" />  \n",
    "\n",
    "$\\quad$通过$LU$分解求解$A\\mathbf{x}=\\mathbf{b}$可以写成$LU\\mathbf{x}=\\mathbf{b}$，可变换成解下列方程来求解$\\mathbf{x}$：\n",
    "\n",
    "<img src=\"./_image/16_3.png\" width=\"100\" height=\"50\" />  \n",
    "\n",
    "先解(1)再(2)，因为$L,U$都是三角矩阵，因此很容易计算。  \n",
    "$\\quad$举一个例子：\n",
    "\n",
    "<img src=\"./_image/16_4.png\" width=\"400\" height=\"350\" />  \n",
    "## 2.算法流程\n",
    "$\\quad$算法并不复杂，总的来说为：\n",
    "1. 矩阵$A$经过一系列初等行变换变成阶梯型矩阵，即$U$;\n",
    "2. 换过程在每个主元列，把主元以下的元素除以主元即为$L$在该列主元以下的元素。  \n",
    "\n",
    "以一个例子来讲解：\n",
    "\n",
    "<img src=\"./_image/16_5.png\" width=\"400\" height=\"350\" />  \n",
    "\n",
    "## 3.算法性能分析\n",
    "$\\quad$下列运算次数的计算适用于$n\\times n$稠密矩阵$A$（大部分元素非零），$n$相当大，例如$n\\geq 30$。\n",
    "1. 计算$A$的$LU$分解大约需要$2n^{3}/3$浮算，而求$A^{-1}$大约需要$2n^{3}$浮算。\n",
    "2. 解$L\\mathbf{y}=\\mathbf{b}$和$U\\mathbf{x}=\\mathbf{y}$大约需要$2n^{3}$浮算，因为任意$n\\times n$三角方程组可以用大约$n^{3}$浮算解出。\n",
    "3. 把$\\mathbf{b}$乘以$A^{-1}$也需要$2n^{3}$浮算，但结果可能不如$L$和$U$得出的精确(由于计算$A^{-1}$及$A^{-1}\\mathbf{b}$的舍入误差)。\n",
    "4. 若$A$是稀疏矩阵（大部分元素为0），则$L$和$U$可能也是稀疏的，然而$A^{-1}$很可能是稠密的，显然用$LU$分解来解$A\\mathbf{x}=\\mathbf{b}$很可能比用$A^{-1}$快很多。  \n",
    "\n",
    "## 4.LUP分解\n",
    "$\\quad$考虑下面一个矩阵的$LU$分解：\n",
    "\n",
    "$$A=\\begin{bmatrix}\n",
    "   2 & 4 & -1\\\\\n",
    "   0 & 0 & 3\\\\\n",
    "   0 & -5 & -4\n",
    "  \\end{bmatrix} \n",
    "$$\n",
    "\n",
    "根据之前所述算法，先将矩阵$A$化为阶梯形矩阵，并在变换的过程中求出$L$。但是很明显，在这种情况下，会出现除数为0的情况，这当然是灾难性的。  \n",
    "$\\quad$除了除数为0外，还有除数很小的情况，这会产生数值不稳定，因此我们希望尽可能选一个较大的主元。所以有的时候我们必须在矩阵的非对角线元素中选主元。  \n",
    "$\\quad$我们先引入一个**置换矩阵**的概念，考虑下面两个矩阵的相乘：\n",
    "\n",
    "<img src=\"./_image/16_6.png\" width=\"300\" height=\"250\" />  \n",
    "\n",
    "根据我们之前所学知识很容易解出来，求得：\n",
    "\n",
    "$$A=\\begin{bmatrix}\n",
    "   2 & 4 & -1\\\\\n",
    "   0 & -5 & -4\\\\\n",
    "   0 & 0 & 3\n",
    "  \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "可以发现，矩阵$A$似乎没什么变化，只是行的位置改变了而已。我们把这样的矩阵称之为**置换矩阵**。置换矩阵是一种系数只由0和1组成的方阵。矩阵的每一行/列的第$i$个元素为1，表示原矩阵的该行/列为第$i$行/列。具体置换的行or列取决于是左乘还是右乘：\n",
    " * 当矩阵$A$左乘一个置换矩阵，交换的是矩阵的行。即$P\\cdot A$;\n",
    " * 当矩阵$A$右乘一个置换矩阵，交换的是矩阵的列。即$A\\cdot P$.\n",
    " \n",
    "$\\quad$让我们回到$LUP$分解。借助这个置换矩阵，我们可以将矩阵$A$的行进行置换，每步重新选取较大的主元进行行替换。原来的$A=LU$我们改写为$PA=LU$，其中$P$是一个置换矩阵。该式子表示为先对$A$进行行置换，再对行置换后的$A$进行$LU$分解。  \n",
    "$\\quad$当我们要求解$A\\mathbf{x}=\\mathbf{b}$，可做如下变换：\n",
    "\n",
    "<img src=\"./_image/16_7.png\" width=\"200\" height=\"150\" />  \n",
    "\n",
    "于是问题可以变换为：\n",
    "\n",
    "<img src=\"./_image/16_8.png\" width=\"100\" height=\"50\" />  \n",
    "\n",
    "求解到的$\\mathbf{x}$就是$A\\mathbf{x}=\\mathbf{b}$的解，证明如下：\n",
    "\n",
    "<img src=\"./_image/16_9.png\" width=\"250\" height=\"200\" />  \n",
    "\n",
    "$\\quad$其实$LU$分解是$LUP$分解的一种，当$P=I$时，$LUP$分解就成为$LU$分解。可以理解成是$A$矩阵不进行置换的情况下$LUP$分解就成为了$LU$分解。  \n",
    "## 5.应用 \n",
    "$\\quad$利用好矩阵的因式分解，不只是在求解方程组，在求逆矩阵、最小二乘逼近方面也能大大提高效率。目前计算机在计算矩阵的逆都是采用$LU$分解。  \n",
    "$\\quad$在求逆矩阵时，我们可以有两种思路：\n",
    "\n",
    "<img src=\"./_image/16_10.png\" width=\"300\" height=\"250\" />  \n",
    "\n",
    "$\\quad$通过$LUP$分解来求逆矩阵的过程中，分解的过程需要$O(n^{3})$，求解三角矩阵的过程需要$O(n^{2})$，避免了主元素为0的情况。可提高求解一系列具有相同系数矩阵中的线性方程的效率。  \n",
    "$\\quad$在Python中$LUP$分解可以借助scipy直接求解，代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1. 0. 0.]\n",
      " [0. 0. 1.]\n",
      " [0. 1. 0.]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from scipy.linalg import lu\n",
    "if __name__ == '__main__':\n",
    "    a = np.asarray([[2, 4, -1],  \n",
    "                     [0, 0, 3],  \n",
    "                     [0, -5, -4]])  \n",
    "    p, l, u = lu(a)\n",
    "    print(p)"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}