d(fn(x),fn+1(x))≤qnd(x,f(x)) - can show by induction.
∀m>n,d(fn(x),fm(x))≤qn+qn+1+…+qm−1≤qn1−q→n→∞0
Therefore, fn(x) is a Cauchy sequence, and since (X, d) is complete, it must have a limit in X. Suppose y=limn→∞fn(x) . Then d(y,fn+1(x))≤qd(y,fn(x)) , therefore d(y,fn(x))≤qnd(x,y)
#2
Suppose y=limn→∞fn(x) . Let’s show that y is a fixed point. Indeed, for any n, d(fn(x),f(y))≤qd(fn+1(x),y) , and if we take the limit in both sides, we get d(y,f(y))≤qd(y,y)=0 .
Let’s show uniqueness: suppose x and y are fixed points, then d(x,y)=d(f(x),f(y))≤qd(x,y) , therefore d(x,y) = 0.
#3
X=[1,+∞) , f(x) = x + 1/x.
#4
Suppose f(x)=ϵ||x||2+h(x) , where h is some convex function and ϵ<1/2. Take x,y∈Rn. Since h is convex on segment [x,y], its directional derivative is nondecreasing. Its directional derivative is a projection of gradient of g on the [x,y] line. Therefore, we have ⟨∇h(y),y−x⟩≥⟨∇h(x),y−x⟩ , or ⟨∇h(y)−∇h(x),y−x⟩≥0 . Hence,
Therefore, g is a contraction mapping, and from problem 1 it follows that the gradient descent converges exponentially quickly.
#5
Suppose A is an NxN positive matrix, and e is its minimal entry. (Then e < 1/N). Then we can write A = eJ + (1 - Ne)Q, where J is a matrix whose entries are all 1, and Q is a matrix whose entries are all nonnegative and the sum of each column is 1 (because the sum of each column is 1 in A and Ne in J). Suppose x and y are probability distributions, i.e. N-dimensional vectors with nonnegative entries whose sum is 1. Then ||Ax−Ay||1=||eJ(x−y)+(1−Ne)Q(x−y)||1=(1−Ne)||Q(x−y)||
Denote x+=max(x−y,0) , x−=min(x−y,0) (pointwise max/min). Then x−y=x+−x− ,||Q(x−y)||1=||Qx+−Qx−||1≤||Qx+||1+||Qx−||1=||x+||1+||x−||1=||x−y||1 ,
so ||Ax−Ay||1≤(1−Ne)||x−y||1 . The space of all probability distributions with metric induced by—||.||1norm is a compact subset of Rn, so it is a complete metrics space, therefore, the sequence An(x) converges to a unique fixed point.
#6
Let us assume x≤f(x) (the proof for x≥f(x) is the same). Then, from monotonicity of f, x≤f(x)≤f(f(x))≤… is an ascending chain. This sequence cannot have more that |P| distinct elements, so an element of this sequence is going to repeat: fm(x)=fn(x),m<n,m<|P| . Then all the inequalities in fm(x)≤fm+1(x)≤…≤fn(x) must be equalities, so f(fm(x))=fm(x) , fm(x) is a fixed point.
#1
d(fn(x),fn+1(x))≤qnd(x,f(x)) - can show by induction.
∀m>n,d(fn(x),fm(x))≤qn+qn+1+…+qm−1≤qn1−q→n→∞0
Therefore, fn(x) is a Cauchy sequence, and since (X, d) is complete, it must have a limit in X. Suppose y=limn→∞fn(x) . Then d(y,fn+1(x))≤qd(y,fn(x)) , therefore d(y,fn(x))≤qnd(x,y)
#2
Suppose y=limn→∞fn(x) . Let’s show that y is a fixed point. Indeed, for any n, d(fn(x),f(y))≤qd(fn+1(x),y) , and if we take the limit in both sides, we get d(y,f(y))≤qd(y,y)=0 .
Let’s show uniqueness: suppose x and y are fixed points, then d(x,y)=d(f(x),f(y))≤qd(x,y) , therefore d(x,y) = 0.
#3
X=[1,+∞) , f(x) = x + 1/x.
#4
Suppose f(x)=ϵ||x||2+h(x) , where h is some convex function and ϵ<1/2. Take x,y∈Rn. Since h is convex on segment [x,y], its directional derivative is nondecreasing. Its directional derivative is a projection of gradient of g on the [x,y] line. Therefore, we have ⟨∇h(y),y−x⟩≥⟨∇h(x),y−x⟩ , or ⟨∇h(y)−∇h(x),y−x⟩≥0 . Hence,
||x−∇f(x)−y+∇f(y)||=||x−2ϵx−∇h(x)−y−2ϵy+∇h(y)||≤(1−2ϵ)||x−y||
Therefore, g is a contraction mapping, and from problem 1 it follows that the gradient descent converges exponentially quickly.
#5
Suppose A is an NxN positive matrix, and e is its minimal entry. (Then e < 1/N). Then we can write A = eJ + (1 - Ne)Q, where J is a matrix whose entries are all 1, and Q is a matrix whose entries are all nonnegative and the sum of each column is 1 (because the sum of each column is 1 in A and Ne in J). Suppose x and y are probability distributions, i.e. N-dimensional vectors with nonnegative entries whose sum is 1. Then ||Ax−Ay||1=||eJ(x−y)+(1−Ne)Q(x−y)||1=(1−Ne)||Q(x−y)||
Denote x+=max(x−y,0) , x−=min(x−y,0) (pointwise max/min). Then x−y=x+−x− ,||Q(x−y)||1=||Qx+−Qx−||1≤||Qx+||1+||Qx−||1=||x+||1+||x−||1=||x−y||1 ,
so ||Ax−Ay||1≤(1−Ne)||x−y||1 . The space of all probability distributions with metric induced by—||.||1norm is a compact subset of Rn, so it is a complete metrics space, therefore, the sequence An(x) converges to a unique fixed point.
#6
Let us assume x≤f(x) (the proof for x≥f(x) is the same). Then, from monotonicity of f, x≤f(x)≤f(f(x))≤… is an ascending chain. This sequence cannot have more that |P| distinct elements, so an element of this sequence is going to repeat: fm(x)=fn(x),m<n,m<|P| . Then all the inequalities in fm(x)≤fm+1(x)≤…≤fn(x) must be equalities, so f(fm(x))=fm(x) , fm(x) is a fixed point.