# Householder’s Method

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