Lecture note 2 Numerical Analysis Stopping criteria (I)Select a maximum iteration number N.We stop the iteration after N itera- tions. (II)Select a small tolerance e>0.We stop the iteration whenever one of the following is met. 1.The error is small enough (a)Absolute error,lp-pnl<c. (b)Relative error etc. IPl But we don't know p before we find it! 2.The residual is small enough (a)absolute lf(pn)<e. (b)relative<etc. But If(pn)is small the relative error Ipn-pl is small. Example::f(x)=(x-1)10,p=1,andp:=1+1/n.fp2)≤9.8×10-4 but lp2 -pl =0.5. 3.The difference between successive iterations is small enough (a)absolute Ipn -Pn-1l<c. (b)relativeap<,and pn0. But Ipn-Pn-1 converges to zero Pn converges.Counter example: pn=∑i=i(/).lpm-pn-i→0 but p diverges.. Which one is best?It depends! For safety (to avoid infinite loops),we use:when (I)OR (II)is met,we stop. Of course,the algorithm might fail when (I)is met. Convergence and Error estimate Theorem 1 (Theorem 2.1 in the textbook)Suppose -fECla,]. -f(a)f(b)<0. Then the sequence pn generated by the bisection method satisfies pn-p< where p is a zero of f in (a,b). Proof. bn-an=5bn-1-an-1） 11 =互2bm-2-am-2）=2z6m-2-am-2） (1.1) 1 1 -2nb1-a1）=2mb-a 4Lecture note 2 Numerical Analysis Stopping criteria (I) Select a maximum iteration number N. We stop the iteration after N itera￾tions. (II) Select a small tolerance ǫ > 0. We stop the iteration whenever one of the following is met. 1. The error is small enough (a) Absolute error, |p − pn| < ǫ. (b) Relative error |p−pn| |p| < ǫ, |p−pn| |p−p1| < ǫ, etc. But we don’t know p before we find it! 2. The residual is small enough (a) absolute |f(pn)| < ǫ. (b) relative |f(pn)| |f(p0)| < ǫ etc. But |f(pn)| is small 6=⇒ the relative error |pn − p| is small. Example: f(x) = (x − 1)10 , p = 1, and pi = 1 + 1/n. f(p2) ≤ 9.8 × 10−4 but |p2 − p| = 0.5. 3. The difference between successive iterations is small enough (a) absolute |pn − pn−1| < ǫ. (b) relative |pn−pn−1| |pn| < ǫ, and pn 6= 0. But |pn − pn−1| converges to zero 6=⇒ pn converges. Counter example: pn = Pn i=1(1/i). |pn − pn−1| → 0 but pn diverges. • Which one is best? It depends! • For safety (to avoid infinite loops), we use: when (I) OR (II) is met, we stop. Of course, the algorithm might fail when (I) is met. Convergence and Error estimate • Theorem 1 (Theorem 2.1 in the textbook) Suppose – f ∈ C[a, b]. – f(a)f(b) < 0. Then the sequence pn generated by the bisection method satisfies |pn−p| ≤ b−a 2n , where p is a zero of f in (a, b). Proof. bn − an = 1 2 (bn−1 − an−1) = 1 2 · 1 2 (bn−2 − an−2) = 1 2 2 (bn−2 − an−2) . . . = 1 2 n−1 (b1 − a1) = 1 2 n−1 (b − a) (1.1) 4