Číslo podmínky - Condition number
V oblasti numerická analýza, číslo podmínky funkce měří, jak moc se může výstupní hodnota funkce změnit pro malou změnu vstupního argumentu. To se používá k měření jak citlivý funkcí je změna nebo chyba na vstupu a kolik chyb na výstupu je výsledkem chyby na vstupu. Velmi často se řeší inverzní problém: daný jeden řeší pro X, a proto musí být použito číslo podmínky (místní) inverze. v lineární regrese číslo podmínky momentová matice lze použít jako diagnostiku pro multicollinearity.[1][2]
Číslo podmínky je aplikací derivátu a je formálně definováno jako hodnota asymptotické nejhorší relativní změny výstupu pro relativní změnu vstupu. „Funkce“ je řešením problému a „argumenty“ jsou data v problému. Číslo podmínky je často aplikováno na otázky v lineární algebře, v takovém případě je derivace přímočará, ale chyba může být v mnoha různých směrech, a je tedy počítána z geometrie matice. Obecněji lze čísla podmínek definovat pro nelineární funkce v několika proměnných.
Říká se, že je problém s nízkým počtem stavů dobře podmíněný, zatímco se říká, že je problém s vysokým počtem stavů špatně podmíněný. Z nematematického hlediska je špatně podmíněným problémem problém, kdy pro malou změnu ve vstupech („ nezávislé proměnné nebo na pravé straně rovnice) došlo k velké změně v odpovědi nebo závislá proměnná. To znamená, že je těžké najít správné řešení / odpověď na rovnici. Číslo podmínky je vlastností problému. Spárované s problémem je libovolný počet algoritmů, které lze použít k vyřešení problému, tj. K výpočtu řešení. Některé algoritmy mají vlastnost nazvanou zpětná stabilita. Obecně lze očekávat, že zpětně stabilní algoritmus přesně vyřeší dobře podmíněné problémy. Učebnice numerické analýzy poskytují vzorce pro počty podmínek problémů a identifikují známé zpětně stabilní algoritmy.
Jako pravidlo platí, pokud je číslo podmínky , pak můžete ztratit až číslice přesnosti navíc k tomu, co by se ztratilo numerické metodě kvůli ztrátě přesnosti z aritmetických metod.[3] Číslo podmínky však neposkytuje přesnou hodnotu maximální nepřesnosti, která se může v algoritmu vyskytnout. Obecně to omezuje odhadem (jehož vypočítaná hodnota závisí na volbě normy pro měření nepřesnosti).
Obecná definice v kontextu analýzy chyb
Vzhledem k problému a algoritmus se vstupem X, absolutní chyba je a relativní chyba je .
V této souvislosti absolutní číslo podmínky problému F je
a relativní číslo podmínky je
Matice
Například číslo podmínky spojené s lineární rovniceSekera = b dává jistotu, jak nepřesné řešení X bude po aproximaci. Všimněte si, že toto je před účinky chyba zaokrouhlení jsou brány v úvahu; klimatizace je vlastnost matice, nikoli algoritmus nebo plovoucí bod přesnost počítače použitého k řešení příslušného systému. Zejména je třeba uvažovat o počtu podmínek jako o (velmi zhruba) rychlosti řešení X se změní s ohledem na změnu v b. Pokud je tedy číslo podmínky velké, dokonce i malá chyba v b může způsobit velkou chybu v X. Na druhou stranu, pokud je číslo podmínky malé, pak chyba v X nebude mnohem větší než chyba v b.
Číslo podmínky je přesněji definováno jako maximální poměr relativní chyba v X k relativní chybě v b.
Nechat E být chyba v b. Za předpokladu, že A je nesingulární matice, chyba v řešení A−1b je A−1E. Poměr relativní chyby v řešení k relativní chybě v b je
Maximální hodnota (pro nenulovou hodnotu b a E) je pak považován za produkt těchto dvou normy provozovatele jak následuje:
Stejná definice se používá pro všechny konzistentní norma, tj. ten, který uspokojí
Když je číslo podmínky přesně jedna (což se může stát, pouze pokud A je skalární násobek a lineární izometrie ), pak algoritmus řešení může najít (v zásadě to znamená, že pokud algoritmus nezavádí vlastní chyby) aproximaci řešení, jehož přesnost není o nic horší než u dat.
Neznamená to však, že se algoritmus rychle sblíží s tímto řešením, ale že se nebude lišit libovolně z důvodu nepřesnosti zdrojových dat (zpětná chyba), za předpokladu, že se dopředná chyba zavedená algoritmem také neodchyluje, protože hromadění přechodných chyb zaokrouhlování.[je zapotřebí objasnění ]
Číslo podmínky může být také nekonečné, ale to znamená, že problém je špatně pózoval (nemá jedinečné, dobře definované řešení pro každou volbu dat; to znamená, že matice není invertibilní) a nelze očekávat, že spolehlivě najde řešení žádný algoritmus.
Definice čísla podmínky závisí na volbě normy, jak lze ilustrovat na dvou příkladech.
Li je norma definované ve čtvercovém součtu sekvenční prostor ℓ2 (který odpovídá obvyklé vzdálenosti ve standardním euklidovském prostoru a je obvykle označován jako ), pak
kde a jsou maximální a minimální singulární hodnoty z resp. Proto:
- Li je normální, pak
- kde a jsou maximální a minimální (podle modulů) vlastní čísla z resp.
- Li je unitární, pak
Číslo podmínky s ohledem na L2 vzniká tak často v číselné podobě lineární algebra že dostal jméno, číslo podmínky matice.
Li je norma definované v sekvenční prostor ℓ∞ ze všech ohraničený sekvence (která odpovídá maximu vzdáleností naměřených na projekcích do základních podprostorů a je obvykle označena ), a je spodní trojúhelníkový ne singulární (tj. ), pak
Číslo podmínky vypočtené pomocí této normy je obecně větší než číslo podmínky vypočtené pomocí sekvencí se čtvercovými součty, ale lze jej vyhodnotit snadněji (a toto je často jediné prakticky vypočítatelné číslo podmínky, když problém k řešení zahrnuje nelineární algebra[je zapotřebí objasnění ], například při aproximaci iracionálních a transcendentálních funkcí nebo čísel pomocí numerických metod).
Pokud číslo podmínky není příliš velké než jedna, je matice dobře kondicionována, což znamená, že její inverzi lze vypočítat s dobrou přesností. Pokud je číslo podmínky velmi velké, pak se o matici říká, že je špatně kondicionovaná. Prakticky je taková matice téměř singulární a výpočet její inverzní funkce nebo řešení lineárního systému rovnic je náchylný k velkým numerickým chybám. Matice, která není invertibilní, má počet podmínek rovný nekonečnu.
Nelineární
Čísla podmínek lze také definovat pro nelineární funkce a lze je vypočítat pomocí počtu. Počet podmínek se liší podle bodu; v některých případech lze použít maximální (nebo nadřazené) číslo podmínky nad doménou funkce nebo domény otázky jako celkové číslo podmínky, zatímco v jiných případech je číslo podmínky v konkrétním bodě zajímavější.
Jedna proměnná
Číslo podmínky rozlišitelné funkce v jedné proměnné je funkce . Vyhodnoceno v bodě , tohle je
Nejelegantněji to lze chápat jako (absolutní hodnotu) poměru logaritmická derivace z , který je a logaritmická derivace , který je , čímž se získá poměr . Důvodem je, že logaritmická derivace je nekonečně malá rychlost relativní změny ve funkci: je to derivace zmenšen o hodnotu . Všimněte si, že pokud má funkce v bodě nulu, její číslo podmínky v bodě je nekonečné, protože nekonečně malé změny ve vstupu mohou změnit výstup z nuly na kladný nebo záporný, čímž se získá poměr s nulou ve jmenovateli, tedy nekonečný relativní změna.
Příměji, vzhledem k malé změně v relativní změna v je , zatímco relativní změna v je . Vezmeme-li poměrné výnosy
Poslední termín je rozdílový kvocient (sklon sečanové čáry) a při použití limitu se získá derivace.
Počet podmínek společného základní funkce jsou zvláště důležité při práci na počítači významné postavy a lze jej okamžitě vypočítat z derivátu; vidět aritmetika významnosti transcendentálních funkcí. Níže uvádíme několik důležitých:
název | Symbol | Číslo podmínky |
---|---|---|
Sčítání / odčítání | ||
Skalární násobení | ||
Divize | ||
Polynomiální | ||
Exponenciální funkce | ||
Funkce přirozeného logaritmu | ||
Sinusová funkce | ||
Kosinová funkce | ||
Tečná funkce | ||
Funkce inverzní sinus | ||
Funkce inverzní kosinus | ||
Funkce inverzní tangenty |
Několik proměnných
Pro jakoukoli funkci lze definovat čísla podmínek mapování jeho dat z některých doména (např -tuple reálných čísel ) do některých codomain (např -tuple reálných čísel ), kde jsou jak doména, tak doména Banachovy prostory. Vyjadřují, jak citlivá je tato funkce na malé změny (nebo malé chyby) v jejích argumentech. To je zásadní při hodnocení citlivosti a potenciálních obtíží s přesností mnoha výpočetních problémů, například polynomiální kořenový nález nebo na počítači vlastní čísla.
Počet podmínek v určitém okamžiku (konkrétně jeho relativní číslo podmínky[4]) je pak definován jako maximální poměr zlomkové změny v na jakoukoli částečnou změnu v , v limitu, kde je změna v se stává nekonečně malým:[4]
kde je norma na doméně / doméně .
Li je diferencovatelné, to odpovídá:[4]
kde označuje Jacobian matrix z částečné derivace z na , a je indukovaná norma na matrici.
Viz také
- Numerické metody pro lineární nejmenších čtverců
- Hilbertova matice
- Špatně položený problém
- Singulární hodnota
Reference
- ^ Belsley, David A .; Kuh, Edwin; Welsch, Roy E. (1980). „Číslo podmínky“. Regrese Diagnostics: Identification Influential Data and Sources of Collinearity. New York: John Wiley & Sons. 100–104. ISBN 0-471-05856-4.
- ^ Pesaran, M. Hashem (2015). „Problém multicollinearity“. Časové řady a panelová datová ekonometrie. New York: Oxford University Press. 67–72 [str. 70]. ISBN 978-0-19-875998-0.
- ^ Cheney; Kincaid (2008). Numerická matematika a výpočetní technika. p. 321. ISBN 978-0-495-11475-8.
- ^ A b C Trefethen, L. N .; Bau, D. (1997). Numerická lineární algebra. SIAM. ISBN 978-0-89871-361-9.
Další čtení
- Demmel, James (1990). "Nejbližší defektní matice a geometrie špatného kondicionování". In Cox, M. G .; Hammarling, S. (eds.). Spolehlivý numerický výpočet. Oxford: Clarendon Press. str. 35–55. ISBN 0-19-853564-3.