Алгебра · объяснение и практика

Как свободная переменная описывает все решения системы

Как записать полное семейство решений через свободную переменную, почему нулевая строка не является противоречием и что показывает число ведущих столбцов.

Неизвестное x показывает найденное значение — пять.

В теме Матрицы и комплексные числа: углубление · Учебная карта

В маршруте Матрицы и линейные системы · 10 тем

Главная мысль

В совместной линейной системе неведущие переменные можно выбрать свободными и выразить остальные через них. Противоречивая строка 0=c при c≠0 исключает все решения.

Не угадываем одно решение вместо всех

После исключения система может принять вид x+2y−z=5 и y+z=2. Неизвестных три, независимых условий два. Выбор z=t оставляет действительный параметр t, после чего y=2−t и x=1+3t. Ответом является всё семейство, а не только удобная точка при t=0. Каждое значение параметра должно быть разрешено явно.

Роль свободной переменной видна из ступенчатой формы: в столбцах x и y стоят ведущие элементы, а в столбце z своего ведущего элемента нет. Параметром можно выбрать и другую подходящую координату, но тогда формулы изменятся. Разные параметризации иногда описывают одну и ту же прямую решений.

Пример

Для t=−1 получаем (x;y;z)=(−2;3;−1). Подстановка даёт −2+6+1=5 и 3−1=2.

Общая подстановка тоже работает: (1+3t)+2(2−t)−t=5 и (2−t)+t=2. Поэтому проверено не только одно значение, а вся записанная семья.

Нулевая строка и противоречие

Равенство 0=0 ничего не запрещает и обычно означает, что одно уравнение зависело от других. Равенство 0=7 выполнить невозможно. В расширенной матрице эти ситуации отличаются последним столбцом, хотя коэффициентная часть обеих строк состоит из нулей. Проверка только коэффициентов не различает совместность и несовместность.

Ранг коэффициентной матрицы — число независимых ведущих направлений после исключения. Для совместной системы над действительными числами число свободных параметров равно числу неизвестных минус этот ранг. Но формулу применяют после проверки правой части: при противоречии никакого семейства решений нет независимо от числа свободных столбцов.

Как доказать полноту параметризации

Проверьте два направления. Сначала подстановка произвольного t должна давать исходные равенства. Затем любое решение системы должно быть получено при некотором t: здесь достаточно взять t равным его координате z, и остальные координаты уже вынужденно равны найденным формулам. Одна лишь демонстрация нескольких подходящих точек полноту не доказывает.

Если неизвестные по смыслу обязаны быть целыми или неотрицательными, действительное семейство нужно дополнительно ограничить. Например, условие z≥0 превращается в t≥0, а y≥0 добавляет t≤2. Эти ограничения идут из задачи и не возникают автоматически из линейного исключения; забывать их после удобной параметризации нельзя.

От чтения к действию

А теперь — вы

Совместная линейная система пяти действительных неизвестных имеет два ведущих столбца. Сколько свободных параметров требуется для полного семейства решений?

Частые вопросы

Любая нулевая строка даёт бесконечно много решений?

Нет. Другие строки могут содержать противоречие или уже определять все неизвестные. Нужно исследовать всю систему.

Свободный параметр обязан обозначаться буквой t?

Нет. Это выбранное имя. Важно указать допустимые значения и не перепутать параметр с дополнительным независимым условием.

Углублённый разбор

Пересечение аффинных семейств с независимыми параметрами

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

Перед началом: Параметрическое семейство; Системы линейных уравнений.

Одинаковое имя параметра создаёт лишнее ограничение

Пусть первое семейство задано p+tu, а второе q+sv. Общая точка существует, если tu−sv=q−p для некоторых t,s. Это обычная линейная система с двумя неизвестными параметрами. Требование t=s заранее означало бы синхронное движение двух частиц, а не геометрическое пересечение двух множеств точек.

После решения параметров общую точку вычисляют в любом из исходных семейств и проверяют во втором. Такой контроль необходим: ошибка знака перед s может дать формально красивую пару чисел, не соответствующую пересечению. Равенство векторов проверяется по всем координатам пространства.

Ранг отделяет точку, прямую и отсутствие пересечения

Если направления u,v независимы, параметры общей точки определяются единственно, когда система совместна. В плоскости независимость двух направлений гарантирует совместность. В трёхмерном пространстве появляется третье уравнение, которое может её нарушить: непараллельные прямые бывают скрещивающимися.

