Ortogonální pole - Orthogonal array

V matematice, an ortogonální pole je „tabulka“ (pole), jejíž záznamy pocházejí z pevné konečné sady symbolů (obvykle {1,2, ...,n}), uspořádané tak, aby existovalo celé číslo t takže pro každý výběr t sloupce tabulky, vše seřazeno t-n-tice symbolů, vytvořených převzetím položek v každém řádku omezených na tyto sloupce, se objeví stejný počet opakování. Číslo t se nazývá síla ortogonálního pole. Zde je jednoduchý příklad ortogonálního pole se sadou symbolů {1,2} a silou 2:

1	1	1
2	2	1
1	2	2
2	1	2

Všimněte si, že čtyři objednané páry (2-n-tice) tvořené řádky omezenými na první a třetí sloupec, konkrétně (1,1), (2,1), (1,2) a (2,2) jsou všechny možné uspořádané páry těchto dvou sada prvků a každý se objeví přesně jednou. Druhý a třetí sloupec by poskytl, (1,1), (2,1), (2,2) a (1,2); opět všechny možné seřazené páry, z nichž každý se objevil jednou. Stejný příkaz by platil, kdyby byl použit první a druhý sloupec. Toto je tedy ortogonální pole síly dva.

Ortogonální pole zobecňují myšlenku vzájemně kolmé latinské čtverce ve formě tabulky. Tato pole mají mnoho připojení k jiným kombinatorickým návrhům a mají aplikace ve statistice návrh experimentů, teorie kódování, kryptografie a různé typy testování softwaru.

Definice

A t-(proti,k, λ) ortogonální pole (t ≤ k) je λproti^t × k pole, jehož položky jsou vybrány ze sady X s proti body takové, že v každé podskupině t sloupce pole, každý t-tuple bodů z X se zobrazí v přesně λ řádcích.

V této formální definici je stanoveno opakování t-tuples (λ je počet opakování) a počet řádků je určen ostatními parametry.

V mnoha aplikacích mají tyto parametry následující názvy:

proti je počet úrovně,

k je počet faktory,

λproti^t je počet experimentálních běží,

t je síla, a

λ je index.

Ortogonální pole je jednoduchý pokud neobsahuje žádné opakované řádky.

Ortogonální pole je lineární -li X je konečné pole řádu q, F_q (q hlavní síla) a řádky pole tvoří podprostor vektorový prostor (F_q)^k.^[1]

Každé lineární ortogonální pole je jednoduché.

Příklady

Příklad 2- (4, 5, 1) ortogonálního pole; design síly 2, 4 úrovně indexu 1 se 16 běhy.

Příklad 2- (3,5,3) ortogonálního pole (zapsaného jako jeho přemístit pro snadné prohlížení):^[2]

Triviální příklady

Žádný t-(proti, t, λ) bude uvažováno ortogonální pole triviální protože jsou snadno sestavitelné pouhým uvedením všech t-tuples of proti-nastavte λ krát.

Vzájemně kolmé latinské čtverce

A 2- (proti,k, 1) ortogonální pole je ekvivalentní množině k − 2 vzájemně kolmé latinské čtverce řádu proti.

Index jedna, síla 2 ortogonální pole jsou také známé jako Hypergreco-latinský čtvercový design ve statistické literatuře.

Nechat A být ortogonální pole síly 2, index 1 na a proti-sada prvků, identifikovaná množinou přirozených čísel {1, ...,proti}. Vyberte a opravte v pořadí dva sloupce A, nazvaný indexování sloupců. Všechny objednané páry (i, j) s 1 ≤ i, j ≤ proti se zobrazí přesně jednou v řádcích indexovacích sloupců. Vezměte jakýkoli jiný sloupec A a vytvořte čtvercové pole, jehož vstup do polohy (i,j) je položka A v tomto sloupci v řádku, který obsahuje (i, j) ve indexovacích sloupcích A. Výsledný čtverec je a Latinský čtverec řádu proti. Zvažte například ortogonální pole 2- (3,4,1):

