Indeedなう E - Page Rank

• 問題
• AC

全部$1$のベクトルからスタートして、漸化式を1000回くらい回せば収束する。

正当性があまりわかってない。漸化式中の行列を$A$としたとき、つまり$PR = 0.1 + A \cdot PR$としたとき、

1. $A$の列毎の絶対値の和が$1$未満なので$\| A \|_1 <1$。$1$ノルムについては$\|A^p\| \le \|A\|^p$が成り立つ。したがって$\lim_{p \rightarrow \infty} A^p$は収束するので漸化式も収束する。（本当に？）¹
2. 収束するなら極限は漸化式の不動点になるから、漸化式を回すだけでよい。

くらいでわかった気になっておいた。

---

1. 式変形で非正則な行列が出てこなければ大丈夫そう。非正則な場合は知らない。 ↩︎