0

I may be missing something simple here, but in the section for stability of Wikinson's polynomial in Wikipedia the derivative is defined as:

$-\frac{\alpha^{19}}{\prod_{k \ne j}(\alpha_j - \alpha_k)}$

The denominator is defined as $p^{\prime}(\alpha_j)$ but I don't see where this derivative comes from? I can see it has to be something to do with the product rule which sets to zero all the non-k derivatives, but I am not entirely sure which variables are being changed here.

Sam Keays
  • 103

1 Answers1

2

The general idea is that you have a polynomial $p$ with one exact root $\alpha$. Due to numerical representation of the coefficients or the evaluation procedure the computer sees another polynomial that can, to some degree, be represented as $p(x)+\epsilon c(x)$. The basic idea of the perturbation calculation is now that this new polynomial still has a root close to $\alpha$, write it as $\alpha+\delta$. Now look at the Taylor expansion $$ 0+p'(\alpha)\delta+O(\delta^2)+\epsilon c(\alpha)+O(\epsilon\delta) $$ If $p'(\alpha)$ is large against $\epsilon$ and $\delta$, then a root approximation for the perturbed polynomial can be found at $$\delta=-\epsilon\frac{c(\alpha)}{p'(\alpha)},$$ that is $$ x=\alpha-\epsilon\frac{c(\alpha)}{p'(\alpha)} $$ If you see that as the start of a Taylor expansion of the root curve $x(\epsilon)$, then this second term is the linear term of the expansion associate with the derivative $x'(0)$.


The derivative of $p(x)=\prod_{k=1}^n(x-\alpha_k)$ is $$ p'(\alpha_m)=\lim_{x\to\alpha_m}\frac{p(x)-0}{x-\alpha_m}=\prod_{k\ne m}(\alpha_m-\alpha_k). $$

Lutz Lehmann
  • 126,666
  • Yes, good explanation. Just one other thing I realised, the bottom derivative, for conditioning, is taken at the root. So the 20 separate terms for the derivative (by the chain rule) collapse to just the one which isn't zero, the one where the root was differentiated, hence the equation above. Perhaps obvious but it stumped me for a while. – Sam Keays Feb 06 '24 at 00:52