numerisches Integral vs Wurzeln zählen

Ich habe ein Problem, das auf zwei verschiedene Arten betrachtet werden kann:

Berechnen Sie eine $n$ -dimensionales Integral, numerischer Kontext. Die Domäne der Integration ist eine $n$ -dimensionaler Hyperwürfel der Seite $L$ .
Zähle (zähle einfach) die Wurzeln eines $n$ -dimensionale Funktion (kein Polynom).

Die Lösung nur eines davon reicht aus, um das ursprüngliche Problem zu lösen. Ich weiß, dass einfache Algorithmen für die numerische Integration erforderlich wären $O(L^n)$ , lineare Zeit pro Dimension nehmen. Ich bin mir aber nicht sicher, ob es für (1) asymptotisch schnellere Algorithmen gibt.

Für (2) sind mir Algorithmen bekannt, die Wurzeln finden können (Newton und Bisection), aber ich bin mir nicht sicher, welche Algorithmen am besten geeignet sind, um zu zählen, wie viele Wurzeln sich in einem Nicht-Polynom befinden $n$ -dimensionale Funktion.

Was sind die besten Algorithmen für (2)? Sind sie besser als die schnellsten von (1)?

algorithms numerical-analysis counting labotsirc
quelle

Kein Experte, aber "Best" würde wahrscheinlich von Ihrer spezifischen Situation abhängen ...

Aryabhata

Details zur Funktion würden sicherlich helfen. Kannst du das berücksichtigen? Führen Sie eine Substitution durch, bei der Variablen gruppiert werden (wobei einige weggelassen werden)? Woher wissen Sie, dass es isolierte Wurzeln gibt, keine Hyperebenen, auf denen die Funktion verschwindet?

vonbrand

@ Aryabhata könnte sein. Auf jeden Fall ist der einzige Parameter als Eingabe

n

$n$ (

L

$L$ wächst linear als

O (n)

$O(n)$ ).

Labotsirc

@vonbrand: Leider können wir das nicht berücksichtigen. Für die Substitution sagt die Intuition nein, aber wir werden diesen Aspekt genauer untersuchen. Die Wurzeln sind isoliert, selbst wenn die Domäne kontinuierlich ist, fallen die Wurzeln nur an diskreten Stellen. Vielen Dank.

Labotsirc

Antworten:

Erwägen Sie die Verwendung der Monte-Carlo-Methode zur Berechnung der Quadratur. Es ist eine gute Wahl, wenn Sie keine so genaue Annäherung benötigen und die Dimension der Domäne groß ist.

Sie sollten auf jeden Fall mehr Details angeben.

Jan Brezina
quelle

Wenn Sie die Bewertung Ihrer Funktion an Quadraturpunkten des Tensorprodukts im Würfel anzeigen, bildet das resultierende Zahlenfeld einen Tensor. Wenn diesem Tensor eine Struktur mit niedrigem Rang zugrunde liegt, können Sie einige der neuen Tensor-Zug-Approximationstechniken verwenden, um den Tensor zu approximieren, während Sie den Tensor an viel weniger Quadraturpunkten bewerten. Siehe die Arbeit von Ivan Osledets an Tensorzügen, insbesondere TT-Kreuz, das auf der Skelettmatrixzerlegung für die verschiedenen Matrizisierungen des Tensors basiert.

http://www.mat.uniroma2.it/~tvmsscho/papers/Tyrtyshnikov5.pdf

Nick Alger
quelle