Convergence Rate (cont.) .Base 2 (i.e.,bites of accuracy) n>log2(6-a)-1-10g2r i.e.,number of steps is a constant plus one step per bit ●Linear convergence rate:]C∈0，l) xn+1-r≤Cxm-rl,n≥0 i.e.,monotonic decreasing error at every step,and lzn+1-r≤Cm+lzo-rl Copyright©2011，NA⊙Yin Last Modification:Oct.2011 g Convergence Rate (cont.) • Base 2 (i.e., bites of accuracy) n > log2 (b − a) − 1 − log2 r i.e., number of steps is a constant plus one step per bit • Linear convergence rate: ∃C ∈ [0, 1) |xn+1 − r| ≤ C|xn − r|, n ≥ 0 i.e., monotonic decreasing error at every step, and |xn+1 − r| ≤ C n+1|x0 − r| Copyright c 2011, NAYin Last Modification: Oct. 2011 9