Výběrem sloupců 3 a 4 (v tomto pořadí) jako indexovacích sloupců vytvoří první sloupec latinský čtverec,

zatímco druhý sloupec vytváří latinský čtverec,

Latinské čtverce vyrobené tímto způsobem z ortogonálního pole budou ortogonální latinské čtverce, takže k - 2 sloupce jiné než indexující sloupce vytvoří sadu k − 2 vzájemně kolmé latinské čtverce.

Tato konstrukce je zcela reverzibilní, a proto lze ortogonální pole síly 2, index 1 sestrojit ze sad vzájemně ortogonálních latinských čtverců.^[3]

Latinské čtverce, latinské kostky a latinské hyperkrychle

Ortogonální pole poskytují jednotný způsob, jak popsat tyto různorodé objekty, které jsou ve statistice zajímavé návrh experimentů.

Latinské čtverce

Jak již bylo zmíněno v předchozí části, latinský řád řádu n lze považovat za 2- (n, 3, 1) ortogonální pole. Ve skutečnosti může ortogonální pole vést k šesti latinským čtvercům, protože jako indexovací sloupce lze použít jakoukoli uspořádanou dvojici odlišných sloupců. To jsou však všechny izotopový a jsou považovány za rovnocenné. Pro úplnost vždy předpokládáme, že jako indexovací sloupce jsou použity první dva sloupce v jejich přirozeném pořadí.

Latinské kostky

Ve statistické literatuře, a Latinská kostka je n × n × n trojrozměrná matice skládající se z n vrstvy, z nichž každá má n řádky a n sloupce takové, že n odlišné prvky, které se objevují, se opakují n² krát a uspořádány tak, aby v každé vrstvě rovnoběžně s každým ze tří párů protilehlých ploch krychle byly všechny n objeví se odlišné prvky a každý se přesně opakuje n krát v této vrstvě.^[4]

U této definice nemusí být vrstva latinské krychle latinským čtvercem. Ve skutečnosti nemusí být žádný řádek, sloupec nebo soubor (buňky konkrétní pozice v různých vrstvách) permutace z n symboly.^[5]

Latinská kostka řádu n je ekvivalentní s 2- (n, 4, n) ortogonální pole.^[2]

Dvě latinské kostky řádu n jsou ortogonální pokud mezi n³ párů prvků vybraných z odpovídajících buněk dvou kostek, každá odlišná uspořádaná dvojice prvků se vyskytuje přesně n krát.

Sada k - 3 vzájemně kolmé latinské kostky řádu n je ekvivalentní s 2- (n, k, n) ortogonální pole.^[2]

Příklad dvojice vzájemně ortogonálních latinských kostek řádu tři byl uveden jako 2- (3,5,3) ortogonální pole v Příklady část výše.

Na rozdíl od případu s latinskými čtverci, ve kterých nejsou žádná omezení, musí být indexovací sloupce reprezentace ortogonálního pole latinské krychle vybrány tak, aby tvořily 3- (n, 3,1) ortogonální pole.

Latinské hyperkrychle

An m-dimenzionální Latinská hyperkrychle řádu n z rth třída je n × n × ... ×n m-rozměrná matice mající n^r odlišné prvky, každý opakovaný n^m − r časy a takové, že každý prvek se vyskytuje přesně n ^{m − r − 1} krát v každém ze svých m sady n paralelní (m - 1) -dimenzionální lineární podprostory (nebo "vrstvy"). Dvě takové latinské hyperkrychle stejného řádu n a třída r s vlastností, že když je jeden superponovaný na druhý, každý prvek jednoho se vyskytuje přesně n^m − 2r časy s každým prvkem toho druhého, se říká, že jsou ortogonální.^[6]

Sada k − m vzájemně kolmé m-rozměrné latinské hyperkrychky řádu n je ekvivalentní s 2- (n, k, n^m − 2) ortogonální pole, kde indexovací sloupce tvoří m-(n, m, 1) ortogonální pole.

Dějiny

