preliminaries/la_crash_course.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Linear algebra background"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Вопросы\n",
    "\n",
    "- Что такое вектор и матрица?\n",
    "- Какие основные свойства векторов и матриц?\n",
    "- Какая сложность базовых операций с векторами и матрицами?\n",
    "- Какие функции от векторов и матриц существуют?\n",
    "- Какие типы матриц Вы знаете?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Объекты\n",
    "\n",
    "- Вектор: $x = (x_1, \\ldots, x_n) \\in \\mathbb{R}^n$\n",
    "- Матрица: $A = (a_{ij}) \\in \\mathbb{R}^{m \\times n}$, $i=1,\\ldots,m$, $j = 1,\\ldots,n$\n",
    "- Система линейных уравнений: $Ax = b$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Свойства\n",
    "- **Определение** Набор ненулевых векторов называется *линейно зависимым*, если существует их линейная комбинация, с хотя бы одним ненулевым коэффициентом, равная нулю  \n",
    "- **Определение** *Рангом* матрицы $A$ называется число линейно независимых столбцов\n",
    "- **Определение** Матрица $A$ называется *положительно-определённой*, если для любого ненулевого вектора $x$ выполнено\n",
    "$$\n",
    "A \\succ 0 \\iff x^{\\top}A x > 0\n",
    "$$\n",
    "Аналогично определяется отрицательная определённость и полуопределённость (положительная и отрицательная)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- **Определение** Матрица называется ортогональной, если \n",
    "$$\n",
    "AA^{\\top} = I\n",
    "$$\n",
    "- **Определение** Следом квадратной матрицы $A$ называется сумма диагональных элементов:\n",
    "$$\n",
    "\\mathrm{trace}(A) = \\sum_{i=1}^n a_{ii}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Теоремы\n",
    "\n",
    "- Теорема о ранге матрицы: строчной ранг матрицы равен её столбцовому рангу\n",
    "- Критерий Сильвестра: матрица положительно определена тогда и только тогда, когда все её главные миноры положительны"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Операции\n",
    "\n",
    "- Сложение и вычитание векторов, умножение вектора на скаляр - поэлементно - $O(n)$ операций (flops)\n",
    "- Скалярное произведение: \n",
    "$$\n",
    "\\langle x, y \\rangle = \\sum_{i=1}^n x_i y_i - O(n) \\text{ операций}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Умножение матрицы на вектор: \n",
    "$$\n",
    "(Ax)_i = \\sum_{k=1}^n a_{ik}x_k,\n",
    "$$ \n",
    "где $A \\in \\mathbb{R}^{m \\times n}$ и $x \\in \\mathbb{R}^n$:\n",
    "    - для плотной матрицы $A$ &mdash; $O(mn)$\n",
    "    - для разреженной матрицы $A$ с $N \\ll mn$ ненулевыми элементами &mdash; $O(N)$\n",
    "    - для малоранговой матрицы $A = UV^{\\top}$, где $U \\in \\mathbb{R}^{m \\times p}, \\; V \\in \\mathbb{R}^{n \\times p}$ и $p \\ll \\min(n, m)$ &mdash; $O(p(n + m))$\n",
    "    - для некоторых специальных типов матриц ([Тёплицева матрица](https://en.wikipedia.org/wiki/Toeplitz_matrix), [циркулянт](https://en.wikipedia.org/wiki/Circulant_matrix), [$\\mathcal{H}$ и $\\mathcal{H}^2$ матрицы](https://en.wikipedia.org/wiki/Hierarchical_matrix)) умножение на вектор может быть выполнено быстрее\n",
    "   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Умножение матрицы на матрицу: \n",
    "$$\n",
    "A = BC \\qquad a_{ij} = \\sum_{k=1}^p b_{ik}c_{kj},\n",
    "$$\n",
    "где $A \\in \\mathbb{R}^{m \\times n}$, $B \\in \\mathbb{R}^{m \\times p}$ и $C \\in \\mathbb{R}^{p \\times n}$\n",
    "    - для плотных матриц $B$ и $C$ &mdash; $O(mnp)$ операций\n",
    "    - существенно меньше если одна или обе матрицы $B$ и $C$ разреженны"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Система линейных уравнений\n",
    "\n",
    "$$\n",
    "Ax = b\n",
    "$$\n",
    "**Для произвольной квадратной матрицы $A \\in \\mathbb{R}^{n \\times n}$ система линейных уравнений решается за $O(n^3)$ операций**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Вопросы\n",
    "\n",
    "- Когда системы линейных уравнений разрешима?\n",
    "- Что такое обратная матрица?\n",
    "- Как решать системы линейных уравнений?\n",
    "- Для каких матриц система линейных равнений может быть легко решена?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Для каких матриц $A$ система может быть быстро решена?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Диагональная матрица $A$ &mdash; $O(n)$ операций\n",
    "- Нижне- или верхнетреугольная &mdash; $O(n^2)$ операций. Метод называется *прямой* или *обратной* подстановкой\n",
    "- Oртогональная матрица $A$ \n",
    "    - для произвольной ортогональной матрицы - $O(n^2)$ операций\n",
    "    - если известна структура матрицы (например $A = I - 2uu^{\\top}$, $u$ - вектор) &mdash; $O(n)$ операций\n",
    "    \n",
    "**Вопрос** Что геометрически означает умножение матрицы $A = I - 2uu^{\\top}$ на вектор?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Метод решения ситемы $Ax = b$ с помощью разложения матрицы $A$\n",
    "\n",
    "1. Представим матрицу $A$ в виде произведения $k$ \"простых\" матриц (диагональных, верхне- или нижнетреугольных и др...)\n",
    "$$\n",
    "A = A_1A_2\\ldots A_k\n",
    "$$\n",
    "2. Для получения $x$ решим $k$ систем вида \n",
    "$$\n",
    "A_1x_1 = b \\quad A_2x_2 = x_1 \\quad \\ldots \\quad A_kx = x_{k-1}\n",
    "$$\n",
    "Это можно сделать быстро, так как матрицы $A_i$ простые."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Также метод удобен для решения набора систем с одинаковой матрицей и $m$ правыми частями $b_i, \\; i=1,\\ldots,m$:\n",
    "- разложить матрицу $A$ в произведение простых матриц необходимо единственный раз\n",
    "- после чего $m$ раз последовательно решить системы для каждого $b_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### LU разложение\n",
    "**Теорема.** Любая невырожденная матрица $A$ может быть представлена в виде\n",
    "$$\n",
    "A = PLU,\n",
    "$$\n",
    "где $P$ &mdash; матрица перестановки, $L$ &mdash; нижнетреугольная матрица, $U$ &mdash; верхнетреугольная матрица\n",
    "\n",
    "Сложность разложения &mdash; $2n^3/3$ операций \n",
    "\n",
    "**Вопрос** Какая сложность решения системы $Ax=b$, если дано LU разложение матрицы $A$?\n",
    "\n",
    "**Вопрос** Зачем нужна перестановка $P$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Разложение Холецкого\n",
    "\n",
    "**Теорема.** Любая симметричная положительно определённая матрица $A$ может быть представлена в виде\n",
    "$$\n",
    "A = LL^{\\top},\n",
    "$$\n",
    "где $L$ &mdash; нижнетреугольная матрица.\n",
    "\n",
    "Сложность вычисления разложения Холецкого &mdash; $n^3/3$ операций\n",
    "\n",
    "**Вопрос** Какая сложность решения системы $Ax=b$ с использованием разложения Холецкого?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Система линейных уравнений вида $(A + BC)x = b$\n",
    "- $A$ &mdash; \"простая\" матрица, т.е. $Ax = b$ можно быстро решить\n",
    "- $BC$ &mdash; представление малоранговой матрицы\n",
    "\n",
    "Как быстро решать такие системы, Вам будет предложено подумать в домашнем задании :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Собственные векторы и собственые значения"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Вопросы\n",
    "\n",
    "1. Что такое собственые вектора и собственные значения?\n",
    "2. Когда матрица являются диагонализуемой и унитарно диагонализуемой?\n",
    "3. Как находить спектр матрицы полностью и частичо?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Определение.** Ненулевой вектор $x$ называется *собственным вектором* преобразования, заданного матрицей $A$, если\n",
    "$$\n",
    "Ax = \\lambda x,\n",
    "$$\n",
    "где $\\lambda$ - собственное значение, соответствующее собственному вектору $x$.\n",
    "\n",
    "Если у матрицы $A$ есть $n$ линейно незаивисимых собственных векторов, то её можно представить в виде *спектрального разложения*:\n",
    "$$\n",
    "A = X\\Lambda X^{-1},\n",
    "$$\n",
    "где $\\Lambda = \\mathrm{diag}(\\lambda_1, \\ldots, \\lambda_n)$, а $X = [x_1, \\ldots, x_n]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Теоремы\n",
    "\n",
    "1. Матрица унитарно диагонализуема тогда и только тогда, когда она *нормальна*:\n",
    "$$\n",
    "AA^* = A^*A\n",
    "$$\n",
    "2. \n",
    "$$ \n",
    "\\mathrm{tr}(A) = \\sum_{i=1}^n \\lambda_i\n",
    "\\quad\n",
    "\\det(A) = \\prod_{i=1}^n \\lambda_i\n",
    "$$\n",
    "3. Матрица положительно определена тогда и только тогда, когда все её собственные значения положительны\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Как вычислять?\n",
    "\n",
    "1. Нахождение всех собственных векторов и собственных значений: $O(n^3)$ - [метод Якоби](https://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm), [QR-алгоритм](https://en.wikipedia.org/wiki/QR_algorithm), использование разложения Шура...\n",
    "2. Однако полное спектральное разложение бывает необходимо редко. Обычно нужно несколько собственных векторов, соответствующих максимальным собственным значениям. Для решения этой задачи используется [*степенной метод*](https://en.wikipedia.org/wiki/Power_iteration) и [*метод обратной итерации*](https://en.wikipedia.org/wiki/Inverse_iteration)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Резюме\n",
    "\n",
    "1. Линейная алгебра &mdash; один из базовых инструментов в методах оптимизации\n",
    "2. Операции с векторами и матрицами\n",
    "3. Решение систем линейных уравнений\n",
    "4. Нахождение собственных значений и векторов"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python [conda env:cvxpy]",
   "language": "python",
   "name": "conda-env-cvxpy-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}