《计算方法计算方法课件_第五章》由会员分享，可在线阅读，更多相关《计算方法计算方法课件_第五章（107页珍藏版）》请在金锄头文库上搜索。
1、,第五章 非线性方程的数值解法,动力与能源工程学院 董平,3/47,本章内容,5.1 引言 5.2 二分法 5.3 迭代法 5.4 牛顿雷扶生法 5.5 正割法 5.6 迭代法的收敛阶和Aitken加速方法（*） 小结 作业与实验,4/47,本章要求,1. 理解方程有根的判别定理； 2. 掌握二分法基本原理，掌握二分法的算法流程; 3. 掌握理解单点迭代的基本思想，掌握迭代的收敛条件； 4. 掌握Newton迭代的建立及几何意义，了解Newton迭代的收敛性； 5. 掌握Newton下上法，掌握正割法，了解抛物线法。,5/47,5.1 引言,本节内容 一. 非线性方程定义 二. 方程求根特点
2、返回章节目录,6/47,5.1 引言,在科学研究中，常常会遇到非线性方程或非线性方程组的问题。例如解方程 或 一般的，我们记非线性方程为,7/47,5.1 引言,一. 非线性方程定义 方程f (x)=0， 当f (x)是一次多项式时，称f (x)=0为线性方程； 否则称之为非线性方程。,8/47,5.1 引言,（1）求解f (x)=0，解x*称为方程的根，即f (x)的零点。 （2） f (x)为n次多项式就是n 次代数方程(n=5，不能用解析式表示解)，f (x)为超越函数时，就是超越方程。 （3）若f (x)=(x-x*)m g(x)，g(x)0，m为正整数，则称 x*为f (x)=0的m
3、重根，或为f (x)的m重零点。 m=1时，称x*为f(x)=0的单根。,P121,9/47,5.1 引言,10/47,线性的（一次解） 单个方程 多项式（n个解） 代数方程 非线性 超越的（解的数目不定） 线性（一组解） 方程组 非线性（多组解） f (x)=0根或 f (x)零点，当 f (x)复杂时，很难求 实际应用中只需求得满足一定精度的近似根即可 （找近似有效简单方法） 。,5.1 引言,先叙述两个基本定理。 定理 1 （代数基本定理） 设 为具有复系数的 n 次代数方程，则 于复数域上恰有 n 个根（r 重根计算 r 个）。如果 为实系数代数方程，则复数根成对出现，即当 是 的复根
4、，则 亦是 的根。 定理2 （1）设 于 上连续： （2）且 ，则存在有 使 即 于 内存在实的零点。 设有非线性，实系数方程 问题是：需要求出方程的所有实根（或复根）。,12/47,5.1 引言,二. 方程求根特点 1. 根的存在性 方程有没有根，有几个根？ 定理1（代数基本定理）：在复数范围内，n次代数方程至少有一个根。 f (x)=anxn+an-1xn-1+a1x+a0=0 其中：n正整数，x复变量， a0an为实、复常数。 定理2：n 次代数方程有 n 个根。,13/47,5.1 引言,2. 根的分布（有根区间） 求根的隔离区间，定一个a, b，使a, b内有且只有一个x*使f(x*
5、)=0 定理3：设函数f(x)在a, b内连续，严格单调，且f(a)*f(b)0，则在a, b内f(x)=0有且仅有一个实根。 通常有两种做法来确定隔离区间： （1）作y = f(x)的草图，看f(x)在x轴的交点位置来定区间a, b （2）逐步搜索，在连续区间a, b内，选取适当的x1，x2(a, b)，若f(x1)*f(x2)0，则x1, x2内有根。,14/47,例1：求xex-2 =0的有根区间 解：变形ex =2/x。则分别做f(x)= ex, g(x)=2/x的草图, f(x)与g(x)的交点的横坐标即是根的大致位置0.5，1内有唯一实根。,5.1 引言,15/47,例2：求f(x
6、)=x3-3x2+4x-3=0的有根区间。 解：三次多项式，作图复杂 f(x)= 3x2-6x+4=3(x-1)2 +1 在(-，+)内f(x)=0，即f(x)为一单调递增函数。 那么f(x)=0在（-，+）内最多只有一个实根。 又 f(0)= 03-3*02+4*0-3=-30 f(0)*f(2)0， 故在0，2内有唯一实根。,5.1 引言,16/47,3. 根的精确化 已知根的近似值后，将其精确化，满足精度要求。 如例2中若取根x*=0.5*（0+2）=1，不精确 但若将0，2进一步缩小，则f（1.5）0， 故1.5，2内有根， 取x*=12（1.5+2）=1.75， 这样精度就提高了。,
7、5.1 引言,17/47,5.2 二分法,本节内容 一. 原理 二. 过程 三. 方法 四. 二分法收敛性 五. 二分法优缺点 六. 二分法的NS图 返回章节目录,18/47,二分法（Bisection Method）又叫对分法，是一种直接法，直观、简单。 一. 原理 设 f (x)=0在a, b内连续，严格单调，且 f (a) * f (b)0， 则f (x)=0在a, b内必有一根。 二. 过程 将区间对分，判别f (x)的符号，逐步缩小有根区间。,5.2 二分法,设有非线性方程 其中， 为 上连续函数且设 （不妨设方程（2.1）于 内仅有一个实根。 求方程（2.1）实根 的二分法过程，就
8、是将含根区间 逐步分半，检查函数符号的变化，以便确定含根的充分小区间。,（2.1）,5.2 二分法,二分法叙述如下；记 （图5-2） 第一步分半计算（k=1）: 将 分半，计算中点 及 ，如果 则根一定在区间 内，否则根一定在区间 内 （若 ，则 ）。于是得到长度缩小一半的含根区间 ，即 第k步分半计算：重复上述过程，设已完成第1步， ，第k-1步分半计算得到含根区间 且满足；（1） 即 ； （2） ； （3）计算 且有,（2.2),（4）确定新的含根区间 ，即如果 ，则根 一定在 内，否则根一定在区间 且有 总之，由上述二分法得到一序列 ，由（2.2），则有 可用二分法求方程 实根 的近似值
9、到任意指定的精度。事实上，设 为给定精度要求，试确定分半次数 k使 由 两边取对数，即得,22/47,5.2 二分法,三. 方法 取xmid=0.5*(a+b) 若f(xmid) 0，则取a1=xmid，b1=b 此时有根区间缩小为a1, b1，区间长度为 b1-a1=0.5*(b-a) 再对a1, b1进行上述过程，直到满足 。,P123,23/47,5.2 二分法,x1,x2,中止条件,或,不能保证 x 的精度,x*,2,24/47,5.2 二分法,四. 二分法收敛性,P124,25/47,5.2 二分法,四. 二分法收敛性,P125,26/47,注： 用二分法求根，最好先给出 f (x)
10、 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak) * f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a) * f (b) 0。,5.2 二分法,27/47,5.2 二分法,28/47,5.2 二分法,29/47,5.2 二分法,30/47,5.2 二分法,例3：（计算方法书P125 例3） 用二分法求f(x)=x6-x-1=0于1,2内的一个实根，且要求精确到小数后第3位（即要求|x*-xk|ln(b-a)-ln/ln2可确定所需分半次数k=11。计算结果见表51。 即结果是x11=1.134277,31/4
11、7,5.2 二分法,五. 二分法优缺点 优点：计算简单，方法可靠，只要求f (x)连续，在两个点上异号。 缺点：不能求偶数重根, 也不能求复根, 收敛速度不算太快(与以1/2为比值的等比级数相同)。 因此，一般在求方程近似根时，不单独使用，常用来为其它方法提供好的初值。 对于方程求根，最常用方法是迭代法。,32/47,5.2 二分法,定义函数 f(x)=,读入数据 a，b，eps,x=(a+b)/2，k=1,|x-a|=eps or |f(x)|=eps,输出 x，f(x),f(x)*f(b)0,Y,N,a=x,b=x,x=(a+b)/2，k=k+1,结束,N,Y,六. 二分法的NS图,33/
12、47,5.3 迭代法,本节内容 一. 迭代格式的构造 二. 迭代过程的几何表示 三. 迭代法的收敛性 四. 整体收敛性 五. 局部收敛性 六. 迭代法N-S图 返回章节目录,解x=g(x)的简单迭代法,34/47,f (x) = 0,x = g (x),f (x) 的根,g (x) 的不动点,5.3 迭代法,迭代法 /* Fixed-Point Iteration */,35/47,5.3 迭代法,一. 迭代格式的构造,P128迭代函数,36/47,5.3 迭代法,二. 迭代过程的几何表示,O x* x2 x1 x0 x,y,y=x,y=g(x),P0,P1,P2,P*,Q1,Q2,37/47
13、,5.3 迭代法,例1：用迭代法求方程f(x)=x2-2x-3=0的根（x1=3，x2= -1） 解：(1)方程改写成 x=(2x+3)1/2 建立迭代公式 xk+1=(2xk+3)1/2 (k=0,1,2)， 取x0=4，x1=3.316，x2= 3.104，x3=3.034， x4= 3.011，x5= 3.004 当k， xk 3，收敛； (2)方程改写成 x=1/2*(x2-3) 建立迭代公式 xk= 1/2 *(xk 2-3) (k=0,1,2)， 取x0=4， x1=6.5 ，x2=19.625 ， x3= 191.0 当k， xk ，发散。,38/47,5.3 迭代法,例2：求方
14、程f(x)=x3-x-1=0在x0=1.5附近的根x*。 解：(1)方程改写成x=(x+1)1/3 ，收敛； (2)方程改写成x=(x3-1) ，发散。,39/47,5.3 迭代法,例3：（数值分析P359 例5、P360 例6 ） 对f(x)=x3+4x2-10=0（此方程在1,2中有唯一根）用不同方法化成等价方程。 解：可化成很多不同等价方程，例如,40/47,5.3 迭代法,取初始近似值x0=1.5，迭代结果见数值分析P360 例6 迭代过程(a)、(b)不适定，(c)、(d)、(e)都收敛，但收敛速度相差很大。,41/47,5.3 迭代法,三. 迭代法的收敛性 g(x)如何构造 基本问题 xk的收敛性(收敛否？如何加速?) 误差估计 从几何上考察迭代法的收敛性，见下页 （另见教材P129）,P129,42/47,5.3 迭代法,43/47,5.3 迭代法,具体的迭代收敛定理, 以及如何加速收敛, 待续。,P130,44/47,5.3 迭代法,四. 整体收敛性,P130定理4,45/47,5.3 迭代法,依此类推,46/47,5.3 迭代法,由定理3结果(3.3)可知，当计算得到的
