计算方法非线性方程求解1课件.ppt

1、第二章第二章 非线性方程数值解非线性方程数值解 1 基础知识基础知识 求 f(x)=0 的根,其中f(x)为非线性函数。此类问题 在工程和科学计算中，此类问题广泛存在。有根区间。b为根，则称a,b区间内至少有一个0在a,若f(x)0的m重根。为f(x)*称xm为大于1的整数，则0,g(x*)g(x),x*)(xf(x)一步，若有为f(x)的零点。进*也称x为方程的根或解，*则称x0,使得f(x*)若存在x*,m 当f(x)为代数多项式时，称为代数方程，否则为超越方程。2 二分法二分法 原理：原理：若若 f Ca,b，且，且 f(a)f(b)0，则，则 f 在在(a,b)上必上必有一根。有一根。

2、abx1x2abx*11xxkk 2)(xf 2xx*误差分析：误差分析：第第1步产生的步产生的20bax有误差有误差20abx*|x第第 k+1 步产生的步产生的 xk 有误差有误差12kkabx*|x 对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k：2lnlnln121abkabk优点：优点：简单简单;对对f(x)要求不高要求不高(只要连续即可只要连续即可).缺点：缺点：无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 转（2）.x,否则置ax,b 则置0,若f(a)f(x)b)/2,(a（3）取x 则停止计算；,a)/2（2）若(b 精度要求；b,（1

3、）取有根区间a 二分法算法：9.计算结果如下表：得k ,a)/2-，有(b区间1,2内有根 0,f(a)f(b)5,f(b)1,f(a)2,b1,解：a.10，取精度要求在1,2内的实根 01xxf(x)用二分法求方程 例11k33 迭代法是数值计算中的一类重要方法，应用广泛。迭代法是一种重要的逐次逼近方法。这种方法用某个固定公式反复校正根的近似值，使之逐步精确化，最后得到满足精度要求的结果。2 迭代法迭代法等价变换为)(xx0)(xf*)(xxf的零点的不动点)(x*x由此也称为不动点迭代法，称为迭代函数。)(x迭代法的一般形式：.,1,0),(111ixxxxmiiiii为定常迭代。代。否

4、则变化，则称为非定常迭随若iii称为多步迭代法。,称为单步迭代法，若,若11mm)(01xx)(12xx,)(1kkxx,.迭代公式若 收敛，即存在 x*使得 ，且 连续，则由 可知 ，即 是 的不动点，也就是f 的根。0kkx*limxxkkkkkkxx limlim1*)(*xx*x从一个初值 出发，计算0 x的交点。与曲线直线迭代法的几何意义是求 (x)yxyxyy=xxyy=xxyy=xxyy=xx*x*x*x*x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1y=(x)y=(x)y=(x)y=(x)(I)当当 x a,b 时，时，(x)a,b；(II)0 L

5、 1 使得使得 则任取则任取 x0 a,b，由，由 xk+1=(xk)得到的序列得到的序列 收收敛于敛于 (x)在在a,b上的唯一不动点。并且有误差估计式：上的唯一不动点。并且有误差估计式：0kkx|11|*|1kkkxxLxx|1|*|01xxLLxxk (k=1,2,)k考虑方程考虑方程 x=(x),(x)Ca,b,若若|)()(|yxLyxb成立a,对yx定理定理1从一个初值 出发，计算则Newtons Method产生的序列 xk 收敛到f(x)在 a,b 的唯一根。由 Taylor 展开：对于给定的精度 ,可估计二分法所需的步数 k：（收敛的充分条件）设 f C2a,b，若由 Tay

6、lor 展开：求 f(x)=0 的根,其中f(x)为非线性函数。(k=1,2,)(3)将(x*x0)2 看成高阶小量，则有：用某个固定公式反复校正根的近似值，使之逐步精简单;三个迭代值组合的方法：迭代法是数值计算中的一类重要方法，应用广泛。考虑方程 x=(x),(x)Ca,b,若用某个固定公式反复校正根的近似值，使之逐步精”，”“。*xx*xx*xlim“存在极限且另有结论定理的所有结论均成立L.(x)均有b,a,x使对1,L0换为若本定理条件(II)k1kk注2注1。的收敛性以及误差估计在唯一性、迭代法结论包括：不动点的存闭性，压缩性;本定理的条件包括：封 不动点唯一不动点唯一反证：若不然，

7、设还有反证：若不然，设还有 ，则，则)(xx|,*|)(*)(|xxLxx|xx*0)1(|Lxx*而而xxL*1 当当k 时，时，xk 收敛到收敛到 x*？|*|kxx|)(*)(|1kxx0|*|.|*|01 xxLxxLkk令令xxxf)()(bxa)(,0)()(aaaf0)()(bbbf)(xf有根有根证明：证明：(x)在在a,b上存在不动点上存在不动点|11|*|1kkkxxLxx|*|*|*|*|11kkkkkkxxLxxxxxxxx|1|*|01xxLLxxkk|.|)()(|01111xxLxxLxxxxkkkkkkk*lim1xxxxxkkk*)(*)*)(lim*lim1

8、xxxxxxxxxkkkkkkk转（2）。1,k，置kN，则停止计算；否则（4）若k则停止计算；,|xx（3）若|);(x（2）计算x0;度要求，置k，最大迭代次数N和精（1）取初始点x算法：k1kk1k0并分析其收敛性。,要求误差不超过10内的一个实根，在1/2，ln2e2.用迭代法求方程x3x例ln2.e1/eee1/2 因而 ln2上单调递减,(x)在区间1/2 所以 ln2，1/2,x0,e(x)由于 性首先分析迭公式的收敛,e(x)其中迭代函数,0,1,k,e取迭代公式x 解：1/2xln2xxx1kk。由此也称为不动点迭代法，(I)当 xa,b 时，(x)a,b；原理：若 f Ca

9、,b，且 f(a)f(b)0，则 f 在(a,b)上必有一根。在整个a,b上 f”不变号且 f(x)0；三个迭代值组合的方法：引入：将非线性方程线性化 Taylor 展开(k=1,2,)其中 ，则其中 ，则在整个a,b上 f(x)0,f”(x)0；原理：若 f Ca,b，且 f(a)f(b)0，则 f 在(a,b)上必有一根。若 收敛，即存在 x*使得，在 x0 和 x 之间。f(a)f(b)0；代入公式，令实、虚部对应相等，可得（局部收敛性）设 f C2a,b，若 x*为 f(x)在a,b上的根，且 f(x*)0，则存在 x*的邻域 使得任取初值 ，Newtons Method产生的序列 x

10、k 收敛到x*，且满足无法求复根及偶重根只要 f(x*)0，则令引入：将非线性方程线性化 Taylor 展开连续注：事实上，定理3是充分必要的，即另有结论：.6,10)75.0(:;63,10)75.0(:,10.75.0,1|.|)|(|;|),1|,0(,|:);10(,|:81281800012020122101102111111limlimkxkxCCeeeeCeCeCeeCeCeeCCCeexCCeexkkkkkkkkkkkkkkkkkkkk须须要使误差小于取则：设差别：价迭代公式迭代步数的下面举例说明不同收敛两个迭代值组合的方法：三个迭代值组合的方法：取 x0 x*，将 f(x)在

11、 x0 做一阶Taylor展开:将(x*x0)2 看成高阶小量，则有：f(a)f(b)0；在整个a,b上 f(x)0,f”(x)0；迭代法是一种重要的逐次逼近方法。则Newtons Method产生的序列 xk 收敛到f(x)在 a,b 的唯一根。则任取x0 a,b，Newtons Method产生的序列 xk 从一个初值 出发，计算在整个a,b上 f(x)0,f”(x)0；由此也称为不动点迭代法，且 连续，则由 可知 ，即 是 的不动点，也就是f 的根。引入：将非线性方程线性化 Taylor 展开f(a)f(b)0；求复根 Newton 公式中的自变量可以是复数迭代法是数值计算中的一类重要方

12、法，应用广泛。原理：若 f Ca,b，且 f(a)f(b)0；由此也称为不动点迭代法，(k=1,2,)代入公式，令实、虚部对应相等，可得xyy=xy=g(x)x*x0P(x0,y0)y0 z01xP(y0,z0)000200012)(xyzxyxx3 牛顿法牛顿法引入：引入：将非线性方程线性化将非线性方程线性化 Taylor 展开展开取取 x0 x*，将将 f(x)在在 x0 做一阶做一阶Taylor展开展开:20000)(!2)()()()(xxfxxxfxfxf ，在在 x0 和和 x 之间。之间。将将(x*x0)2 看成高阶小量，则有：看成高阶小量，则有：)*)()(*)(0000 xx

13、xfxfxf )()(*000 xfxfxx xyx*x0)()(1kkkkxfxfxx （f C1，f(x*)0）单根情形定理定理1 （收敛的充分条件收敛的充分条件）设）设 f C2a,b，若，若f(a)f(b)0；则则Newtons Method产生的序列产生的序列 xk 收敛到收敛到f(x)在在 a,b 的的唯一根。唯一根。.;f(x),f(b)f(a);f(x),f(b)f(a);f(x),f(b)f(a);f(x),f(b)f(a)Ca,bf(x)0004000300020001 分以下四种 )2(),1(,情况：存在唯一根。证明：k.kkkxxx*),(kxxx*,xxx*.x)x

