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

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Апрель 2015 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

Примеры [ править ]

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

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

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

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

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

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

MU Puzzle [ править ]

MU - головоломка ^[8] является хорошим примером логической задачи , где определение инварианта использования для невозможности доказательства . Головоломка просит начать со слова 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 . (Некоторые авторы используют терминологию множественный инвариант ^[9] и поточечный инвариант ^[10], чтобы различать эти случаи.) Например, окружность является инвариантным подмножеством плоскости при вращении.${\displaystyle x\in S\Rightarrow T(x)\in S.}$о центре круга. Далее, коническая поверхность инвариантна как множество относительно гомотетии пространства.

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

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

Официальное заявление [ править ]

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

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

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

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

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

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

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

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

Независимо от представления [ править ]

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

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

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

Без изменений при возмущении [ править ]

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

Инварианты в информатике [ править ]

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

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

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

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

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

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

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

void  MUPuzzle ( void )  {  volatile  int  RandomRule ;  int  ICount  =  1 ,  UCount  =  0 ;  while  ( ICount  %  3  ! =  0 )  //  переключение без завершения цикла ( RandomRule )  {  case  1 :  UCount  + =  1 ;  перерыв ;  случай  2 :  ICount  * =  2 ;  UCount  * =  2 ; перерыв ;  случай  3 :  ICount  - =  3 ;  UCount  + =  1 ;  перерыв ;  случай  4 :  UCount  - =  2 ;  перерыв ;  }  // вычисляемый инвариант: ICount% 3 == 1 || ICount% 3 == 2 }

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

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