Алгебра

Системы линейных уравнений

Цели урока

  • Решать Ax = b методом Гаусса с partial pivoting и понимать связь с LAPACK dgesv
  • Определять тип решения по rank(A) и rank([A|b]) с опорой на теорему о ранге и дефекте
  • Ставить и решать задачу МНК через нормальные уравнения, и знать, когда вместо них нужны SVD или Ridge
  • Распознавать PageRank как задачу на собственный вектор, а цепи Кирхгофа - как линейную систему на матрице инцидентности
  • Ловить мультиколлинеарность признаков через падение ранга и большое число обусловленности

1998 год. Стэнфорд. Брин и Пейдж формализуют веб как матрицу 60 миллиардов на 60 миллиардов и решают Ax = 0 методом power iteration. Через 25 лет это компания на 2 триллиона долларов, и каждый запрос - это шаг линейной алгебры. Метод Гаусса 1801 года, доведённый до промышленного блеска в LAPACK и SPICE, остаётся самым исполняемым алгоритмом в истории.

  • **PageRank:** веб-граф из 60+ миллиардов страниц как матрица переходов; ранг страницы - собственный вектор при λ=1, найденный power iteration
  • **МНК в ML:** `LinearRegression.fit()` в sklearn решает нормальные уравнения; Ridge/Lasso - регуляризованный МНК; псевдообратная через SVD - универсальная замена
  • **SPICE (с 1973):** законы Кирхгофа дают разреженную систему; KLU делает LU для разреженных матриц - на этом проектируется каждый процессор
  • **numpy/scipy:** `linalg.solve` и `lstsq` - тот самый Гаусс с partial pivoting и SVD, миллиард вызовов в день в Jupyter-блокнотах планеты
  • **Eigenvector centrality:** ранжирование пользователей в Twitter/X, выявление лидеров мнений и фрод-кластеров в банковских графах

Предварительные знания

  • Matrices and Determinants

Гаусс и потерянный астероид

1 января 1801 года Пиацци открывает Цереру. Через 41 день она исчезает за солнцем. Никто из астрономов Европы не может предсказать, где она появится снова. 24-летний Гаусс берёт переопределённую систему наблюдений, изобретает МНК и публикует орбиту. В декабре телескоп Цаха находит Цереру ровно в предсказанной точке. Метод наименьших квадратов был рождён прикладной задачей, и через два века он же стоит за каждой подгонкой модели в machine learning.

Метод Гаусса

Карл Фридрих Гаусс, 1801 год. Астероид Церера потерян за солнцем после 41 дня наблюдений - 24-летний Гаусс восстанавливает орбиту, решая переопределённую линейную систему. Через год телескоп находит Цереру ровно там, где он предсказал. Тот же алгоритм сегодня живёт внутри `numpy.linalg.solve`, SPICE-симуляторов и каждого LU-разложения в LAPACK.

Система Ax = b решается приведением расширенной матрицы [A|b] к ступенчатому виду (row echelon form) тремя элементарными преобразованиями строк: обмен строк, умножение строки на ненулевую константу, прибавление одной строки к другой. Далее - обратная подстановка (back substitution). Это тот самый каркас, на котором стоит матричная алгебра.

**Частичный выбор ведущего элемента (partial pivoting):** ставим в ведущую позицию строку с максимальным по модулю элементом. Это даёт численную устойчивость - именно так работает `dgesv` в LAPACK, и через него `numpy.linalg.solve`, MATLAB backslash, R `solve()`. Когда BLAS делает LU-факторизацию матрицы 10000x10000, под капотом - тот же Гаусс 1801 года, только с SIMD и кэш-блокингом.

SPICE (симулятор электронных схем, Berkeley 1973) каждую миллисекунду решает разреженную Ax=b через KLU - LU для разреженных матриц. Любой чип, который проектировался последние 50 лет, прошёл через метод Гаусса миллионы раз.

Сколько операций (порядок) требует метод Гаусса для n×n системы?

Ранг и типы решений

Ранг матрицы rank(A) - число ненулевых строк в ступенчатом виде = число линейно независимых строк = число линейно независимых столбцов. Для системы Ax = b есть ровно три варианта: единственное решение (rank(A) = rank([A|b]) = n), бесконечно много (rank(A) = rank([A|b]) < n), нет решений (rank(A) < rank([A|b])).

**Теорема о ранге и дефекте:** для линейного отображения A: ℝⁿ → ℝᵐ выполняется rank(A) + nullity(A) = n, где nullity - размерность ядра (Ax=0). Дефект показывает число степеней свободы при бесконечном множестве решений.

В ML это превращается в детектор коллинеарности признаков. Если в датасете два столбца дублируют друг друга (рост в см и рост в дюймах), матрица фичей теряет ранг, и линейная регрессия выдаёт бесконечно много эквивалентных решений. `sklearn` ловит это через `np.linalg.matrix_rank` или через числа обусловленности SVD - и предлагает Ridge как лекарство.

УсловиеТип решенияПример
rank(A) = rank([A|b]) = nЕдинственное2 уравнения, 2 неизвестных - пересечение прямых
rank(A) = rank([A|b]) < nБесконечно многоУравнений меньше неизвестных - прямая/плоскость решений
rank(A) < rank([A|b])Нет решенийНесовместная система - параллельные прямые

Если уравнений меньше, чем неизвестных, то решений всегда бесконечно много.

Решений может не быть вовсе - всё решает ранг, а не соотношение строк и столбцов.

