Инвариант (математика) - Invariant (mathematics)

Обои является инвариантным под бесконечным числом  переводов , члены группы , из которых операция , обозначенном является функцией композиции .${\ displaystyle \ circ}$

В математике , инвариантный является свойством математического объекта (или класса математических объектов) , который остается неизменным после операции или преобразования определенного типа применяется к объектам. Конкретный класс объектов и тип преобразований обычно указываются контекстом, в котором используется этот термин. Например, площадь из треугольника является инвариантной относительно изометрии в евклидовой плоскости . Используются оба выражения «инвариантный относительно» и «инвариантный» к преобразованию. В более общем смысле, инвариант относительно отношения эквивалентности - это свойство, которое является постоянным для каждого класса эквивалентности .

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

Примеры

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

Идентичность является уравнением , которое остается верным для всех значений переменных. Существуют также неравенства, которые остаются верными при изменении значений их переменных.

Расстояние между двумя точками на числовой прямой не изменяется при добавлении такого же количества на оба номера. С другой стороны, умножение не обладает этим же свойством, поскольку расстояние не инвариантно относительно умножения.

Углы и отношения расстояний инвариантны относительно масштабирования , вращения , сдвигов и отражений . Эти преобразования производят похожие формы, что является основой тригонометрии . Напротив, углы и соотношения не являются инвариантными при неравномерном масштабировании (например, при растяжении). Сумма внутренних углов треугольника (180 °) инвариантна при всех перечисленных выше операциях. В качестве другого примера, все круги похожи: они могут быть преобразованы друг в друга, а отношение длины окружности к диаметру остается неизменным (обозначается греческой буквой π ( пи )).

Еще несколько сложных примеров:

• Действительная часть и абсолютное значение из комплексного числа инвариантны относительно комплексного сопряжения .
• Степени из полинома инвариантны относительно линейной замены переменных.
• В размерности и группа гомологии топологического объекта инвариантна относительно гомеоморфизма .
• Число неподвижных точек одного динамической системы инвариантно относительно многих математических операций.
• Евклидово расстояние инвариантно относительно ортогональных преобразований .
• Евклидова область инвариантна относительно линейных отображений с определителем ± 1 (см. Эквиареалистическое отображение § Линейные преобразования ).
• Некоторые инварианты проективных преобразований включают коллинеарность трех или более точек, параллелизм трех или более линий, конические сечения , перекрестное отношение .
• В определитель , след , и собственные векторы и собственные значения матрицы А квадратной матрицы инвариантны относительно изменений базиса . Другими словами, спектр матрицы инвариантен к смене базиса.
• Главные инварианты тензоров не меняются при повороте системы координат (см. Инварианты тензоров ).
• В особых значениях из в матрице инвариантны относительно ортогональных преобразований.
• Мера Лебега инвариантна относительно сдвигов.
• Дисперсия из распределения вероятностей инвариантна относительно сдвигов вещественной прямой ; следовательно, дисперсия случайной величины не изменится после добавления константы.
• В фиксированных точках из преобразования являются элементами в домене , которые инвариантны относительно преобразования. В зависимости от приложения они могут называться симметричными по отношению к этому преобразованию. Например, объекты с трансляционной симметрией инвариантны при определенных перемещениях.
• Интеграл от гауссовой кривизны двумерного риманова многообразия инвариантен относительно изменений римановой метрики . Это теорема Гаусса – Бонне .${\ textstyle \ int _ {M} K \, d \ mu}$${\ displaystyle K}$ ${\ displaystyle (M, g)}$ ${\ displaystyle g}$
• Дифференциальные инварианты для дифференциальных уравнений

MU головоломка

Головоломки MU является хорошим примером логической задачи , где определение инварианта использования для невозможности доказательства . Головоломка просит начать со слова MI и преобразовать его в слово MU, используя на каждом этапе одно из следующих правил преобразования:

1. Если строка заканчивается на I, можно добавить U ( x I → x IU)
2. Строка после M может быть полностью продублирована (M x → M xx )
3. Любые три последовательных I (III) могут быть заменены одним U ( x III y → x U y )
4. Любые два последовательных U могут быть удалены ( x UU y → xy )

Пример вывода (с надстрочными индексами, указывающими применяемые правила):

MI → ² MII → ² MIIII → ³ MUI → ² MUIUI → ¹ MUIUIU → ² MUIUIUUIUIU → ⁴ MUIUIIUIU → ...

В свете этого можно задаться вопросом, возможно ли преобразовать MI в MU, используя только эти четыре правила преобразования. На применение этих правил преобразования к строкам можно потратить много часов. Однако было бы быстрее найти свойство , которое инвариантно ко всем правилам (то есть не изменяется ни одним из них) и демонстрирует, что добраться до MU невозможно. Рассматривая загадку с логической точки зрения, можно понять, что единственный способ избавиться от любых «я» - это иметь в строке три последовательных «я». Это делает интересным следующий инвариант:

Количество I в строке не кратно 3 .

Это инвариант проблемы, если для каждого из правил преобразования выполняется следующее: если инвариант сохранялся до применения правила, он будет сохраняться и после его применения. Глядя на чистый эффект применения правил к количеству I и U, можно увидеть, что это действительно так для всех правил:

Правило	#Является	#Нас	Влияние на инвариант
1	+0	+1	Количество "I" не изменилось. Если инвариант соблюдался, он все еще остается в силе.
2	× 2	× 2	Если n не делится на 3, то 2 × n тоже не делится. Инвариант остается в силе.
3	−3	+1	Если n не делится на 3, n −3 тоже не делится. Инвариант остается в силе.
4	+0	−2	Количество "I" не изменилось. Если инвариант соблюдался, он все еще остается в силе.

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