При зависимых ненулевых направлениях прямые параллельны. Тогда q−p либо принадлежит общей прямой направлений, и множества совпадают, либо не принадлежит, и пересечения нет. Нулевое направление задаёт одну точку, а не прямую; этот вырожденный случай разбирается проверкой принадлежности отдельно.

Ограничение параметра меняет объект

Для отрезков после нахождения t,s требуется принадлежность заданным диапазонам, обычно [0,1]. Пересечение несущих прямых за пределами одного из отрезков не является пересечением отрезков. Для луча используется одностороннее условие, а для движения по времени дополнительно может потребоваться именно t=s.

Расстояние между прямыми является другой задачей: минимизируется норма разности, а не требуется её точный нуль. Наличие ненулевого минимального расстояния в пространстве подтверждает отсутствие пересечения. Но в данной главе используются точные линейные равенства, которые дают и параметры, и проверяемый общий вектор.

Пересечение с разными параметрами

Условие. L₁=(1,0)+t(2,1), L₂=(0,3)+s(1,−1). Найдите общую точку и проверьте отрезки при t,s∈[0,1].

  1. Равенство координат даёт 1+2t=s и t=3−s. Не отождествляем t с s.
  2. Подставляем первое выражение во второе: t=2−2t, поэтому t=2/3 и s=7/3.
  3. Общая точка равна (1+4/3,2/3)=(7/3,2/3). Вторая формула даёт тот же результат.
  4. Для первого отрезка t допустим, но s=7/3>1. Поэтому отрезки не пересекаются, хотя прямые пересекаются.

Ответ. Прямые пересекаются в (7/3,2/3); указанные отрезки не пересекаются.

Проверка. Разность направлений системы имеет определитель −3≠0, поэтому найденные параметры единственны. Подстановка в обе исходные прямые подтверждает координаты.

Где легко ошибиться. Параметр каждой прямой является собственной координатой на ней. Одинаковая буква в двух формулах не даёт права добавлять условие синхронизации.

Проверьте понимание

Чему равен параметр второй прямой в точке пересечения?

Вопросы к этой главе

Можно переименовать s в t после ответа?

Для описания одной отдельно взятой прямой да. При совместном решении необходимо различать два независимых выбора, иначе задача будет изменена.

Почему непараллельности мало в пространстве?

Два независимых направления порождают только плоскость разностей. Вектор между началами может лежать вне неё, и тогда система трёх координат несовместна.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Georgia Tech: The Rank Theorem

    Вебом прочитано соотношение ранга и размерности ядра. Вывод о конкретных подпространствах данной главы доказан отдельно; ссылка не означает чтение всей книги.

Неотрицательные решения и границы свободного параметра

Свободный параметр описывает все алгебраические решения, но физические количества часто должны быть неотрицательными. Подстановка параметризации превращает это требование в пересечение интервалов.

Перед началом: Свободные переменные; Линейные неравенства.

Уравнения и допустимость отвечают на разные вопросы

Пусть все решения системы имеют вид x=p+tv, где t действителен. Условие xᵢ≥0 даёт pᵢ+tvᵢ≥0 для каждой координаты. Если vᵢ положителен, получаем нижнюю границу t; если отрицателен — верхнюю. При нулевом vᵢ требуется pᵢ≥0, иначе допустимых решений нет независимо от параметра.

Все координатные ограничения должны выполняться одновременно, поэтому границы пересекают, а не объединяют. Алгебраическое семейство может остаться лучом, отрезком, одной точкой либо исчезнуть. Наличие свободной переменной само по себе не гарантирует бесконечно много физически допустимых решений.

Граничная точка тоже является решением

При нестрогом требовании неотрицательности границы включаются. Нулевая концентрация или нулевой объём по этой модели допустимы, если условие не требует строго положительного значения. Замена ≥ на > меняет достижимость границ и иногда существование оптимума. Поэтому смысл ограничения нужно установить до вычисления интервала.

Если свободных параметров несколько, вместо интервала возникает многогранник в пространстве параметров. Нельзя ограничивать каждый параметр независимо, когда координатные неравенства их связывают. В одномерном случае вся геометрия сводится к сравнению наиболее сильной нижней и наиболее сильной верхней границы.

Целевая величина может выделить один край