Возьмём 3 уравнения с 5 неизвестными, где третье уравнение противоречит комбинации первых двух. Система недоопределена, но несовместна: rank(A) = 2, а rank([A|b]) = 3, и ни один x не удовлетворяет всем трём. Подсчёт уравнений - эвристика, ранг - окончательный вердикт.

Система 3 уравнений, 5 неизвестных, rank(A) = rank([A|b]) = 3. Тип решения:

Метод наименьших квадратов

Когда система Ax = b переопределена (m > n уравнений, больше уравнений чем неизвестных), точного решения чаще всего нет. МНК ищет x*, который минимизирует ||Ax − b||². Решение через нормальные уравнения: AᵀAx = Aᵀb, откуда x* = (AᵀA)⁻¹Aᵀb при условии полного ранга A. Гаусс изобрёл это для астрономии 1809 года - формула пережила два века и попала в каждую ML-библиотеку.

Под капотом `LinearRegression.fit()` из `sklearn` - это ровно нормальные уравнения. Когда столбцы признаков почти коллинеарны, AᵀA становится плохо обусловленной, и решение взрывается. Лекарство - Ridge регрессия: добавить λI к AᵀA, получится (AᵀA + λI)⁻¹Aᵀb. Это эквивалентно регуляризованной псевдообратной, и матрица гарантированно невырождена.

`np.linalg.lstsq` использует SVD под капотом - это численно устойчивее, чем нормальные уравнения (AᵀA может быть плохо обусловлена). В ML эту задачу решает Ridge Regression (с регуляризацией: AᵀAx + λx = Aᵀb), а её обобщение через SVD даёт псевдообратную Мура-Пенроуза - универсальное решение МНК для любых матриц.

Сформировать AᵀA и решать нормальные уравнения напрямую - и есть стандартный способ МНК.

Лучше использовать SVD- или QR-разложение через `np.linalg.lstsq` - формирование AᵀA возводит число обусловленности в квадрат и убивает точность.

Если у A число обусловленности κ, то у AᵀA оно становится κ². На floating-point арифметике это превращает умеренно плохо обусловленную регрессию в численную катастрофу. Production-код использует QR или SVD, а не наивные нормальные уравнения.

Нормальные уравнения для МНК имеют вид:

PageRank и цепи Кирхгофа

1998 год. Стэнфорд. Двое аспирантов формализуют веб-граф из 60+ миллиардов страниц как стохастическую матрицу P и решают Pᵀv = v методом power iteration. Алгоритм называется PageRank. Через 6 лет Google выходит на IPO с капитализацией 23 миллиарда долларов, спустя ещё двадцать - 2 триллиона. Вся империя стоит на одной задаче на собственный вектор - простейший случай Ax = b, где b = 0.

Густав Кирхгоф, Гейдельберг 1845. Закон узлов плюс закон контуров дают линейную систему: матрица A - это топология цепи (incidence matrix), b - вектор источников ЭДС. Через сто двадцать лет SPICE превратит это в основу проектирования любого процессора. Каждый чип, на котором запускается этот текст, рождён из решения Ax = b методом Гаусса для разреженных матриц.

**Power iteration:** умножение вектора v на P снова и снова сходится к собственному вектору при наибольшем собственном значении. Для PageRank λ_max = 1 (матрица стохастическая). Тот же приём - eigenvector centrality в социальных сетях, спектральная кластеризация и анализ важности узлов в цепях Маркова. Один и тот же O(n) шаг работает на графе из миллиардов вершин - прямое решение Ax=0 за O(n³) было бы невозможно физически.

PageRank сводится к нахождению:

Ключевые идеи

  • **Метод Гаусса:** O(n³) операций; с partial pivoting численно устойчив; основа LAPACK, numpy.linalg.solve, MATLAB backslash
  • **Ранг + теорема о дефекте:** rank(A) + nullity(A) = n; тип решения определяется rank(A) и rank([A|b]); коллинеарность признаков ловится через ранг
  • **МНК:** переопределённые системы → нормальные уравнения AᵀAx = Aᵀb; lstsq через SVD надёжнее; Ridge добавляет λI как страховку от плохой обусловленности
  • **PageRank:** стационарный вектор цепи Маркова = собственный вектор при λ=1; power iteration O(n) на итерацию работает на графах в миллиарды узлов

Связанные темы

Системы уравнений - ворота в прикладную линейную алгебру:

  • Линейные пространства — Пространство решений и ядро - фундаментальные подпространства матрицы
  • Собственные значения — PageRank - частный случай задачи на собственные векторы
  • SVD — lstsq использует SVD; псевдообратная A⁺ - обобщение обратной для прямоугольных матриц
  • Линейная регрессия — LinearRegression.fit() - это нормальные уравнения МНК

Вопросы для размышления

  • PageRank работает с матрицей размером миллиарды на миллиарды. Почему power iteration предпочтительнее прямого решения системы?
  • МНК минимизирует сумму квадратов ошибок. Когда это не подходит и нужны другие нормы (L1, L∞)?
  • Что происходит с нормальными уравнениями AᵀAx = Aᵀb, когда столбцы A почти линейно зависимы? Как Ridge Regression исправляет это?

Связанные уроки

  • alg-06 — Матрицы и определители - фундамент для записи Ax=b
  • alg-10 — Собственные значения: PageRank как задача на eigenvector
  • alg-16 — SVD и псевдообратная обобщают МНК на любые матрицы
  • ml-06-linear-regression — LinearRegression.fit() решает нормальные уравнения под капотом
  • ml-08-regularization — Ridge регрессия - регуляризованный псевдообратный МНК
  • la-06-gauss
Системы линейных уравнений

0

1

Войти