Given $$x_k=(I-aP)x_{k-1}-aq$$ I need to prove that it is equal to $$x_k=(I-aP)x_0-kaq$$
Asked
Active
Viewed 55 times
0
-
did you try anything? – Arnaldo Mar 24 '17 at 14:10
-
In order to improve your question use: https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference – Arnaldo Mar 24 '17 at 14:10
-
writting down all equations up to x(0) and then sum them all together – someoneOutThere Mar 24 '17 at 14:11
-
and i get x(k)=(I-aP)x(0)-kaq-aP(x(k-1)+x(k-2)+...+x(1)) – someoneOutThere Mar 24 '17 at 14:16
-
You should write in your question what you have tried, so that people can help you more efficiently. See also http://math.stackexchange.com/help/how-to-ask. – Arnaud D. Mar 24 '17 at 14:17
-
1This relationship is false. – Jean Marie Mar 24 '17 at 14:25
-
If you have a correct formula for the answer, you can prove it by induction. – GEdgar Mar 24 '17 at 14:36
-
Is $I-ap$ idempotent? – J.G. Mar 24 '17 at 14:39
-
P is positive definite – someoneOutThere Mar 24 '17 at 14:42
2 Answers
1
Hint: Let $x_k=y_k+b$ and then $$ y_k+b=(I-aP)(y_{k-1}+b)-aq $$ Try to get a condition for $b$ such that $y_k=(I-aP)y_{k-1}$.
xpaul
- 44,000
1
$$x_1=(I-aP)x_{0}-aqI\\ x_2=(I-aP)x_{1}-aqI\\ x_3=(I-aP)x_{2}-aqI\\ ...\\ x_{k-1}=(I-aP)x_{k-2}-aqI\\ x_k=(I-aP)x_{k-1}-aqI$$
From that you can multiply equation $i$ by $(I-aP)^{k-i}$ and write:
$$(I-aP)^{k-1}x_1=(I-aP)^{k}x_{0}-(I-aP)^{k-1}aq\\ (I-aP)^{k-2}x_2=(I-aP)^{k-1}x_{1}-(I-aP)^{k-2}aq\\ (I-aP)^{k-3}x_3=(I-aP)^{k-2}x_{2}-(I-aP)^{k-3}aq\\ ...\\ (I-aP)x_{k-1}=(I-aP)^2x_{k-2}-(I-aP)aq\\ x_k=(I-aP)x_{k-1}-aqI$$
Now you can sum every equation and get:
$$x_k=(I-aP)^{k}x_0-aq[I+(I-aP)+(I-aP)^2+...(I-aP)^{k-1}]$$
We also have:
$$[I+(I-aP)+(I-aP)^2+...(I-aP)^{k-1}][I-(I-aP)]=I-(I-aP)^k$$
If $P^{-1}$ exist and $a\ne 0$ then
$$I+(I-aP)+(I-aP)^2+...(I-aP)^{k-1}=\frac{1}{a}P^{-1}[I-(I-aP)^k]$$
Finaly the equation would be
$$x_k=(I-aP)^{k}x_0-qP^{-1}[I-(I-aP)^k]$$
PS.: The relation that you are trying to prove is FALSE.
Arnaldo
- 21,342
-
question about your last two lines,you are summing matices,so does the relation you wrote holds? – someoneOutThere Mar 24 '17 at 14:32
-
1
-
-
@Mika10: please take another look. The solution depends on $a$ and $P$ as I wrote. Need time, please, try to write a full statement. – Arnaldo Mar 24 '17 at 14:45
-
Full task: Consider the subgradient method with constant step size a,uesd to minimize the quadratic function f(x)=1/2(x(trasposed)Px+q(transposed)x,P is positive semidefinite matrix.For which values of a do we have convergence? What values of a give the fastest asymptotic convergence? – someoneOutThere Mar 24 '17 at 14:53
-
Each iteration od subgradient is x(k+1)=x(k)-a(Px(k)+q)=(I-aP)x(k)-aq. – someoneOutThere Mar 24 '17 at 14:54