Przejdź do zawartości

Postać kanoniczna

Z Wikipedii, wolnej encyklopedii

Postać kanoniczna (normalna, standardowa) obiektu matematycznego – w matematyce i informatyce standardowy sposób przedstawiania obiektu jako wyrażenia algebraicznego. W niektórych dziedzinach matematyki mogą zachodzić różnice między pojęciem „kanoniczna” oraz „normalna”. W większości dziedzin postać kanoniczna oznacza unikatową reprezentację każdego obiektu, zaś postać normalna jedynie precyzuje jego formę, bez konieczności bycia postacią unikatową.

Postać kanoniczna liczby naturalnej w zapisie dziesiętnym to skończony ciąg cyfr, który nie zaczyna się od zera.

Bardziej ogólnie, dla klasy obiektów, na której została określona relacja równoważności, postać kanoniczna polega na wyborze konkretnego obiektu w każdej z klas. Na przykład postać Jordana jest postacią kanoniczną podobieństwa macierzy, a macierz schodkowa postacią kanoniczną, gdy uznamy za równoważne macierz oraz wynik iloczynu tej macierzy i pewnej macierzy odwracalnej.

W informatyce, a konkretnie w algebrze komputerowej, istnieje zazwyczaj wiele różnych sposobów na przedstawienie tego samego obiektu. W tym wypadku postać kanoniczna oznacza takie przedstawienie, w którym każdy obiekt ma swoją unikatową reprezentację. W ten sposób można łatwo sprawdzić równość dwóch obiektów poprzez sprawdzenie równości ich postaci kanonicznych. Jednak wybór postaci kanonicznej bardzo często zależy od kwestii czysto arbitralnych (jak kolejność zmiennych), a to może powodować trudności w porównywaniu dwóch obiektów będących wynikami niezależnych obliczeń. Dlatego w algebrze komputerowej postać normalna to słabsze określenie – przedstawienie takie, że zero ma swoją unikatową reprezentację. To pozwala na porównywanie poprzez przedstawienie różnicy między obiektami w postaci normalnej.

Postać (forma) kanoniczna może oznaczać też formę różniczkową, która została przedstawiona naturalnie (kanonicznie).

Proces zamiany obiektu na postać kanoniczną nazywany jest normalizacją[a]

Definicja

[edytuj | edytuj kod]

Załóżmy, że mamy zbiór obiektów z relacją równoważności. Postać kanoniczna jest dana poprzez wyznaczenie niektórych obiektów w do bycia „w postaci kanonicznej” takiej, że każdy obiekt w zbiorze jest równoważny jednemu i tylko jednemu obiektowi w postaci kanonicznej. Innymi słowy, postaci kanoniczne w reprezentują klasy abstrakcji, każda dokładnie jednokrotnie. By sprawdzić, czy dwa obiekty są równe, wystarczy sprawdzić równość ich postaci kanonicznych. W ten sposób postać kanoniczna nie tylko klasyfikuje każdą klasę abstrakcji, ale daje też wyróżnionego (kanonicznego) reprezentanta.

W praktyce warto umieć rozpoznawać postaci kanoniczne. Jest też do rozważenia problem algorytmiczny – jak przejść od danego obiektu należącego do do postaci kanonicznej ? Postaci kanoniczne są zazwyczaj używane, by uczynić operacje na klasach abstrakcji bardziej efektywne. Na przykład w arytmetyce modularnej postacią kanoniczna klasy reszty jest zazwyczaj jej najmniejsza nieujemna liczba całkowita. Operacje na klasach są wykonywane poprzez połączenie tych reprezentantów, a następnie zredukowanie wyniku do jego najmniejszej nieujemnej reszty.

Postać kanoniczna może czasem być po prostu pewną konwencją lub też być określona twierdzeniem. Na przykład wielomiany są najczęściej zapisywane w kolejności malejących potęg. Częstszy jest zapis niż pomimo że obie postaci definiują ten sam wielomian. Zupełnie innym przypadkiem jest postać Jordana będąca określona głębokim twierdzeniem.

Przykłady

[edytuj | edytuj kod]

Uwaga: „z dokładnością do” jakiejś relacji identyczności E oznacza, że postać kanoniczna nie jest unikatowa w ujęciu ogólnym, ale jeśli jeden obiekt ma dwie postaci kanoniczne, są one E-identyczne.

Algebra liniowa

