中国科学技术大学：《计算方法》课程教学课件（PPT讲稿）第4章 非线性方程求根

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第4章非线性方程求根 非线性科学是当今科学发展的一个重要研究方向，而非线性 方程的求根也成了一个不可缺的内容。但是，非线性方程的求根 非常复杂。 通常非线性方程的根的情况非常复杂： a=1 无解 sin( a= 一个解 无穷组解 Jy=x2+a 4 lx=y2+a a=0 两个解 y= a=-1 四个解

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第4章 非线性方程求根 非线性科学是当今科学发展的一个重要研究方向，而非线性 方程的求根也成了一个不可缺的内容。但是，非线性方程的求根 非常复杂。 通常非线性方程的根的情况非常复杂：      = = 2 1 ) 2 sin( y x y  无穷组解        = − = = =     = + = + 1 0 4 1 1 2 2 a a a a x y a y x a 无解 一个解 两个解 四个解

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 所以，只在某个区域内可能解存在唯一，而且经常很简单的 形式得不到精确解： e*-1=cos(x) 因此，通常我们用迭代法解非线性方程 看迭代法之前，先看看一种简单直观的方法 原理：f(a)f(b)<0→3x,s.t,f(x)=0

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 所以，只在某个区域内可能解存在唯一，而且经常很简单的 形式得不到精确解： 因此，通常我们用迭代法解非线性方程 看迭代法之前，先看看一种简单直观的方法 原理： f (a) f (b)  0  x,s.t., f (x) = 0 e 1 cos( x) x − = 

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 4.1对分法 什么时候停止？ 缸 x 2 x+-<或f(x)<2

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 4.1对分法 a b x1 x2 a b 什么时候停止？ 1 1 x x ε k+ − k  2 或 f (x)  ε x*

中图 科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 算法 While(la-bl>eps) x=(a+b)/2 fx刈 若(Ifx<eps)x为解 若f*fb)<0修正区间为x,b 若f(a)*fx<0修正区间为a,刈 End while 每次缩小一倍的区间，收敛速度为1/2，较慢，且只能求 一个根，使用条件限制较大 不能保证x的精度

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS While(|a-b|>eps) x=(a+b)/2 f(x) 若(|f(x)|<eps) x为解 若f(x)*f(b)<0 修正区间为[x,b] 若f(a)*f(x)<0 修正区间为[a,x] End while 每次缩小一倍的区间，收敛速度为1/2，较慢，且只能求 一个根，使用条件限制较大 算法  2 x* x 不能保证 x 的精度

中图科堂技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 4.2迭代法 等价变换 fx)=0 x=g(x) f(x)的根 g(心)的不动点 从一个初值x出发，计算x1=go),x2=gc1), 思 x+1=g化，.若{x收敛，即存在*使得 路 mxk=x*,且g连续，则由mxk+1=阿( gc*),即x*是g的不动点，也就是f的根

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 4.2 迭代法 f (x) = 0 x = g (x) 等价变换 f (x) 的根 g (x) 的不动点 思 路 从一个初值 x0 出发，计算 x1 = g(x0 ), x2 = g(x1 ), ., xk+1 = g(xk ), . 若 收敛，即存在 x* 使得 ，且 g 连续，则由 可知 x* = g(x* )，即x* 是 g 的不动点，也就是f 的根。    k k=0 x lim x x * k k = → ( ) k k k k x g x → + → lim 1 = lim

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 迭代法的基本步骤如下： 1、给出方程的局部等价形式f(x)=0台x=p(x) 2、取合适的初值，产生迭代序列，x+1=(x) 3、 求极限x*=limx,易知，该值为方程的根 一定收敛吗？

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 迭代法的基本步骤如下： 1、给出方程的局部等价形式 f (x) = 0  x =(x) 2、取合适的初值，产生迭代序列 , ( ) 0 i 1 i x x = x + 3、求极限 n n x x →+ * = lim 易知，该值为方程的根 一定收敛吗？

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS y=x y=x y=g(x) J=g田) X X X

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS x y y = x x* y=g(x) x0 p0 x1 p1 ✓ x y y = x x* y=g(x) x0 p0 x1 p1 

中图 科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 定理 p(x),x∈[a,b]若满足： 1、a≤p(x)≤b,x∈[a,b] 2、p(x)可导，且存在正数L<1,使得对任意的x,有 p'(x)≤L 则有： 1、存在唯一的点x*,x*=p(x*) 2、x,∈[a,b]迭代收敛，且有误差估计 x*-x≤1 -

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS (x), x[a,b] 若满足： 1、 a (x)  b, x[a,b] 2、 (x) 可导，且存在正数L<1，使得对任意的x，有 '(x)  L 则有： 1、存在唯一的点 x*, x* =(x*) 2、 x a,b  0  迭代收敛，且有误差估计 1 0 1 * x x L L x x k k − − −  定理

中图科亨技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 证明： ①存在唯一性 做辅助函数w(x)=x-p(x),则有w(a)≤0，w(b)≥0 所以，存在点x*,S.t,w(x*)=0→x*=p(x*) 若x*=p(x**),则有： x*-x*剂=p(x*)-p(x*=p'(5(x*-x*)≤Lx*-x*州 又，L<1→x*=X** ②x∈[a,b]则 Xk+1-x*=p(x)-p(x*)=0'(5)(x-x*) x1-x剂≤Lx-x剂≤.≤L+xo-x*剂 所以，任意的初值都收敛

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS ①存在唯一性 ② 做辅助函数  (x) = x −(x) ，则有  (a)  0, (b)  0 所以，存在点 x*,s.t., (x*) = 0  x* =(x*) 若 x** =(x**) ，则有： x*−x** = (x*)−(x**) = '()(x*−x**)  L x*−x** 又， L 1  x*= x** [ , ] x0  a b 则 * ( ) ( *) '( )( *) 1 x x x x x x k+ − = k − =  k − * * 0 * 1 1 x x L x x L x x k k −  k −   − + +  所以，任意的初值都收敛 证明：

中图科学技术大学数学系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS ③误差估计 xk+1-xx=p(xx)-p(xk-≤LXk-Xk-≤.≤LX1-x xp-x≤+p-k+p-++1-x ≤（亿+p1++Lx-x 小 由p的任意性，令卫→+o0 *5- 证毕

数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS ③误差估计 1 1 1 1 0 x x (x ) (x ) L x x L x x k k+ − k =  k − k−  k − k−  − k p k k p k p k k  x − x  x − x + + x − x + + + −1  +1 ( ) 1 0 1 L L x x k p k  + + − + +  ( ) 1 0 1 0 1 1 1 x x L L x x L L L k p k − − −  − − = 由p的任意性，令 1 0 1 * x x L L x x k k − − −  p →+ 证毕