trovando rapidamente il primo punto in cui una funzione è uguale a 0 utilizzando scipy.optimize

Question

In sostanza, data una funzione che produce uscite come questo per diversi parametri:

voglio trovare rapidamente il primo a x che la funzione è uguale a 0. Quindi con i parametri che producono la curva blu su x, voglio trovare x = 134. Per la curva verde, voglio trovare x = 56, etc.

ho pensare la funzione sarà sempre monotonicamente decrescente fino a raggiungere lo zero, ma non ne sono del tutto sicuro.

La funzione non è necessariamente monotonicamente decrescente.

I am sicuro che verrà colpito solo 0 una volta e quindi rimarrà zero.

Attualmente sono bruto-forzandolo iterando attraverso i valori x fino a quando non raggiungo lo zero, ma voglio qualcosa che sia migliore nel fare ipotesi plausibili (basate sulla pendenza?) E iterare.

Idealmente, voglio usare qualcosa già cotto (since 90% of programmers can't even write a binary search correctly), come qualcosa da scipy.optimize, ma sembra che tutti vogliano trovare un minimo globale o uno zero-crossing.

(Questa funzione è una sorta di distanza_della parete del cubo RGB per un dato croma nello spazio di colore Lch (quindi fondamentalmente la costruzione di una funzione "sanely clip to RGB"), ma poiché la mappatura tra IRGB e LCh può variare in base alla libreria e con parametri come illuminante, ecc. Penso che sia meglio provare solo alcuni valori fino a trovare quello giusto invece di provare a calcolare il valore direttamente?)

Answer 1

Ecco il codice per rimpolpare @ bisection/risposta ricerca binaria di ExP:

def find_first_zero(func, min, max, tol=1e-3): 
    min, max = float(min), float(max) 
    assert (max + tol) > max 
    while (max - min) > tol: 
     mid = (min + max)/2 
     if func(mid) == 0: 
      max = mid 
     else: 
      min = mid 
    return max 

Answer 2

Se non per il fatto che la mano destra del curva è 0 ovunque, il metodo di Newton (https://en.wikipedia.org/wiki/Newton's_method) funzionerebbe benissimo. Ma penso che una variante funzionerà ancora bene:

1) Scegliere un punto.

2) Se siamo su una pendenza, prendiamo il gradiente della pendenza localmente e tracciamo una linea da lì alla intercetta x e prendiamo questo come nuovo punto (vai a 1)).

3) Se siamo in piano (x = 0, derivata = 0), quindi se un bit a sinistra è una pendenza (dovrebbe sintonizzarsi per capire quanto rimane da controllare), quindi effettuare una ricerca locale (probabilmente ricerca binaria con tolleranza) per trovare il punto in cui la funzione è uguale a zero. In caso contrario, prendi il punto che è il punto intermedio tra questo punto e l'ultimo punto su una pendenza che abbiamo provato (vai a 1 con questo nuovo punto).

Per stimare la derivata (per determinare se ci si trova in pendenza o meno), è possibile campionare un punto a sinistra ea destra, abbastanza lontano da essere certi che si otterrà un'approssimazione uniforme del derivato.

Answer 3

Prova bisection: controlla se è 0 nel mezzo del tuo intervallo; se lo è, continua a sinistra, altrimenti, a destra. Fai la stessa cosa con l'intervallo ridotto in modo ricorsivo finché non sei abbastanza vicino. Questo metodo è di complessità O (log n) rispetto al tuo, che è O (n).