Struggles understanding the derivation of the Householder's method

130 Views Asked by At

The Wikipedia article on Householder's method for root-finding derives it in their first approach with:

First step

I understand this first part.

They continue by saying:

"The coefficient of degree $d$ has the value ${\displaystyle C\,a^{-d}}$. Thus, one can now reconstruct the zero $a$ by dividing the coefficient of degree $d − 1$ by the coefficient of degree $d$. Since this geometric series is an approximation to the Taylor expansion of $1/f(x)$, one can get estimates of the zero of $f(x)$ – now without prior knowledge of the location of this zero – by dividing the corresponding coefficients of the Taylor expansion of $1/f(x)$ or, more generally, $1/f(b+x)$."

This is the part that makes no sense to me. When they say "this" geometric series, I assume they mean the one shown in the first picture, but their claim that it is approximately equal to the Taylor expansion of a general $1/f(x)$ form I can't understand. I attempted to expand $1/f(x)$, centered around $a$, and at the second derivative term had already arrived at a very lengthy and ugly expression - how it is almost equal to the geometric series shown in the image is something I need help with.

Thanks.

1

There are 1 best solutions below

9
On BEST ANSWER

I found that explanation very hard to understand, to be honest.

Here's another try:

$$\frac{1}{f(x)}=\frac{x-a}{f(x)} \frac{1}{x-a} \\ = -\frac{1}{a} \frac{x-a}{f(x)} \frac{1}{1-x/a} \\ = -\frac{1}{a} \frac{x-a}{f(x)} \sum_{n=0}^\infty \left ( \frac{x}{a} \right )^n$$

if $|x|<|a|$.

Now suppose you have chosen to stop everything at degree $n$, then you should in principle expand $\frac{x-a}{f(x)}$ up to degree $n$ also. If you do that, you get

$$\frac{1}{f(x)}= \\ -\frac{1}{a} \cdot \left ( \sum_{k=0}^n \frac{1}{k!} g^{(k)}(0) x^k + \frac{1}{(n+1)!} g^{(n+1)}(\xi(x)) x^{n+1} \right ) \cdot \left ( \sum_{k=0}^n \left ( \frac{x}{a} \right )^k + \frac{\left ( \frac{x}{a} \right )^{n+1}}{1-x/a} \right )$$

using the Lagrange remainder in the first expansion, and where $g(x)=\frac{x-a}{f(x)}$.

So now what is the true coefficient of degree $x^j$ in the expansion of $\frac{1}{f(x)}$, for $j=0,1,\dots,n$? It is

$$c_j=-\frac{1}{a} \sum_{k=0}^j \frac{1}{k!} \left ( \frac{1}{a} \right )^{j-k} g^{(k)}(0).$$

The idea of Householder expansion is that as $a \to 0$, the dominant term in this sum is the $k=0$ term, since it has the highest power of $1/a$.

Anyway, if this approximation is good then it suggests $\frac{c_n}{c_{n+1}}$ should be approximately $\frac{-\frac{1}{a^{n+1}} g(0)}{-\frac{1}{a^{n+2}} g(0)}=a$, and so you can use this ratio (obtained by actually differentiating $\frac{1}{f}$) as an approximation of $a$. To deal with $a$ not close to $0$, you can replace $x$ by $b+x$ where $b \approx a$.

This method of analysis doesn't actually expose any advantage of large $n$; it ostensibly implies $\frac{c_n}{c_{n+1}}=a+O(a^2)$ regardless of what $n$ is. You need a somewhat more sophisticated mode of attack (for example what is described in https://en.wikipedia.org/wiki/Householder%27s_method#Derivation) to see why large $n$ has any advantages.