Koncepty Latinské čtverce a vzájemně kolmé latinské čtverce byly zobecněny na latinské kostky a hyperkrychle a ortogonální latinské kostky a hyperkrychle podle Kishen (1942).^[7] Rao (1946) zobecnil tyto výsledky na sílu t. Současný pojem ortogonálního pole jako zobecnění těchto myšlenek, kvůli C. R. Rao, se objeví v Rao (1947).^[8]

Ostatní stavby

Hadamardovy matice

Pokud existuje a Hadamardova matice objednávky 4m, pak existuje 2- (2, 4m − 1, m) ortogonální pole.

Nechat H být Hadamardovou maticí řádu 4m ve standardizované podobě (položky prvního řádku a sloupce jsou všechny +1). Smažte první řádek a vezměte přemístit získat požadované ortogonální pole.^[9]

Řád 8 standardizované Hadamardovy matice níže (± 1 položek označených pouze znaménkem),

produkuje 2- (2,7,2) ortogonální pole:^[10]

Pomocí sloupců 1, 2 a 4 jako indexovacích sloupců vytvoří zbývající sloupce čtyři vzájemně kolmé latinské kostky řádu 2.

Kódy

Nechat C ⊆ (F_q)ⁿbýt lineární kód dimenze m s minimální vzdáleností d. Pak C^⊥ (ortogonální doplněk vektorového podprostoru C) je (lineární) (d − 1)-(q, n, λ) ortogonální pole kde
λ =q^{n − m − d + 1}.^[11]

Aplikace

Prahová schémata

Tajné sdílení (také zvaný tajné rozdělení) se skládá z metod distribuce a tajný mezi skupinou účastníků, z nichž každý je přidělen a podíl tajemství. Tajemství lze rekonstruovat pouze v případě, že je kombinován dostatečný počet sdílených složek, případně různých typů; jednotlivé akcie nejsou samy o sobě k ničemu. Tajné schéma sdílení je perfektní pokud každá sbírka účastníků, která nesplňuje kritéria pro získání tajemství, nemá žádné další znalosti o tom, co je tajemstvím, než jednotlivec bez podílu.

V jednom typu schématu sdílení tajemství existuje jeden obchodník a n hráči. Dealer dává hráčům podíly tajemství, ale pouze pokud budou splněny konkrétní podmínky, budou hráči moci toto tajemství rekonstruovat. Dealer toho dosáhne tak, že každému hráči dá podíl takovým způsobem, aby ho mohla libovolná skupina t (pro práh) nebo více hráčů může společně rekonstruovat tajemství, ale žádná skupina s méně než t hráči mohou. Takový systém se nazývá (t, n) -prahové schéma.

A t-(proti, n + 1, 1) ortogonální pole lze použít ke konstrukci dokonalého (t, n) -prahové schéma.^[12]

Nechat A být ortogonální pole. První n sloupce budou použity k poskytnutí sdílení hráčům, zatímco poslední sloupec představuje tajemství, které se má sdílet. Pokud si prodejce přeje sdílet tajemství S, pouze řádky A jehož poslední záznam je S jsou použity v systému. Dealer náhodně vybere jeden z těchto řádků a rozdá hráči i položka v tomto řádku ve sloupci i jako akcie.

Faktoriální návrhy

A faktoriální experiment je statisticky strukturovaný experiment, ve kterém několik faktory (zalévání, antibiotika, hnojiva atd.) jsou aplikovány na každou experimentální jednotku v různé (ale integrální) úrovně (vysoká, nízká nebo různé střední úrovně).^[13] V plný faktoriální experiment je třeba otestovat všechny kombinace úrovní faktorů, ale aby se minimalizovaly matoucí vlivy, měly by se hladiny v rámci jakéhokoli experimentálního běhu měnit.

K návrhu faktoriálního experimentu lze použít ortogonální pole síly 2. Sloupce představují různé faktory a položky představují úrovně, na kterých lze faktory použít (za předpokladu, že všechny faktory lze použít na stejném počtu úrovní). Experimentální běh je řada ortogonálního pole, to znamená použití příslušných faktorů na úrovních, které se v řádku objevují. Při použití jednoho z těchto návrhů by měly být ošetřovací jednotky a zkušební pořadí randomizovány tak, jak to design umožňuje. Jedním doporučením je například, aby bylo z dostupných velikostí náhodně vybráno ortogonální pole s odpovídající velikostí, poté randomizujte pořadí běhu.