Линейная величина cᵀx=cᵀp+t(cᵀv) монотонна по t либо постоянна. На замкнутом ограниченном интервале максимум и минимум находятся на концах, если коэффициент при t ненулевой. Если он равен нулю, все допустимые точки дают одинаковый результат. Это простейшая задача линейного программирования на найденном семействе.

После отбора границ полезно проверить исходные уравнения для произвольного t, а не только для концов. Затем отдельно проверяют неотрицательность каждого конца. Первая проверка отвечает за полноту алгебраической параметризации, вторая — за корректное включение допустимых граничных состояний.

Семейство количеств

Условие. Все решения имеют вид (x,y,z)=(4−2t,1+t,t). Найдите неотрицательные решения и максимум величины x+y.

  1. Ограничение x≥0 даёт t≤2. Ограничение y≥0 даёт t≥−1.
  2. Последняя координата z≥0 требует t≥0, что сильнее предыдущей нижней границы.
  3. Пересечение всех условий равно 0≤t≤2. На концах получаются (4,1,0) и (0,3,2).
  4. Целевая величина x+y=5−t убывает. Её максимум пять достигается при t=0.

Ответ. Допустимо t∈[0,2]; max(x+y)=5 при (4,1,0).

Проверка. При t<0 нарушается z≥0, при t>2 нарушается x≥0. Внутри интервала все три координаты неотрицательны, так что условия и необходимы, и достаточны.

Где легко ошибиться. Не выбирайте удобное значение свободной переменной вместо полного пересечения ограничений. Один допустимый пример не описывает множество всех допустимых решений.

Проверьте понимание

Какой точный допустимый интервал параметра в задаче?

Вопросы к этой главе

Возможна единственная допустимая точка при свободном параметре?

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

Когда максимум не существует?

Например, при открытой границе интервала и возрастающей цели возможен конечный супремум без достижения. На неограниченном луче цель может неограниченно возрастать.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Georgia Tech: The Rank Theorem

    Вебом прочитано соотношение ранга и размерности ядра. Вывод о конкретных подпространствах данной главы доказан отдельно; ссылка не означает чтение всей книги.

Определимая величина при неопределимых координатах

Отдельные неизвестные могут оставаться неопределёнными, тогда как нужная сумма измеряется точно. Разберём, какие линейные величины сохраняют одно значение на всём семействе решений.

Перед началом: Ядро матрицы; Линейная комбинация строк.

Смотрите на невидимые изменения неизвестных

Пусть Ax=b совместна. Любые два решения различаются на h∈ker A, поэтому величина cᵀx одинакова на всех решениях тогда и только тогда, когда cᵀh=0 для каждого такого h. Проверка одного произвольно выбранного направления недостаточна при многомерном ядре: нужен полный базис невидимых изменений.

В конечномерном вещественном пространстве условие равносильно принадлежности c пространству строк A. Если cᵀ=λᵀA, то cᵀx=λᵀb для любого решения. Вектор λ даёт короткий сертификат определимости: достаточно проверить равенство коэффициентов, после чего нужный результат получается из наблюдений без восстановления каждого xᵢ.

Определимость зависит от вопроса, а не только от ранга

При неполном ранге часть линейных величин определима, часть нет. Наличие свободного параметра запрещает единственное восстановление всего вектора, но не отдельных функционалов. Например, измерение x+y позволяет знать эту сумму точно, хотя x−y может принимать любое действительное значение.

Если требуется нелинейная величина, принадлежности c пространству строк уже недостаточно, поскольку фиксированного c может не существовать. Тогда исследуют значение выражения на всём параметрическом семействе. Неотрицательность или другие дополнительные ограничения тоже способны уменьшить множество возможных значений, но это информация сверх исходной линейной системы.

Сертификат даёт способ распространить ошибку данных

При возмущении b на δb оценка определимой величины меняется на λᵀδb, если модель A остаётся той же. Разные представления через λ при зависимых строках дают одинаковое значение для совместных точных данных, но могут различаться на несовместном шуме. Для измерений с ошибкой потребуется явно выбрать правило согласования.

Отказ определимости тоже имеет короткое свидетельство: найдите h∈ker A с cᵀh≠0. Тогда x₀+th сохраняет наблюдения, а функционал меняется линейно по t. Это доказывает отсутствие единственного ответа конструктивно, вместо общей фразы о недостатке уравнений.

Измеримая сумма

Условие. Известны x+y=5 и y+z=4. Какие значения могут иметь x+2y+z и x−z? Определяется ли x+z?

  1. Сумма двух уравнений сразу даёт x+2y+z=9 для каждого решения.
  2. Вычитание второго уравнения из первого даёт x−z=1 независимо от свободной координаты.
  3. Положив y=t, получаем x=5−t, z=4−t. Поэтому x+z=9−2t меняется.
  4. Направление h=(−1,1,−1) лежит в ядре и меняет x+z на −2 за единичный шаг параметра.

Ответ. x+2y+z=9 и x−z=1 определимы; x+z не определяется.

Проверка. Строковые сертификаты для двух постоянных величин имеют веса (1,1) и (1,−1). Для третьей h даёт явное свидетельство изменения при одинаковых наблюдениях.

Где легко ошибиться. Неполный ранг запрещает восстановить весь вектор, но не любую интересующую величину. Нужно проверять именно функционал, указанный в вопросе.

Проверьте понимание

Что можно утверждать о x+z при данных из задачи без дополнительных ограничений?

Вопросы к этой главе

Нужно сначала находить частное решение?

Для вычисления λᵀb нет, если совместность уже установлена. Но при несовместной системе говорить об общем значении на её решениях как об измеренной величине нельзя.

Может ли определяться отдельная координата?

Да. Берут c равным соответствующему единичному вектору и проверяют то же условие. Свободными могут оставаться другие координаты, не влияющие на эту.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Georgia Tech: The Rank Theorem

    Вебом прочитано соотношение ранга и размерности ядра. Вывод о конкретных подпространствах данной главы доказан отдельно; ссылка не означает чтение всей книги.

Лучшая матрица меньшего ранга и остаточная сингулярная величина

Ограниченный ранг — ограничение числа независимых направлений, которые может передавать модель. Усечение сингулярного разложения даёт наилучшую спектральную ошибку среди всех матриц выбранного ранга, а не только среди диагональных кандидатов.

Перед началом: Сингулярные величины; Операторная евклидова норма.

Ранг ограничивает число сохранённых каналов

Пусть A=Σᵢσᵢuᵢvᵢᵀ, где сингулярные величины расположены по убыванию. Сохраним первые k слагаемых и получим Aₖ. Её ранг не больше k. Ортогональность левых и правых векторов показывает, что остаток действует независимо по отброшенным направлениям, а его операторная2-норма равна σₖ₊₁. Это верхняя оценка оптимальной ошибки с явным достигающим её кандидатом.

Остаётся доказать, что произвольная другая B ранга не больше k не может быть лучше. Рассмотрим пространство первых k+1 правых сингулярных направлений. Ограничение B на него имеет нетривиальное ядро. Для некоторого единичного x из этого пространства Bx=0, тогда ||(A−B)x||=||Ax||≥σₖ₊₁. Полученная нижняя граница относится ко всем B и завершает доказательство оптимальности.

Назовите норму до обсуждения качества

В спектральной норме измеряется наибольшее усиление ошибки по одному единичному входу. В норме Фробениуса суммируются квадраты всех отброшенных сингулярных величин, и ошибка равна квадратному корню этой суммы. Одна и та же усечённая матрица оптимальна для обоих критериев, но численные значения ошибок различны. Смешивать σₖ₊₁ с суммой квадратов нельзя.

Оптимальность также не означает единственности в спектральной норме. У diag(3,2) любой кандидат diag(c,0) с1≤c≤5 имеет ранг1 и ошибку max(|3−c|,2)=2. Даже разрыв3>2 не устраняет это семейство. Для многих задач усечённое SVD выбирают как канонический удобный ответ, не объявляя его единственным без дополнительного критерия.

Изменение координат должно сохранять используемую норму

Доказательство опирается на ортогональные левые и правые базисы. Произвольное строковое исключение сохраняет ранг, но может сильно менять евклидову ошибку. Поэтому занулить малый элемент лестничной формы и вернуть преобразования обратно — не общий алгоритм лучшей аппроксимации. При измеренных данных малые сингулярные величины можно трактовать как слабые каналы, однако выбор ранга требует отдельной модели шума или бюджета ошибки.

Два бюджета ранга

