# How is additive error handled in this simple algorithm? 'Product of all elements'

Say we have two unit vectors $$\hat{u}, \hat{v} \in \mathbb{R}^n$$ where $$\hat{u} = (u_1,...,u_n)$$ and $$\hat{v}$$ approximates $$\hat{u}$$. $$~\hat{v} = (u_1+\epsilon, ...,u_n+\epsilon)$$ where $$\epsilon = \frac{1}{poly(n)}$$.

We have an algorithm which takes the product of all elements and outputs the product. For the exact case (with $$\hat{u}$$), $$x = \prod_i^nu_i$$. For the approximate case (with $$\hat{v}$$), $$x^* = \prod_i^n(u_i + \epsilon)$$.

What is the error of $$x^*$$ with respect to $$x$$? How do we bound the error of $$x^*$$ in terms of epsilon? How is the error analysis typically handled in this situation?

• Do you really mean it is the same $\epsilon$ in each coordinate, or do you perhaps mean $(u_1+\epsilon_1,\dots,u_n+\epsilon_n)$? Do you care about relative error or absolute error? – D.W. May 7 at 20:59
• 1) this is neither computer science, nor research level. 2) your notation needs to be fixed the way @DW suggested. 3) already for $n=2$ you can see that $|x^* - x|$ can be as large as $\epsilon(u_1+u_2) + \epsilon^2$ and will not be a function of only $\epsilon$. – Sasho Nikolov May 8 at 7:42

Use Taylor series expansion for the function $$\prod_{i=1}^{n} (u_i + y)$$ around $$y=0$$ to obtain the error as $$\epsilon (\prod_{j=1}^{n} u_j) \sum_{i=1}^{n} u_i^{-1} + O(\epsilon^2)$$. Note that Taylor series works for $$\epsilon = O(1/poly(n))$$, because $$\mathbf{u}$$ is a unit normed vector and the product $$\prod_{j=1}^{n} u_j < 1$$.
• I'm having some slight difficulty parsing this. Should it be "obtain the error as $\epsilon = ...$? Also, can we make a statement about how wrong our algorithm can be just in terms of $\epsilon$? Thanks! Still trying to wrap my head around this. – stats_man97531 May 7 at 21:29
• $n\epsilon+ O(\epsilon^2)$ should work – Soumya Basu May 8 at 13:41