# Householder’s Method
Householder’s method of order \(d\) to solve \(f(x)=0\) has rate of convergence \(d+1\):
\[x \to x + d \frac{(1/f)^{(d-1)}(x)}{(1/f)^{(d)}(x)} =: H_d(x)\]
\(d=1\) corresponds to Newton’s method.
Using (wx)Maxima:
H(d, x) := factor(ratsimp(x + d *
(diff(1/f(x), x, d - 1)) / (diff(1/f(x), x, d))));
# 1 General \(f(x)\)
\[ H_1(x) = x - \frac{f(x)}{f'(x)} \]
\[ H_2(x) = x - \frac{1}{\frac{f'(x)}{f(x)} - \frac{f''(x)}{2 f'(x)}} \]
\(H_3(x)\) is getting complicated…
# 2 Reciprocal Square Root
\[x = \frac{1}{\sqrt{a}}\]
can be rearranged to
\[f(x) = x^{-2} - a = 0\]
Using (wx)Maxima:
f(x) := x^(-2) - a;
H(1, x);
H(2, x);
H(3, x);
H(4, x);
Gives
\[\begin{aligned} H_1(x) &= \frac{(3 - a x^2)x}{2} \\ H_2(x) &= \frac{(3 + a x^2)x}{3 a x^2 + 1} \\ H_3(x) &= \frac{a^2x^4 + 6ax^2 + 1}{4ax(ax^2+1)} \\ H_4(x) &= \frac{x(a^2x^4 + 10ax^2 + 5)}{5a^2x^4 + 10ax^2 + 1} \\ \end{aligned}\]
Expected number of steps for \(N\) digit accuracy is \[\frac{\log N}{\log (d+1)}\]
Cost in terms of cost \(M\) of high precision multiplication or division, assuming \(a\) is low precision exact and that addition and low precision multiplication can be neglected:
\[\begin{aligned} \operatorname{cost}(H_1) = \frac{2}{\log 2} M \log(N) \\ \operatorname{cost}(H_2) = \frac{3}{\log 3} M \log(N) \\ \operatorname{cost}(H_3) = \frac{4}{\log 4} M \log(N) \\ \operatorname{cost}(H_4) = \frac{4}{\log 5} M \log(N) \\ \end{aligned}\]
Cost assuming \(a\) is high precision:
\[\begin{aligned} \operatorname{cost}(H_1) = \frac{3}{\log 2} M \log(N) \\ \operatorname{cost}(H_2) = \frac{4}{\log 3} M \log(N) \\ \operatorname{cost}(H_3) = \frac{5}{\log 4} M \log(N) \\ \operatorname{cost}(H_4) = \frac{5}{\log 5} M \log(N) \\ \end{aligned}\]
These are decreasing with higher \(d\), indicating that the extra complexity is worthwhile.
# 3 Iterated Quadratic Polynomial
\(f(z) = z^2 + c\)
\(M\) cost of high precision real multiplication or division.
Complex squaring costs \(3 M\), complex multiplication \(4 M\).
Cost of iteration is proportional to iteration count \(P\):
Cost of \(f\): \(3 M P\)
Cost of \(f'\): \(4 M P\)
Cost of \(f''\): \(7 M P\)
Cost of the additional algebra in \(H_d\) does not depend on \(P\) so is negligible.
Hence:
Cost of \(H_1\): \(\frac{7}{\log 2} M P \log N \approx 10.1 M P \log N\)
Cost of \(H_2\): \(\frac{14}{\log 3} M P \log N \approx 12.7 M P \log N\)
These are increasing with higher \(d\), indicating that the extra complexity is not worthwhile.