Учитывая, что в исходной строке MI есть одно I, которое не кратно трем, можно сделать вывод, что перейти от MI к MU невозможно (поскольку число I никогда не будет кратно трем). ).

Инвариантный набор

Подмножество S домена U из отображения T : U → U является инвариантным множеством при отображении , когда Обратите внимание , что элементы из S не фиксируются , даже если множество S фиксируется в наборе мощности из U . (Некоторые авторы используют терминологию множественный инвариант или поточечный инвариант, чтобы различать эти случаи.) Например, окружность - это инвариантное подмножество плоскости при вращении вокруг центра окружности. Далее, коническая поверхность инвариантна как множество относительно гомотетии пространства. ${\ displaystyle x \ in S \ подразумевает T (x) \ in S.}$

Инвариантное множество операции Т также считается стабильным при T . Например, нормальные подгруппы , которые так важны в теории групп, - это те подгруппы , которые стабильны относительно внутренних автоморфизмов объемлющей группы . В линейной алгебры , если линейное преобразование Т имеет собственный вектор V , то линия , проходящая через 0 и v является инвариантным множеством при Т , и в этом случае собственные векторы охватывают собой инвариантное подпространство , которое стабильно при Т .

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

Официальное заявление

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

Без изменений при групповом действии

Во-первых, если у кого-то есть группа G, действующая на математический объект (или набор объектов) X, то можно спросить, какие точки x остаются неизменными, «инвариантными» относительно действия группы или под элементом g группы.

Часто у кого-то будет группа, действующая на множестве X , что оставляет возможность определять, какие объекты в ассоциированном множестве F ( X ) являются инвариантными. Например, вращение в плоскости вокруг точки оставляет точку, относительно которой он вращается, неизменной, в то время как перемещение в плоскости не оставляет неизменными никакие точки, но оставляет все прямые, параллельные направлению перемещения, неизменными как линии. Формально определим множество прямых на плоскости P как L ( P ); тогда жесткое движение плоскости превращает линии в линии - группа жестких движений действует на множество линий - и можно спросить, какие линии не изменяются действием.

Что еще более важно, можно определить функцию на множестве, такую ​​как «радиус круга на плоскости», а затем спросить, инвариантна ли эта функция относительно группового действия, такого как жесткие движения.

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

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

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

Независимо от презентации

Во-вторых, функция может быть определена в терминах некоторого представления или декомпозиции математического объекта; например, эйлерова характеристика из клеточного комплекса определяется как сумма переменного числа клеток в каждом измерении. Можно забыть сложную ячеистую структуру , и смотреть только на подстилающем топологическом пространстве ( многообразия ) - как различные клеточные комплексы дают один и тот же основной коллектор, один может спросить , если эта функция не зависит от выбора представления, в этом случае она является внутренне определенный инвариант. Так обстоит дело с характеристикой Эйлера, и общий метод определения и вычисления инвариантов состоит в том, чтобы определить их для данного представления, а затем показать, что они не зависят от выбора представления. Обратите внимание, что в этом смысле нет понятия группового действия.

Наиболее распространенные примеры:

• Представление многообразия в терминах координат диаграммы - инварианты должны быть неизменными при изменении координат .
• Различные разложения многообразий , как обсуждалось для эйлеровой характеристики.
• Инварианты представления группы .

Без изменений при возмущении

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

Инварианты в информатике

В информатике можно встретить инварианты, на истинность которых можно положиться во время выполнения программы или в течение некоторой ее части. Это логическое утверждение , которое всегда остается верным на определенном этапе выполнения. Например, инвариант цикла - это условие, которое выполняется в начале и в конце каждого выполнения цикла.

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

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

Автоматическое обнаружение инвариантов в императивных программах

Инструменты абстрактной интерпретации могут вычислять простые инварианты данных императивных компьютерных программ. Тип свойств, которые можно найти, зависит от используемых абстрактных доменов . Типичными примерами свойств являются диапазоны отдельных целочисленных переменных, например 0<=x<1024отношения между несколькими переменными 0<=i-j<2*n-1, и информация о модуле, например y%4==0. В прототипах академических исследований также учитываются простые свойства структур указателей.

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

В контексте приведенного выше примера головоломки MU в настоящее время не существует общего автоматизированного инструмента, который мог бы обнаружить, что переход от MI к MU невозможен, используя только правила 1–4. Однако, как только абстракция от строки до числа ее «я» была сделана вручную, что привело, например, к следующей программе на C, инструмент абстрактной интерпретации сможет обнаружить, что ICount%3не может быть 0, и, следовательно, цикл while никогда не завершится.

void MUPuzzle(void) {
    volatile int RandomRule;
    int ICount = 1, UCount = 0;
    while (ICount % 3 != 0)                         // non-terminating loop
        switch(RandomRule) {
        case 1:                  UCount += 1;   break;
        case 2:   ICount *= 2;   UCount *= 2;   break;
        case 3:   ICount -= 3;   UCount += 1;   break;
        case 4:                  UCount -= 2;   break;
        }                                          // computed invariant: ICount % 3 == 1 || ICount % 3 == 2
}

Смотрите также

Заметки

Рекомендации

Внешние ссылки

• «Апплет: визуальные инварианты в алгоритмах сортировки» Уильяма Брайнена, 1997 г.