Oszacuj Normę działania czarnej skrzynki

Pozwolić $V$ być skończoną przestrzenią wektorową z normą $\|\cdot\|$ i niech $F : V \rightarrow \mathbb R$ będzie ograniczoną funkcją liniową. Jest podawany tylko jako czarna skrzynka.

Chciałbym oszacować normę $F$ (od góry i od dołu). Ponieważ $F$ jest czarną skrzynką, jedynym sposobem na to jest przetestowanie go za pomocą wektorów jednostkowych z $V$ i, na podstawie wyniku, znalezienie $v \in S^1 V$ które maksymalizuje $|F(v)|$ .

Czy znasz taki algorytm? W aplikacji, o której myślę, $V$ jest przestrzenią elementów skończonych, a $F$ jest skomplikowaną funkcją w tej przestrzeni.

EDYCJA: Moim pierwszym pomysłem jest losowe wybranie $v \in S^1 V$ , zakłócenie go w kilku kierunkach, powiedzmy, $v_1,\dots,v_k$ , a następnie powtórzenie procedury z $v_i$ które uzyskało największy $F(v_i)$ . Nie wiem, gdzie znaleźć algorytmy i analizy dla tego problemu.

linear-algebra algorithms shuhalo
źródło

Czy normą jest również czarna skrzynka? A może jest to zwykła norma dla spacji Banacha, ?

‖ \cdot ‖_{\infty}

$\|\cdot\|_\infty$

Jack Poulson,

Czy jesteś zainteresowany normą w regionie (lub w punkcie), w którym funkcja ma ciągłą pochodną?

Jed Brown

@Jack: Norma przestrzeni wektorowej jest obliczalna, a na przestrzeni elementu skończonego można ją obliczyć na podstawie macierzy masy i macierzy sztywności. ( i pochodna).

0

$0$

1

$1$

shuhalo,

@Jed: jest liniowy, więc można go już różnicować.

F

$F$

shuhalo,

Odpowiedzi:

Jeśli twoja przestrzeń jest przestrzenią Hilberta, to twierdzenie Riesz mówi, że możesz reprezentować i możesz obliczyć jak wspomniasz, wypróbowując wektory jednostkowe. Jeśli przestrzeń ma większe wymiary, staje się to niepraktyczne, ale można przynajmniej obliczyć oszacowania , obliczając dla sekwencji losowych wektorów . $V$ $F(v)=\left< f, v \right>$ $f$ $f$ $F(v)$ $v$

Wolfgang Bangerth
źródło

Może możesz zmodyfikować estymator numeru stanu Hagera (patrz np. Artykuł http://eprints.ma.man.ac.uk/321/01/35608.pdf ), co ograniczagdy znane jest rozkładanie na czynniki , dla konkretnego przypadku. $\|A^{-1}\|$ $A$

Arnold Neumaier
źródło