Условие. Пусть A=[[3,0,0],[0,0,2],[0,1,0]]. Найдите оптимальную спектральную ошибку при ранге не больше1 и не больше2. Для усечения ранга1 найдите также ошибку Фробениуса.

  1. Матрица AᵀA диагональна и равна diag(9,1,4). Поэтому сингулярные величины A в убывающем порядке равны3,2,1.
  2. Сохраняя только первый канал, берём B₁=diag(3,0,0). Оставшиеся растяжения2 и1 дают спектральную ошибку2.
  3. Для ранга2 сохраняем также элемент A₂₃=2. Тогда B₂=[[3,0,0],[0,0,2],[0,0,0]], остаток имеет единственный элемент1 и спектральную норму1.
  4. При ранге1 квадрат нормы Фробениуса остатка равен2²+1²=5. Следовательно, эта ошибка равна√5, хотя спектральная ошибка равна2.

Ответ. Минимальные спектральные ошибки:2 при ранге≤1 и1 при ранге≤2; ||A−B₁||_F=√5.

Проверка. Прямые произведения остатка на его транспонированную дают квадраты заявленных норм. Нижняя граница по ядру произвольной B доказывает оптимальность и не ограничивается проверкой двух показанных кандидатов.

Где легко ошибиться. Не подменяйте минимизацию ошибки условием сохранения нескольких крупных элементов. Ранг относится к направлениям преобразования, а крупные элементы зависят от выбранных координат.

Проверьте понимание

Какова минимальная спектральная ошибка при ранге не больше1?

Вопросы к этой главе

Собственные значения A подходят вместо сингулярных?

В общем случае нет. Операторная ошибка определяется растяжениями единичных входов, то есть корнями собственных значений AᵀA. У несамосопряжённой A её собственный спектр может описывать совсем другую геометрию.

Почему нижняя граница учитывает все матрицы меньшего ранга?

Любое отображение ранга≤k на пространстве размерности k+1 имеет ненулевое ядро. Доказательство не предполагает специальной формы B, поэтому нельзя обойти границу выбором недиагональных элементов.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Ming-Hsuan Yang: EECS275, Lecture5

    Вебом прочитаны слайды10–12 Low-rank approximation: нормы2 и Фробениуса, формула Эккарта — Янга. На первых слайдах часть PDF-текста искажена, нужная формулировка читается. Пример и контрпример единственности наши.

Обобщённое собственное значение при другой метрике

Если длина определяется положительной матрицей B, задача на собственные направления меняется. Экстремумы xᵀAx/(xᵀBx) определяют пару A,B; собственные значения одной A в обычной евклидовой метрике уже не отвечают поставленному вопросу.

Перед началом: Положительная форма как метрика; Симметричное собственное разложение.

Положительная метрика делает знаменатель безопасным

Пусть A и B действительные симметричные, а B положительно определена. Тогда xᵀBx>0 при любом ненулевом x, поэтому обобщённое отношение Рэлея определено на всех направлениях. Вариационная задача может выражать энергию на единицу массы, стоимость на единицу нормированной мощности или форму в неортонормированном базисе. Важно, что один и тот же B используется и в ограничении, и в отношении.

Сделаем замену y=B^(1/2)x. Тогда знаменатель становится yᵀy, а числитель — yᵀCy с симметричной C=B^(−1/2)AB^(−1/2). Таким образом, задача сводится к обычному симметричному спектру C. Замена невырождена, поэтому не теряет направлений. Минимум и максимум равны крайним собственным значениям C.

Обобщённый вектор решает другое уравнение

Если Cy=λy и x=B^(−1/2)y, то Ax=λBx. Это обобщённое собственное уравнение. Хотя B⁻¹A имеет тот же спектр, она обычно не симметрична в обычной метрике; её симметрия относится к скалярному произведению с B. Поэтому применять к ней евклидову ортогональность без изменения метрики нельзя.

Разные обобщённые собственные направления можно выбирать B-ортогональными: xᵢᵀBxⱼ=0 при разных значениях. Из Axᵢ=λᵢBxᵢ и симметричности обеих матриц следует (λᵢ−λⱼ)xᵢᵀBxⱼ=0. Это короткий сертификат, объясняющий, почему стандартное скалярное произведение двух исходных векторов не обязано обращаться в ноль.

Вырождение метрики меняет саму задачу

