Programowanie funkcyjne/Procedury wyższych rzędów/Ćwiczenia

Praca domowa

• Wygładzenie funkcji z odstępem $dx$ polega na uśrednieniu $f(x-dx)$, $f(x)$ i $f(x+dx)$. Napisz procedurę wygładzającą daną funkcję z zadanym odstępem.

• Jaki typ ma procedura compose zastosowana w wyrażeniu:

compose twice twice;;

Ćwiczenia

Ćwiczenie [Semantyka wyrażeń]

Przypomnij sobie zadanie dotyczące wyliczania wartości wyrażeń. Rozszerz składnię wyrażeń o zmienne. Procedura obliczająca wartość wyrażenia będzie wymagać dodatkowego parametru -- wartościowania zmiennych, czyli procedury, która nazwie zmiennej przyporządkowuje jej wartość.

Ćwiczenie [Przybliżanie zer przez bisekcję]

Zaimplementuj przybliżanie zer funkcji przez bisekcję. Parametrami powinny być:

• funkcja $f$, której zer szukamy,
• dwa punkty, w których funkcja przyjmuje wartości przeciwnych znaków,
• precyzja poszukiwać, tzn. taki $\epsilon$, że jeżeli wynik $x$ spełnia $|fx|\le \epsilon$, to jest dobrym przybliżeniem zera.

Laboratorium

Ćwiczenie [Odwrotność funkcji]

Niech $f:{ℛ}\to {ℛ}$ będzie funkcją 1-1 i "na" oraz taką, że $f(0)=0$, $f$ jest rosnąca i $|f(x)|\ge |x|$. Zaimplementuj procedurę odwrotnosc, której wynikiem dla parametru $f$ będzie przybliżenie $f^{-1}$ z dokładnością zadaną przez stałą epsilon (czyli jeśli g = odwrotnosc f, to $\mathrm{\forall }x|g(x)-f^{-1}(x)|\le epsilon$).

Ćwiczenie [Pierwiastkowanie jako punkt stały [AS] ]

Przedstawione w wykładzie tłumienie przez uśrednianie opiera się na średniej arytmetycznej. Czasami zamiast średniej arytmetycznej należy użyć średniej ważonej, z odpowiednio dobraną wagą. Punktem stałym funkcji $y\to \frac{x}{y^{n-1}}$ jest $\sqrt[n]{x}$. Zaimplementuj obliczanie $n$-tego pierwiastka z $x$ za pomocą obliczania punktu stałego i tłumienia przez uśrednianie z odpowiednimi wagami. Uwaga: W jaki sposób wagi zależą od $n$?

Rozwiązanie

Uśrednienie funkcji $f$ z wagą $a$ możemy zdefiniować następująco:

 let usrednij a f x = a *. (f x) +. (1. -. a) *. x;;
 val usrednij : float -> (float -> float) -> float -> float = <fun>

Żeby iterowanie przekształcenia $y\to \frac{x}{y^{n-1}}$ było zbieżne do jego punktu stałego, musimy je uśrednić ze współczynnikiem mniejszym od $\frac{2}{n}$, np. $\frac{2}{n+1}$.

 let root n x = 
   punkt_staly (usrednij (2. /. float(n+1)) (fun y -> x /. potega y (n-1))) 1.;;