Coverage for src/algolib/numerics/diff.py: 35%

1from __future__ import annotations 

2import math 

3from typing import Callable 

4 

5def derivative_cstep(f: Callable[[complex], complex], x: float, h: float = 1e-20) -> float: 

6 """ 

7 Complex-step derivative approximation: 

8 

9 f'(x) ≈ Im(f(x + i*h)) / h 

10 

11 Requires f to support complex input. Very stable since 

12 there is no subtractive cancellation. 

13 """ 

14 return (f(x + 1j * h)).imag / h 

15 

16def derivative_central( 

17 f: Callable[[float], float], 

18 x: float, 

19 *, 

20 h: float | None = None, 

21 max_iter: int = 6, 

22) -> float: 

23 """ 

24 Central difference derivative approximation with Richardson extrapolation. 

25 

26 Useful when f does not support complex input. 

27 Accuracy is O(h^2) per step and improved by extrapolation. 

28 """ 

29 scale = max(1.0, abs(x)) 

30 h = 1e-3 * scale if h is None else h 

31 

32 T = [] 

33 for k in range(max_iter): 

34 hk = h / (2 ** k) 

35 T0k = (f(x + hk) - f(x - hk)) / (2.0 * hk) 

36 T.append([T0k]) 

37 for j in range(1, k + 1): 

38 num = T[k][j - 1] - T[k - 1][j - 1] 

39 T[k].append(T[k][j - 1] + num / (4 ** j - 1)) 

40 return T[-1][-1]