Nonlinear Equations →Motivation ●Bisection Method ·Newton's Method ·Secant Method ●Summary Copyright©2011，NA⊙Yin Last Modification:Oct.2011 2
Nonlinear Equations ⇒ Motivation • Bisection Method • Newton’s Method • Secant Method • Summary Copyright c 2011, NA Yin Last Modification: Oct. 2011 2
Motivation .For a given function f(),find its root(s),i.e.: =find x (or r=root)such that f(x)=0 ·BVP:dipping of suspended power cable.What isλ？ 入cosh 50-λ-10=0 (Some)simple equations=solve analytically 6x2-7x+2=0c0s3x-c0s7x=0 (3x-2)(2x-1)=02sin5xsin2x=0 x= x=,暨，n∈Z Copyright©2011，NAOYin Last Modification:Oct.2011 3
Motivation • For a given function f(x), find its root(s), i.e.: ⇒ find x (or r=root) such that f(x) = 0 • BVP: dipping of suspended power cable. What is λ? λ cosh 50 λ − λ − 10 = 0 • (Some) simple equations ⇒ solve analytically 6x 2 − 7x + 2 = 0 cos 3x − cos 7x = 0 (3x − 2)(2x − 1) = 0 2 sin 5x sin 2x = 0 x = 2 3 , 1 2 x = nπ 5 , nπ 2 , n ∈ Z Copyright c 2011, NA Yin Last Modification: Oct. 2011 3
Motivation(cont.) In genetal,we cannot exploit the function,e.g.: 22-10x+1=0 and cosh(Vz2+1-e)+log sinx=0 Note:at times 3 multiple roots e.g.,previous parabola and cosine we want at least one we may only get one(for each search) Need a general,function-independent algorithm. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 4
Motivation(cont.) • In genetal, we cannot exploit the function, e.g.: 2 x 2 − 10x + 1 = 0 and cosh(p x 2 + 1 − e x ) + log |sin x| = 0 • Note: at times ∃ multiple roots ∗ e.g., previous parabola and cosine ∗ we want at least one ∗ we may only get one(for each search) Need a general, function-independent algorithm. Copyright c 2011, NA Yin Last Modification: Oct. 2011 4
Nonlinear Equations ●Motivation →Bisection Method ●Newton's Method ·Secant Method Summary Copyright 2011,NAOYin Last Modification:Oct.2011 5
Nonlinear Equations • Motivation ⇒ Bisection Method • Newton’s Method • Secant Method • Summary Copyright c 2011, NA Yin Last Modification: Oct. 2011 5
Bisection Method-Example 3 2 anjen uonounj 1 0 -1 -3 -4 -5 T2 43 1 0 b Intuitive,like guessing a number∈[0，l00l. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 6
Bisection Method–Example Intuitive, like guessing a number ∈ [0, 100]. Copyright c 2011, NA Yin Last Modification: Oct. 2011 6
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+) 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 ) 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
Exercise 1.Find where the graphs of y=3x and y =e2 intersect by finding roots of e2-3x =0 correct to four decimal digits. 2.If a =0.1 and 6=1.0,how many steps of the bisection method are needed to determine the roots with an error of at mostx 10-8? 3.Find a root of the equation 6(e-z)=6+3x2+2x3 between -1 and 1 using the bisection method. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 11
Exercise 1. Find where the graphs of y = 3x and y = e x intersect by finding roots of e x − 3x = 0 correct to four decimal digits. 2. If a = 0.1 and b = 1.0, how many steps of the bisection method are needed to determine the roots with an error of at most 1 2 × 10−8 ? 3. Find a root of the equation 6(e x − x) = 6 + 3x 2 + 2x 3 between −1 and 1 using the bisection method. Copyright c 2011, NA Yin Last Modification: Oct. 2011 11