Системы линейных уравнений: от школы до TensorFlow

Линейная регрессия, фильтр Калмана, метод наименьших квадратов - все они в итоге сводятся к решению системы линейных уравнений. Понять, когда система совместна, когда имеет единственное решение, а когда множество - значит понять фундамент половины методов ML.

• Линейная регрессия: нормальное уравнение (XᵀX)w = Xᵀy - система линейных уравнений
• Компьютерная графика: нахождение точки пересечения лучей - система 3 уравнений
• Электротехника: законы Кирхгофа для сети с n узлами - система n уравнений
• Экономика: равновесие рынков в модели Вальраса - большая линейная система
• GPS: определение координат из 4 уравнений дальности до спутников

Системы линейных уравнений: от школы до TensorFlow

**Каждую секунду numpy.linalg.solve вызывается миллионы раз по всему миру** - в физических симуляторах, финансовых моделях, нейросетях, компьютерном зрении. За этим вызовом стоит ровно одно уравнение: **Ax = b**. Трансформация A известна, результат b известен, нужен исходный вектор x. Школьная система уравнений - это то же самое, просто записанное построчно. Матричная запись позволяет решать её за O(n²) вместо O(n³) и использовать GPU.

**О чём этот урок на самом деле**: не "как решать задачи в столбик", а три практических вопроса. Первый: как работает np.linalg.solve и почему inv(A) @ b медленнее. Второй: что делать с переопределёнными системами (больше уравнений чем неизвестных) - это 90% задач в ML. Третий: conjugate gradient и зачем он нужен когда матрица гигантская.

Три формы одного уравнения

Три формы одного уравнения

1. КЛАССИЧЕСКАЯ (школьная): 2x + 3y - z = 5 x - y + 2z = 1 3x + y + z = 4 2. МАТРИЧНАЯ: A · x = b ┌ ┐ ┌ ┐ ┌ ┐ │ 2 3 -1 │ │ x │ │ 5 │ │ 1 -1 2 │ · │ y │ = │ 1 │ │ 3 1 1 │ │ z │ │ 4 │ └ ┘ └ ┘ └ ┘ 3. СТОЛБЦОВАЯ (комбинация столбцов): ┌ 2 ┐ ┌ 3 ┐ ┌ -1 ┐ ┌ 5 ┐ x · │ 1 │ + y · │ -1 │ + z · │ 2 │ = │ 1 │ └ 3 ┘ └ 1 ┘ └ 1 ┘ └ 4 ┘ Вопрос столбцовой формы: «Как представить вектор b в виде линейной комбинации столбцов A?» Коэффициенты x, y, z - это и есть решение.

**Столбцовая интерпретация мощнее**: она напрямую связана с рангом матрицы и понятием линейной оболочки. Если b лежит в пространстве, натянутом на столбцы A - решение есть. Не лежит - решения нет. Именно отсюда вырастает теория совместности систем.

Сколько решений: три случая

Сколько решений: три случая

np.linalg.solve vs inv: почему inv медленнее

np.linalg.solve vs inv: почему inv медленнее

Наивный способ решить Ax = b - вычислить A⁻¹ и умножить: x = A⁻¹ · b. Это **неправильный** подход в production-коде. np.linalg.solve(A, b) быстрее и точнее, потому что использует LU-разложение напрямую, без вычисления обратной матрицы.

**Почему solve быстрее**: np.linalg.inv строит полную обратную матрицу O(n³), потом умножает A⁻¹ · b за O(n²). np.linalg.solve сразу решает через LU-разложение с пивотингом - один проход вместо двух, меньше округлений. В LAPACK это функция dgesv. При 10 правых частях b₁...b₁₀ solve вызывается один раз с матрицей B - снова выигрыш.

Переопределённые системы: lstsq и нормальное уравнение

Переопределённые системы: lstsq и нормальное уравнение

В ML почти всегда уравнений **больше** чем неизвестных: 10000 примеров, 100 признаков. Точного решения нет - b не лежит в образе A. Выход: найти x*, который **минимизирует** ||Ax - b||². Это задача ~наименьших квадратов~{least squares: min ||Ax - b||²}.

Задача: min ||Ax - b||² при A размера (m x n), m > n Теорема: минимум достигается при AᵀA · x* = Aᵀb Если AᵀA обратима (что бывает при полном ранге A): x* = (AᵀA)⁻¹ Aᵀ b ЭТО И ЕСТЬ линейная регрессия! X = матрица признаков (n_samples x n_features) y = вектор меток w* = (XᵀX)⁻¹ Xᵀy ПРОБЛЕМА нормального уравнения: XᵀX может быть плохо обусловлена (κ >> 1) → использовать scipy.linalg.lstsq или sklearn LinearRegression (внутри они используют SVD, а не явное обращение)

**Когда lstsq лучше нормального уравнения**: всегда, когда данные потенциально мультиколлинеарны или матрица признаков плохо обусловлена. lstsq использует SVD внутри - даже при ранг-дефицитной матрице выдаёт минимальную по норме ||x*|| псевдорешение. sklearn LinearRegression делает ровно то же самое.

LU, Cholesky, QR: выбор алгоритма по ситуации

LU, Cholesky, QR: выбор алгоритма по ситуации

np.linalg.solve умеет выбирать алгоритм автоматически, но понимание того, какой алгоритм используется внутри, помогает диагностировать проблемы и выбирать scipy-функции явно.

Conjugate Gradient: когда матрица не помещается в память

Conjugate Gradient: когда матрица не помещается в память

LU-разложение требует O(n³) операций и O(n²) памяти. При n = 10⁶ (типично для задач на графах, PDE, больших sparse систем) это невозможно. ~Метод сопряжённых градиентов~{conjugate gradient: итеративный метод для SPD систем} (CG) решает Ax = b итерационно: каждый шаг O(n) умножений, сходится за ≤ n шагов.

Задача: min f(x) = (1/2) xᵀAx - bᵀx Градиент: ∇f(x) = Ax - b = 0 → это и есть Ax = b ЭТО ТА ЖЕ ЗАДАЧА что и решение системы! CG решает её как задачу оптимизации. КАЖДЫЙ ШАГ: r_k = b - A·x_k (невязка, residual) p_k = -r_k + β·p_{k-1} (сопряжённое направление) x_{k+1} = x_k + α_k·p_k (шаг вдоль p_k) ГДЕ ИСПОЛЬЗУЕТСЯ: scipy.sparse.linalg.cg(A, b) - для sparse SPD матриц PyTorch L-BFGS оптимайзер - NN обучение с точным CG Gaussian Process posterior - GPyTorch использует CG

**Preconditioned CG в оптимизации нейросетей**: чистый градиентный спуск - это CG с нулевой памятью о прошлых направлениях. L-BFGS и Hessian-free optimization используют приближения сопряжённых направлений. Именно поэтому L-BFGS в sklearn.LogisticRegression быстрее SGD на табличных данных - он учитывает кривизну поверхности потерь.

Однородные системы: ядро матрицы

Однородные системы: ядро матрицы

~Однородная система~{homogeneous system: Ax = 0} - это вопрос «какие векторы A обнуляет?». Множество таких векторов называется ~ядром~{null space / kernel} матрицы A.

Ax = 0 всегда имеет нулевое решение x = 0. ЕСЛИ det(A) ≠ 0 → только x = 0 (ядро нулевое) ЕСЛИ det(A) = 0 → ядро ненулевое (бесконечно векторов) ГЕОМЕТРИЯ: Проекция на ось X: ker = вся ось Y Поворот: ker = только {0} ML-применение: null space матрицы весов в нейросети = направления, которые слой «не видит». Именно из-за ненулевого ядра в underdetermined системах решений бесконечно - нужна регуляризация (L2 / L1 / dropout) чтобы выбрать одно конкретное.

Ax = b в ML-инфраструктуре

Где решение систем работает прямо сейчас

Практика: решение линейной системы

Практика: решение линейной системы

Вопросы для собеседования

Что унести из урока

• **Ax = b** - одно уравнение за тремя видами записи; матричная форма открывает GPU и библиотечные solver-ы
• **np.linalg.solve** быстрее и точнее чем inv(A) @ b - использовать всегда, когда нужно решить систему
• **Переопределённые системы** (m > n) - нет точного решения; lstsq минимизирует ||Ax - b||² через SVD
• **Нормальное уравнение** AᵀA·x = Aᵀb - это вся линейная регрессия в одной формуле
• **Выбор алгоритма**: LU - общий, Cholesky - SPD (в 2x быстрее), QR/SVD - переопределённые, CG - sparse/огромные
• **Ядро матрицы** (null space) - направления которые система «не видит»; именно из-за него underdetermined задачи имеют бесконечно решений

Куда дальше

Системы уравнений - пересечение всего линейной алгебры

• Свойства матриц — Обусловленность и SPD-ность определяют выбор solver-а
• Обратная матрица — A⁻¹ существует ↔ det(A) ≠ 0 ↔ Ax=b имеет единственное решение
• SVD и псевдообратная — lstsq = A⁺b через SVD; псевдообратная обобщает решение на ранг-дефицитный случай

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

• nm-01