04.01 Linear Algebra - definitions and main concepts.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Основные понятия линейной алгебры\n",
    "В даннном материале мы рассмотрим основные понятия линейной алгебры, которые необходимы для понимания основ машинного обучения. \n",
    "Основными понятиями линейной алгебры являются векторы и матрицы. Основные операции линейной алгебры определяются с помощью линейных отображений. Во многом именно линейные отображения делают линейную алгебру столь важной для прикладных задач. \n",
    "\n",
    "## Почему линейная алгебра столь важна?\n",
    "Окружающий нас мир очень сложен и многие его проблемы имеют нелинейную природу. Изучение и понимание этих нелинейных связей в природе и в технике крайне сложно. Из-за этого инженеры, вместо того чтобы напрямую работать с нелинейными моделями, часто прибегают к линейным приблежениям этих моделей. Для этого нелинейную модель разбивают на многие меньшие части, где каждая часть в отдельности очень хорошо апроксимируется (т.е. приближается) линейным отображением. Как только проблема сформулирована в виде линейных отображений, сразу появляется возможность решить её очень эффективно и быстро с помощью методов линейной алгебры. \n",
    "\n",
    "В данном материале будут даны лишь общие понятия, описание терминов и некоторые теоремы без доказательств. Для более глубокого изучения нужно обратиться к специализированным курсам по линейной алгебре.\n",
    "\n",
    "## Скалярная величина (scalar) \n",
    "Скалярная величина — величина, каждое значение которой может быть выражено одним действительным числом. Другими словами любое действительное число является скалярным значением. Термин появился в физике для обозначения величин, значения которых может быть выражено одним числом (длина, площадь, время, температура и т. д.), в отличии от других величин, которые выражаются с помощью векторов (например, сила имеет не только величину, но и направление). Скалярное значение обозначается маленькими буквами греческого (например, $\\alpha$, $\\beta$, $\\gamma$) или латинского (например, a, b, c) алфавитов.\n",
    "\n",
    "## Вектор (vector)\n",
    "Вектором размера n мы будем называть одномерный массив из n чисел. Для обозначения вектора используется буква латинского алфавита со стрелочкой $\\vec{x}$. Для записи вектора вместе с элементами в столбец используется следующая нотация\n",
    "$$\n",
    "\\begin{align}\n",
    "\\vec{x} &= \\begin{bmatrix}\n",
    "        x_{1} \\\\\n",
    "        x_{2} \\\\\n",
    "        \\vdots \\\\\n",
    "        x_{n}\n",
    "     \\end{bmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Вместо записи в столбец, веткор может быть записан в виде строки следующим образом:\n",
    "1. $\\vec{x} = (x_1, x_2, \\ldots, x_n)$\n",
    "2. $\\vec{x} = \\left<x_1, x_2, \\ldots, x_n\\right>$\n",
    "\n",
    "Каждый элемент вектора является действительным числом. Для обозначения этого свойства используется нотация $x_i \\in \\mathbb{R}$, где $\\mathbb{R}$ обозначает множество действительных чисел, а символ $\\in$ принадлежность к данному множеству. Для обозначения того, что вектор размера n состоит из действительных чисел исопльзуется нотация $\\vec{x} \\in \\mathbb{R^n}$.\n",
    "\n",
    "В python мы будем использовать библиотеку NumPy для работы с векторами. Как было сказано выше, вектор размера n это одномерный массив с n числами. В NumPy мы можем создать $\\vec{x} = (1, 2, 3)$ следующим образом"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.057222Z",
     "start_time": "2017-12-30T14:22:44.960722Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2, 3])"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "np.array([1, 2, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Стандартный единичный вектор (standard unit vector)\n",
    "Стандартным или базисным (basis) единичным вектором называются векторы размера n, у которых один элемент равен 1, а все остальные 0. У стандартного вектора $\\vec{e_j}$ элемент на позиции j равен 1, а все остальные позиции равны 0:\n",
    "$$\n",
    "\\begin{align}\n",
    "\\vec{e_j} &= \\begin{bmatrix}\n",
    "        0 \\\\\n",
    "        \\vdots \\\\\n",
    "        0 \\\\\n",
    "        1 \\\\\n",
    "        0 \\\\\n",
    "        \\vdots \\\\\n",
    "        0\n",
    "     \\end{bmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Единичные векторы в двухмерном пространстве обозначаются как $\\hat{i}$ и $\\hat{j}$\n",
    "$$\n",
    "\\begin{align}\n",
    "\\hat{i}=\\vec{e_0} &= \\begin{bmatrix}\n",
    "        1 \\\\\n",
    "        0\n",
    "     \\end{bmatrix} &\n",
    "\\hat{j}=\\vec{e_1} &= \\begin{bmatrix}\n",
    "        0 \\\\\n",
    "        1\n",
    "     \\end{bmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Единичные векторы в трехмерном пространстве обозначаются как $\\hat{i}$, $\\hat{j}$ и $\\hat{k}$\n",
    "$$\n",
    "\\begin{align}\n",
    "\\hat{i}=\\vec{e_0} &= \\begin{bmatrix}\n",
    "        1 \\\\\n",
    "        0 \\\\\n",
    "        0\n",
    "     \\end{bmatrix} &\n",
    "\\hat{j}=\\vec{e_1} &= \\begin{bmatrix}\n",
    "        0 \\\\\n",
    "        1 \\\\\n",
    "        0\n",
    "     \\end{bmatrix} &\n",
    "\\hat{k}=\\vec{e_2} &= \\begin{bmatrix}\n",
    "        0 \\\\\n",
    "        0 \\\\\n",
    "        1\n",
    "     \\end{bmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Стандартный единичный вектор имеет важное значение, которое мы увидем далее. Ниже приведен пример создания единичных векторов в трехмерном прастранстве с помощью NumPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.065723Z",
     "start_time": "2017-12-30T14:22:45.059222Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([1, 0, 0]), array([0, 1, 0]), array([0, 0, 1]))"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = np.array([1, 0, 0])\n",
    "j = np.array([0, 1, 0])\n",
    "k = np.array([0, 0, 1])\n",
    "i, j, k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Произведение вектора на скалярное значение\n",
    "При произведении вектора на скалярное значение каждый элемент этого вектора умножается на скалярное значение. Например, если мы хотим скалярное значение $\\alpha$ умножить на вектор $\\vec{x}=(x_1, x_2, \\ldots, x_n)$, то в результате получим \n",
    "$$\n",
    "\\begin{align}\n",
    "\\alpha\\vec{x} &= \\begin{bmatrix}\n",
    "        \\alpha x_1 \\\\\n",
    "        \\alpha x_2 \\\\\n",
    "        \\vdots \\\\\n",
    "        \\alpha x_n\n",
    "     \\end{bmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Умножение вектора на скалярное значение также называется масштабированием вектора (vector scaling), так как при этом длина вектора увеличивается (или уменьшается если $0 < \\alpha < 1$ ) на соответсвтвующее скалярное значение. \n",
    "\n",
    "Следующий код релизует умножение вектора $\\vec{x}=(1, 2, 3)$ на скалярное значение 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.084224Z",
     "start_time": "2017-12-30T14:22:45.067721Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 5 10 15]\n"
     ]
    }
   ],
   "source": [
    "x = np.array([1, 2, 3])\n",
    "y = np.zeros_like(x)\n",
    "a = 5\n",
    "for i in range(len(x)):\n",
    "    y[i] = x[i] * a\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Однако, на практике писать такой код не стоит. Как было показано в разделе про векторизованные вычисления в NumPy, данный код можно реализовать значительно короче и эффективнее"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.101221Z",
     "start_time": "2017-12-30T14:22:45.086222Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 5, 10, 15])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Сложение и вычитание векторов (addition and substraction of vectors)\n",
    "При сложении двух векторов каждый элемент первого вектора складывается с соответствующим по индексу элементом второго вектора. Т.е. если нам даны два вектора $\\vec{x}=(x_1, x_2, \\ldots, x_n)$ и $\\vec{y}=(y_1, y_2, \\ldots, y_n)$, то при их сложении мы получим следующий вектор\n",
    "$$\n",
    "\\begin{align}\n",
    "\\vec{x} + \\vec{y} &= \\begin{bmatrix}\n",
    "        x_1 + y_1 \\\\\n",
    "        x_2 + y_2 \\\\\n",
    "        \\vdots \\\\\n",
    "        x_n + y_n\n",
    "     \\end{bmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Чтобы сложить два вектора их размер должен быть одинаковым. \n",
    "\n",
    "Следующий пример реализует сложение векторов на python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.113724Z",
     "start_time": "2017-12-30T14:22:45.102723Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5 7 9]\n"
     ]
    }
   ],
   "source": [
    "x = np.array([1, 2, 3])\n",
    "y = np.array([4, 5, 6])\n",
    "z = np.zeros_like(x)\n",
    "for i in range(len(x)):\n",
    "    z[i] = x[i] + y[i]\n",
    "print(z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализация с помощью NumPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.128723Z",
     "start_time": "2017-12-30T14:22:45.116223Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([5, 7, 9])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x + y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вычитание веткоров выполняется аналогично сложению, только вместо складывания каждого элемента они вычитаются. Если даны два вектора $\\vec{x}=(x_1, x_2, \\ldots, x_n)$ и $\\vec{y}=(y_1, y_2, \\ldots, y_n)$, то при их вычитании мы получим следующий вектор\n",
    "$$\n",
    "\\begin{align}\n",
    "\\vec{x} - \\vec{y} &= \\begin{bmatrix}\n",
    "        x_1 - y_1 \\\\\n",
    "        x_2 - y_2 \\\\\n",
    "        \\vdots \\\\\n",
    "        x_n - y_n\n",
    "     \\end{bmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Чтобы сложить два вектора их размер должен быть одинаковым. Следующий пример реализует сложение веткоров на python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.140223Z",
     "start_time": "2017-12-30T14:22:45.130724Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-3 -3 -3]\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(x)):\n",
    "    z[i] = x[i] - y[i]\n",
    "print(z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализация с помощью NumPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.154223Z",
     "start_time": "2017-12-30T14:22:45.142222Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-3, -3, -3])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x - y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Линейная комбинация векторов (linear combination)\n",
    "Допустим, что нам даны два вектора размера m: $\\vec{x}, \\vec{y} \\in \\mathbb{R^m}$ и два скалярных значения: $\\alpha, \\beta \\in \\mathbb{R}$. Линейной комбинацией векторов $\\vec{x}, \\vec{y}$ с коэффициентами $\\alpha, \\beta$ называется следующий вектор\n",
    "$$\n",
    "\\begin{align}\n",
    "\\alpha \\vec{x} + \\beta \\vec{y} &= \\begin{bmatrix}\n",
    "        \\alpha x_1 + \\beta y_1 \\\\\n",
    "        \\alpha x_2 + \\beta y_2 \\\\\n",
    "        \\vdots \\\\\n",
    "        \\alpha x_n + \\beta y_n\n",
    "     \\end{bmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Линейная комбинация является одной из центральных понятий в линейной алгебре и многие другие понятия определяются с помощью нее. Линейная комбинация может быть обобщена на случай большего количества веткоров. Допустим у нас есть n векторов размера m: $\\vec{x_1}, \\vec{x_2}, \\ldots, \\vec{x_n} \\in \\mathbb{R^m}$ и n скалярных значений: $a_1, a_2, \\ldots, a_n \\in \\mathbb{R}$. Тогда линейной комбинацией этих векторов называется вектор, полученный следующим образом\n",
    "$$\n",
    "\\begin{align}\n",
    "a_1 \\vec{x_1} + a_2 \\vec{x_2} + \\cdots + a_n \\vec{x_n} &= \\begin{bmatrix}\n",
    "         a_1 x_{1,1} + a_2 x_{1,2} + \\cdots + a_n x_{1,n}\\\\\n",
    "         a_1 x_{2,1} + a_2 x_{2,2} + \\cdots + a_n x_{2,n}\\\\\n",
    "         \\vdots \\\\\n",
    "         a_1 x_{m,1} + a_2 x_{m, 2} + \\cdots + a_n x_{m, n}\\\\\n",
    "     \\end{bmatrix} &= \\sum_{i=1}^{n} a_i \\vec{x_i}\n",
    "\\end{align}\n",
    "$$\n",
    "Значение $x_{i,j}$ соответствует элементу i вектора j. Символ $\\sum_{i=1}^{n}$ означает сумму элементов от 1 до n. Это математический символ соотвествующий циклу в языках программирования. Линейная комбинация двух векторов может быть реализована в python следующим образом"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.170222Z",
     "start_time": "2017-12-30T14:22:45.156223Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4 4 4]\n"
     ]
    }
   ],
   "source": [
    "x = np.array([1, 1, 1])\n",
    "y = np.array([2, 2, 2])\n",
    "a = 2\n",
    "b = 1\n",
    "z = np.zeros_like(x)\n",
    "for i in range(len(x)):\n",
    "    z[i] = a * x[i] + b * y[i]\n",
    "print(z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализация с помощью NumPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.182724Z",
     "start_time": "2017-12-30T14:22:45.172226Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([4, 4, 4])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * x + b * y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Представление векторов в виде линейной комбинации стандартных базисных векторов\n",
    "Любой вектор можно представить с помощью линейной комбинации стандартных единичных векторов. Допустим у нас есть вектор $\\vec{x}=(1, 2, 3)$. Этот вектор можно записать следующим обрзом:\n",
    "$$\n",
    "\\begin{align}\n",
    "\\vec{x} &= \\begin{bmatrix}\n",
    "        1 \\\\\n",
    "        2 \\\\\n",
    "        3\n",
    "     \\end{bmatrix} &= 1 \\begin{bmatrix}\n",
    "        1 \\\\\n",
    "        0 \\\\\n",
    "        0\n",
    "     \\end{bmatrix} + 2 \\begin{bmatrix}\n",
    "        0 \\\\\n",
    "        1 \\\\\n",
    "        0\n",
    "     \\end{bmatrix} + 3 \\begin{bmatrix}\n",
    "        0 \\\\\n",
    "        0 \\\\\n",
    "        1\n",
    "     \\end{bmatrix} &= 1 \\vec{e_1} + 2 \\vec{e_2} + 3 \\vec{e_3}\n",
    "\\end{align}\n",
    "$$\n",
    "В более общем виде, когда у нас есть вектор размера n $\\vec{x} \\in \\mathbb{R}^n$, он может быть выражен с помощью стандартных единичных векторов следующим образом:\n",
    "$$\n",
    "\\begin{align}\n",
    "\\vec{x} &= \\begin{bmatrix}\n",
    "        x_1 \\\\\n",
    "        x_2 \\\\\n",
    "        \\vdots \\\\\n",
    "        x_n\n",
    "     \\end{bmatrix} &= x_1 \\begin{bmatrix}\n",
    "        1 \\\\\n",
    "        0 \\\\\n",
    "        \\vdots \\\\\n",
    "        0\n",
    "     \\end{bmatrix} + x_2 \\begin{bmatrix}\n",
    "        0 \\\\\n",
    "        1 \\\\\n",
    "        \\vdots \\\\\n",
    "        0\n",
    "     \\end{bmatrix} + \\cdots + x_n \\begin{bmatrix}\n",
    "        0 \\\\\n",
    "        0 \\\\\n",
    "        \\vdots \\\\\n",
    "        1\n",
    "     \\end{bmatrix} = x_1 \\vec{e_1} + x_2 \\vec{e_2} + \\cdots + x_n \\vec{e_n} = \\sum_{i=1}^{n} x_i \\vec{e_i}\n",
    "\\end{align}\n",
    "$$\n",
    "Такая форма представления векторов понадобится нам при определении матриц."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.198725Z",
     "start_time": "2017-12-30T14:22:45.184723Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ True,  True,  True], dtype=bool)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.array([1, 2, 3])\n",
    "i = np.array([1, 0, 0])\n",
    "j = np.array([0, 1, 0])\n",
    "k = np.array([0, 0, 1])\n",
    "\n",
    "y = x[0] * i + x[1] * j + x[2] * k\n",
    "x == y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Скалярное произведение векторов (dot product)\n",
    "Допустим, что нам даны два вектора размера m: $\\vec{x}, \\vec{y} \\in \\mathbb{R^m}$. Скалярным или внутренним произведением этих двух векторов называется **скалярное** значение полученное следующим образом\n",
    "$$\n",
    "\\begin{align}\n",
    "\\operatorname{dot(\\vec{x}, \\vec{y})} = \\vec{x} \\cdot \\vec{y} = x_1 y_1 + x_2 y_2 + \\cdots + x_n y_n = \\sum_{i=1}^{n} x_i y_i\n",
    "\\end{align}\n",
    "$$\n",
    "Часто для обозначения скалярного произведения векторов используется нотация $\\vec{x}^T\\vec{y}$. Символ $T$ означает транспозицию. При применении данного оператора из вектора в столбец получается вектор в строку:\n",
    "$$\n",
    "\\begin{align}\n",
    "\\vec{x}^T\\vec{y} &= \\begin{bmatrix}\n",
    "        x_1 \\\\\n",
    "        x_2 \\\\\n",
    "        \\vdots \\\\\n",
    "        x_n\n",
    "     \\end{bmatrix}^T \\begin{bmatrix}\n",
    "        y_1 \\\\\n",
    "        y_2 \\\\\n",
    "        \\vdots \\\\\n",
    "        y_n\n",
    "     \\end{bmatrix} \\\\\n",
    "     &= [x_1, x_2, \\cdots, x_n] \\begin{bmatrix}\n",
    "        y_1 \\\\\n",
    "        y_2 \\\\\n",
    "        \\vdots \\\\\n",
    "        y_n\n",
    "     \\end{bmatrix} \\\\\n",
    "     &= \\sum_{i=1}^{n} x_i y_i\n",
    "\\end{align}\n",
    "$$\n",
    "Скалярное произведение векторов можно реализовать на python следующим образом"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.210723Z",
     "start_time": "2017-12-30T14:22:45.200226Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "32\n"
     ]
    }
   ],
   "source": [
    "x = np.array([1, 2, 3])\n",
    "y = np.array([4, 5, 6])\n",
    "z = 0\n",
    "for i in range(len(x)):\n",
    "    z += x[i] * y[i]\n",
    "print(z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализация с помощью NumPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.223221Z",
     "start_time": "2017-12-30T14:22:45.212223Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.dot(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Длина вектора (vector length)\n",
    "Длина, величина или норма (length, magnitude, norm) вектора размера m: $\\vec{x} \\in \\mathbb{R^m}$ обозначается как $||\\vec{x}||$ и вычисляется следующим образом:\n",
    "$$\n",
    "\\begin{align}\n",
    "||\\vec{x}|| = \\sqrt{x_1^2 + x_2^2 + \\cdots + x_n^2} = \\sqrt{\\sum_{i=1}^{n} x_i^2}\n",
    "\\end{align}\n",
    "$$\n",
    "Длина вектора, определенная таким образом, также называется евклидовой длиной. В двухмерном и трехмерном пространствах данное определение соответствует теореме пифагора для нахождения расстояния до точки от начала координат. Обратите внимание, что длина вектора также может быть определена через скалярное произведение вектора на самого себя:\n",
    "$$\n",
    "\\begin{align}\n",
    "||\\vec{x}|| = \\sqrt{\\vec{x}^T\\vec{x}}\n",
    "\\end{align}\n",
    "$$\n",
    "Вычисление длины вектора можно реализовать на python следующим образом"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.233221Z",
     "start_time": "2017-12-30T14:22:45.224723Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.0\n"
     ]
    }
   ],
   "source": [
    "x = np.array([3, 4])\n",
    "l = 0\n",
    "for i in range(len(x)):\n",
    "    l += x[i] ** 2\n",
    "l = l ** 0.5\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для вычисления длины вектора с помощью NumPy мы можем вомпользоваться функцией `norm` из модуля `numpy.linalg`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.248721Z",
     "start_time": "2017-12-30T14:22:45.234723Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.linalg.norm(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Вектор-функция (vector function)\n",
    "Вектор-функция - функция, значениями которой являются векторы двух, трёх или более измерений. Аргументами функции могут быть скалярные значения и векторы. Нас будут интересовать вектор-функции, которые на вход принимают вектор и на выходе выдают другой вектор. При этом размеры входного и выходного векторов могут быть разными. Вектор функция принимающая в качестве аргумента вектор размера m и отображающая его на вектор размера n обозначается следующим образом:\n",
    "$$\n",
    "\\begin{align}\n",
    "    f\\colon \\mathbb R^m \\to \\mathbb R^n\n",
    "\\end{align}\n",
    "$$\n",
    "Примерами векторных функций могут быть функция, которая выполняет сложение или вычитание векторов, функция, которая умножает скалярное значение на вектор и т.д. В разделе про векторизованные вычисления в NumPy мы видели примеры функций, которые принимают на вход массив и применяют функцию каждому элмементу этого массива. Данные функции также являются примерами вектор функций. Например, функция `np.exp` возводит число $e$ в степень каждого элемента вектора и возвращает вектор такого же размера"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.259723Z",
     "start_time": "2017-12-30T14:22:45.250723Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  2.71828183,   7.3890561 ,  20.08553692])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.array([1, 2, 3])\n",
    "np.exp(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Линейное отображение (linear map)\n",
    "Вектор функция $L\\colon \\mathbb R^m \\to \\mathbb R^n$ называется *линейным отображением* (или линейным оператором) если для всех $\\vec{x}, \\vec{y} \\in \\mathbb{R^m}$ и $\\alpha \\in \\mathbb{R}$ удовлетворяет следующим двум условиям\n",
    "1. Отображение произведения вектора на скалярное значение равно произведению скалярного значения на отображение вектора\n",
    "$$L(\\alpha \\vec{x}) = \\alpha L(\\vec{x})$$\n",
    "2. Отображение сложения векторов равно сложению отображений векторов\n",
    "$$L(\\vec{x} + \\vec{y}) = L(\\vec{x}) + L(\\vec{y})$$\n",
    "\n",
    "В качестве примера линейного отображения можно рассмотреть, функцию, которая вычисляет среднее значение всех элементов вектора. Например, если взять два вектора $\\vec{x}=(1, 2, 3), \\vec{y}=(4, 5, 6)$, то следующий код показывает свойства этого отображения"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.270721Z",
     "start_time": "2017-12-30T14:22:45.261225Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "126.0 = 126.0\n",
      "7.0 = 7.0\n"
     ]
    }
   ],
   "source": [
    "x = np.array([1, 3, 5])\n",
    "y = np.array([2, 4, 6])\n",
    "a = 42\n",
    "\n",
    "print('{0} = {1}'.format((a * x).mean(), a * x.mean()))\n",
    "print('{0} = {1}'.format((x + y).mean(), x.mean() + y.mean()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Из свойств линейного отображения следует равенство: $L(\\alpha \\vec{x} + \\beta \\vec{y}) = \\alpha L(\\vec{x}) + \\beta L(\\vec{y})$. Можно обобщить данное выражение на большее количество векторов. Допустим у нас есть n векторов размера m: $\\vec{x_1}, \\vec{x_2}, \\ldots, \\vec{x_n} \\in \\mathbb{R^m}$ и n скалярных значений: $a_1, a_2, \\ldots, a_n \\in \\mathbb{R}$. Тогда верно следующее выражение, которое здесь приводится без доказательства:\n",
    "$$L(a_1 \\vec{x_1} + a_2 \\vec{x_2} + \\cdots + a_n \\vec{x_n}) = a_1 L(\\vec{x_1}) + a_2 L(\\vec{x_2}) + \\cdots + a_n L(\\vec{x_n})$$\n",
    "\n",
    "Можно записать данное выражение в более сжатом виде следующим образом:\n",
    "$$L(\\sum_{i=1}^n a_i \\vec{x_i}) = \\sum_{i=1}^n a_i L(\\vec{x_i})$$\n",
    "\n",
    "# Матрица\n",
    "Выше мы видели, что любой вектор может быть записан в виде линейной комбинации базисных векторов: \n",
    "$$\\vec{x} = \\sum_{i=1}^{m} x_i \\vec{e_i}$$\n",
    "Поэтому линейное отображение вектора эквивалентно выражению: \n",
    "$$L(\\vec{x}) = L(\\sum_{i=1}^{m} x_i \\vec{e_i})$$\n",
    "Однако мы только что видели, что линейное отображение суммы векторов равно сумме линейных отображений каждого из этих векторов. Поэтому линейное отображение вектора можно записать следующим образом: \n",
    "$$L(\\vec{x}) = L(\\sum_{i=1}^{m} x_i \\vec{e_i}) = \\sum_{i=1}^{m} x_i L(\\vec{e_i})$$\n",
    "Если определить вектор $\\vec{u_i}=L(\\vec{e_i})$, то любое линейное отображение может быть полностью определено через линейную комбинацию векторов $\\vec{u_i}$: \n",
    "$$L(\\vec{x}) = \\sum_{i=1}^m x_i \\vec{u_i}$$\n",
    "Эти векторы ${\\vec{u_1}, \\vec{u_2}, \\ldots, \\vec{u_n}}$ можно записать в двухмерном виде следующим образом:\n",
    "$$\n",
    "\\begin{align}\n",
    "A &= (\\vec{u_1}, \\vec{u_2}, \\ldots, \\vec{u_n}) &= \\begin{pmatrix}\n",
    "        u_{1,1} & u_{1,2} & \\cdots & u_{1,n} \\\\\n",
    "        u_{2,1} & u_{2,2} & \\cdots & u_{2,n} \\\\\n",
    "        \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "        u_{m,1} & u_{m,2} & \\cdots & u_{m,n} \\\\\n",
    "     \\end{pmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Данная двухмерная структура называется матрицей линейного отображения. Любое линейное отображение может быть применено для каждого базисного вектора и результат может быть записан в виде матрицы. Линейное отображение может быть записано с помощью матрицы следующим образом:\n",
    "$$L(\\vec{x}) = A\\vec{x}$$\n",
    "## Умножение матрицы на вектор\n",
    "Выражение $A\\vec{x}$ называется умножением матрицы на вектор. Так как это выражение эквивалентно линейному отображению, то умножение матрицы на вектор можно получить из определения линейного отображения:\n",
    "$$\n",
    "\\begin{align}\n",
    "A\\vec{x} &= L(\\vec{x}) &= x_1\\vec{u_1} + x_2\\vec{u_2} + \\cdots + x_n\\vec{u_n} &= x_1 \\begin{bmatrix}\n",
    "        u_{1,1} \\\\\n",
    "        u_{2,1} \\\\\n",
    "        \\vdots \\\\\n",
    "        u_{m,1}\n",
    "     \\end{bmatrix} + x_2 \\begin{bmatrix}\n",
    "        u_{1,2} \\\\\n",
    "        u_{2,2} \\\\\n",
    "        \\vdots \\\\\n",
    "        u_{m,2}\n",
    "     \\end{bmatrix} + \\cdots + x_n \\begin{bmatrix}\n",
    "        u_{1,n} \\\\\n",
    "        u_{2,n} \\\\\n",
    "        \\vdots \\\\\n",
    "        u_{m,n}\n",
    "     \\end{bmatrix} &= \\begin{pmatrix}\n",
    "        x_1 u_{1,1} + x_2 u_{1,2} + \\cdots + x_n u_{1,n} \\\\\n",
    "        x_1 u_{2,1} + x_2 u_{2,2} + \\cdots + x_n u_{2,n} \\\\\n",
    "        \\vdots \\\\\n",
    "        x_1 u_{m,1} + x_2 u_{m,2} + \\cdots + x_n u_{m,n} \\\\\n",
    "     \\end{pmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Умножение матрицы на вектор можно реализовать на python следующим образом"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.285223Z",
     "start_time": "2017-12-30T14:22:45.272223Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 1])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([[0, -1], \n",
    "              [1, 0]])\n",
    "x = np.array([1, 0])\n",
    "y = np.zeros_like(x)\n",
    "for i in range(len(x)):\n",
    "    for j in range(len(x)):\n",
    "        y[i] += A[i, j] * x[j]\n",
    "y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В NumPy для умножения матрицы на вектор можно использовать функцию `dot`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.298723Z",
     "start_time": "2017-12-30T14:22:45.287222Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 1])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.dot(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Умножение матриц\n",
    "Перед тем как определить умножение двух матриц рассмотрим последовательное применение двух линейных отображений. Пусть у нас есть два линейных отображения $L_A\\colon \\mathbb R^k \\to \\mathbb R^m$ и $L_B\\colon \\mathbb R^n \\to \\mathbb R^k$. Тогда последовательное применение этих двух линейных отображений даст нам третье линейное отображение $L_C\\colon \\mathbb R^n \\to \\mathbb R^m$:\n",
    "$$L_C(\\vec{x}) = L_A(L_B(\\vec{x}))$$\n",
    "Выше мы видели, что любое линейное отображение может быть представлено в виде соответствующей матрицы. Допустим, матрица $A \\in \\mathbb{R}^{m \\times k}$ представляет $L_A$ и матрица $B \\in \\mathbb{R}^{k \\times n}$ представляет $L_B$. Тогда матрица $C \\in \\mathbb{R}^{m \\times n}$, которая представляет $L_C$, вычисляется с помощью умножения двух матриц: $C=AB$. Линейное отображение $L_C$ может быть записано с помощью этих матриц следующим образом:\n",
    "$$L_C(\\vec{x})=C\\vec{x}=(AB)\\vec{x}=(A(B\\vec{x}))$$\n",
    "Каждый элемент матрицы $C$ может быть вычислен по следующей формуле:\n",
    "$$\n",
    "c_{i,j} = \\sum_{k=1}^{n} a_{i,k} b_{k,j}\n",
    "$$\n",
    "Рассмотрим следующий пример:\n",
    "$$\n",
    "\\begin{align}\n",
    "C &= \\begin{pmatrix}\n",
    "        0 & -1 \\\\\n",
    "        1 & 0\n",
    "     \\end{pmatrix} \\times \\begin{pmatrix}\n",
    "        -1 & 0 \\\\\n",
    "        0 & -1\n",
    "     \\end{pmatrix} &= \\begin{pmatrix}\n",
    "        0 * (-1) + (-1) * 0 & 0 * 0 + (-1) * (-1) \\\\\n",
    "        1 * (-1) + 0 * 0 & -1 * 0 + 0 * (-1)\n",
    "     \\end{pmatrix} &= \\begin{pmatrix}\n",
    "        0 & 1 \\\\\n",
    "        -1 & 0\n",
    "     \\end{pmatrix}\n",
    "\\end{align}\n",
    "$$\n",
    "Умножение матриц можно реализовать на python следующим образом"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.312223Z",
     "start_time": "2017-12-30T14:22:45.300724Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0,  1],\n",
       "       [-1,  0]])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([[0, -1], \n",
    "              [1, 0]])\n",
    "B = np.array([[-1, 0], \n",
    "              [0, -1]])\n",
    "C = np.zeros_like(A)\n",
    "for i in range(A.shape[0]):\n",
    "    for j in range(B.shape[1]):\n",
    "        for k in range(A.shape[1]):\n",
    "            C[i, j] += A[i, k] * B[k, j]\n",
    "C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В NumPy для умножения матриц можно использовать функцию `dot`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-12-30T14:22:45.324721Z",
     "start_time": "2017-12-30T14:22:45.314226Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0,  1],\n",
       "       [-1,  0]])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.dot(B)"
   ]
  }
 ],
 "metadata": {
  "hide_input": false,
  "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.6.1"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}