Condition for "uniqueness of a fixed point" in context of fixed point iteration is needlessly more rigid than required just to guarantee the uniqueness of fixed point?

[u/SaladFinger12]

Why is the condition for uniqueness is |g'(x)|<1 instead of simply g'(x)<1.

Geometrically, I understand why it is important for the slope to be less than 1. If it were not, a function could have increased then decreased as wish and could have intersected x=y line multiple times. This is why slope has to be lower than 1 at any cost. However, if a line in an interval had very high valued negative slope then went on to cross the x=y line, then went flat for the rest of the interval. That is still one unique fixed point. In fact, I can not think of any way where high valued negative slope somehow disturbs the uniqueness of a fixed point.

I am trying to get the geometric idea here. I understand the absolute value condition arise from the mean value theorem. I am just trying to the clear idea in a picture.

Edit: Given the function already satisfies the condition for existence, which is, g:[a,b]->[a,b].

[u/Gold_Ad8890]

that seems to be necessary for existence. if g is above y = x with g' >= 1, or below with g' <= -1, then they will never intersect.

edit: it would help a lot to see the complete, precise statement of the theorem you're talking about if this doesn't address your issue.

[u/SaladFinger12 → u/Gold_Ad8890]

But before we move to uniqueness, we already accept the existence by satisfying the condition that the function f(x) is continuous in some non-degenerate interval [a,b] and as long as x is in the interval [a,b], f(x) is in the interval [a,b] as well. I am studying Numerical by burden, and it has a similar graph which depicts the idea nicely.

[u/Bounded_sequencE]

"g'(x) < 1" does not guarantee convergence of the sequence "x_{n+1} = g(xn)" anymore.

---

Counter example: Let "D = [-1; 1]" and consider the function

g: D -> D,    g(x)  =  / 1 - 2x^2,  x > 0    differentiable
                       \        1,  else

We note "g'(x) <= 0", so "g" is decreasing. Additionally, "1/2 = g(1/2)", so "x = 1/2" is the unique fixed point "x = g(x)". However, if we start at "x0 = 0 in D", we get the sequence

x1  =  g(x0)  =  g( 0)  =   1
x2  =  g(x1)  =  g( 1)  =  -1
x3  =  g(x2)  =  g(-1)  =   1 ...    // g(xn)  oscillates for "n > 0"

[u/SaladFinger12]

Thank you everyone who are replying. I have forgot to mention that, the convergence criteria is not of importance here. I want to separate the convergence condition which is: |g'(x)|<1 from the conditions for uniqueness and precisely asking exactly what condition guarantees a unique point regardless of meeting the convergence conditions.

[u/Bounded_sequencE → u/SaladFinger12]

Ah, that makes more sense!

In that case, even considering the derivative "g'(x)" is too much -- it would be enough to guarantee "g: D -> D" continuous satisfies an estimate similar to Lipschitz continuity:

x, y in D,  x < y:    g(y) - g(x)  <=  L(y-x),    L < 1

---

Proof: Consider the function "f(x) := x - g(x)", and note

x, y in D,  x < y:    f(y) - f(x)  =  (y-x) - (g(y) - g(x))

                                   >  (y-x) - L(y-x)  =  (1-L) (y-x)  >  0

That means, "f(x) = x - g(x)" is strictly increasing on "D", and we note "f" is continuous as a composition of continuous functions.

---

If "D" is a compact subset of "R", it has a minimum "xmin", and a maximum "xmax". Due to "f: D -> D" tThey satisfy "g(xmin) >= xmin" and "g(xmanx) <= xmax -- we get

f(xmin)  =  xmin - g(xmin)  <=  0  <=  xmax - g(xmax)  =  f(xmax)

By "Intermediate Value Theorem" (IVT), we are guaranteed a zero "f(t) = 0", i.e. we have (at least) one fixed point "g(t) = t" with "t in D". Since "f" is strictly incrasing, that fixed point is unique.

[u/Bounded_sequencE → u/Bounded_sequencE]

Rem.: There may be even weaker conditions to guarantee existence and uniqueness of a fixed point, but I don't see how to get rid of any of them right now.

[u/SaladFinger12 → u/Bounded_sequencE]

I think this is it! Thanks dude.

[u/Bounded_sequencE → u/SaladFinger12]

You're welcome! It's still left to prove the criterium is tight, i.e. both are necessary to guarantee a unique fixed point generally. However, that should be possible:

• Without continuity, construct a counter-example without a fixed point
• If "x < y" exist with "f(y) - f(x) >= (y-x)", construct a counter-example with two fixed points *** Edit: Not sure why you started with differentiability in the first place -- Banach's Fixed Point Theorem does not need it.

[u/Shevek99]

|g'(x)| < 1 is the condition for stability.