Numerická certifikace - Numerical certification

Numerická certifikace je proces ověřování správnosti řešení kandidáta na a soustava rovnic. V (numerické) výpočetní matematice, jako je numerická algebraická geometrie řešení kandidátů jsou počítána algoritmicky, ale existuje možnost, že chyby kandidáty poškodily. Například kromě nepřesnosti vstupních dat a kandidátních řešení mohou mít numerické chyby nebo chyby v diskretizaci problému za následek poškození kandidátských řešení. Cílem numerické certifikace je poskytnout certifikát, který prokazuje, kteří z těchto kandidátů jsou skutečně přibližnými řešeními.

Metody certifikace lze rozdělit do dvou příchutí: a priori certifikace a a posteriori osvědčení. A posteriori Certifikace potvrzuje správnost konečných odpovědí (bez ohledu na to, jak jsou generovány), zatímco a priori Certifikace potvrzuje správnost každého kroku konkrétního výpočtu. Typický příklad a posteriori certifikace je Smale teorie alfa, zatímco typický příklad a priori certifikace je aritmetika intervalu.

Certifikáty

A osvědčení pro root je výpočetní důkaz správnosti kandidátského řešení. Například certifikát může sestávat z přibližného řešení ${ displaystyle x}$ , oblast ${ displaystyle R}$ obsahující ${ displaystyle x}$ a důkaz toho ${ displaystyle R}$ obsahuje právě jedno řešení soustavy rovnic.

V této souvislosti an a priori číselný certifikát je certifikát ve smyslu správnost v informatice. Na druhou stranu, a posteriori numerický certifikát funguje pouze na řešeních, bez ohledu na to, jak jsou počítána. Proto, a posteriori certifikace se liší od správnosti algoritmu - pro extrémní příklad by algoritmus mohl náhodně generovat kandidáty a pokusit se je certifikovat jako přibližné kořeny pomocí a posteriori osvědčení.

A posteriori certifikační metody

Existuje celá řada metod a posteriori certifikace, včetně

Teorie alfa

Základní kámen města Smaleova alfa teorie ohraničuje chybu pro Newtonova metoda. Smaleova práce z roku 1986^[1] představil množství ${ displaystyle alpha}$ , který kvantifikuje konvergenci Newtonovy metody. Přesněji řečeno ${ displaystyle F}$ být systémem analytických funkcí v proměnných ${ displaystyle x}$ , ${ displaystyle D}$ the derivát operátor a ${ displaystyle N}$ operátor Newton. Množství

{ displaystyle beta (f, x) = | x-N (x) | = | Df (x) ^ {- 1} f (x) |}

{ displaystyle gamma (f, x) = sup _ {k geq 2} vlevo | { frac {Df (x) ^ {- 1} D ^ {k} f (x)} {k! }} doprava | ^ { frac {1} {k-1}}}

a

{ displaystyle alpha (f, x) = beta (f, x) gama (f, x)}

slouží k certifikaci kandidátského řešení. Zejména pokud

{ displaystyle alpha (f, x) <{ frac {13-3 { sqrt {17}}} {4}},}

pak

{ displaystyle x}

je přibližné řešení pro

{ displaystyle f}

kandidát je tedy v doméně kvadratická konvergence pro Newtonovu metodu. Jinými slovy, pokud tato nerovnost platí, pak existuje kořen

{ displaystyle x ^ { ast}}

z

{ displaystyle F}

takže iterace Newtonova operátoru konvergují jako

{ displaystyle left | N ^ {k} (x) -x ^ { ast} right | leq { frac {1} {2 ^ {2 ^ {k} -1}}} | xx ^ { ast} |.}

Softwarový balíček alphaCertified poskytuje implementaci alfa testu pro polynomy odhadem ${ displaystyle beta}$ a ${ displaystyle gamma}$ .^[2]

Intervalové Newtonovy a Krawczyckovy metody

Předpokládat ${ displaystyle G: mathbb {R} ^ {n} rightarrow mathbb {R} ^ {n}}$ je funkce, jejíž pevné body odpovídají kořenům ${ displaystyle F}$ . Například operátor Newton má tuto vlastnost. Předpokládejme to ${ displaystyle I}$ je tedy region,

Li ${ displaystyle G}$ mapy ${ displaystyle I}$ do sebe, tj. ${ displaystyle G (I) subseteq I}$ , poté Brouwerova věta o pevném bodě, ${ displaystyle G}$ má alespoň jeden pevný bod v ${ displaystyle I}$ , a tedy ${ displaystyle F}$ má alespoň jeden kořen v systému Windows ${ displaystyle I}$ .
Li ${ displaystyle G}$ je stahovací v oblasti obsahující ${ displaystyle I}$ , pak je v nanejvýš jeden kořen ${ displaystyle I}$ .

