1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Estimating the error of an iterative sequence

  1. Feb 16, 2013 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations
    I want to estimate the error of the following iteration that finds x:

    Take [itex]x^2=a[/itex] 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 [itex]0< a <1[/itex], then make the substitutions of [itex]y=1-x[/itex] and [itex]b=1-a[/itex] to get [itex]2y=(b+y^2)[/itex]. You can turn this into [itex]y_{i+1}=\frac{1}{2}(b+y_{i}^{2})[/itex] which converges monotically, and converges for any [itex]y_{0}[/itex] between 0 and 1. So far, we're gravy.

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

    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 [itex]a[/itex])? 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.
  2. jcsd
  3. Feb 16, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    With the assumption that ##y_i \approx y## after a few steps,
    $$\frac{|y_{i+1}-y|}{|y_{i}-y|} \approx y$$
    $$\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 yi is smaller than y, this approximation is valid, otherwise it might depend on the initial value.

    A more conservative estimate (using just yi<1) leads to
    $$|y_{i+n}-y| < \left(\frac{1+y}{2}\right)^n$$
  4. Feb 16, 2013 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    From your iterative equation, if ##y_i \leq y## then also ##y_{i+1} \leq y##, so
    [tex] |y_{i+1}-y|= \frac{1}{2}|y_{i}- y| |y_i + y| \leq \frac{1}{2} |y_i - y|\, 2y,[/tex]
    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.
  5. Feb 17, 2013 #4
    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 [itex]\frac{1}{2}|y_{i}-y|\rightarrow \frac{1}{2}2y[/itex] 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 [itex]y_{i}<y[/itex] and [itex]y_{i}<y[/itex].

    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 [itex]|y_{i}-y|\leq k|y_{i}-y|[/itex] when [itex]y_{i}>y[/itex], is that because [itex]k>1[/itex] for all i (even if just barely) if we take [itex]k=\frac{1}{2}|y_{i}+y|[/itex]? Is that the meat of the issue here?

    mfb: I love the breakdown you gave, and I agree that [tex]\left ( \frac{1+y}{2} \right )^{n}[/tex] 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.
  6. Feb 17, 2013 #5


    User Avatar
    2017 Award

    Staff: Mentor

    Those cases are hard to separate, indeed :wink:.

    You can derive it in the same way I did this for yi<y, using yi<1 instead.
    Experience? I never saw that algorithm before.
  7. Feb 17, 2013 #6
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook