chapter08.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第八讲：求解$Ax=b$：可解性和解的结构\n",
    "\n",
    "举例，同上一讲：$3 \\times 4$矩阵\n",
    "$\n",
    "A=\n",
    "\\begin{bmatrix}\n",
    "1 & 2 & 2 & 2\\\\\n",
    "2 & 4 & 6 & 8\\\\\n",
    "3 & 6 & 8 & 10\\\\\n",
    "\\end{bmatrix}\n",
    "$，求$Ax=b$的特解：\n",
    "\n",
    "写出其增广矩阵（augmented matrix）$\\left[\\begin{array}{c|c}A & b\\end{array}\\right]$：\n",
    "\n",
    "$$\n",
    "\\left[\n",
    "\\begin{array}{c c c c|c}\n",
    "1 & 2 & 2 & 2 & b_1 \\\\\n",
    "2 & 4 & 6 & 8 & b_2 \\\\\n",
    "3 & 6 & 8 & 10 & b_3 \\\\\n",
    "\\end{array}\n",
    "\\right]\n",
    "\\underrightarrow{消元}\n",
    "\\left[\n",
    "\\begin{array}{c c c c|c}\n",
    "1 & 2 & 2 & 2 & b_1 \\\\\n",
    "0 & 0 & 2 & 4 & b_2-2b_1 \\\\\n",
    "0 & 0 & 0 & 0 & b_3-b_2-b_1 \\\\\n",
    "\\end{array}\n",
    "\\right]\n",
    "$$\n",
    "\n",
    "显然，有解的必要条件为$b_3-b_2-b_1=0$。\n",
    "\n",
    "讨论$b$满足什么条件才能让方程$Ax=b$有解（solvability condition on b）：当且仅当$b$属于$A$的列空间时。另一种描述：如果$A$的各行线性组合得到$0$行，则$b$端分量做同样的线性组合，结果也为$0$时，方程才有解。\n",
    "\n",
    "解法：令所有自由变量取$0$，则有$\n",
    "\\Big\\lbrace\n",
    "\\begin{eqnarray*}\n",
    "x_1 & + & 2x_3 & = & 1 \\\\\n",
    "    &   & 2x_3 & = & 3 \\\\\n",
    "\\end{eqnarray*}\n",
    "$\n",
    "，解得\n",
    "$\n",
    "\\Big\\lbrace\n",
    "\\begin{eqnarray*}\n",
    "x_1 & = & -2 \\\\\n",
    "x_3 & = & \\frac{3}{2} \\\\\n",
    "\\end{eqnarray*}\n",
    "$\n",
    "，代入$Ax=b$求得特解\n",
    "$\n",
    "x_p=\n",
    "\\begin{bmatrix}\n",
    "-2 \\\\ 0 \\\\ \\frac{3}{2} \\\\ 0\n",
    "\\end{bmatrix}\n",
    "$。\n",
    "\n",
    "令$Ax=b$成立的所有解：\n",
    "\n",
    "$$\n",
    "\\Big\\lbrace\n",
    "\\begin{eqnarray}\n",
    "A & x_p & = & b \\\\\n",
    "A & x_n & = & 0 \\\\\n",
    "\\end{eqnarray}\n",
    "\\quad\n",
    "\\underrightarrow{两式相加}\n",
    "\\quad\n",
    "A(x_p+x_n)=b\n",
    "$$\n",
    "\n",
    "即$Ax=b$的解集为其特解加上零空间，对本例有：\n",
    "$\n",
    "x_{complete}=\n",
    "\\begin{bmatrix}\n",
    "-2 \\\\ 0 \\\\ \\frac{3}{2} \\\\ 0\n",
    "\\end{bmatrix}\n",
    "+\n",
    "c_1\\begin{bmatrix}-2\\\\1\\\\0\\\\0\\\\\\end{bmatrix}\n",
    "+\n",
    "c_2\\begin{bmatrix}2\\\\0\\\\-2\\\\1\\\\\\end{bmatrix}\n",
    "$\n",
    "\n",
    "对于$m \\times n$矩阵$A$，有矩阵$A$的秩$r \\leq min(m, n)$\n",
    "\n",
    "列满秩$r=n$情况：\n",
    "$\n",
    "A=\n",
    "\\begin{bmatrix}\n",
    "1 & 3 \\\\\n",
    "2 & 1 \\\\\n",
    "6 & 1 \\\\\n",
    "5 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "$\n",
    "，$rank(A)=2$，要使$Ax=b, b \\neq 0$有非零解，$b$必须取$A$中各列的线性组合，此时A的零空间中只有$0$向量。\n",
    "\n",
    "行满秩$r=m$情况：\n",
    "$\n",
    "A=\n",
    "\\begin{bmatrix}\n",
    "1 & 2 & 6 & 5 \\\\\n",
    "3 & 1 & 1 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "$\n",
    "，$rank(A)=2$，$\\forall b \\in R^m都有x \\neq 0的解$，因为此时$A$的列空间为$R^m$，$b \\in R^m$恒成立，组成$A$的零空间的自由变量有n-r个。\n",
    "\n",
    "行列满秩情况：$r=m=n$，如\n",
    "$\n",
    "A=\n",
    "\\begin{bmatrix}\n",
    "1 & 2 \\\\\n",
    "3 & 4 \\\\\n",
    "\\end{bmatrix}\n",
    "$\n",
    "，则$A$最终可以化简为$R=I$，其零空间只包含$0$向量。\n",
    "\n",
    "总结：\n",
    "\n",
    "$$\\begin{array}{c|c|c|c}r=m=n&r=n\\lt m&r=m\\lt n&r\\lt m,r\\lt n\\\\R=I&R=\\begin{bmatrix}I\\\\0\\end{bmatrix}&R=\\begin{bmatrix}I&F\\end{bmatrix}&R=\\begin{bmatrix}I&F\\\\0&0\\end{bmatrix}\\\\1\\ solution&0\\ or\\ 1\\ solution&\\infty\\ solution&0\\ or\\ \\infty\\ solution\\end{array}$$"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}