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