Otočný prvek - Pivot element

The pivot nebo otočný prvek je prvek a matice, nebo pole, který je nejprve vybrán znakem algoritmus (např. Gaussova eliminace, simplexní algoritmus atd.), provést určité výpočty. V případě maticových algoritmů je obvykle vyžadováno, aby byl pivotní záznam alespoň odlišný od nuly a často od ní vzdálený; v tomto případě se nazývá nalezení tohoto prvku otočný. Po otočení může následovat výměna řádků nebo sloupců, aby se otočný čep dostal do pevné polohy a umožnil algoritmu úspěšně pokračovat a případně snížit zaokrouhlovací chybu. Často se používá k ověření řádkový sled.

Pivoting lze považovat za prohození nebo třídění řádků nebo sloupců v matici, a proto jej lze reprezentovat jako násobení podle permutační matice. Algoritmy však zřídka přesouvají prvky matice, protože by to stálo příliš mnoho času; místo toho jen sledují permutace.

Otočení celkově přidává další operace k výpočtovým nákladům na algoritmus. Tyto další operace jsou někdy nutné, aby algoritmus vůbec fungoval. Jindy jsou tyto další operace užitečné, protože přidávají numerická stabilita ke konečnému výsledku.

Příklady systémů, které vyžadují otočení

V případě Gaussovy eliminace vyžaduje algoritmus, aby pivotní prvky nebyly nulové. Výměna řádků nebo sloupců v případě nulového pivotního prvku je nutná. Níže uvedený systém vyžaduje pro eliminaci řádky 2 a 3.

${displaystyle left [{egin {array} {ccc | c} 1 & -1 & 2 & 8 0 & 0 & -1 & -11 0 & 2 & -1 & -3end {array}} ight]}$

Systém, který je výsledkem otočení, je následující a umožní eliminační algoritmus a zpětnou substituci k výstupu řešení do systému.

${displaystyle left [{egin {array} {ccc | c} 1 & -1 & 2 & 8 0 & 2 & -1 & -3 0 & 0 & -1 & -11end {array}} ight]}$

Kromě toho je v Gaussově eliminaci obecně žádoucí zvolit otočný prvek s velkým absolutní hodnota. To zlepšuje numerická stabilita. Následující systém je dramaticky ovlivněn chybou zaokrouhlování při provádění Gaussovy eliminace a zpětné substituce.

${displaystyle left [{egin {array} {cc | c} 0,00300 a 59,14 a 59,17 5,291 & -6,130 a 46,78 end {pole}} vpravo]}$

Tento systém má přesné řešení x₁ = 10,00 a x₂ = 1.000, ale když se eliminační algoritmus a zpětná substituce provádějí pomocí čtyřmístné aritmetiky, malá hodnota a₁₁ způsobí šíření malých zaokrouhlovacích chyb. Algoritmus bez otáčení poskytuje aproximaci x₁ ≈ 9873,3 a x₂ ≈ 4. V tomto případě je žádoucí, abychom zaměnili dva řádky tak, aby a₂₁ je v otočné poloze

${displaystyle left [{egin {array} {cc | c} 5.291 & -6.130 & 46.78 0.00300 & 59.14 & 59.17 end {array}} nocleh.}$

Vzhledem k tomuto systému poskytuje eliminační algoritmus a zpětná substituce pomocí čtyřmístného aritmetického výpočtu správné hodnoty x₁ = 10,00 a x₂ = 1.000.

Částečné a úplné otočení

v částečné otočení, algoritmus vybere položku s největší absolutní hodnotou ze sloupce matice, který je aktuálně považován za otočný prvek. Částečné otočení je obecně dostatečné k odpovídajícímu snížení chyby zaokrouhlování. U určitých systémů a algoritmů však úplné otočení (nebo maximální otočení) může být vyžadováno pro přijatelnou přesnost. Dokončete otočné záměny řádků i sloupců, abyste mohli jako otočný prvek použít největší (v absolutní hodnotě) prvek v matici. Úplné otočení obvykle není nutné k zajištění numerické stability a vzhledem k dalším nákladům na hledání maximálního prvku je zlepšení numerické stability, které poskytuje, obvykle vyváženo sníženou účinností pro všechny matice kromě nejmenších. Proto se používá jen zřídka.^[1]

Škálovatelné otáčení

Variace strategie částečného otočení je otočená v měřítku. V tomto přístupu algoritmus vybere jako otočný prvek položku, která je největší vzhledem k položkám v jejím řádku. Tato strategie je žádoucí, pokud velké rozdíly ve velikosti záznamů vedou k šíření zaokrouhlovací chyby. Měřítko otáčení by mělo být použito v systému, jako je ten níže, kde se položky řady velmi liší. V níže uvedeném příkladu by bylo žádoucí zaměnit tyto dva řádky, protože aktuální otočný prvek 30 je větší než 5,191, ale je relativně malý ve srovnání s ostatními položkami v jeho řádku. Bez výměny řádků v tomto případě budou chyby zaokrouhlování šířeny jako v předchozím příkladu.

${displaystyle left [{egin {array} {cc | c} 30 & 591400 & 591700 5.291 & -6.130 & 46.78 end {array}} ight]}$

Otočná poloha

Otočná pozice v matici, A, je pozice v matici, která odpovídá řádku vedoucímu 1 v snížená řada echelon forma A. Protože forma A se sníženým sledem řádků je jedinečná, polohy otočných čepů jsou jednoznačně určeny a nezávisí na tom, zda se v procesu redukce provádějí či nevyměňují řádky. Otočení řádku se také musí objevit napravo od otočení ve výše uvedeném řádku v řádkový sled.

Reference

Tento článek včlení materiál od Pivoting on PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.

• R. L. Burden, J. D. Faires, Numerická analýza, 8. vydání, Thomson Brooks / Cole, 2005. ISBN  0-534-39200-8
• G. H. Golub, C. F. půjčka, Maticové výpočty, 3. vydání, Johns Hopkins, 1996. ISBN  0-8018-5414-8.
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Křížové metody: nový pohled na pivotní algoritmy". Matematické programování, řada B.. Příspěvky ze 16. mezinárodního symposia o matematickém programování, které se konalo v Lausanne, 1997. 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373. doi:10.1007 / BF02614325. PAN  1464775. Postprintový předtisk. Citovat má prázdné neznámé parametry: |1= a |2= (Pomoc)
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot pravidla pro lineární programování: Průzkum o nedávném teoretickém vývoji". Annals of Operations Research. Degenerace v optimalizačních problémech. 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658. doi:10.1007 / BF02096264. ISSN  0254-5330. PAN  1260019. Citovat má prázdný neznámý parametr: |1= (Pomoc)