Newton-Raphson Equation Root Finder

calculator.py

from abc import abstractmethod, ABC
from typing import Tuple, List, Generator


class Function(ABC):
    """Function for Newton-Raphson algorithm
    """

    @abstractmethod
    def calculate(self, x: float) -> float:
        """Executes function on x which is iteratively corrected guess value,
           until is step is smaller than precision """
        pass


class FDx(Function):
    """Derived F(x) == F'(x), e.g. if F(x) = x^2 => F'(x) = 2x """

    @abstractmethod
    def calculate(self, x: float) -> float:
        """see Function.calculate"""
        pass


class Fx(Function):
    """Function from which we are calculating F(x) = 0"""

    @abstractmethod
    def calculate(self, x: float) -> float:
        """see Function.calculate"""
        pass

    @property
    @abstractmethod
    def derived(self) -> FDx:
        """Create a derivation of this function"""
        pass


class NewtonRaphsonCalculator(object):
    """General implementation of Newton-Raphson method

    Accepts more functions, but every Fx should have its derived version FDx
    """
    DEFAULT_GUESS = 0.01
    DEFAULT_PRECISION = 7
    MAXIMUM_ITERATIONS = 10000

    def __init__(self, *fs: Fx, precision: int = DEFAULT_PRECISION):
        assert all(isinstance(f, Fx) for f in fs), \
            "NewtonRaphsonCalculator accepts only `Fx` objects"
        self.fxs: List[Fx] = list(fs)
        self.precision = self._precision = precision

    def execute_functions(self, guess: float) -> Generator[Tuple[float, float], None, None]:
        """Executes functions on guessed value"""
        return ((fx.calculate(guess), fx.derived.calculate(guess)) for fx in self.fxs)

    @property
    def precision(self):
        return pow(10, -self._precision)

    @precision.setter
    def precision(self, value: int):
        assert isinstance(value, int)
        self._precision = value

    def calculate(self, guess: float = DEFAULT_GUESS) -> float:
        """Executes the iterative calculation

        See more about this method in https://en.wikipedia.org/wiki/Newton%27s_method
        basically you want to calculate x when F(x) = 0, so you will need F'(x) with this method
        If there are partial functions, they will summed together:
            F(x) = F1(x) + F2(x) + ... + Fn(x)
            F'(x) = F1'(x) + F2'(x) + ... + Fn'(x)
        """
        diff = 1.0
        value = guess
        iterations = 0
        while diff > self.precision:
            assert iterations < self.MAXIMUM_ITERATIONS, \
                "Maximum iteration loop `count:{}` exceeded".format(self.MAXIMUM_ITERATIONS)
            iterations += 1
            # sum up all results of all functions
            ys, yds = zip(*self.execute_functions(value))
            y, yd = sum(ys), sum(yds)
            # remember the last value
            old_value = value
            assert yd != 0, "for `value:{}` f'(x) returned bad value: 0".format(value)
            # value[n] = value[n-1] - Fn(x)/Fn'(x)
            value = old_value - y / yd
            diff = abs(old_value - value)
        return value