[edytuj | edytuj kod]
Obiekty jest równoważne jeśli: Postać kanoniczna Uwagi
Macierze normalne nad liczbami zespolonymi dla pewnej macierzy unitarnej Macierz diagonalna (z dokładnością do zmiany kolejności) Twierdzenie spektralne
Macierze nad liczbami zespolonymi dla pewnej macierzy unitarnej oraz Macierz diagonalna z rzeczywistymi, dodatnimi elementami (w porządku malejącym) Rozkład według wartości osobliwych
Macierze nad ciałami algebraicznie domkniętymi dla pewnej odwracalnej macierzy Postać Jordana (z dokładnością do zmiany kolejności bloków)
Macierze nad ciałami algebraicznie domkniętymi dla pewnej odwracalnej macierzy Postać kanoniczna Weyra (z dokładnością do zmiany kolejności bloków)
Macierze nad ciałem dla pewnej odwracalnej macierzy Postać kanoniczna Frobeniusa
Macierze nad dziedziną ideałów głównych dla pewnych odwracalnych macierzy i Postać kanoniczna Smitha Równoważność polega na tym samym, co pozwolenie na przemienne podstawowe transformacje rzędów i kolumn
Przestrzenie wektorowe o skończonej ilości wymiarów nad ciałem i są izomorficzne jako przestrzenie wektorowe gdzie jest liczbą naturalną

Logika klasyczna

[edytuj | edytuj kod]

Analiza funkcjonalna

[edytuj | edytuj kod]
Obiekty jest równoważne jeśli: Postać kanoniczna
Przestrzeń Hilberta Jeśli i są obie ośrodkowymi przestrzeniami Hilberta nieskończonego wymiaru, wtedy oraz są izometrycznie izomorficzne. przestrzeniami sekwencyjnymi (z dokładnością do wymiany zbioru indeksów na inny zbiór indeksów o tej samej mocy zbioru)

Teoria liczb

[edytuj | edytuj kod]

Algebra

[edytuj | edytuj kod]
Obiekty jest równoważne jeśli: Postać kanoniczna
Skończenie wygenerowane -moduły, gdzie jest dziedziną ideałów głównych i są izomorficzne jako -moduły Podstawowa dekompozycja (z dokładnością do zmiany kolejności) lub niezmienna rozkładu czynników.

Geometria

[edytuj | edytuj kod]
  • Równanie prostej: gdzie oraz
  • Równanie okręgu:

Istnieją alternatywne formy zapisywania równań. Na przykład równanie prostej można zapisać jako równanie liniowe, mając dany punkt należący do prostej oraz jej nachylenie lub jej współczynnik nachylenia i wyraz wolny.

Notacja matematyczna

[edytuj | edytuj kod]

Postać standardowa jest używana przez wielu matematyków i naukowców w celu zapisywania bardzo dużych liczb w bardziej zwięzły i zrozumiały sposób.

Teoria zbiorów

[edytuj | edytuj kod]

Postać normalna Cantora liczby porządkowej

Teoria gier

[edytuj | edytuj kod]

Systemy przepisywania

[edytuj | edytuj kod]
  • W abstrakcyjnych systemach przepisywania, postać kanoniczna jest nieredukowalnym obiektem.

Rachunek lambda

[edytuj | edytuj kod]
  • Postać normalna Beta, jeśli niemożliwa jest redukcja beta; Rachunek lambda jest szczególnym przypadkiem abstrakcyjnego systemu przepisywania.

Formy różniczkowe

[edytuj | edytuj kod]

Do kanonicznych form różniczkowych zaliczamy formę Liouville’a, ważną w badaniu mechaniki Hamiltona i rozmaitości symplektycznych.

Informatyka

[edytuj | edytuj kod]

W informatyce, przekształcanie danych do postaci kanonicznej jest potocznie nazywane normalizacją danych.

Na przykład normalizacja bazy danych jest procesem organizowania pól i tabel relacyjnej bazy danych, aby zminimalizować redundancję danych. W dziedzinie bezpieczeństwa oprogramowania oprogramowanie często podatne jest na niewłaściwe dane wejściowe. Odpowiedzią na ten problem jest poprawna ratyfikacja danych wejściowych. Zanim można ją przeprowadzić, dane wejściowe muszą zostać znormalizowane – odszyfrowane i zredukowane do ciągu znaków.

Inne typy danych, często kojarzone z przetwarzaniem sygnałów (w tym audio lub obrazów) lub uczeniem maszynowym, mogą być znormalizowane w celu podania skończonego zakresu wartości.

Zobacz też

[edytuj | edytuj kod]
  1. Czasem używa się też pojęcia „kanonizacja”.

Bibliografia

[edytuj | edytuj kod]
  • Georgi E. Shilov: Linear Algebra. Dover, 1977. ISBN 0-486-63518-X.
  • Vagn Lundsgaard Hansen: Functional Analysis: Entering Hilbert Space. World Scientific Publishing, 2006. ISBN 981-256-563-9.