マルチグリッド法
特に最も細かい格子 N 1 {\displaystyle N_{1}} に関して
W 1 = W 2 + ρ K N 1 {\displaystyle W_{1}=W_{2}+\rho KN_{1}\,}
の関係が格子 k {\displaystyle k} 上での計算量に関して成り立つ。これらと N k = ρ k − 1 N 1 {\displaystyle N_{k}=\rho ^{k-1}N_{1}} の関係から、
W 1 = K N 1 ∑ p = 0 n ρ p {\displaystyle W_{1}=KN_{1}\sum _{p=0}^{n}\rho ^{p}}
が得られる。幾何級数を使えば、(有限の n {\displaystyle n} について)
W 1 < K N 1 1 1 − ρ {\displaystyle W_{1}<KN_{1}{\frac {1}{1-\rho }}}
なので、解は O ( N ) {\displaystyle O(N)} の計算時間で得られることが分かる。
Roman Wienands and Wolfgang Joppich:"Practical Fourier Analysis for Multigrid Methods", Chapman and Hall/CRC, ISBN 978-1584884927 (2004年).