# # 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.