Niezmienny (matematyka) - Invariant (mathematics)
W matematyce An niezmienna jest właściwością obiektu matematycznego (lub klasy obiektów matematycznych), która pozostaje niezmieniona po operacji lub transformacje określonego typu są stosowane do przedmiotów. Na konkretną klasę obiektów i rodzaj przekształceń wskazuje zwykle kontekst, w którym termin jest używany. Na przykład, obszar z trójkąta jest niezmienny w odniesieniu do izometrycznych w euklidesowej płaszczyźnie . Używane są wyrażenia „niezmienny pod” i „niezmienny względem” transformacji. Mówiąc bardziej ogólnie, niezmiennik w odniesieniu do relacji równoważności to właściwość, która jest stała dla każdej klasy równoważności .
Niezmienniki są używane w różnych dziedzinach matematyki, takich jak geometria , topologia , algebra i matematyka dyskretna . Niektóre ważne klasy przekształceń są definiowane przez niezmiennik, który pozostawiają bez zmian. Na przykład mapy konforemne są definiowane jako przekształcenia płaszczyzny, które zachowują kąty . Odkrycie niezmienników jest ważnym krokiem w procesie klasyfikacji obiektów matematycznych.
Przykłady
Prosty przykład niezmienności wyraża się w naszej zdolności do liczenia . Dla skończonego zbioru obiektów dowolnego rodzaju istnieje liczba, do której zawsze dochodzimy, niezależnie od kolejności, w jakiej liczymy obiekty w zbiorze . Ilość – liczba kardynalna – jest powiązana ze zbiorem i jest niezmienna w procesie liczenia.
Tożsamość jest równanie, które pozostaje prawdziwe dla wszystkich wartości jego zmiennych. Istnieją również nierówności, które pozostają prawdziwe, gdy zmieniają się wartości ich zmiennych.
Odległość między dwoma punktami na osi liczbowej nie ulega zmianie przez dodanie takiej samej ilości do obu numerów. Z drugiej strony mnożenie nie ma tej samej własności, ponieważ odległość nie jest niezmienna przy mnożeniu.
Kąty i stosunki odległości są niezmienne przy skalowaniach , obrotach , translacjach i odbiciach . Te przekształcenia dają podobne kształty, co jest podstawą trygonometrii . W przeciwieństwie do tego kąty i stosunki nie są niezmienne w przypadku skalowania niejednorodnego (takiego jak rozciąganie). Suma kątów wewnętrznych trójkąta (180°) jest niezmienna we wszystkich powyższych operacjach. Jako inny przykład, wszystkie koła są podobne: można je przekształcić w siebie, a stosunek obwodu do średnicy jest niezmienny (oznaczony grecką literą π ( pi )).
Kilka bardziej skomplikowanych przykładów:
- Część rzeczywista i wartość bezwzględna liczby zespolonej są niezmienne przy sprzężeniu zespolonym .
- Stopni z wielomianem jest niezmienny pod liniowej zmiany zmiennych.
- Na wymiar i grupy homologii topologicznej obiektu są niezmienne pod homeomorfizmu .
- Liczba stałych punktów danego układu dynamicznego jest niezmienny pod wielu operacji matematycznych.
- Odległość euklidesowa jest niezmienna w przekształceniach ortogonalnych .
- Obszar euklidesowy jest niezmienny pod mapami liniowymi, które mają wyznacznik ±1 (patrz mapa ekwiaryczna § Przekształcenia liniowe ).
- Niektóre niezmienniki przekształceń rzutowych obejmują kolinearność trzech lub więcej punktów, współbieżność trzech lub więcej linii, przekroje stożkowe , współczynnik krzyżowy .
- W determinant , śledzenia i wektory i wartości własnych o kwadratowej macierzy jest niezmienny podczas zmiany podstawy . Innymi słowy, widmo macierzy jest niezmienne względem zmiany bazy.
- Główne niezmienniki tensorów nie zmieniają się wraz z obrotem układu współrzędnych (patrz Niezmienniki tensorów ).
- Te pojedyncze wartości o matrycy jest niezmienna przy prostopadłych transformacji.
- Miara Lebesgue'a jest niezmienna w tłumaczeniach.
- Wariancji z rozkładu prawdopodobieństwa jest niezmienny pod tłumaczeń prostej rzeczywistej ; stąd wariancja zmiennej losowej pozostaje niezmieniona po dodaniu stałej.
- Na stałe punkty przekształcenia są elementy w domenie , które są niezmienne w ramach transformacji. W zależności od zastosowania można je nazwać symetrycznymi w stosunku do tej transformacji. Na przykład obiekty z symetrią translacyjną są niezmienne w niektórych tłumaczeniach.
- Całka z krzywizny Gaussa dwuwymiarowej rozmaitości riemannowskiej jest niezmienna przy zmianach metryki riemannowskiej . To jest twierdzenie Gaussa-Bonneta .
- Niezmienniki różniczkowe dla równań różniczkowych
MU puzzle
MU puzzle jest dobrym przykładem logicznego problemu gdzie ustalania niezmiennik jest użytkowania na dowód niemożności . Zagadka prosi o rozpoczęcie od słowa MI i przekształcenie go w słowo MU, używając w każdym kroku jednej z następujących reguł transformacji:
- Jeśli ciąg kończy się na I, można dodać U ( x I → x IU)
- Ciąg po M może być całkowicie zduplikowany (M x → M xx )
- Dowolne trzy kolejne I (III) można zastąpić jednym U ( x III y → x U y )
- Można usunąć dowolne dwie kolejne litery U ( x UU y → xy )
Przykładowe wyprowadzenie (z indeksami górnymi wskazującymi zastosowane reguły) to:
- MI → 2 MII → 2 MIIII → 3 MUI → 2 MUIUI → 1 MUIUIU → 2 MUIUIUUIUIU → 4 MUIUIIUIU → ...
W związku z tym można się zastanawiać, czy możliwe jest przekształcenie MI w MU, używając tylko tych czterech reguł transformacji. Można by spędzić wiele godzin stosując te reguły transformacji do łańcuchów. Jednak szybciej może być znalezienie właściwości, która jest niezmienna w stosunku do wszystkich reguł (tj. nie jest zmieniana przez żadną z nich) i pokazuje, że dostanie się do MU jest niemożliwe. Patrząc na łamigłówkę z logicznego punktu widzenia, można zdać sobie sprawę, że jedynym sposobem na pozbycie się jakiegokolwiek „ja” jest posiadanie trzech kolejnych „ja” w łańcuchu. To sprawia, że następujący niezmiennik jest interesujący do rozważenia:
- Liczba I w ciągu nie jest wielokrotnością 3 .
Jest to niezmiennik problemu, jeśli dla każdej z reguł transformacji obowiązuje następująca zasada: jeśli niezmiennik zachował się przed zastosowaniem reguły, będzie również obowiązywał po jej zastosowaniu. Patrząc na efekt netto zastosowania reguł na liczbę I i U, można zauważyć, że tak naprawdę jest w przypadku wszystkich reguł:
Reguła #Jest #Nas Wpływ na niezmiennik 1 +0 +1 Liczba I pozostaje bez zmian. Jeśli niezmiennik się utrzyma, to nadal. 2 ×2 ×2 Jeśli n nie jest wielokrotnością 3, to 2× n też nie jest. Niezmiennik nadal obowiązuje. 3 -3 +1 Jeśli n nie jest wielokrotnością 3, n- 3 też nie jest. Niezmiennik nadal obowiązuje. 4 +0 -2 Liczba I pozostaje bez zmian. Jeśli niezmiennik się utrzyma, to nadal.
Powyższa tabela pokazuje wyraźnie, że niezmiennik obowiązuje dla każdej z możliwych reguł transformacji, co oznacza, że którakolwiek reguła zostanie wybrana, w jakimkolwiek stanie, jeśli liczba I nie była wielokrotnością trzech przed zastosowaniem reguły, to nie być później.
Biorąc pod uwagę, że w początkowym ciągu MI występuje jedno ja i takie, które nie jest wielokrotnością trzech, można wnioskować, że przejście z MI do MU jest niemożliwe (ponieważ liczba ja nigdy nie będzie wielokrotnością trzech ).
Niezmienny zestaw
Podzbiór S domeny U z odwzorowaniem T : U → U jest niezmienna zestaw pod odwzorowywania Należy zauważyć, że elementy z S nie są stałe , mimo że zbiór S jest zamocowany w zestawie zasilania z U . (Niektórzy autorzy używają terminologii niezmienniczość setwise, vs. niezmiennik punktowy, aby odróżnić te przypadki.) Na przykład okrąg jest niezmiennym podzbiorem płaszczyzny pod obrotem wokół środka okręgu. Ponadto, powierzchnia stożkowa jest niezmienny w zestawie pod jednokładności przestrzeni.
O niezmiennym zbiorze operacji T mówi się również, że jest stabilny pod T . Na przykład, normalne podgrupy, które są tak ważne w teorii grup, to te podgrupy, które są stabilne pod wewnętrznymi automorfizmami grupy otoczenia . W algebrze liniowej , jeśli transformacja liniowa T ma wektor własny v , to prosta przechodząca przez 0 i v jest zbiorem niezmienników pod T , w którym to przypadku wektory własne obejmują podprzestrzeń niezmienniczą , która jest stabilna pod T .
Gdy T jest przemieszczenie śruba The oś śruba jest niezmienna linia, choć jeśli murawa jest niezerowe, T nie ma stałego punktów.
Formalne oświadczenie
Pojęcie niezmienności jest sformalizowane w matematyce na trzy różne sposoby: poprzez działania grupowe , prezentacje i deformację.
Bez zmian w ramach działania grupowego
Po pierwsze, jeśli mamy grupę G działającą na obiekt matematyczny (lub zbiór obiektów) X, to możemy zapytać, które punkty x są niezmienne, „niezmiennicze” pod działaniem grupy, czy pod elementem g grupy.
Często mamy grupę działającą na zbiorze X , co pozostawia jedną osobę do określenia, które obiekty w skojarzonym zbiorze F ( X ) są niezmienne. Na przykład obrót w płaszczyźnie wokół punktu pozostawia punkt, wokół którego obraca się on niezmiennikiem, podczas gdy translacja w płaszczyźnie nie pozostawia niezmiennych żadnych punktów, ale wszystkie linie równoległe do kierunku ruchu translacji pozostawia jako linie. Formalnie zdefiniuj zbiór linii w płaszczyźnie P jako L ( P ); wtedy ruch sztywny płaszczyzny przenosi linie na linie – grupa ruchów sztywnych oddziałuje na zbiór linii – i można zapytać, które linie pozostają niezmienione działaniem.
Co ważniejsze, można zdefiniować funkcję na zbiorze, np. „promień okręgu na płaszczyźnie”, a następnie zapytać, czy ta funkcja jest niezmienna w działaniu grupowym, takim jak ruchy sztywne.
Podwójne do pojęcia niezmienników są koinwarianty , znane również jako orbity, które formalizują pojęcie kongruencji : obiekty, które mogą być sprowadzone do siebie poprzez działanie grupowe. Na przykład w grupie sztywnych ruchów płaszczyzny obwód trójkąta jest niezmiennikiem, a zbiór trójkątów przystających do danego trójkąta jest niezmiennikiem.
Są one połączone w następujący sposób: niezmienniki są stałe na koinwariantach (na przykład przystające trójkąty mają ten sam obwód), podczas gdy dwa obiekty, które zgadzają się co do wartości jednego niezmiennika, mogą być przystające lub nie (na przykład dwa trójkąty o tym samym obwodzie nie muszą być zgodne). W problemach klasyfikacyjnych można dążyć do znalezienia pełnego zbioru niezmienników , takiego, że jeśli dwa obiekty mają te same wartości dla tego zbioru niezmienników, to są one przystające.
Na przykład trójkąty takie, że wszystkie trzy boki są równe, są przystające pod sztywnymi ruchami, poprzez kongruencję SSS , a zatem długości wszystkich trzech boków tworzą kompletny zestaw niezmienników dla trójkątów. Trzy miary kąta trójkąta są również niezmienne w przypadku sztywnych ruchów, ale nie tworzą pełnego zestawu, ponieważ nieprzystające trójkąty mogą mieć te same miary kąta. Jeśli jednak dopuścimy skalowanie oprócz ruchów sztywnych, to kryterium podobieństwa AAA pokazuje, że jest to kompletny zestaw niezmienników.
Niezależnie od prezentacji
Po drugie, funkcję można zdefiniować w kategoriach jakiejś prezentacji lub rozkładu obiektu matematycznego; Na przykład, cecha Eulera z kompleksu komórki jest określona jako suma zmiennego liczby komórek w każdym wymiarze. Można zapomnieć o strukturze kompleksu komórkowego i patrzeć tylko na leżącą u podłoża przestrzeń topologiczną ( rozmaitość ) – ponieważ różne kompleksy komórkowe dają tę samą podstawową rozmaitość, można zapytać, czy funkcja jest niezależna od wyboru prezentacji, w tym przypadku jest to samoistnie zdefiniowany niezmiennik. Tak jest w przypadku charakterystyki Eulera, a ogólną metodą definiowania i obliczania niezmienników jest zdefiniowanie ich dla danej prezentacji, a następnie wykazanie, że są one niezależne od wyboru prezentacji. Zauważ, że w tym sensie nie ma pojęcia o działaniu grupowym.
Najczęstsze przykłady to:
- Prezentacja kolektora pod względem współrzędnych wykresy - niezmienniki muszą być niezmienione pod zmianą współrzędnych .
- Różne rozkłady wielorakie , jak omówiono dla charakterystyki Eulera.
- Niezmienniki prezentacji grupy .
Niezmieniony pod perturbacją
Po trzecie, jeśli badamy obiekt, który różni się w rodzinie, co jest powszechne w geometrii algebraicznej i geometrii różniczkowej , można zapytać, czy właściwość jest niezmieniona w przypadku zaburzeń (na przykład, czy obiekt jest stały w rodzinach lub niezmienny w przypadku zmiany metryczny).
Niezmienniki w informatyce
W informatyce można napotkać niezmienniki, na których można polegać podczas wykonywania programu lub podczas jego części. Jest to logiczne twierdzenie, które zawsze uważa się za prawdziwe podczas pewnej fazy egzekucji. Na przykład niezmiennik pętli to warunek, który jest spełniony na początku i na końcu każdego wykonania pętli.
Niezmienniki są szczególnie przydatne przy wnioskowaniu, czy program komputerowy jest poprawny. Teoria optymalizacji kompilatorów , metodologia projektowania na podstawie umowy oraz formalne metody określania poprawności programu , wszystkie w dużym stopniu opierają się na niezmiennikach.
Programiści często używają asercji w swoim kodzie, aby wyraźnie określić niezmienniki. Niektóre języki programowania obiektowego mają specjalną składnię do określania niezmienników klas .
Automatyczne wykrywanie niezmienników w programach imperatywnych
Narzędzia interpretacji abstrakcyjnej mogą obliczać proste niezmienniki danych imperatywnych programów komputerowych. Rodzaj właściwości, które można znaleźć, zależy od użytych domen abstrakcyjnych . Typowymi przykładowymi właściwościami są zakresy pojedynczych zmiennych całkowitych, takie jak 0<=x<1024
, relacje między kilkoma zmiennymi, takie jak 0<=i-j<2*n-1
, oraz informacje o module, takie jak y%4==0
. Prototypy badań akademickich uwzględniają również proste właściwości struktur wskaźnikowych.
Bardziej wyrafinowane niezmienniki zazwyczaj muszą być wprowadzane ręcznie. W szczególności podczas weryfikowania programu imperatywnego za pomocą rachunku Hoare'a niezmiennik pętli musi być wprowadzony ręcznie dla każdej pętli w programie, co jest jednym z powodów, dla których takie podejście jest ogólnie niepraktyczne w przypadku większości programów.
W kontekście powyższego przykładu łamigłówki MU , obecnie nie ma ogólnego zautomatyzowanego narzędzia, które mogłoby wykryć, że wyprowadzenie z MI na MU jest niemożliwe przy użyciu tylko reguł 1–4. Jednak po ręcznej abstrakcji od łańcucha do liczby jego „I”, co prowadzi na przykład do następującego programu w C, narzędzie do interpretacji abstrakcyjnej będzie w stanie wykryć, że ICount%3
nie może być 0, i stąd pętla "while" nigdy się nie kończy.
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
}
Zobacz też
Uwagi
Bibliografia
- Fraleigh, John B. (1976), Pierwszy kurs algebry abstrakcyjnej (2nd ed.), Czytanie: Addison-Wesley , ISBN 0-201-01984-1
- Herstein, IN (1964), Tematy z algebry , Waltham: Blaisdell Publishing Company , ISBN 978-1114541016
- Kay, David C. (1969), College Geometry , New York: Holt, Rinehart i Winston , LCCN 69-12075
- McCoy, Neal H. (1968), Wprowadzenie do współczesnej algebry, wydanie poprawione , Boston: Allyn and Bacon , LCCN 68-15225
- JD Fokker, H. Zantema , SD Swierstra (1991). "Iteratie en invariatie", Programren en Correctheid. Usługa akademicka. ISBN 90-6233-681-7 .
- Weisstein, Eric W. „Niezmienny” . MatematykaŚwiat .
- Popov, VL (2001) [1994], "Niezmienny" , Encyklopedia Matematyki , EMS Press
Linki zewnętrzne
- „Applet: Visual Invariants in Sorting Algorithms” Williama Braynena w 1997 r.