Если B лишь полуопределена, некоторые ненулевые направления имеют нулевой знаменатель. Отношение может быть неограниченным даже при положительной A. Например для A=I, B=diag(1,0), x=(ε,1) оно равно1+1/ε² и растёт без границы. Следовательно, нельзя просто заменить отсутствующий обратный корень псевдообратной и сохранить прежнюю теорему. Нужно явно ограничить пространство или сформулировать новую вариационную задачу.

Другая масса двух координат

Условие. Даны A=[[8,2],[2,2]], B=diag(4,1). Найдите крайние значения xᵀAx/(xᵀBx) и два достигающих направления.

  1. Матрица B положительна, B^(−1/2)=diag(1/2,1). Приведённая симметричная матрица C равна [[2,1],[1,2]].
  2. На векторах y₊=(1,1), y₋=(1,−1) она имеет собственные значения3 и1. Значит отношение лежит между1 и3.
  3. Возвращаемся к исходным координатам: x₊=(1/2,1), x₋=(1/2,−1). Прямая подстановка даёт значения3 и1 соответственно.
  4. Проверяем det(A−λB)=4(λ−1)(λ−3). Кроме того x₊ᵀBx₋=1−1=0, хотя обычный скалярный продукт этих векторов равен−3/4.

Ответ. Минимум1 на направлении(1/2,−1), максимум3 на направлении(1/2,1).

Проверка. Точное раскрытие даёт xᵀAx−xᵀBx=(2x₁+x₂)²≥0 и3xᵀBx−xᵀAx=(2x₁−x₂)²≥0. Это независимые глобальные границы без решения характеристического уравнения.

Где легко ошибиться. Не нормируйте обобщённые направления по обычной длине, когда условие задачи задано xᵀBx=1. Масштаб направления можно менять, но используемая метрика должна оставаться указанной в модели.

Проверьте понимание

Каков максимум указанного обобщённого отношения?

Вопросы к этой главе

Нужно ли B коммутировать с A?

Нет. Достаточно симметричности A и положительной определённости B. Симметричная приведённая C строится конгруэнтным преобразованием и без коммутации; одновременная обычная диагонализация не требуется.

Могут ли обобщённые значения быть отрицательными?

Да, если A имеет отрицательные направления. Положительность B гарантирует безопасный знаменатель и вещественный спектр приведённой C, но не положительность числителя. Знаки экстремумов отражают форму A.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Sergei Treil: Linear Algebra Done Wrong

    Прочитаны глава7§4.2: минимакс собственных значений, и §5: положительные формы как скалярные произведения. Обобщённое отношение Рэлея приводится к обычному собственной заменой метрики; матрицы и дополнительные плоскости наши.

Когда неотрицательное решение Ax=b является вершиной

Неотрицательная система Ax=b обычно имеет много решений, но лишь некоторые являются вершинами допустимого многогранника. Их можно распознать без перебора соседних точек: достаточно проверить независимость столбцов, соответствующих строго положительным координатам решения. Число положительных координат само по себе такого ответа не даёт.

Перед началом: Ядро линейной системы; Выпуклая комбинация точек.

Положительная поддержка задаёт разрешённые малые движения

Пусть P={x:Ax=b,x≥0}, а x уже проверен как допустимый. Обозначим J={j:x_j>0}. Если столбцы A_J зависимы, существует ненулевой d, поддержанный на J, с Ad=0. Поскольку все x_j на этой конечной поддержке строго положительны, можно выбрать достаточно малое t>0, чтобы обе точки x+td и x−td оставались неотрицательными.

Эти две разные точки удовлетворяют тем же равенствам и имеют среднее x. Следовательно, x не является крайней точкой. Важно, что направление не затрагивает нулевые координаты: отрицательное движение через такую координату сразу покинуло бы P. Обычное наличие ненулевого ядра A ещё не исключает вершины; запрещено именно поддержанное допустимое двустороннее движение.

Независимость исключает любое разложение

Пусть столбцы A_J независимы и x=(u+v)/2 для допустимых u,v. В координатах вне J стоят нули x. Из неотрицательности u,v следует, что и у них эти координаты нулевые. Поэтому u−v поддержан на J, а A(u−v)=0. Независимость вынуждает u=v=x. Получено обратное направление: критерий необходим и достаточен.

При полном строковом ранге m независимую поддержку можно дополнить до m базисных столбцов. Незаполненные базисные координаты остаются нулевыми. Так появляется базисное допустимое решение. Оно может иметь меньше m положительных координат; это вырожденный случай. Требование ровно m положительных значений ошибочно отвергло бы настоящую вершину.