14、(x)f(x)f(!)f(x)f(xxx*.)x)(xf(!)(x-xf(x)f(xf(x*),x)f(x)f(xx x xx*,f(x*)f(x)f(xf(xa,b.,f(x)f(x)f(x),abf(a)f(b)(a,b),f(110112000000200000000010000121210000000).1定理定理2 （局部收敛性局部收敛性）设）设 f C2a,b，若，若 x*为为 f(x)在在a,b上的根，且上的根，且 f(x*)0，则存在，则存在 x*的邻域的邻域 使得任取初使得任取初值值 ，Newtons Method产生的序列产生的序列 xk 收敛到收敛到x*，且满足且满足*)

15、(xB*)(0 xBx *)(2*)()*(*lim21xfxfxxxxkkk .*0)(,lim,21210,0111221xllf)f(x)f(xxxlxlx,xxx*.x)x(x*)f(x)f(!)f(x)f(xxx*.)x)(x*f(!)(x-xf(x)f(xf(x*),x)f(x)f(xx x)f(xxx*kkkkkkkkkkkkkkkkkkkkkkkkkkkk证明：证明：Newtons Method 事实上是一种特殊的不动点迭代事实上是一种特殊的不动点迭代 其中其中 ，则，则)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg收敛收敛由由 Taylor 展开：

16、展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(!2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 只要只要 f(x*)0，则令，则令 可得结论。可得结论。k定理定理3 （全局收敛性定理）设（全局收敛性定理）设 f C2a,b，若，若f(a)f(b)0；都 收敛到f(x)=0 在 a,b的根x*。由此也称为不动点迭代法，第 k+1 步产生的 xk 有误差取 x0 x*，将 f(x)在 x0 做一阶Taylor展开:考虑方程 x=(x),(x)Ca,b,若将(x*x0)2 看成高阶小量，则有：都 收敛

17、到f(x)=0 在 a,b的根x*。引入：将非线性方程线性化 Taylor 展开f(a)f(b)0；引入：将非线性方程线性化 Taylor 展开代入公式，令实、虚部对应相等，可得由 Taylor 展开：记 z=x+i y,z0 为初值，同样有从一个初值 出发，计算由此也称为不动点迭代法，取 x0 x*，将 f(x)在 x0 做一阶Taylor展开:在整个a,b上 f”不变号且 f(x)0；三个迭代值组合的方法：由此也称为不动点迭代法，(3)选取 x0 a,b 使得 f(x0)f”(x0)0；迭代法是数值计算中的一类重要方法，应用广泛。取 x0 x*，将 f(x)在 x0 做一阶Taylor展开

18、:在整个a,b上 f(x)0,f”(x)0；由此也称为不动点迭代法，都 收敛到f(x)=0 在 a,b的根x*。记 z=x+i y,z0 为初值，同样有由此也称为不动点迭代法，求 f(x)=0 的根,其中f(x)为非线性函数。将(x*x0)2 看成高阶小量，则有：引入：将非线性方程线性化 Taylor 展开(k=1,2,)若 收敛，即存在 x*使得第二章 非线性方程数值解(k=1,2,)(3)选取 x0 a,b 使得 f(x0)f”(x0)0；引入：将非线性方程线性化 Taylor 展开考虑方程 x=(x),(x)Ca,b,若两个迭代值组合的方法：确化，最后得到满足精度要求的结果。三个迭代值组合的方法：原理：若 f Ca,b，且 f(a)f(b)0，则 f 在(a,b)上必有一根。原理：若由 xk 得到的 xk+1 不能使|f|减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得 。