Postać kanoniczna

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

Załóżmy, że mamy zbiór ${\displaystyle S}$ obiektów z relacją równoważności. Postać kanoniczna jest dana poprzez wyznaczenie niektórych obiektów w ${\displaystyle S}$ 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 ${\displaystyle S}$ 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 ${\displaystyle s}$ należącego do ${\displaystyle S}$ do postaci kanonicznej ${\displaystyle s}$? 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 ${\displaystyle x^{2}+x+30}$ niż ${\displaystyle x+30+x^{2},}$ 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

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

Obiekty	${\displaystyle A}$ jest równoważne ${\displaystyle B,}$ jeśli:	Postać kanoniczna	Uwagi
Macierze normalne nad liczbami zespolonymi	${\displaystyle A=U^{*}BU}$ dla pewnej macierzy unitarnej ${\displaystyle U}$	Macierz diagonalna (z dokładnością do zmiany kolejności)	Twierdzenie spektralne
Macierze nad liczbami zespolonymi	${\displaystyle A=UBV^{*}}$ dla pewnej macierzy unitarnej ${\displaystyle U}$ oraz ${\displaystyle V}$	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	${\displaystyle A=P^{-1}BP}$ dla pewnej odwracalnej macierzy ${\displaystyle P}$	Postać Jordana (z dokładnością do zmiany kolejności bloków)
Macierze nad ciałami algebraicznie domkniętymi	${\displaystyle A=P^{-1}BP}$ dla pewnej odwracalnej macierzy ${\displaystyle P}$	Postać kanoniczna Weyra (z dokładnością do zmiany kolejności bloków)
Macierze nad ciałem	${\displaystyle A=P^{-1}BP}$ dla pewnej odwracalnej macierzy ${\displaystyle P}$	Postać kanoniczna Frobeniusa
Macierze nad dziedziną ideałów głównych	${\displaystyle A=P^{-1}BQ}$ dla pewnych odwracalnych macierzy ${\displaystyle P}$ i ${\displaystyle Q}$	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 ${\displaystyle K}$	${\displaystyle A}$ i ${\displaystyle B}$ są izomorficzne jako przestrzenie wektorowe	${\displaystyle K^{n},}$ gdzie ${\displaystyle n}$ jest liczbą naturalną

Logika klasyczna

• dysjunkcyjna postać normalna
• forma preneksowa
• koniunkcyjna postać normalna
• skolemizacja

Analiza funkcjonalna

Obiekty	${\displaystyle A}$ jest równoważne ${\displaystyle B,}$ jeśli:	Postać kanoniczna
Przestrzeń Hilberta	Jeśli ${\displaystyle A}$ i ${\displaystyle B}$ są obie ośrodkowymi przestrzeniami Hilberta nieskończonego wymiaru, wtedy ${\displaystyle A}$ oraz ${\displaystyle B}$ są izometrycznie izomorficzne.	${\displaystyle \ell ^{2}(I)}$ są przestrzeniami sekwencyjnymi (z dokładnością do wymiany zbioru indeksów ${\displaystyle I}$ na inny zbiór indeksów o tej samej mocy zbioru)

Teoria liczb

• Postać kanoniczna liczb naturalnych
• Postać kanoniczna ułamka łańcuchowego

Algebra

Obiekty	${\displaystyle A}$ jest równoważne ${\displaystyle B,}$ jeśli:	Postać kanoniczna
Skończenie wygenerowane ${\displaystyle R}$-moduły, gdzie ${\displaystyle R}$ jest dziedziną ideałów głównych	${\displaystyle A}$ i ${\displaystyle B}$ są izomorficzne jako ${\displaystyle R}$-moduły	Podstawowa dekompozycja (z dokładnością do zmiany kolejności) lub niezmienna rozkładu czynników.

Geometria

• Równanie prostej: ${\displaystyle Ax+By=C,}$ gdzie ${\displaystyle A^{2}+B^{2}=1}$ oraz ${\displaystyle C\geqslant 0.}$

• Równanie okręgu: ${\displaystyle (x-h)^{2}+(y-k)^{2}=r^{2}.}$

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

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

Postać normalna Cantora liczby porządkowej

Teoria gier

• Gra w postaci normalnej

Systemy przepisywania

• W abstrakcyjnych systemach przepisywania, postać kanoniczna jest nieredukowalnym obiektem.

Rachunek lambda

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

Formy różniczkowe

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

Informatyka

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ż

• baza kanoniczna
• normalizacja

Uwagi

1. Czasem używa się też pojęcia „kanonizacja”.

Bibliografia

• Georgi E. Shilov: Linear Algebra. Dover, 1977. ISBN 0-486-63518-X. Brak numerów stron w książce
• Vagn Lundsgaard Hansen: Functional Analysis: Entering Hilbert Space. World Scientific Publishing, 2006. ISBN 981-256-563-9. Brak numerów stron w książce