Ve složitých číslech existují verze následujících metod, ale jak aritmetika intervalu, tak podmínky musí být upraveny tak, aby odrážely tento případ.

Intervalová Newtonova metoda

V jednorozměrném případě lze Newtonovu metodu přímo zobecnit k ověření kořene v určitém intervalu. Na interval ${ displaystyle J}$ , nechť ${ displaystyle m (J)}$ být středem ${ displaystyle J}$ . Potom se aplikoval interval Newtonova operátoru ${ displaystyle J}$ je

{ displaystyle IN (J) = m (J) -F (m (J)) / F '(J).}

V praxi jakýkoli interval obsahující ${ displaystyle F '(J)}$ lze použít v tomto výpočtu. Li ${ displaystyle x}$ je kořenem ${ displaystyle F}$ , poté věta o střední hodnotě, některé jsou ${ displaystyle c v J}$ takhle ${ displaystyle F (m (J)) - F '(c) (m (J) -x) = F (x) = 0}$ . Jinými slovy, ${ displaystyle F (m (J)) = F '(c) (m (J) -x)}$ . Od té doby ${ displaystyle F '(J)}$ obsahuje inverzní z ${ displaystyle F}$ ve všech bodech ${ displaystyle J}$ , z toho vyplývá, že ${ displaystyle m (J) -x ve F (m (J)) / F '(J)}$ . Proto, ${ displaystyle x = m (J) - (m (J) -x) v IN (J)}$ .

Kromě toho, pokud ${ displaystyle 0 ne v F '(J)}$ , pak buď ${ displaystyle m (J)}$ je kořenem ${ displaystyle F}$ a ${ displaystyle IN (J) = {m (J) }}$ nebo ${ displaystyle m (J) ne v IN (J)}$ . Proto, ${ displaystyle J cap N (J)}$ je nanejvýš poloviční šířka ${ displaystyle J}$ . Proto, pokud existuje nějaký kořen ${ displaystyle F}$ v ${ displaystyle J}$ , iterativní postup nahrazení ${ displaystyle J}$ podle ${ displaystyle J cap IN (J)}$ se sblíží s tímto kořenem. Pokud na druhé straně není kořen ${ displaystyle F}$ v ${ displaystyle J}$ , tento iterační postup nakonec vytvoří prázdný interval, který bude svědkem neexistence kořenů.

Vidět intervalová Newtonova metoda pro analogie tohoto přístupu s vyšší dimenzí.

Krawczyckova metoda

Nechat ${ displaystyle Y}$ být kdokoli ${ displaystyle n krát n}$ invertibilní matice v ${ displaystyle GL (n, mathbb {R})}$ . Typicky, jeden bere ${ displaystyle Y}$ být aproximací k ${ displaystyle F '(y) ^ {- 1}}$ . Poté definujte funkci ${ displaystyle G (x) = x-YF (x).}$ To pozorujeme ${ displaystyle x}$ je pevná z ${ displaystyle G}$ kdyby a jen kdyby ${ displaystyle x}$ je kořenem ${ displaystyle F}$ . Proto lze výše uvedený přístup použít k identifikaci kořenů ${ displaystyle F}$ . Tento přístup je podobný vícerozměrné verzi Newtonovy metody, která nahrazuje derivaci pevnou maticí ${ displaystyle Y}$ .

Pozorujeme, že pokud ${ displaystyle J}$ je kompaktní a konvexní oblast a ${ displaystyle v J}$ , tedy pro všechny ${ displaystyle x v J}$ , existují ${ displaystyle c_ {1}, tečky, c_ {n} v J}$ takhle

{ displaystyle G (y) -G (x) = { begin {bmatrix} nabla g_ {1} (c_ {1}) ^ {T} vdots nabla g_ {n} (c_ { n}) ^ {T} end {bmatrix}} (yx).}

Nechat ${ displaystyle G '(J)}$ být jakobiánská matice ${ displaystyle G}$ hodnoceno dne ${ displaystyle J}$ . Jinými slovy, položka ${ displaystyle (G '(J)) _ {ij}}$ se skládá z obrazu ${ displaystyle { frac { částečné g_ {i}} { částečné x_ {j}}}}$ přes ${ displaystyle J}$ . Z toho pak vyplývá ${ displaystyle G (x) v G (y) + nabla G (J) (x-y),}$ kde se produkt matice-vektor počítá pomocí intervalové aritmetiky. Pak dovolte ${ displaystyle x}$ lišit se ${ displaystyle J}$ , z toho vyplývá, že obraz ${ displaystyle G}$ na ${ displaystyle J}$ splňuje následující omezení: ${ displaystyle G (J) podmnožina G (y) + G '(J) (J-y),}$ kde jsou výpočty opět počítány pomocí intervalové aritmetiky. V kombinaci s tímto vzorcem pro ${ displaystyle G}$ , výsledkem je operátor Krawczyck

{ displaystyle K_ {y, Y} (J) = y-YF (y) + (I-F '(J)) (J-y),}

kde ${ displaystyle I}$ je matice identity.

Li ${ displaystyle K_ {y, Y} (J) podmnožina J}$ , pak ${ displaystyle G}$ má pevný bod v ${ displaystyle J}$ , tj., ${ displaystyle F}$ má kořen v ${ displaystyle J}$ . Na druhou stranu, pokud maximum maticová norma za použití nadřazená norma pro vektory všech matic v ${ displaystyle I-F '(J)}$ je méně než ${ displaystyle 1}$ , pak ${ displaystyle G}$ je uvnitř smlouvy ${ displaystyle J}$ , tak ${ displaystyle G}$ má jedinečný pevný bod.

Jednodušší test, když ${ displaystyle J}$ je osově zarovnaný rovnoběžnostěn, používá ${ displaystyle y = m (J)}$ , tj. střed ${ displaystyle J}$ . V tomto případě existuje jedinečný kořen ${ displaystyle F}$ -li

{ displaystyle | K (X) -m (X) | <{ frac {w (X)} {2}},}

kde ${ displaystyle w (X)}$ je délka nejdelší strany ${ displaystyle J}$ .

Mirandův test

Miranda test (Yap, Vegter, Sharma)

A priori certifikační metody

Intervalová aritmetika (Moore, Arb, Mezzarobba)
Čísla podmínek (Beltran – Leykin)

Intervalová aritmetika

Interval aritmetika lze použít k poskytnutí a priori číselný certifikát výpočtem intervalů obsahujících jedinečná řešení. Použitím intervalů místo jednoduchých číselných typů během sledování cesty jsou výslední kandidáti reprezentováni intervaly. Kandidát na interval řešení je sám o sobě certifikátem v tom smyslu, že je zaručeno, že řešení bude uvnitř intervalu.

Čísla podmínek

Numerická algebraická geometrie řeší polynomiální systémy pomocí pokračování homotopy a metody sledování cesty. Monitorováním čísla podmínky pro sledovanou homotopii v každém kroku a zajištěním, že se nikdy neprotínají dvě cesty řešení, lze vypočítat číselný certifikát spolu s řešením. Toto schéma se nazývá a priori sledování cesty.^[3]

Necertifikované numerické sledování dráhy se spoléhá na heuristické metody pro řízení velikosti a přesnosti časového kroku.^[4] V porovnání, a priori certifikované sledování cesty jde nad rámec heuristiky, aby poskytovalo kontrolu velikosti kroku záruky že pro každý krok na cestě je aktuální bod v doméně kvadratická konvergence pro aktuální cestu.

Reference

^ Smale, Steve (1986). "Newtonova metoda odhaduje z údajů v jednom bodě". Sloučení disciplín: nové směry v čisté, aplikované a výpočetní matematice: 185–196.
^ Hauenstein, Jonathan; Sottile, Frank (2012). "Algoritmus 921: alphaCertified: certifikace řešení polynomiálních systémů". Transakce ACM na matematickém softwaru. 38 (4): 28. doi:10.1145/2331130.2331136.
^ Beltran, Carlos; Leykin, Anton (2012). "Certifikované číselné sledování homotopy". Experimentální matematika. 21 (1): 69–83.
^ Bates, Daniel; Hauenstein, Jonathan; Sommese, Andrew; Wampler, Charles (2009). Msgstr "Krokové ovládání pro sledování cesty". Současná matematika. 496 (21).

[1] Smale, Steve (1986). "Newtonova metoda odhaduje z údajů v jednom bodě". Sloučení disciplín: nové směry v čisté, aplikované a výpočetní matematice: 185–196.

[alphacertified-2] Hauenstein, Jonathan; Sottile, Frank (2012). "Algoritmus 921: alphaCertified: certifikace řešení polynomiálních systémů". Transakce ACM na matematickém softwaru. 38 (4): 28. doi:10.1145/2331130.2331136.

[3] Beltran, Carlos; Leykin, Anton (2012). "Certifikované číselné sledování homotopy". Experimentální matematika. 21 (1): 69–83.

[4] Bates, Daniel; Hauenstein, Jonathan; Sommese, Andrew; Wampler, Charles (2009). Msgstr "Krokové ovládání pro sledování cesty". Současná matematika. 496 (21).

[1]

[2]

[3]

[4]