Kontrola kvality

Ortogonální pole hrála ústřední roli ve vývoji Taguchi metody podle Genichi Taguchi, která se uskutečnila během jeho návštěvy u Indický statistický institut na počátku 50. let. Jeho metody byly úspěšně použity a přijaty japonským a indickým průmyslovým odvětvím a následně byly také přijaty americkým průmyslovým odvětvím, i když s určitými výhradami.

Testování

Testování ortogonálního pole je testování černé skříňky technika, která je systematická, statistický způsob testování softwaru.^[14][15] Používá se, když je počet vstupů do systému relativně malý, ale příliš velký, aby umožnil vyčerpávající testování všech možných vstupů do systému. systémy.^[14] Je zvláště efektivní při hledání chyb souvisejících s vadnými logika v rámci počítač softwarové systémy.^[14] Lze použít ortogonální pole uživatelské rozhraní testování, testování systému, regrese testování a testování výkonu.v obměny úrovní faktorů zahrnujících jednu léčbu jsou zvoleny tak, aby jejich odpovědi nebyly korelovány, a proto každá léčba poskytuje jedinečný kus informace. Čistým účinkem organizování experimentu v takovýchto postupech je to, že stejná informace je shromážděna v minimálním počtu experimenty.

Viz také

• Kombinatorický design
• Latinské hyperkrychle vzorkování
• Řecko-latinské čtverce

Poznámky

Reference

• Box, G. E. P .; Hunter, W. G .; Hunter, J. S. (1978). Statistiky pro experimentátory: Úvod do designu, analýzy dat a vytváření modelů. John Wiley and Sons.
• Dénes, J .; Keedwell, A. D. (1974), Latinské čtverce a jejich aplikace, New York-Londýn: Academic Press, ISBN  0-12-209350-X, PAN  0351850
• Hedayat, A.S .; Sloane, N.J.A .; Stufken, J. (1999), Ortogonální pole, teorie a aplikace, New York: Springer
• Kishen, K. (1942), „On latin and hyper-graeco cubes and hypercubes“, Současná věda, 11: 98–99
• Kishen, K. (1950), „O konstrukci latinských a hypergreco-latinských kostek a hyperkrychlí“, J. Indian Soc. Agric. Statistika, 2: 20–48
• Raghavarao, Damaraju (1988). Konstrukce a kombinatorické problémy při navrhování experimentů (opravený dotisk edice Wiley z roku 1971). New York: Dover.CS1 maint: ref = harv (odkaz)
• Raghavarao, Damaraju a Padgett, L.V. (2005). Blokové vzory: analýza, kombinatorika a aplikace. World Scientific.CS1 maint: více jmen: seznam autorů (odkaz)
• Rao, C.R. (1946), „Hypercubes of power '' d '' vedoucí ke zmateným designům ve faktoriálních experimentech", Bulletin of Calcutta Mathematical Society, 38: 67–78
• Rao, C.R. (1947), "Faktoriální experimenty odvozitelné z kombinatorických uspořádání polí", Dodatek k věstníku Královské statistické společnosti, 9: 128–139, JSTOR  2983576
• Stinson, Douglas R. (2003), Kombinatorické návrhy: Konstrukce a analýza, New York: Springer, ISBN  0-387-95487-2
• Ulice, Anne Penfoldová & Ulice, Deborah J. (1987). Kombinatorika experimentálního designu. Oxford U. P. [Clarendon]. ISBN  0-19-853256-3.

externí odkazy

• Hypergreco-latinský čtvercový design
• Příklad SAS využívající PROC FACTEX
• Kuhfeld, Warren F. "Ortogonální pole". SAS Institute Inc. SAS poskytuje katalog více než 117 000 ortogonálních polí.

Tento článek zahrnujepublic domain materiál z Národní institut pro standardy a technologie webová stránka https://www.nist.gov.