Разные базисы могут описывать одну вершину

Для малой системы можно выбрать каждый набор из m независимых столбцов, решить квадратную систему на нём и отбросить отрицательные координаты. После этого одинаковые результирующие точки следует объединить: разные наборы базисных индексов иногда дают одну вырожденную вершину. Число базисов и число геометрических вершин поэтому не обязаны совпадать.

Критерий не требует заданной целевой функции. Он описывает геометрию допустимости. Если позже добавлен линейный критерий с достигнутым конечным оптимумом в такой стандартной форме, вершины становятся кандидатами для симплексного поиска. Но отсутствие ограничения сверху или существование направлений неограниченного роста нужно исследовать отдельно, а не считать любой найденный базис решением оптимизационной задачи.

Одна невырожденная вершина, одна вырожденная и внутренняя точка

Условие. Заданы A=[[1,1,1,0],[0,1,2,1]], b=(2,2). Классифицируйте v=(1,0,1,0), w=(0,2,0,0), u=(1,1,0,1) и независимо найдите все вершины P.

  1. Все три точки удовлетворяют Ax=b и неотрицательности. У v положительны координаты 1 и3; соответствующие столбцы (1,0),(1,2) имеют определитель 2, поэтому v является вершиной.
  2. У w поддержка состоит только из второго столбца (1,1), который ненулевой и потому независим. Значит w тоже вершина, хотя положительная координата всего одна при двух независимых уравнениях.
  3. Для u направление d=(−1,1,0,−1) лежит в ядре и поддержано на положительных координатах. Точки u±d/2 допустимы и различны, поэтому u не вершина.
  4. Перебирая шесть пар столбцов, получаем ровно три различные неотрицательные базисные точки: w, v и (2,0,0,2). Три разные пары, содержащие столбец 2, повторяют w; пара столбцов 3,4 даёт отрицательную координату и отбрасывается.

Ответ. v и w являются вершинами, u — нет. Всего у заданного многогранника три вершины; w вырождена.

Проверка. Подстановка двух концов u±d/2 проверяет явное разложение u. Независимый перебор всех пар решает каждую квадратную систему точными дробями и удаляет дубликаты, подтверждая полный список вершин.

Где легко ошибиться. Проверяйте независимость именно положительной поддержки, а не всех столбцов A и не произвольного выбранного квадрата. Нулевые базисные координаты допускаются; вырожденная вершина не перестаёт быть крайней.

Проверьте понимание

Как классифицируется w=(0,2,0,0)?

Вопросы к этой главе

Может ли вершина существовать при ненулевом ядре A?

Да. В примере неизвестных четыре, а ранг равен двум, поэтому ядро ненулевое. Однако у каждой вершины нет ненулевого направления ядра, целиком лежащего на её положительной поддержке.

Почему при нулевой координате среднего обе исходные координаты тоже нулевые?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Kyle Cheung: Basic and basic feasible solutions, Proposition6.1

    Прочитаны предпосылка полного строкового ранга, определение базиса и Proposition6.1 о независимой поддержке. Доказательство крайней точки, четыре столбца собственного примера и полный перебор пар изложены отдельно; примеры курса не переносились.

Инцидентность сети даёт целые вершины многогранника

Рациональная параметризация потоков допускает дробные значения даже при целых запасах. Однако вершины сетевого многогранника остаются целыми. Причина сильнее обратимости одного базиса: каждый квадратный минор ориентированной инцидентности равен нулю, единице или минус единице, что контролирует сразу все возможные базисы.

Перед началом: Базисное допустимое решение и вершина; Определитель и целочисленная обратная при det=±1.

Два противоположных знака в каждом столбце

Ориентированная сеть без петель с целыми балансами и конечными целыми границами потоков; непустое допустимое множество.

У столбца дуги u→v запишем −1 в строке u и +1 в строке v. Остальные элементы нулевые. Рассмотрим любой квадратный минор. Если в нём есть нулевой столбец, определитель нулевой. Если в столбце один ненулевой элемент, раскрытие по нему уменьшает порядок и меняет результат только на знак. Так индукция сводит ответ к минору меньшего размера.

Остаётся случай, когда каждый столбец выбранного квадрата содержит оба ненулевых элемента. Тогда сумма всех его строк нулевая, поэтому квадрат вырожден. Получено доказательство тотальной унимодулярности: все квадратные миноры находятся в {0,1,−1}. Для неориентированной матрицы с двумя плюсами эта аргументация уже не работает; у треугольного графа возникает минор с модулем два.

