Estimating the error of an iterative sequence

[jeku1987]

Homework Statement

This isn't quite homework (though it's close), but I'm working on a quantum circuit and wish to implement an iterative method to find the square root of a number using elementary arithmetic operations (and without reciprocals). I've gotten most of it down, but the error analysis is kicking me hard in the teeth.

Homework Equations

I want to estimate the error of the following iteration that finds x:

Take $x^2=a$ where a is known (sort of; the QC would be calculating a bunch of possible a's in superposition via the inverse quantum Fourier transform/eigenvalue kickback, but that's not super relevant) and $0< a <1$, then make the substitutions of $y=1-x$ and $b=1-a$ to get $2y=(b+y^2)$. You can turn this into $y_{i+1}=\frac{1}{2}(b+y_{i}^{2})$ which converges monotically, and converges for any $y_{0}$ between 0 and 1. So far, we're gravy.

The Attempt at a Solution

Now if we subtract y from both sides, we get
$$y_{i+1} - y = \frac{1}{2}(y_{i}^{2} - y^{2})$$
And after some manipulation, along with some blindly-added absolute value signs, we end up with
$$\left | y_{i+1}-y \right | = \frac{1}{2} \left | y_{i}-y \right | \left | y_{i}+y \right |$$
Here's the meat of my issue; I want $\left | y_{i+1}-y \right | < \varepsilon$ and to get there my intuition says to take some delta such that $\frac{1}{2}\left | y_{0}-y \right | < \delta$ which would lead to $\left | y_{i}-y \right | < \delta^i\left | y_{0}-y \right |$

But at this point I'm kind of getting lost in all of the details of the individual parts and can't really step outside very well to see the Big Picture. How can I represent the error of the iterations in terms of things that I know (which in this case, I think is only going to be $a$)? And I don't know where to go from here, is anyone well-versed in error estimation? Or analysis? Am I done here, or are there more steps to go?

Any and all help is, of course, immensely appreciated.

 

[mfb]

With the assumption that $y_i \approx y$ after a few steps,
$$\frac{|y_{i+1}-y|}{|y_{i}-y|} \approx y$$
Therefore:
$$\frac{|y_{i+n}-y|}{|y_{i}-y|} \approx y^n$$
Using $|y_{i}-y|<1$ and ignoring the first steps,
$$|y_{i+n}-y| < y^n$$
If y_i is smaller than y, this approximation is valid, otherwise it might depend on the initial value.

A more conservative estimate (using just y_i<1) leads to
$$|y_{i+n}-y| < \left(\frac{1+y}{2}\right)^n$$

 

[Ray Vickson]

Homework Statement

This isn't quite homework (though it's close), but I'm working on a quantum circuit and wish to implement an iterative method to find the square root of a number using elementary arithmetic operations (and without reciprocals). I've gotten most of it down, but the error analysis is kicking me hard in the teeth.

Homework Equations

I want to estimate the error of the following iteration that finds x:

Take $x^2=a$ where a is known (sort of; the QC would be calculating a bunch of possible a's in superposition via the inverse quantum Fourier transform/eigenvalue kickback, but that's not super relevant) and $0< a <1$, then make the substitutions of $y=1-x$ and $b=1-a$ to get $2y=(b+y^2)$. You can turn this into $y_{i+1}=\frac{1}{2}(b+y_{i}^{2})$ which converges monotically, and converges for any $y_{0}$ between 0 and 1. So far, we're gravy.

The Attempt at a Solution

Now if we subtract y from both sides, we get
$$y_{i+1} - y = \frac{1}{2}(y_{i}^{2} - y^{2})$$
And after some manipulation, along with some blindly-added absolute value signs, we end up with
$$\left | y_{i+1}-y \right | = \frac{1}{2} \left | y_{i}-y \right | \left | y_{i}+y \right |$$
Here's the meat of my issue; I want $\left | y_{i+1}-y \right | < \varepsilon$ and to get there my intuition says to take some delta such that $\frac{1}{2}\left | y_{0}-y \right | < \delta$ which would lead to $\left | y_{i}-y \right | < \delta^i\left | y_{0}-y \right |$

But at this point I'm kind of getting lost in all of the details of the individual parts and can't really step outside very well to see the Big Picture. How can I represent the error of the iterations in terms of things that I know (which in this case, I think is only going to be $a$)? And I don't know where to go from here, is anyone well-versed in error estimation? Or analysis? Am I done here, or are there more steps to go?

Any and all help is, of course, immensely appreciated.

From your iterative equation, if $y_i \leq y$ then also $y_{i+1} \leq y$, so
$$|y_{i+1}-y|= \frac{1}{2}|y_{i}- y| |y_i + y| \leq \frac{1}{2} |y_i - y|\, 2y,$$
so $|y_{i+1}-y| \leq y\, |y_i - y|$, hence $|y_i - y|$ is dominated by $c y^i$.

The case $y_i > y$ is trickier; we have that $y_{i+1} > y$ also, but getting a nice $y_i$-independent multiplier $k \in (0,1)$ with $|y_{i+1}-y| \leq k \,|y_i - y|$ is trickier. I think it can be done, but I will leave the rest to you.

 

[jeku1987]

First, thank you both so very much! I've been struggling to look at this in so many different ways because analysis isn't my strongest suit, and your (in hindsight, simple) suggestions to let $\frac{1}{2}|y_{i}-y|\rightarrow \frac{1}{2}2y$ is exactly the hint I needed. HOWEVER, I'm having trouble seeing that the error estimate would have to be different for the cases of $y_{i}<y$ and $y_{i}<y$.

Ray Vickson: because knowing what the problem is can be half the battle sometimes, when you say it'll be trickier finding a multiplier such that $|y_{i}-y|\leq k|y_{i}-y|$ when $y_{i}>y$, is that because $k>1$ for all i (even if just barely) if we take $k=\frac{1}{2}|y_{i}+y|$? Is that the meat of the issue here?mfb: I love the breakdown you gave, and I agree that $$\left ( \frac{1+y}{2} \right )^{n}$$ shrinks as n increases, but is that result derived from anywhere? Or is it just something you know that works from experience?

And again, thank you both very much for all your help thus far.

 

[mfb]

HOWEVER, I'm having trouble seeing that the error estimate would have to be different for the cases of $y_{i}<y$ and $y_{i}<y$.

Those cases are hard to separate, indeed .

mfb: I love the breakdown you gave, and I agree that $$\left ( \frac{1+y}{2} \right )^{n}$$ shrinks as n increases, but is that result derived from anywhere? Or is it just something you know that works from experience?

You can derive it in the same way I did this for y_i<y, using y_i<1 instead.
Experience? I never saw that algorithm before.

 

[jeku1987]

Ahhhh I see what you were saying now. And I just meant experience with error estimation more generally sorry, my use of pronouns went dumb for half a tick.