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!

About an iteration technique

  1. Dec 18, 2009 #1
    Recently my dad wrote a computer program that finds an approximate solution to the "crossed-ladders problem"

    http://en.wikipedia.org/wiki/Crossed_ladders_problem

    for inputed ladder lengths and height of ladder intersection. It uses what I just learned is called "fixed point iteration" to find the square of the width (approximately) and then after about ten cycles returns the square root of the result.

    We are both impressed with how efficiently it finds so precise an answer, but neither of us completely understands why it works, especially when if one takes a random polynomial function and attempts to find a solution to it by isolating the exponent=1 term, making an initial guess, plugging it into the other side and iterating, the result almost always diverges.

    So my question is: under what circumstances will fixed point iteration converge? I've played around with a few sample functions and right now I have the impression that it always works if the absolute value of the slope of the function (with the exponent=1 term removed and its coeffecient made into unity by diving both sides as necessary) never gets bigger than one. But I don't know if that's in fact true.
     
  2. jcsd
  3. Dec 18, 2009 #2

    Borek

    User Avatar

    Staff: Mentor

    Square root? I guess you are using

    [tex]x_{n+1} = \frac 1 2 (x_n + \frac a {x_n})[/tex]

    and xn is approximation of square root of a?

    As far as I remember this is variant of the Newton method, and Newton method works only if derivative of the function between starting point and solution is larger than 1. Or something close to that, could be it depends on the side from which you approach the solution, my imagination went on strike.
     
  4. Dec 18, 2009 #3
    Unfortunately, LaTeX is no longer displaying correctly on this old computer of mine so I'll have to just type the characters and hope they appear correctly.

    The program starts with the relationship

    [tex]


    \frac {1}{h} = \frac {1}{\sqrt{l^2 - w^2}} + \frac {1}{\sqrt{s^2 - w^2}}


    [/tex]

    where h is the intersection height, l and s and the lengths of the long and short ladders respectively, and w is the width between the buildings.

    It rearranges this to

    [tex]

    w^2 = s^2 - ( \frac {1}{h} - \frac {1}{\sqrt{l^2 - w^2}} ) ^ {-2}

    [/tex]

    Then it starts with a guess value for [itex] w^2 [/itex], puts that into the right side of the equation to produce a new [itex] w^2 [/itex], plugs that back into the [itex] w^2 [/itex] on the right, and so on. After about ten cycles it takes the square root of the last value [itex] w^2 [/itex] it found, and that's the approximate value of [itex] w [/itex].

    Since this is of the form [itex] a_{n+1} = f (a_n) [/itex] (where [itex] w^2 [/itex] is the [itex] a [/itex]), it's an example of fixed point iteration as I understand it.
     
    Last edited: Dec 18, 2009
  5. Dec 19, 2009 #4
    Fixed point iteration will converge provided the function involved decreases distances. More precisely, the condition is that

    [tex]|f(x) - f(y)| < k \; |x - y|[/tex] for all x, y
    for some [tex]k < 1[/tex].

    Another test that guarantees convergence is that [tex]|f'(x)| < k[/tex] for some [tex]k < 1[/tex].
     
  6. Dec 20, 2009 #5
    Thanks awkward; that's about what I suspected.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook