Математика · объяснение и практика
Знаки перед векторами: как гарантировать короткую сумму
Доказываем существование выбора плюсов и минусов через средний квадрат длины и получаем последовательное построение; различаем квадрат нормы, сумму длин и точный минимум.

В теме Оценки и неравенства: углубление · Учебная карта
Главная мысль
Для любых конечных действительных векторов v₁,…,vₙ одинаковой размерности найдутся знаки εᵢ∈{−1,1}, для которых |Σ εᵢvᵢ|²≤Σ|vᵢ|². Можно выбирать знаки последовательно: из S+v и S−v хотя бы один имеет квадрат длины не больше |S|²+|v|².
Выбираются направления вкладов, а не новые длины
Каждый исходный вектор разрешено оставить либо заменить противоположным. Умножать его на произвольное действительное число нельзя. Задача состоит в выборе общего набора знаков, который ограничит длину результирующей суммы независимо от взаимных направлений исходных векторов. Сумма квадратов их длин заранее известна и не меняется при выборе знаков.
Если все n векторов единичны, правая часть равна n, поэтому можно получить длину не больше корня из n. Для неодинаковых длин используется именно сумма их квадратов. Удвоение одного вектора добавляет в правую часть вчетверо больший вклад этого вектора. Простая сумма длин даёт другую, обычно более грубую оценку по неравенству треугольника и не объясняет выгоду выбора знаков.
Случайные знаки уничтожают смешанные слагаемые в среднем
Выберем каждый знак независимо и симметрично. Раскрывая квадрат нормы суммы через скалярное произведение, получаем сумму |vᵢ|² и удвоенную сумму εᵢεⱼ(vᵢ·vⱼ) по парам разных индексов. Квадрат каждого знака равен единице. Для разных индексов ожидание произведения знаков равно нулю, потому что они независимы и каждый имеет нулевое среднее.
Следовательно, средний квадрат длины результирующей суммы равен сумме квадратов исходных длин. Среди конечного числа наборов знаков существует набор с квадратом длины не выше этого среднего. Мы сначала усредняем квадрат, а потом извлекаем корень из неравенства для найденного набора. Заменять среднее квадрата квадратом среднего вектора нельзя: средний вектор здесь нулевой, но ни один конкретный результат не обязан быть нулём.
Пример
Выберите последовательно знаки для (2;0), (1;3), (−3;1), начиная с плюса у первого вектора. Проверьте общую границу.
После первого шага S=(2;0). Его скалярное произведение со вторым равно 2, берём минус: S=(1;−3), квадрат длины 10. Произведение этой суммы с третьим равно −6, берём плюс: S=(−2;−2), квадрат длины 8. Сумма исходных квадратов равна 4+10+10=24, и 8≤24. Граница для длины есть √24, фактическая длина √8. Мы не объявляем этот результат глобальным минимумом без отдельной проверки остальных наборов.
Последовательный выбор обходится без случайного эксперимента
Пусть S — уже построенная сумма, а v следующий вектор. Тождество |S+v|²+|S−v|²=2|S|²+2|v|² показывает, что меньший из двух квадратов не превосходит их среднего. Выбираем соответствующий знак. Повторяя это действие от нулевой суммы, на каждом шаге сохраняем оценку через сумму уже учтённых квадратов длин и приходим к нужной границе.
В вычислении достаточно знака скалярного произведения S·v: при положительном выгоднее минус, при отрицательном плюс, при нуле оба квадрата одинаковы. Алгоритм гарантирует границу, но не обещает самого короткого из всех возможных итогов. Выбор порядка способен менять результат. Если вектор нулевой, оба знака дают одно положение; делить на его длину для применения метода не требуется.
От чтения к действию
А теперь — вы
Частые вопросы
Почему средний вектор ноль не гарантирует нулевой суммы?
Среднее берётся по разным наборам знаков. Например, один ненулевой вектор имеет два противоположных результата, среднее которых ноль, но каждый результат ненулевой.
Нужны ли единичные векторы?
Нет. Общая правая часть равна сумме квадратов любых исходных длин. Единичность лишь превращает эту сумму в число векторов.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как неравенство Коши ограничивает сумму произведений
Оцените линейную комбинацию по известной сумме квадратов: согласуйте пары коэффициентов и проверьте пропорциональность при равенстве.
Открыть темуПочему математические ожидания складываются даже без независимости
Складываем ожидаемые значения зависимых величин, используем индикаторы для подсчёта событий и отделяем линейность суммы от правил для произведений и дисперсий.
Открыть темуСкалярное произведение: как координаты проверяют угол двух векторов
Считаем скалярное произведение по координатам и связываем знак с углом: различаем острый, прямой и тупой случаи, отдельно проверяем нулевые векторы.
Открыть тему