На ютубе таймстемпы в комментариях кликабельные. Здесь копии для удобства поиска сразу по всем видеозаписям.
- ШАД prep 2021 — линал 01
- ШАД prep 2021 — линал 02
- ШАД prep 2021 — линал 03
- ШАД prep 2021 — линал 04
- ШАД prep 2021 — линал 05
- ШАД prep 2021 — линал 06
- ШАД prep 2021 — линал 07
- ШАД prep 2021 — линал 08
0:00:00 Вступительные слова о курсе.
0:09:25 Система линейных уравнений, алгоритм Гаусса.
0:16:24 Элементарные преобразования, они не меняют пространство решений.
0:26:27 Ступенчатый вид, главные и свободные переменные.
0:32:14 Улучшенный ступенчатый вид.
0:35:45 Существование решений, три ситуации: решений нет, решение одно, решений бесконечное количество.
0:53:27 Задача про количество главных переменных в зависимости от параметра, в домашнем задании есть похожая чуть сложнее.
1:05:09 Матрицы, операции над ними.
1:12:57 Важные примеры: матрица сдвига, у которой все нули, кроме единиц над диагональю, матрица цикла.
Если у B в прозведении AB есть нулевой столбец, то и в результате будет там же нулевой.
Аналогично, если у А в прозведении AB есть нулевая строка, то и в результате будет нулевая строка
1:20:26 Умножение на диагональную матрицу слева или справа — строки или столбцы умножаются на диагональные элементы.
1:25:53 Связь между системами линейных уравнений и операциями над матрицами.
1:28:16 Хорошие свойства операций над матрицами: дистрибутивность, ассоциативность — чем матрицы похожи на числа.
1:33:35 Плохие свойства: коммутативности нет, разные размеры в зависимости от порядка умножения.
1:36:24 Простой пример, когда результат умножения разный в зависимости от порядка умножения.
1:38:39 Делители нуля — произведение запросто может оказаться нулевым при ненулевых сомножителях, AB = 0.
1:39:35 Произведение диагональных матриц, они коммутируют.
1:40:29 Иллюстрация для интуиции: связь между диагональными матрицами и функции над конечными множествами.
1:43:05 И еще никого не удивляет, что произведение двух ненулевых функций может оказаться нулевой функцией.
1:44:42 Тот факт, что бывают делители нуля это не плохо, иначе у системы Ax=0 было бы лишь одно нулевое решение.
1:45:37 Если матрица A широкая ▭, то у Ax=0 всегда существует ненулевое решение, за это мы их любим.
1:48:53 Еще пара слов о программе курса.
1:50:42 Нильпотенты – третий пример плохих свойств.
—
1:53:50 Перерыв, обсуждаем литературу по линейной алгебре: Винберг и Linear Algebra Done Right норм, еще материалы курсов на ФКН, а Кострикин это как машинный код, для роботов.
1:57:05 Ответ на вопрос про здравое отношение взрослого человека к подробным доказательствам: прямая аналогия напрашивается про прикладных программистов и разработчиков компиляторов.
—
2:03:23 Задача из ДЗ: какие матрицы коммутируют с диагональной, ответ — диагональные.
По ходу дела комментарий, что формализм и строгость — вещи малосвязанные. Так что бывают доказательства строгие и неформальные, мы ими и занимаемя, все наглядно, но без пробелов. А бывают с кучей формализма и нестрогие, с набором дыр.
2:10:43 Задача из ДЗ: какие матрицы коммутируют с любыми матрицами, ответ — скалярные матрицы.
2:27:03 Задача из ДЗ: какие матрицы коммутируют с матрицей J(0).
2:42:44 Блочная формула умножения матриц.
2:48:09 Частный случай: умножение AB как умножение A на блочную матрицу ( B_1 | ... | B_k).
2:49:20 Иногда удобно произведение матриц AB рассматривать как сумму, если смотреть на них как на блочную строку A и блочный столбец B.
2:52:35 Произведение двух блочных матриц вида (A B \ 0 C), где нулевой блок.
2:54:05 Транспонирование сложения и умножения, (AB)^t = B^t A^t и (A + B)^t = A^t + B^t.
2:57:00 След матрицы tr(A), мы его будем позже обсуждать подробнее, а пока определение и важные свойства tr(AB) = tr(BA), tr(A + B) = tr(A) + tr(B).
3:00:27 Деление и обратная матрица.
Комментарий: можно потребовать любое из AB = E и BA = E, чтобы B была обратой, и доказательство не очевидно, но мы его пока не обсуждаем.
3:04:24 Единственность обратной.
3:06:27 Задача из ДЗ: пусть A прямоугольная, A B_1 = E_n и B_2 A = E_m, тогда m=n, то есть A квадратная — решается через след.
3:10:04 Шесть эквивалентных определений невырожденности, по ходу курса добавятся еще два.
Это удобно, когда надо перейти с одного языка на другой. Например, с языка про системы на язык про обратимость.
В следующий раз будем обсуждать подробней. Когда видишь не первый раз, уже не так страшно.
3:18:00 Задача из ДЗ: пусть A^m = 0, доказать обратимость матрицы E - A и найти ее явный вид.
3:25:48 Завершающие слова: знание — это не какпокупка автомобиля, знание — это как спорт, тренер покажет путь, но заниматься надо самому.
0:02:33 Матрицы, соответствующие элементарным преобразованиям.
0:21:19 Замечание: если надо проделать преобразование строк, а потом преобразоавние слолбцов, то результат будет тот же, что если сделать в обратном порядке, сначала над столбцами, потом над строками: (U_1 A) U_2 = U_1 (A U_2)
0:26:10 Замечание: когда мы решаем систему Ax = b, мы умножаем слева на матрицы элементарных преобразований, UAx = Ub
0:27:50 Замечание: матрицы элементарных преобразований обратимы, явный вид обратных.
0:34:37 Умножение и обратимость:
(1) AB обратима ⇔ A обратима и B обратима по отдельности;
(2) (AB)^{-1} = B^{-1} A^{-1}
0:41:04 Шесть эквивалентных определений невырожденности, по ходу курса добавятся еще два.
0:56:10 Важный момент: обратимость имеет смысл только для квадратных матриц. Частая ошибка бывает, когда глядя на уравнения, записанные в матричном виде, забывают про это и сокращают на какую-нибудь прямоугольную матрицу.
0:57:11 Быстрые критерии необратимости матриц.
(1) Когда есть нулевая строка или столбец;
(2) Если можно элементарными преобразованиеми занулить строку. Например, две строки одинаковые.
1:07:30 В явном виде отрицание всех пунктов из эквивалентных определений невырожденности, для лучшего понимания.
1:09:07 Поиск обратной матрицы: ( A | E ) ~> ( E | A^{-1} ), как это работает.
1:24:29 Рассмотрим Ax=0 и Bx=0 для квадратных матриц одинаковой ширины. Мн-ва решений совпадают ⇔ улучшенные ступенчатые виды A и B совпадают (если отбросить нули).
В конспектах утверждение шире. Следующее эквивалентно:
(1) Системы имеют одно и то же множество решений;
(2) A приводится к B элементарными преобразованиями;
(3) ∃ обратимая C: CA = B;
(4) Улучшенные ступенчатые виды A и B совпадают (если отбросить нули).
1:29:49 Ответ на вопрос: если улучшенный ступенчатый вид разный, то что будет с общими решениями?
Утверждение выше про полное совпадение. Если надо пересечение, то к матрице A приписывается снизу матрица B
1:31:31 Задача из ДЗ. Пусть A прямоугольная размера m×n, а B размера n×m. Утверждение: E - AB обратима ⇔ E - BA обратима.
1:33:55 Пример применения этого утверждения. Матрица A — столбец, B — строка. Тогда AB — это большая матрица, а BA — это просто число. Так можно сокращать размер матрицы для проверки обратимости.
1:37:00 Доказательство самого утверждения.
1:50:25 Трюковое доказательство.
2:12:58 Блочные элементарные преобразования.
2:22:32 Пример.
2:27:43 Подстановка матрицы в многочлен.
2:30:44 Зануляющий многочлен. Примеры.
2:32:52 Для любой матрицы существует зануляющий мн-н, причем deg p(t) ≤ n.
Это сложно доказать, а вот это просто: deg p(t) ≤ n^2.
2:35:47 Задача. Сама матрица A не дана, но дан зануляющий мн-н. Нужно выразить обратную матрицу через нее.
2:39:08 Свойства подстановки в многочлен.
2:46:13 Спектр матрицы. Пример: спектр диагональной матрицы.
2:50:14 Матрицы с пустым вещественным спектром. При этом комплексный спектр всегда непуст.
2:52:40 Свойства спектра.
2:58:12 Минимальный многочлен.
3:08:43 Ответ на вопрос, как готовиться.
0:01:07 Определитель. Геометрическая интуиция про ориентированный объем.
0:20:43 Три способа определить определитель.
(1) Через единственность функции, согласованной с умножением матриц;
(2) Через единственность полилинейной и кососимметрической функции на столбцах;
(3) Через явную формулу с перестановками — это почти никогда не нужно.
0:37:55 Пояснение, про структуру явной формулы.
0:43:50 Определители для матриц 2x2 и 3x3.
0:50:07 Как считать: табличный случай и правило по сведению произвольной матрицы к табличному случаю.
Определитель матрицы в ступенчатом виде равен произведению элементов на диагонали.
Простой геометрический пример со следующими матрицами:
a b a 0
0 d 0 d
0:56:19 Пояснение про определение через полилинейную и кососимметрическую функцию на столбцах.
1:03:05 Как меняется определитель при элементарных преобразованиях.
1:12:52 Пара быстрых способов выянить, равен ли определитель нулю.
(-) Строчка или столбец нулевой;
(-) Есть одинаковые или пропорциональные строки или столбцы.
1:15:50 Еще пара свойств:
(-) Транспонирование не меняет определитель;
(-) Определитель единичной и скалярной матрицы;
(-) det(λA) = λ^n det(A);
(-) det(AB) = det(A) det(B).
Определитель — единственная функция, которая уважает произведение.
1:22:22 Важно, что сам определитель и определитель произведения det(AB) работают только на квадратных матрицах.
1:24:09 Резюме по рассказанному об определителю.
1:26:36 К эквивалентным определениям невырожденности добавляется еще один пункт про определитель.
1:29:49 Определитель блочной матрицы
A B
0 D
1:37:37 Ответ на вопрос и корректировка небольшого недопонимания про связь определителя верхнетреугольной матрицы и блочного определителя.
1:47:00 Задача из ДЗ про определитель матирицы, где везде единицы, а на диагонали лямбды.
1:53:33 Задача из ДЗ: определитель Вандермонда.
2:03:00 Задача из ДЗ: дана матрица X = ( X_1 | ... | X_n ), нарезанная на столбцы и набор лямбд, надо посчитать det(λ_1 X_1 X_1^t + ... + λ_n X_n X_n^t). Ответ: det( X diag(λ_1, ..., λ_n) X^t ) = det(X)^2 λ_1, ..., λ_n
2:12:03 Разложение определителя по столбцу или строке.
2:19:40 Вычисление обратной матрицы через присоединенную матрицу. Это теоретический результат, когда мы можем сказать, что мы знаем, как выражаются элементы обратной через элементы исходной матрицы.
2:25:10 Случай 2x2. Запоминается так: диагональные элементы меняются местами, у недиагональных меняется знак, все это делится на определитель.
2:28:10 Характеристический многочлен.
2:35:41 Свойства:
(1) χ(λ) = λ^n - tr(A) λ^{n-1} + ... + (-1)^n det(A). Надо помнить второй и последний коэффициенты, а то, что скрывается за многоточием вряд ли понадобится;
(2) Спектр — это корни характеристического многочлена;
(3) теорема Гамильтона-Кэли: характеристический многочлен зануляет матрицу. Или, что то же самое, минимальный многочлен делит характеристический.
2:44:30 Пример.
2:47:54 Как быстро считать характеристический многочлен для матрицы 2x2: χ(λ) = λ^2 - tr(A) λ + det(A)
2:48:52 Характеристический многочлен блочной матрицы: χ_S(λ) = χ_A(λ) χ_D(λ)
A B
0 D
где A и D квадратные блоки.
2:50:30 Замечание. A-λE обратима для всех лямбд, кроме конечного числа тех, что в спектре. И если была необратимая матрица, то ее легко сделать обратимой, сдвинув ее на λE почти для всех лямбд.
2:52:18 Задача из ДЗ: принцип продолжения по непрерывности для определителя блочной матрицы, det( A B \ C D) = det(A) det( D - C A^{-1} B ), когда A обратима (здесь A — n×n, D — m×m).
Получается умножением на матрицу элементарного преобразования (E 0 \ -CA^{-1} E).
Эта формула близка к той, которую очень хотелось бы: det( A B \ C D) = det( AD - BC ), но во-первых, размеры A не позволяют внести ее во второй сомножитель, и во-вторых, A и C не обязательно коммутируют.
3:01:28 Но если блоки квадратные и соседние коммутируют, то такая формула и получается.
3:03:20 Решение этой задачи в два шага.
0:00:50 Вспоминаем, что E-AB обратима <=> E-BA обратима. Сегодня разеберем, что для квадратных матриц spec(AB) = spec(BA). И χ_{AB}(t) = χ_{BA}(t). Для прямоугольных будут поправки к этому факту.
0:03:12 Вспоминаем, что такое спектр.
0:04:42 Равенство характеристических многочленов матриц AB и BA через продолжение по непрерывности.
0:41:50 Минимальные многочлены матриц AB и BA не обязательно равны, пример: матрицы 2x2 заданы как A = diag(1, 0) и B = J(0), f_min(AB)=t^2, f_min(BA)=t.
0:45:28 Когда матрица A широкая ▭, B высокая ▯: характеристические матриц AB и BA различаются на множитель t^{n-m}. Из этого еще следует, что spec(BA) = {0} ∪ spec{AB} — спектры различаются на включение нуля.
0:50:06 Ответ на вопрос. Что будет, если дана квадратная матрица A с характеристическим χ_{A}(t) = t^k g(t), где g(t)≢0. Можно ли говорить, A раскладывается на произведение высокой ▯ и широкой ▭ матриц. Обсудим это позже, это про тензорный ранг.
0:53:12 Доказательство, утверждения выше, что t^{n-m} χ_{AB}(t) = χ_{BA}(t).
1:01:52 Резюме вышесказанного про AB и BA для квадратных и прямоугольных матриц.
1:07:54 Векторные пространства. Конкретные и абстрактные.
1:15:30 Определение из двух пунктов: интерфейс — множество со сложением и умножением на числа;
1:23:20 И контракт — естественные аксиомы про сложение, умножение, единицу.
1:29:47 Пара примеров векторных пространств: R^n, многочлены, функции на прямой.
1:33:39 Еще важный пример: { y | Ay=0 } — множество решений однородной системы уравнений, со сложением и умножением. То есть, если есть два решения, то их сложение и умножение на числа останется в этом множестве.
1:38:38 Подпространство. Это подмножество, которое замкнуто относительно сложения и умножения на скаляр. Важно, что оно тоже пространство. Пример выше есть подпространство в R^n, и его как пространство не сложней изучать, чем само R^n.
1:41:08 Ответ на вопрос. Умножение u на v не задается. Многочлены можно перемножать, но для пространств это лишняя информация.
1:42:25 Изоморфизм, биекция. Линейное отображние.
1:49:10 Самое важное: любое линейное отображение φ: R^n -> R^m устроено как x -> Ax. И никаких других не бывает. То есть, в R^n любое линейное отображение — это то же самое, что умножить слева на матрицу.
1:50:28 И еще важное: линейное отображение φ: R^n -> R^n из пространства в себя — это линейная деформация пространства. Это растяжения, наклоны, повороты, проекции, симметрии, etc.
Все, что мы изучали про матрицы, будет важно, когда мы будем изучать линейные отображения.
1:51:55 Еще важно, что любое /конечномерное/ пространство изоморфно R^n.
То есть любое конечномерное пр-во (в каком-то смысле маленькое) будет устроено так же как R^n, и его изучать конечномерные пространства — все равно что изучать R^n.
1:52:49 Ответ на вопрос: как определять одинаковость. Пример изоморфизма: нарезка матрицы вертикально в один длинный вертикальный вектор.
1:55:19 Линейная зависимость.
2:12:39 Базис — набор линейно-независимых векторов, через которые выражаются все в пространстве.
Эквивалентные определения:
Базис — максимально линейно-независимый набор. Добавить еще вектор не получится, поломается линейная-независимость.
Базис — минимально-порождающий набор. Выкинуть вектор не получится.
То есть, можно снизу вверх строить базис, а можно сверху вниз.
И еще ∃! набор коэффициентов для выражения вектора в базисе. То есть, координаты вектора в базисе однозначны.
2:18:49 Пример. Стандартный базис. Он есть в R^n и нет в других векторных пространствах. Чтобы были координаты, надо ввести какой-то базис.
2:23:37 Размерность пространства — количество векторов в базисе. И если даны два базиса, то их размеры одинаковы.
2:24:32 Если в каком-то пространстве V дан базис, то это сразу задает биекцию между V и R^n.
2:27:09 Если V ⊇ U, то dim V ≥ dim U. И равенство достигается только при равенстве пространств.
Это позволяет делать проверку того, что набор векторов является базисом.
f_1, ..., f_m ∈ R^n
Это базис или нет? Если m≠n, то нет.
А если m=n, то еще проверяем: либо линейную независимость, либо то, что они порождающие. Достаточно половину определения проверить.
2:29:14 Смена координат. Матрица перехода вектора из одного базиса в другой.
2:38:31 Пример. Как искать эту матрицу в R^n.
2:42:32 Ответ на вопрос про C^{-1} B C: как избавиться от C. Ответ: никак. Это матрицы, и они не коммутируют (за редким исключенем). Путаницу вызвало, что det(C^{-1} B C) = det(C^{-1}) det(B) det(C) = det(B), но здесь числа.
2:44:16 Линейная оболочка.
2:48:09 Все пространства устроены как R^n, и мы хотим теперь понять, как задавать подпространства в R^n.
(-) С помощью линейных оболочек.
(-) Через систему уравнений, { y | Ay = 0 }
2:51:13 Пример A=(1 1), тогда пространство задается так: { (x y)^t | x+y=0 }, и через линейную оболочку: < (1, -1)^t >.
Всегда можно пересчитать из одного способа задания в другой.
Короткое замечание: rk(A) + rk(span) = n.
2:54:17 Как найти базис, если пространство задано одним из способов выше. Вот первый:
Задача: Задан набор векторов, надо среди них выбрать базис и остальные через него выразить.
3:12:18 Скелетное разложение. Оно же ранговая факторизация.
3:22:44 Задача: Подпространство задано матрицей, { y | Ay = 0 }, надо найти базис. Это называется ФСР — фундаментальная система решений.
3:43:46 Обсуждение, как готовиться.
0:02:37 Ранг матрицы.
Следующие определения эквивалентны. И сами числа равны.
(-) Столбцовый ранг
(-) Строковый ранг
(-) Факториальный ранг
(-) Тензорный ранг
(-) Минорный ранг
(-) Количество главных переменных в улучшенном ступенчатом виде
0:30:13 Как эти определения связаны. Самое главное — все эти ранги равны. То есть, это просто ранг.
0:32:18 Пояснение, что факториальный ранг равен тензорному.
0:41:02 Как считать ранг.
0:45:14 Пара свойств:
rk AC = rk DA = rk A, когда C и D обратимы
rk A^t = rk A
0:48:04 Пояснение, что строковый ранг равен столбцовому.
0:54:16 Задача из ДЗ: посчитать ранг матрицы, где везде единицы, а на диагонали лямбды.
1:02:52 Как искать представлеление для факториального и тензорного ранга. Вспоминаем ранговую факторизацию (скелетное разложение), а если ее раскрыть, то получается представление для тензорного ранга.
1:09:17 rk A = 0 ⇔ A=0
rk A = 1 ⇔ A = x y^t — т.е. раскладывается в произведение ненулевых столбца и строки
1:10:40 Задача из ДЗ: минорный ранг. Как найти максимальный минор: для этого сначала находим базис столбцов через ранговую факторизацию, а потом вторым Гауссом находим базис строк.
1:14:50 Минорный ранг позволяет оценить ранг снизу: если видно, что какая-то подматрица невырождена, то ранг матрицы не меньше.
1:17:40 Оценки рангов суммы и произведения.
(-) | rk A - rk B | ≤ rk(A+B) ≤ rk A + rk B
Причем обе оценки достигаются. Примеры на диагональных матрицах.
То есть, если есть ранги слагаемых, не получится ранг суммы автоматом вычислить, его можно лишь оценить. И это лучшая оценка, которая есть.
(-) rk A + rk B - k ≤ rk(AB) ≤ min(rk A, rk B)
k — общая размерность, A размера m⨯k, B размера k⨯n
Причем первое неравенство совсем не очевидно. Остальные оценки простые. Если есть задача на ранги, то велика вероятность, что в одном из шагов это неравенство.
1:31:35 Количество главных переменных = rk A
И dim { y | Ay=0 } = количество свободных переменных = n - rk A.
1:33:16 Еще на всякий случай. Один из двух способов задания подпространства — через линейную оболочку. Размерность линейной оболочки равен рангу матрицы, составленной из векторов.
1:34:14 Ранг квадратных матриц: rk A = n ⇔ det A ≠ 0
Это восьмое эквивалентное определение невырожденности.
1:35:00 Замечание. Два случая: det A ≠ 0 и det A = 0. В первом ранг полный. В остальных ранг показывает, насколько матрица вырожденна.
Еще замечание ранг блочно-диагональной матрицы равен сумме рангов блоков на диагонали.
1:38:37 Матрица A m⨯n может быть представлена в виде C F D, где C и D обратимы, а F прямоугольная с единицами на диагонали, причем их количество равно рангу A.
Это достикается сначала приведением к ступенчатому виду по строкам, а потом по столбцам.
1:43:40 Линейные отображения.
1:45:57 Линейные операторы, из пространства в себя, это линейная деформация. Примеры.
1:54:36 Как задавать линейное отображение из V в U.
Выбираем базис в V и говорим, куда его векторы переходят в U, это однозначно задает всё линейное отображение.
Векторы могут при этом переходить в одно и то же, и в ноль, это нормально.
1:58:54 Задача. Проверить, существует ли отображение, которое переводит набор заданных векторов из V в заданные векторы U.
2:06:26 Еще одно решение этой задачи: отображение задается матрицей с неизвестными коэффициентами, записываем все условия в одну большую систему уравнений и решаем ее.
Но система может получиться довольно большой, можно устать ее решать.
2:09:50 Что делать, если линейно-независимых векторов в данном нам наборе оказалось недостаточно для базиса всего пространства.
Тогда берем и просто проверяем для линейной оболочки, которая представляет из себя подпространство, что есть такое отображение из него в U.
2:16:46 Как дополнить набор векторов до базиса.
2:26:55 Еще раз кратко предыдущая задача про проверку существования отображения с геометрическим пояснением и картинкой.
2:36:35 Отображение из R^n в R^m. Матрица линейного отображения.
2:55:06 Смена базиса. Матрица при замене координат.
3:08:11 Ядро и образ.
Ядра естественным образом задаются с помощью систем Ker φ = { x | Ax = 0 }
Образы естественным образом задаются с помощью линейных оболочек Im φ = { Ax } = { x_1 A_1 + ... + x_n A_n } = < A_1, ..., A_n >
3:13:11 dim Im Φ + dim Ker Φ = dim V
Количество главных и свободных переменных.
3:14:14 Геометрический смысл ядра и образа.
Прообраз есть какое-то решение плюс ядро.
3:19:45 Ответ на вопрос, что линейный оператор — отображение из R^n в R^n, в себя. Ввели отдельный термин, потому что отображение в другое пространоство и отображение в само себя по-разному себя ведут.
0:00:00 Два слова, чтобы вспомнить про линейные отображения, ядро и оброз, и про смену базиса.
0:04:03 Линейные операторы — отображения из пространства в себя, это линейные деформации пространства. Это центральный объект для изучения в линейной алгебре. Для их изучения важны собственные значения и векторы.
0:04:53 В линейной алгебре многое делается методом Гаусса и по-разному интерпретируется. Но есть черта: как только начинаются собственные значения, метод Гаусса уже не позволяет продвинуться, нужны другие методы.
0:05:52 Примеры линейных деформаций.
0:08:09 Когда мы работаем с линейным операторатором, мы пишем не R^n → R^n, а V → V, потому что сразу ясно, что это одно и то же пространоство. У нас один базис. И квадратная матрица.
0:12:04 Диагонализуемые операторы. Это когда в каком-то базисе матрица диагональна. То есть, оператор растягивает пространство вдоль каких-то осей.
0:25:08 Вспоминаем, что Im A — это линейная оболочка ее столбцов, Ker A — это ФСР.
dim Im A = количество главных переменных
dim Ker A = количество свободных переменных
dim Im A + dim Ker A = dim V = n
0:30:50 Для отображения φ: V → V эквивалентны:
(1) φ — биективно (сущ. обратн.)
(2) φ — инъективно
(3) φ — сюрьективно
Замечание:
инъективно ⇔ Ker φ = 0
сюрьективно ⇔ Im φ = V
Геометрический взгляд: Ker φ — прообраз ядра, прообраз точки u будет φ^{-1}(u) = v_0 + Ker φ
В терминах систем уравнений
Ker φ = { y | Ay = 0 }
Im φ = { b | Ax = b }
Если мы знаем частное решение x_0 системы Ax=b, то общее решение будет выглядеть как x_0 + y.
Инъективность и сюрьективность в равенстве dim Im A + dim Ker A = dim V = n
инъективность ⇔ dim Ker φ = 0
сюрьективность ⇔ dim Im φ = n
0:47:25 Лемма о стабилизации.
(1) Ядро при применении преобразования растет до какого-то шага, а потом после некоторого шага стабилизируется:
Ker φ ⊆ Ker φ^2 ⊆ Ker φ^3 ⊆ ...
И ∃k, начиная с которого стабилизируется: { 0 } ≠ Ker φ ≠ Ker φ^2 ≠ Ker φ^3 ≠ ... ≠ Ker φ^k = Ker φ^{k+1} = Ker φ^{k+2} = ...
(2) Такое же поведение для образов, только вложение наоборот:
Im φ ⊇ Im φ^2 ⊇ Im φ^3 ⊇ ...
Начиная с того же k стабилизируется: { 0 } ≠ Im φ ≠ Im φ^2 ≠ Im φ^3 ≠ ... ≠ Im φ^k = Im φ^{k+1} = Im φ^{k+2} = ...
0:51:02 Задача. A ∈ M_n и в какой-то большой степени зануляется, A^N = 0. Тогда эта матрица в степени своей размерности зануляется, A^n = 0.
1:02:36 Задача. Дана матрица A размера 3x3. Найти базис Im A^2021.
1:08:00 Характеристики линейных операторов.
tr, det, χ(t), минимальный — не зависят от выбора базиса.
И не зависят от матрицы линейного оператора.
1:18:12 Задача. Даны две матрицы nxn. Существует ли оператор такой, что в одном базисе он задается матрицей A, а в другом базисе матрицей B.
1:23:24 Это было более ли менее все, что можно знать про линейные операторы до собственных значений. Если удобней думать про линейные операторы в терминах матриц, то выбираем базис и вспоминаем, что мы знаем про квадратные матрицы.
1:24:30 Мы хотели бы выбрать базис, чтобы матрица имела простой вид. В идеале, диагональный. Но не все операторы диагонализуемы.
1:29:22 План дальнейшего обсуждения: диагонализуемость и жорданова нормальная форма, ЖНФ.
1:33:28 Собственные значения и векторы: φ(v) = λv
Замечание: считать нулевой вектор собственным или не считать — это вопрос определения.
1:37:46 В терминах матриц. Ax = λx ⇔ (A-λE)x=0 ⇔ A-λE необратима ⇔ det(A-λE)=0
1:44:56 Алгебраическая кратность и геометрическая кратность.
1:58:40 Пример. Какие собственные векторы у следующих матриц:
(1) Диагональная матрица с разными собственными значениями;
(2) C повторяющимися;
(3) J(0) — это пример, когда геометриеская кратность меньше алгебраической.
2:02:36 Как действует J(0) геометрически — схлопывает в вертикаль, которая потом кладется горизонтально.
Замечание: Im J(0) = Ker J(0) = ⟨e_1⟩
2:05:57 Собственные векторы, отвечающие разным собственным значениям, линейно независимы. Это пока дается как факт, оставляется без доказательства.
2:07:02 Диагонализуемость.
Критерий: сумма алгебраических кратностей должна совпадать с размерностью пространства и геометрические кратности должны быть равны алгебраическим.
2:13:11 Если свалить все собственные векторы в кучу, то они линейно-независимы. И внутри наборов, отвечающих одним собственным значениям. И между наборами.
2:14:15 Собственный базис, как в нем выглядит матрица оператора.
2:18:15 Ответ на вопрос, как это все связано с рангом: ранг мало связан с собственными значениями. Все, что мы можем сказать, это rk Ker φ = количество собственных векторов, отвечающих нулевому собственному значению.
2:21:24 Признаки диагонализуемости:
(-) Кратности в характеристическом многочлене все единичны.
(-) Есть какой-то зануляющий с линейными множителями.
2:26:26 Задача. A^2 = A, rk(A-E)=k. Надо rk A. Решение через матрицы.
2:30:58 Решение через операторы.
2:39:55 Задача. A ∈ M_n(R), A^2 = E. A = ? — Это про корни из единицы в матрицах.
2:47:00 Жорданова нормальная форма, ЖНФ.
Совет сразу рассматривать матрицу в этой форме, если в задаче не дан базис, это скорее всего задача на понимание устройства матрицы с данными условиями.
2:56:47 Ответ на вопрос: как устроена матрица перехода к ЖНФ и как ее получить, составлена ли эта матрица из собственного базиса. Пример: J(0), собственный вектор один, это e_1, из него обратимую матрицу перехода не составить.
2:59:44 На примере демонстрация, что такое алгебраическая кратность, геометрическая кратность.
Максимальный размер клетки, ее связь с леммой о стабилизации.
3:05:28 Замечание: ЖНФ бывает в злобных экзаменационных задачах, а на практике нужна в основном для диффуров. Матрицы диагонализируемы с вероятностью 1, ЖНФ это скорее исключение, и в data science этот случай не учитывается.
3:06:44 Самая главная концепция: когда мы работаем с линейным оператором, если выберем базис, то пространство превращается в R^n, оператор превращается в умножение на квадратную матрицу, и решать задачи для оператора это все равно, что решать задачи для матрицы. А если дана сложная матрица, можно перейти к более удобному базису и рассматривать более простую матрицу.
3:08:33 Полный набор инвариантов для матриц.
3:16:28 Ответ на вопрос, как решать задачу. Как найти ранг для матрицы с χ(t) = (t-2)^2 (t-3)^3 и для χ(t) = t^2 (t-3)^2.
0:01:18 Билинейные формы.
0:07:58 Пример, самый главный: стандартное скалярное произведение.
0:11:04 Матрица билинейной формы.
0:21:47 Замечание: у нас есть два разных объекта, которые описываются квадратными матрицами.
0:24:30 Смена базиса для матрицы билинейной формы.
0:33:05 Симметричные и кососимметричные билинейные формы. Замечание: они не зависят от базиса.
В матричной записи: B^t = B, B^t = -B.
0:36:00 Пример. Матрица стандартного скалярного произведения. B = E, симметричная.
Пример, работает только на плоскости: определитель на матрицах 2x2 есть билинейная форма с матрицей
0 1
-1 0
0:38:08 Замечание: в основном изучаются симметричные билинейные формы, они геометрически осмысленны. Кососимметричные приходят в основном из комплана.
0:40:13 Свойства билинейных форм, которые не зависят от базиса:
(-) ранг: rk B' = rk B
(-) знак определителя: det B' = det(C^t B C) = det B (det C)^2 — определитель может меняться, но знак нет. Из-за этого определитель матрицы билинейной формы лишается смысла, потому что смена базиса меняет определитель.
(-) симметричность и кососимметричность
Замечание: для линейных операторов симметричность зависит от базиса.
0:52:15 Дефекты матриц билинейных форм:
(-) след никак не связан с билинейной формой: tr B' ≠ tr B, можно подобрать базис, чтобы это было любое число
(-) И еще раз, det B' ≠ det B, только знак.
(-) Характеристические многочлены меняются, χ_{B'} ≠ χ_B
(-) Спектр тоже, spec_{B'} ≠ spec_B
0:55:30 Ортогональное дополнение. Левое и правое. У симметричных и кососимметричных билинейных форм они совпадают.
1:01:12 Симметричные билинейные формы, диагональный вид, сигнатура.
1:06:22 Нахождение сигнатуры.
1:17:50 Замечание. rk B = #1 + #-1 = n - #0
1:19:08 Метод якоби.
1:29:02 Продвинутый способ для симметричных билинейных форм: знаки собственных значений дают нам сигнатуру.
1:33:35 Квадратичные формы.
1:36:17 Пример, когда разные матрицы задают разные билинейные формы, но одну и ту же квадратичную форму Q(x_1, x_2) = 2 x_1 x_2
B_1 =
0 2
0 0
B_2 =
0 1
1 0
B_3 =
0 0
2 0
Но если билинейная форма симметричная, то ее всегда можно восстановить из квадратичной.
То есть, взаимно-однозначное соответствие такое:
β(u, v) = 1/2 ( Q(v+u) - Q(v) - Q(u) )
1:42:23 Квадратичная форма — функция от вектора, и мы можем рассмотреть график. Примеры Q(x, y) с разными сигнатурами.
Замечание. Это используется в матане для определения, является ли критическая точка положением минимума или максимума, когда это сводится к подсчету сигнатуры гессиана, его матрица строится из вторых частных производных.
1:55:41 Как получить матрицу из квадратичной формы. Например, Q(x,y,z) = x^2 + xy + yz
2:02:55 Положительно-определенные и неотрицательно-определенные билинейные формы.
2:05:42 Скалярное произведение — симметричная положительно-определенная билинейная форма.
2:10:24 Стандартное скалярное произведение.
2:14:12 Замечание. B^t = B
B>0 ⇔ ∃ невырожденная C, такая что B раскладывается в произведение B = C^t C
B≥0 ⇔ B = C^t C — без невырожденности
Доказательство для B>0.
Для B≥0 оно сложное, но можно им пользоваться без доказательства.
2:22:20 Евклидово пространство — векторное пространство со скалярным произведением.
Пример. Возьмем пространство матриц V = M_mn(R) и зададим скалярное произведение на нем:
(A,B) = tr( A^t B )
Тогда для ненулевых A будет (A,A) = tr( A^t A ) = \sum a_ij^2 > 0.
Это одно и самых популярных скалярных произведений на матрицах.
2:24:41 Пример. Возьмем пространство непрерывных на отрезке функций V = C[0, 1].
Зададим (f,g) = \int_0^1 f(x) g(x) dx
Тогда для ненулевых (f,f) = \int_0^1 f^2(x) dx > 0
2:26:25 Изоморфизм евклидовых пространств.
Утверждение: (V, .) ≃ (U, .) ⇔ dim V = dim U
Здесь скалярные произведения разные для V и для U, так записано для краткости.
Важность утверджения в том, что если размерности одинаковые, то все скалярные произведения устроены одинаково.
2:35:25 Пример. Школьная плоскость R^2, скалярное произведение (x,y) = x_1 y_1 + x_2 y_2. И школьное пространство R^3 со скаларным произведением.
|v| := \sqrt(v,v) — длина вектора
С таким определением длины можно доказать утверждение Коши-Буняковского: | (v,u) | ≤ |v| |u|
Угол между векторами: cos a = (u,v) / |u| |v|
2:40:37 Мотивация для утверждения выше: если есть какая-то интуиция для школьной плоскости и пространства, то они верны и для произвольного евклидова пространства такой же размерности.
То есть, можно найти удобную биекцию с R^n и спокойно пользоваться скалярным произведением для работы с расстояниями и углами.
Замечание. Это соответствие, конечно, работает только для скалярного произведения. То есть, если есть какие-то свойства в векторных пространствах, то они могут запросто потеряться в этом изоморфизме.
2:49:24 Расстояние между векторами: ρ(u,v) = | v - u |. Неравенство треугольника.
2:52:18 Ортогональность: (v,u) = 0. Ортонормированнй базис, B = E.
2:56:31 Задача на подумать. Пространство квадратных матриц V = M_n(R). Существует ли скалярное произведение такое, что множество верхнетреугольных матриц ортогонально матрице, целиком заполненной единицами.
2:58:10 Ортонормированные базисы в R^n.
Утверждение. Следующие пункты эквивалентны:
(-) C^t C = E — это значит, что столбцы C образуют ортонормированный базис
(-) C C^t = E — оказывается, что если нарезать C на строки, то они тоже образуют ортонормированный базис
(-) C^t = C^{-1} — это значит, что обратную брать очень легко, надо просто транспонировать матрицу
Если любое из этого выполнено, то матрица C называется ортогональной. Это такой класс матриц, которые часто используются в контексте стандартного скалярного произведения.
Теперь мы знаем, как выглядят все ортонормированные базисы в R^n, они описываются ортогональными матрицами.
3:07:17 Ортогонализация, процесс Грама-Шмидта. Дана линейная оболочка, и задача в том, чтобы найти в ней ортонормированный базис.
3:21:57 Ответ на вопрос: в чем идея ортогонализировать пространство матриц.
3:26:12 Двойственность для подпространств. Ортогональное дополнение S^⟂ = { v | (s, v) = 0 }.
Если S = ⟨u_1, ..., u_k⟩, то S^⟂ ортогонально каждому u_i.
И S^⟂ = { y | Uy = 0 }, где в U уложенные по строкам векторы u_i.
3:30:00 Сумма подпространств: U + W = { u+w }, еще записывается ⟨U,W>.
3:31:02 Самые главные свойства двойственности. Пусть (V, .) — евклидово пространство, подпространство W ⊆ V, тогда
(1) dim W + dim W^⟂ = dim V — например, в трехмерном пространстве ортогональным дополнением к прямой будет плоскость, и наоборот;
(2) W ∩ W^⟂ = 0, W + W^⟂ = V — например, в трехмерном пространстве ортогональные плоскость и прямая пересекаются только в нуле и их сумма дает все пространство.
(3) Если даны вложенные подпространства W ⊆ U ⊆ V, то их ортогональные дополнения вложены в обратном порядке, W^⟂ ⊇ U^⟂
(4) W^⟂⟂ = W
(5) (W + U)^⟂ = W^⟂ ∩ U⟂
(6) (W ∩ U)^⟂ = W^⟂ + U⟂
3:35:40 Здесь связь с системами уравнений из S^⟂ = { y | Uy = 0 }, можно из них все это вывести.
3:36:17 Аналогия с НОК и НОД. Диаграмма, где ортогональное дополнение переворачивает отношения между подпространствами. Двойственностью удобно пользоваться, когда надо что-то доказать про подпространства, и удобней обращаться с их ортогональными дополнениями.
0:06:00 Проекторы. Возьмем разложение пространства V = U + W, U∩W=0. Оператор φ проецирует на u, φ: V -> U. Тогда эквивалентные свойства проекторов:
Геометрическое — U = Im φ, W = ker φ
Алгебраическое — φ^2 = φ
0:17:22 Пример. В частности, в R^n отображение φ — проектор ⇔ A^2 = A.
На что мы проецируем: Im φ = линейная оболочка столбцов A.
Вдоль чего: Ker φ = { y | Ay = 0 }
0:18:20 Ответ на вопрос. Что значит спроецировать на прямую вдоль плоскости. Иллюстрация.
0:22:07 Замечание. Раз φ^2 = φ, то зануляющий многочлен p(x) = x^2 - x, его корни 0 и 1. То есть, проекторы диагонализуются с единицами и нулями на диагонали.
f_min(x) делит зануляющий и будет или x, или x-1, или x^2-x. Первый и второй случай тривиальны, это нулевое отображение и id.
Если выбрать базис, то проекторы отправляют часть базисных векторов в ноль.
0:26:25 У проекторов tr A = dim U, целое число. То есть, если A^2=A, то tr A = rk A.
0:30:16 Задача. U дано в виде базиса, W дано в виде ФСР { y | Ay=0 }. Как в явном виде записать матрицу проектора на U вдоль W?
B = (u_1 | ... | u_k), A sxn широкая ▭
Ответ: P = B (AB)^{-1} A — мнемоническое правило BABA.
Замечание: AB обратима.
0:43:07 Ортопроекторы. Задача: найти матрицу ортопроектора, то есть проектора на подпространства вдоль его ортогонального дополнения.
Подпространство задано базисом в столбцах A. Тогда ортогональное дополнение W = { y | A^t y = 0 }
Ответ: P = A (A^t A)^{-1} A^t — мнемоническое правило ATATA.
0:57:24 Метод наименьших квадратов. Геометрический смысл, решение через ортопроекцию.
x = (A^t A)^{-1} A^t b
1:05:00 Матрица Грама для набора векторов, G_ij = (v_i, v_j). Если применить к базису, эта матрица будет совпадать с матрицей скалярного произведения.
1:09:50 Пример. Если взять стандартное скалярное произведение в R^n и составить матрицу A из векторов, то матрица Грама будет G(v_1, ..., v_k) = A^t A. Количество векторов может быть и меньше, и больше размерности пространства.
Если в задаче где-то есть A^t A, то возможно, будет выход на объемы, и геометрическая интуиция будет помогать.
1:10:57 Свойства матрицы Грама. (1) Линейная зависимость столбцов в матрице A и в A^t A.
1:15:14 (2) rk G(v_1, ..., v_k) = dim < v1_, ..., v_k > — в терминах матриц это означает, что rk A^t A = rk A, ранг не падает.
1:16:14 (3) det G(v_1, ..., v_k) ≥ 0, то есть, det(A^t A) ≥ 0
Все собственные значения ≥ 0
И > 0 ⇔ v_1, ..., v_k линейно-независимы
1:17:27 (4) Процесс ортгонализации его не меняет. Это следует отсюда: если заменить набор векторов вот так: (v_1, ..., v_k) C = (f_1, ..., f_k), то det G(f_1, ..., f_k) = det C^2 det G(v_1, ..., v_k).
1:20:07 Неориентированные объемы и матрица Грама. k-мерный объем параллелепипеда будет равен Vol_k = sqrt( det G ). Если векторы линейно-зависимы, то объем нулевой.
1:21:25 Пример в R^n. Vol_k = sqrt( det A^t A ) = | det A |
1:25:40 Ориентированный объем.
В R^n со стандартным скалярным произведением (x, y) = x^t y задается как vol_n (v_1, ..., v_n) = det A.
Другие пространства с ортонормированным базисом изоморфны R^n, поэтому там задается так же.
То есть, чтобы определитель задавал ориентированный объем, нужнен ортонормированный базис. Мы ради ортонормированности к определителю вернулись.
1:31:27 Объем линейного оператора.
Рассматривается объем параллелепипеда и объем того, куда он переходит: vol φ(П) = det φ vol П.
1:38:35 Операторы в евклидовом пространстве. Два самых важных класса: движения (ортогональные операторы) и самосопряженные операторы (симметричные).
1:41:07 Движения. Пусть дан оператор. Тогда следующие утверждения эквивалентны:
(1) ( φ(v), φ(u) ) = (u, v)
(2) длины | φ(v) | = |v| и углы α_uv = α_{φ(u)φ(v)}
(3) | φ(v) | = |v|
Вторые два условия наглядные и геометрические, но их сложно проверять: надо для любых векторов и длины проверить, и углы.
А первое непонятное алгебраическое, но им легко пользоваться.
1:46:22 Пояснение, почему из (3) следует (2): сохранение углов следует из равенства треугольников.
Связь алгебраической части (1) с геометрическими: длины выражаются через скалярное произведение, и наоборот, скалярное произведение выражается через длины и углы.
1:49:40 Пример. Как выглядит матрица A движения φ в R^n со стандартным скалярным произведением (x, y) = x^t y.
x^t y = (Ax)^t Ay = x^t A^t A y, то есть, A^t A = E, матрица ортогональная.
В ортонормированном базисе матрица движения ортогональная.
Для движений легко считать обратные матрицы.
1:54:40 Примеры движений в R^2 со стандартным скалярным произведением (x, y) = x^t y: симметрия и вращение, их матрицы.
det Rotation = 1, det Symm = -1. Других вариантов нет, определитель либо 1, либо -1, потому что det A^t A = 1.
Собственные и несобственные движения.
Вращение в R^2 — собственное движение, симметрия в R^2 — несобственное движение.
2:00:21 Примеры движений в R^3. Все движения описываются просто вращениями или вращениями вместе с симметрией. Те, что с симметрией в R^3 — несобственные движения.
2:05:04 Ответ на вопрос, как выглядят вращения вместе с симметрией.
2:08:00 Спектр движений. Все комплексные собственные числа движений являются числами по модулю 1.
2:13:34 Утверждение. Матрица движений выглядит следующим образом: на диагонали идет блок единиц, потом блок минус единиц, а дальше блоки 2x2, состоящие из матриц вращения.
Сам базис мы искать не будем, это техническая задача,
2:16:08 Обзор сказанного про движения.
2:16:52 Самосопряженные операторы, обзор.
Мы любим диагонализируемые операторы.
Хотим разобраться, как выглядят операторы, которые даны в евклидовом пространстве и диагонализуются в ортонормированном базисе.
То есть мы хотим не просто базис, вдоль которого происходит растяжение, а ортонормированный базис.
В алгебраических терминах это дает самосопряженные (симметричные) операторы. В произвольном ортонормированном базисе они будут задаваться симметричными матрицами.
2:20:34 Ответ на вопрос и корректировка недопонимания, что векторы в базисах всегда под углами 90 градусов. До введения скалярного произведения мы рассматривали базисы абстрактно, что иногда запутывает, потому что нам проще воспринимать более сложные понятия из реального мира.
2:24:24 Определение просто сопряженных операторы, пока не самосопряженных.
Дан оператор φ, хотим найти φ* такой, что (φ v, u) = (v, φ* u).
Оказывается, такой φ* существует и единственный.
У сопряженных операторов нет никакого очевидного геометрического смысла, только алгебраический.
Если не пишут в книгах об их геометрическом смысле, это не значит, что они поленились привести примеры, а просто поленились написать о том, что его нет.
2:28:17 Пример. Выберем ортонормированный базис, пространство превратится в R^n со стандартным скалярным произведением (x, y) = x^t y. Оператор φ будет задаваться матрицей A, надо найти матрицу B сопряженного оператора φ*.
(φx, y) = (x, φ* y)
(Ax)^t y = x^t By
x^t A^t y = x^t By
A^t = B
В ортонормированном базисе матрица сопряженного оператора задается просто транспонированием.
И важно, что B = A^t только в ортонормированном базисе. В других базисах будет сложней.
2:33:00 Редкий пример, когда мы можем понять геометрическое действие: A = J_2(0).
2:35:10 Самосопряженные операторы. Самосопряженность φ* = φ означает, что матрица симметричная, A^t = A.
Изучать самосопряженные операторы в ортонормированном базисе это то же самое, что изучать симметричные матрицы. Если в задачах что-то надо сказать про симметричные матрицы, вспоминаем самосопряженные операторы.
Замечание, на всякий случай, еще симметричные матрицы изучаются в билинейных формах, это другое.
2:37:30 Что нужно знать про самосопряженный оператор φ* = φ:
(-) все собственные значения вещественные φx = λx
(-) для разных собственных значений собственные векторы ортогональны
(-) существует ортонормированный базис, где матрица диагональна
2:41:40 Переформулировка в R^n с (x, y) = x^t y. Матрица симметричная, A^t = A.
(-) характеристический многочлен χ(t) имеет только вещественные корни, то есть раскладывается на линейные множители
(-) для разных собственных значений будет Ax = λx, Ay = μy, тогда x^t y = 0, они ортогональны
(-) ∃ C ортогональная, C^t C = E, такая что A = C D C^t — в C собственные векторы, в D собственные значения
Замечание. Здесь аналогия с комплексными сопряженными числами, z* = z, когда z вещественное.
2:48:00 Диагонализация самосопряженного оператора. Хотим A = C D C^t.
(1) находим корни и кратности характеристического многочлена — сумма кратностей будет равна размерности пространства и корни будут вещественные. Выкладываем группами на диагональ, это будет матрица D.
(2) для каждого i решаем ФСР ( A - λ_i ) x = 0 — количество векторов будет равно кратности
(3) ортогонализация Грама-Шмидта, нормируем, выставляем группами по столбцам, получаем C.
2:57:19 Ответ на вопрос, зачем мы это делаем. Для диагонализации симметричных матриц и для SVD. И еще попросили пример в числах.
A =
2 1
1 2
χ(t) = t^2 - 4t + 3 = (t-1)(t-3)
D = diag(3, 1)
И нахождение C для каждого собственного значения.
3:03:12 Ответ на вопрос: нужно ли это для возведения в степень. Любая диагонализация хороша для возведения в степень, а для диагонализации симметричных матриц еще хорошо, что обратную брать не нужно, достаточно транспонировать.
3:04:20 Сингулярное разложение, SVD: A = U Σ V^t.
3:12:35 До обсуждения алгоритмов — обзор, что дает это разложение. Усеченное разложение. Полное разложение нужно, если на V^t хочется сократить, а так пользуются усеченным.
3:18:04 Распишем SVD по блочным формулам. A = σ_1 u_1 v_1^t + ... + σ_k u_k v_k^t
Эта штука похожа на тензорное разложение. k = rk A.
3:21:41 Взгляд на матрицу A как на картинку, и использование SVD для сжатия с потерями. Исходная картинка занимает O(nm) памяти, первые r слагаемых O( r(m+n+1) ).
3:28:10 Компактное разложение, в нем уже нечего отрезать из матриц U и V^t. И замечание про не единственность U и V^t.
3:33:14 Поиск SVD. План действий.
Хотим A = U Σ V^t для широкой матрицы.
Рассмотрим симметричную матрицу S = AA^t = U Σ V^t V Σ^t U^t = U Σ^2 U^t.
Чтобы найти такое ее разложение, диагонализируем самосопряженный оператор, это даст нам Σ и U. Останется найти V.
Рассматриваем AA^t, а не A^t A, потому что рассматриваем широкую матрицу A.
Тогда AA^t меньше размером, меньше вычислений.
Когда A высокая, алгоритм тот же, просто мы ее предварительно транспонируем в широкую, а потом разложение еще раз транспонируем.
3:37:18 Алгоритм, как искать SVD.
(1) Диагонализируем симметричную матрицу S = AA^t, получаем U и Σ из S = U Σ^2 U^t.
Собственные значения AA^t неотрицательны, потому что < AA^t x, x > = < Ax, Ax > ≥ 0
(2a) Поиск первых r значимых столбцов V.
v_i = 1/σ_i A^t u_i
Это получается отсюда:
A^t = V Σ^t U^t
A^t u = V Σ
(2b) Находим ФСР Ay=0, ортогонализация Грама-Шмидта, нормировка.
3:44:30 Еще раз обзор алгоритма.
3:46:50 Пример на маленькой матрице 2x3.
3:52:30 Обзор пары современных применений SVD: как исследователи некоторые элементы физики превращают в real-time с помощью нейронок, и как можно вырезать статический фон из изображений, отбрасывая большие сингулярные значения.
Еще вернемся к SVD, когда будем обсуждать PCA, который будет в рамках тервера.