La teoria dei punti fissi e la funzione isGoodEnough - scala, computer science, punto fisso

Nel corso di Coursera Functional Programming Principles in Scala, il docente parla del Fixed Point e ne scrisse una semplice implementazione.

def isCloseEnough(x: Double, y: Double) =
math.abs((x - y) / x) / x < tolerance

def fixedPoint(f: Double => Double)(guess: Double) = {

def iterate(guess: Double): Double = {
val next = f(guess)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(guess)
}

Tale implementazione consentirà la seguente funzione f(x) = 1 + x avere un punto fisso.

Tuttavia questo non dovrebbe mai accadere. Come in questo grafico delle funzioni:

E questo è quanto affermato da Wikipedai:

Non tutte le funzioni hanno punti fissi: ad esempio, se f è una funzione definito sui numeri reali come f (x) = x + 1, quindi non ha risolto punti, poiché x non è mai uguale a x + 1 per nessun numero reale.

Il punto qui è nel isCloseEnough che non ho potuto capire perché è scritto in quel modo.

Sono qui per capire il isCloseEnough e perché è stato implementato in quel modo Questo è tutto.

risposte:

2 per risposta № 1

L'algoritmo non è perfetto e dovrebbe ovviamente dipendere dalla tua scelta di tolleranza. Se esaminiamo isCloseEnough:

def isCloseEnough(x: Double, y: Double) =
math.abs((x - y) / x) / x < tolerance

È davvero simile a:

| x - y | / x^2 < tolerance

Solo che per qualche motivo non sta prendendo il valore assoluto della divisione esterna di x, che interrompe completamente l'algoritmo quando x è negativo

L'idea però è che troviamo un punto fisso trovando un x questo è arbitrariamente vicino a f(x), ovvero la differenza tra x e f(x) è piccolo quanto vogliamo (sotto una certa tolleranza). Funziona bene se possiamo trovare rapidamente punti fissi:

scala> fixedPoint(math.sqrt)(2)
res2: Double = 1.0000846162726942

Qui, il punto fisso è x = 1, dove math.sqrt(1) = 1. ero solito tolerance = 0.0001. Se avessi usato qualcosa di più piccolo, avrei ovviamente ottenuto un'approssimazione più ravvicinata del punto fisso 1.

Ma ora dico che ho:

def f(x: Double): Double = x + 1

scala> fixedPoint(f)(1)
res4: Double = 102.0

Trova un punto fisso di circa 102.0. Ovviamente, questo è sbagliato, ma succede perché la differenza tra x e f(x) è sempre 1 per questa funzione e come x diventa più grande, 1 / x^2 diventa sempre più piccolo fino a quando non scende al di sotto del tolerance. Se faccio il tolerance più piccolo, troverò un punto fisso più grande.

val tolerance = 0.000000001

scala> fixedPoint(f)(1)
res5: Double = 31624.0

Anche questo ovviamente è sbagliato. Ma il punto è che qualcosa deve essere un punto fisso che dovrei essere in grado di fare tolerance arbitrariamente piccoloe ottenere comunque un risultato coerente. Con questa funzione, è chiaro che per qualsiasi fisso tolerance, infine 1 / x^2 sarà più piccolo di esso. Ma, per ogni x, Posso sempre sceglierne uno abbastanza piccolo tolerance così 1 / x^2 cadrà sempre al di fuori di esso, quindi non ci sono punti fissi.

Questa non è una prova matematica, ma il punto è che l'algoritmo è imperfetto per alcuni criteri.

---