Restrictions and Max Error Estimate ●Restrictions function slices x-axis at root start with two points a and b f(a)f(b)<0 graphing tool (e.g.,Matlab)can help to find a and b require co[a,(why?note:not a big deal) ●Max error estimate after n steps,guess midpoint of current range *error::e≤2n号((think of=0,1,2) note:error is in x;can also look at error in f(x)or combination enters entire world of stopping criteria Question:Given tolerance (in z),what is n?... Copyright©2011，NA⊙Yin Last Modification:Oct.2011
Restrictions and Max Error Estimate • Restrictions ∗ function slices x-axis at root ? start with two points a and b 3 f(a)f(b) < 0 ? graphing tool (e.g., Matlab) can help to find a and b ∗ require C 0 [a, b] (why? note: not a big deal) • Max error estimate ∗ after n steps, guess midpoint of current range ∗ error: ≤ b−a 2n+1 (think of n = 0, 1, 2) ∗ note: error is in x; can also look at error in f(x) or combination ? enters entire world of stopping criteria Question: Given tolerance (in x), what is n? · · · Copyright c 2011, NA Yin Last Modification: Oct. 2011 7
Convergence Rate Given tolerance T (e.g.,10-6),how many steps are needed? Tolerance restriction (e from before): b-a (e≤2n+)<r ●log(any base) log(b-a)-n log 2<log 2r or 1og(b-a)-log2r n> log 2 Rate is independent of function. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 8
Convergence Rate • Given tolerance τ (e.g., 10−6 ), how many steps are needed? • Tolerance restriction ( from before): ( ≤ b − a 2 n+1 ) < r • log (any base) log(b − a) − n log 2 < log 2r or n > log(b − a) − log 2r log 2 Rate is independent of function. Copyright c 2011, NA Yin Last Modification: Oct. 2011 8
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
Bisection convergence not linear (examples?),but compared to init.max error: similar form:n+1<Cn+1(b-a),with C= Okay,but restrictive and slow. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 10
• Bisection convergence ∗ not linear (examples?), but compared to init. max error: ∗ similar form:|xn+1 − r| ≤ C n+1(b − a), with C = 1 2 Okay, but restrictive and slow. Copyright c 2011, NA Yin Last Modification: Oct. 2011 10