数值分析2(二分法)

1、1/19化大为小化大为小 化繁为简化繁为简 化难为易化难为易 核心的概念核心的概念 误差误差算法的构造与分析算法的构造与分析 病态性病态性 收敛性收敛性 稳定性稳定性 复杂性复杂性8:03非线性方程非线性方程二分法迭代二分法迭代数值分析28:033/19GPS (Global Positioning System)和和LBS (Location Based Service)4/19xyz位置位置收到信号时间收到信号时间 S13,2,310 010.006 922 86S21,3,110 013.342 563 81S35,7,410 016.678 204 76 S41,7,310 020.0

2、13 845 71S57,6,710 023.349 486 66S61,4,910 030.020 768 578:035/19Ref: Timothy Sauer, Numerical Analysis2222222222222222222(3)(2)(3)(1)(3)(1)(5)(7)(10010.00692286)10013.34256381)10016.67820476)4)(1)(7)(3)10020.(7)01384571)1002(6)(7)(3dxyzxyzxyzcd cdxycxyzd cz 22222(1)(4)(9).34948666)10030.02076857)(d

3、 cd cxyz ( , , , )x y z t其其中中表表示示点点的的当当前前位位置置。8:036/19 非线性科学是当今科学发展的一个重要研究非线性科学是当今科学发展的一个重要研究方向方向, ,其中非线性方程的求根是一个不可或缺的其中非线性方程的求根是一个不可或缺的研究内容。但是非线性方程的求根非常复杂。研究内容。但是非线性方程的求根非常复杂。高于高于次的代数方程次的代数方程, ,不存在通用的求根公式不存在通用的求根公式超越方程一般很难直接求出其准确解超越方程一般很难直接求出其准确解01( ) (0)nnnf xaa xa xa( )cos()xf xex 8:03例例: :7/19求求

4、 f (x)= 0 根的问题包括如下方面根的问题包括如下方面: :根的存在性根的存在性, ,即即f(x)=0有没有根有没有根? ? 若有若有, ,有有 几个根几个根? ?根的范围根的范围, ,确定有根区间确定有根区间根的精度根的精度, ,已知一个根的近似值后已知一个根的近似值后, ,能否能否 将它精确到足够精度将它精确到足够精度? ?8:03Where is Flight MH370?8/19定理定理2(零点定理零点定理) 若函数若函数f在闭区间在闭区间 a, b 上上连续连续, ,且且f(a)与与f(b)异号异号, , 则至少存在一点则至少存在一点 x0 0属于属于(a, ,b), ,使得使

5、得f(x0 0)=0, ,即方程即方程f(x)=0在在(a, ,b)内内至少有一个根至少有一个根。 零点定理回答了根的存在性和根的范围的零点定理回答了根的存在性和根的范围的问题问题, ,如何去寻找足够精度的根？如何去寻找足够精度的根？8:039/19游戏游戏: :模仿幸运模仿幸运52请同学们请同学们猜测这猜测这部电部电脑的价格？脑的价格？8:03化大为小8:03a0,b0 x0=0.5(a 0 +b 0)a1,b1=a 0,x0a1,b1=x0,b0 x1=0.5(a1+b1)已知已知f(x)=0在在a0,b0内有一根内有一根,且且f(a0)f(b0)0(2)判断若判断若f(xn-1) f(a

6、n-1)0,则则anan-1,bn xn-1 否则否则 anxn-1, bnbn-1x0 x1 二分法迭代二分法迭代8:03(1)计算计算 xn-1=0.5(an-1+bn-1)和和f(xn-1) 判断若判断若f(xn-1)=0,则则xn-1是根是根,否则转下一步否则转下一步;二分法迭代将得到一系列区间序列二分法迭代将得到一系列区间序列 001122,nna ba ba ba b 定理定理2.2 设设x*是是 f(x)=0在在a 0, b 0内的唯一根内的唯一根,且且 f(a 0)f(b 0)0,则二分过程中则二分过程中,各区间的中点数列各区间的中点数列 ), 2 , 1 , 0( )(21

7、nbaxnnn性质性质:1. f(an)f(bn)0; 2. bn an = (b0 a0)/ 2n满足满足 | xn x*| (b 0 a 0)/ 2n+10023log10ban 300111022nba 只需只需3*1021| xxn注记注记: 若要若要8:03例例 1 二分法求方程二分法求方程 在区间在区间 0, 1内的根内的根。 函数在函数在0,1内有唯一零点内有唯一零点, 故故0,1是隔根区间。是隔根区间。esin()02xx 解解: 令令( )esin()2xxf x 01)0( f01)1(1 ef( )ecos()0, 0122xxfxx 0)1()0( ff8:0314/1

8、9n函数值符号函数值符号区间区间1f(0.5)= - 0.100600.25,0.53f(0.375)=0.131700.375,0.54f(0.4375)=0.01130 0.4375,0.5x4=0.5(0.4375+0.5)=0.4688作为近似值作为近似值, 误差误差不超过不超过1/(25) 。 8:0315/19 二分法思想朴素却蕴含了迭代法的近二分法思想朴素却蕴含了迭代法的近似逼近思想。似逼近思想。 思想简单思想简单, 仅需函数值符号仅需函数值符号, 容易实现。容易实现。二分法的反思二分法的反思: :收敛速度慢收敛速度慢和和不能求复根等不足。不能求复根等不足。function ro

9、ot = bisect(func,x1,x2,filter,tol)for i = 1:n x3 = 0.5*(x1 + x2); f3 = feval(func,x3); if f3 = 0 root = x3; return end if f2*f3 0 x1 = x3; f1 = f3; else x2 = x3; f2 = f3; endend16/19 Iteration in mathematics may refer to the process of iterating a function i.e. applying a function repeatedly, using

10、the output from one iteration as the input to the next. Iteration of apparently simple functions can resolve complex and difficult problems. 迭代的思想迭代的思想 迭代法是一种逐次逼近法迭代法是一种逐次逼近法, , 这种方法使用某这种方法使用某个固定公式反复校正根的近似值个固定公式反复校正根的近似值, , 使之逐步精使之逐步精确化确化, , 最后得到满足精度要求的结果。最后得到满足精度要求的结果。11-1-111110.5(), () ()00.5(),

11、() ()0nnnnnnnnnxaf xf axxbf xf b 如如果果如如果果001()*2|nbanxx 17/19苹果成功的原因苹果成功的原因http:/ a small number of things, and does them very well;Religiously defends its focus;Only makes a product if they have a cohesive strategy behind it;Kills products that dont work out, so they can focus on what does;Comes out with industry-shaking new products, then makes constant, incremental improvements to them.Takeaway: Once simplify the number of elements in your life and concentrate on fewer things, start to make small, incremental improvements to thos