1

This is a question from a computational mathematics course.

An error analysis of Horner's rule shows that the computed value of the polynomial satisfies $$\hat{c}_{0} = (1 + \theta_1)\alpha_0 + (1 + \theta_3)\alpha_1 x + \ldots + (1 + \theta_{2n-1})\alpha_{n-1}x^{n-1} + (1 + \theta_{2n})\alpha_n x^{n}$$ where $|\theta_k| \leq \gamma_k$ (Higham 2002 Accuracy and Stability of Numerical Algorithms, Second Edition). The pattern on the subscript is odd numbers, i.e., increment of 2, until the last which is even, i.e., last increment is 1. Let $$\tilde{p}_n(x) = |\alpha_{0}| + |\alpha_1|x + \ldots + |\alpha_n|x^{n}$$ Show that $$\frac{|p_n(x) - \hat{c}_{0}|}{|p_n(x)|} \leq \gamma_{2n}\frac{\tilde{p}_n(|x|)}{|p_n(x)|}$$ and therefore $$\mathcal{k}_{rel} = \frac{\tilde{p}(|x|)}{|p(x)|}$$ is a relative condition number for perturbations to the coefficients bounded by $\gamma_{2n}$.

I am pretty lost on showing this is the case, I assume I use the equation of $p_n(x) = \alpha_n(x - \mathcal{p}_1) \ldots (x - \mathcal{p}_n)$ where $\mathcal{p}$ or we may be able to use this equation ($p_n(x) = \alpha_0 + \alpha_1x + \ldots + \alpha_n x^{n}$) are the known roots of the polynomial and the equation above to prove the condition. If anyone can give me suggestions, I would greatly appreciate it.

Wolfy
  • 6,495

1 Answers1

1

Given, $$\hat{c}_{0} = (1 + \theta_1)\alpha_0 + (1 + \theta_3)\alpha_1 x + \ldots + (1 + \theta_{2n})\alpha_n x^{n}$$ we can use subtract $\hat{c}_0$ by $p_n(x)$ to get the desired forward error bound $$\hat{c}_0 - p_n(x) = \left[(1 + \theta_1)\alpha_0 + (1 + \theta_3)\alpha_1 x + \ldots + (1 + \theta_{2n})\alpha_n x^{n}\right] - \left[ \alpha_0 + \alpha_1 x + \ldots + \alpha_n x^{n}\right] $$ which yields $$\theta_1\alpha_o + \theta_3\alpha_1 x + \ldots + \theta_{2n}\alpha_n x^{n}$$ Now we can derive our forward error bound, \begin{align*} |\theta_1\alpha_o + \theta_3\alpha_1 x + \ldots + \theta_{2n}\alpha_n x^{n}| \leq |\theta_1||\alpha_0| + |\theta_3||\alpha_1||x| + \ldots + |\theta_{2n}||\alpha_n||x^{n}| \ \text{(by the triangle inequality)} \\ \leq \gamma_{2n}(|\alpha_0| + |\alpha_1||x| + \ldots + |\alpha_n||x^{n}|) = \gamma_{2n}\tilde{p}_n(|x|) \end{align*} where $\tilde{p}_n(x) = |\alpha_{0}| + |\alpha_1|x + \ldots + |\alpha_n|x^{n}$ thus, dividing $|p_n(x)|$ we get $$\frac{|p_n(x) - \hat{c}_{0}|}{|p_n(x)|} \leq \gamma_{2n}\frac{\tilde{p}_n(|x|)}{|p_n(x)|}$$ and therefore $$k_{rel} = \frac{\tilde{p}(|x|)}{|p(x)|}$$

Wolfy
  • 6,495