in numerical analysis Householder methods
are a class of root finding algorithms,
with this update formula where d denotes the number of algorithm in the householder class:
but there is another way to use Householder methods not using the mentioned formula!!
writing Taylor_serie of the given function with d sentences (where d denotes the number of algorithm in
the householder class) around $x_n$ with $x_{n+1}$ as the variable, solving it as algebraic equation would give us the update formula!!
lets take an example, consider $cos(x)$ as the function that we want to find its roots with different householder method
writting taylor serie with $d=1$ we would have:
$\frac{f(x_n)}{0!}+ \frac{f'(x_n)}{1!}(x_{n+1} - x_n) = 0$
$\frac{cos(x_n)}{0!}+ \frac{-sin(x_n)}{1!}(x_{n+1} - x_n) = 0$
$cos(x_n) - sin(x_n)x_{n+1} + sin(x_n)x_n = 0$
$x_{n+1} =\frac{-cos(x_n) - sin(x_n)x_n}{-sin(x_n)} = 0$
$x_{n+1} =x_n + cot(x_n) $
here in this jupyter notebook file
I implemented a function to solve $cos(x) = 0$ equation with a given initial guess and number of generation
if you want to solve another equation replace these lines with your function and its derivatives.
f = math.cos(guess)
fprim = -math.sin(guess)
and here it is the result of running with 10 generation & initial guess equal to one(in radian),
notice that the sequence approaches to the nearest answer to the initial guess.
lets write taylor serie with $d=2$
$\frac{f(x_n)}{0!} + \frac{f'(x_n)}{1!}(x_{n+1} - x_n) + \frac{f''(x_n)}{2!}(x_{n+1} - x_n) = 0$
$\frac{cos(x_n)}{0!} + \frac{-sin(x_n)}{1!}(x_{n+1} - x_n) + \frac{-cos(x_n)}{2!}(x_{n+1} - x_n)^2 = 0$
$(\frac{1}{2}cos(x_n))x_{n+1}^2 + (-sin(x_n)+cos(x_n))x_{n+1} +(-\frac{1}{2}cos(x_n)x_n^2 + sin(x_n)x_n + cos(x_n)) = 0$
lets solve this equation using delta method, with
$a = \frac{1}{2}cos(x_n)$
$b = -sin(x_n)+cos(x_n)$
$c = -\frac{1}{2}cos(x_n)x_n^2 + sin(x_n)x_n + cos(x_n)$
$\Delta = (-sin(x_n)+cos(x_n))^2 - 4(\frac{1}{2}cos(x_n))(-\frac{1}{2}cos(x_n)x_n^2 + sin(x_n)x_n + cos(x_n))$
$x_{n+1} = \frac{(sin(x_n)-cos(x_n) \pm \sqrt{\Delta})}{cos(x_n)}$
and here it is the result of running with 10 generation & initial guess equal to one(in radian),
compare it with newton raphson result diagram!
consider Halley method, what happen if $\Delta$ became negative?
the answer would be an update method including a complex function, does the root finding algorithms have meaning in the complex plane?
a related link