Активные границы сохраняют целочисленный базис

Баланс записывается Bx=b. Одна строка каждой связной компоненты избыточна; её удаляют перед выбором независимого базиса. В вершине часть координат закреплена нижними или верхними границами. Их значения целые. Перенос закреплённых вкладов в b сохраняет целочисленность правой части, а оставшиеся независимые столбцы образуют квадрат с определителем ±1.

Формула через присоединённую матрицу тогда даёт целые свободные координаты вершины. Если остаются нулевые базисные координаты, вырожденность вершины этому не мешает. При конечных границах непустой многогранник компактен, и линейный критерий достигает минимума на некоторой вершине. Значит существует целый оптимальный поток; это не утверждение, что любой оптимум или любая допустимая точка обязательно целы.

Новая строка может разрушить гарантию

Тотальная унимодулярность относится ко всем минорам, а не только к определителю исходной квадратной матрицы. Обычной унимодулярности одного выбранного базиса мало для утверждения обо всех вершинах. Дополнительное ограничение на совместное использование нескольких дуг может создать минор с модулем больше единицы и дробную вершину.

Целые данные также необходимы: даже единичная матрица с дробной правой частью даёт дробное единственное решение. Если постановка содержит отношения выходов или коэффициенты потерь, её столбцы уже не являются обычной инцидентностью. Перед отказом от целочисленного поиска надо проверить именно структуру записанной модели, а не наличие слова «сеть» в описании.

Циркуляция плюс выбор пути к потребителю

Условие. Дуги в порядке: 1→2,2→3,3→1,3→4,4→5,2→5. Все границы 0≤xᵢ≤3. Балансы вход минус выход: b=(−2,0,0,0,2). Найдите все вершины и минимум стоимости c·x при c=(1,1,0,1,1,4).

  1. Положим t=x₃, q=x₄. Балансы вынуждают x=(2+t,t+q,t,q,q,2−q). Пятая строка автоматически выполнена. Все ограничения эквивалентны 0≤t≤1 и 0≤q≤2; условие t+q≤3 уже следует из них.
  2. Аффинная параметризация взаимно однозначна. Поэтому четыре угла прямоугольника дают ровно четыре вершины: (2,0,0,0,0,2), (2,2,0,2,2,0), (3,1,1,0,0,2), (3,3,1,2,2,0). Все целые.
  3. Стоимость сокращается до 10+2t−q. Минимум равен 8 при t=0,q=2, то есть на потоке (2,2,0,2,2,0). Конечные границы исключают неограниченное улучшение по циркуляции.
  4. Точка t=q=1/2 даёт дробный допустимый поток (5/2,1,1/2,1/2,1/2,3/2). Она не вершина: при малом изменении t в обе стороны ограничения сохраняются. Целочисленность вершин не запрещает такую внутреннюю точку.

Ответ. Четыре перечисленные вершины целые; минимум 8 достигается в (2,2,0,2,2,0), но допустимые дробные потоки существуют.

Проверка. Независимая проверка перебирает квадратные миноры сокращённой инцидентности и все наборы четырёх балансных строк с двумя активными координатными границами. Точное исключение возвращает те же четыре различные вершины и стоимости 10,8,12,10.

Где легко ошибиться. Не подменяйте «все вершины целые» утверждением «все допустимые точки целые». Выпуклая комбинация разных целых потоков обычно имеет дробные координаты.

Проверьте понимание

Какое утверждение верно именно для разобранного ограниченного поточного многогранника?

Вопросы к этой главе

Почему можно удалить пятый баланс?

Каждый столбец полной инцидентности суммируется в ноль, а сумма b также нулевая. Если выполнены первые четыре баланса связной сети, пятый следует из их суммы.

Целевая функция обязана иметь целые коэффициенты?

Для существования целой оптимальной вершины нет: геометрия вершин определяется целыми балансами и границами. Вещественная линейная стоимость тоже достигает оптимума в одной из этих вершин.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Stanford CME307 — Lecture17, directed incidence and total unimodularity

    Ориентированная инцидентность, тотальная унимодулярность и целочисленность сетевой релаксации. Наше доказательство миноров, пятиузловая сеть и полный перечень вершин рассчитаны отдельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться