计算方法-2方程求根

nullnullnull学习要点学习要点方程求根的三个问题：根的存在性、根的分布、根的精确化； 二分法：将有根区间二分，根据函数的符号变化逐步缩短有根区间； 迭代法：将方程等价转化为另一种形式，并构造迭代公式； 牛顿迭代法与割线法；2.1 问题的提出2.1 问题的提出 函数方程 f（x）=0 若 f (x)不是x的线性函数, 则称为非线性方程 , 特别地 若f (x)是 n 次多项式，则称为n次多项式方程或代数方程；若f (x)是超越函数，则称为超越方程。 如果函数 f（x）= （x-x*）m g(x) 且g(x* )0, 则称x*是(x)的m重零点或(x)=0的m重根。 当m = 1时，称x*是(x)的单根或单零点。null理论上已证明: 对于次数n<=4的多项式方程，它的根可以用公式表示; 而次数大于 5 的多项式方程，它的根一般不能用解析表达式表示; 因此对于 f(x) = 0 的函数方程，只要得到满足精度要求的根的近似值就可以了。 常用的求根方法分为区间法和迭代法两大类。数值求根问题包括：数值求根问题包括： 根的存在性 根的范围 根的精确化null根的存在定理： 假设函数 y= f (x) ， xa,b ，且f(a)·f(b)<0，函数图象如图则至少存在一点x a,b使得 f (x )=0，这就是根的存在定理。 null 第一步：求根的隔离区间。确定根所在的区间，使方程在这个小区间内有且仅有一个根，这就是根的隔离过程。所得小区间称为方程的根的隔离区间或有根区间。 第二步： 将根精确化。已知一个根的近似值后，再用一种方法将此近似值精确化，使其满足给定的精度要求。通常分两步来求根null 三种方法来求根的隔离区间 作图法 方程等价变换法 搜索法 null 例1 的有根区间 null 例 2 求 的有根区间2.2 二分法2.2 二分法二分法是求方程近似根的方法中，最直观、最简单的一种方法 给定方程 f (x) = 0，设 f (x)在区间[a,b]连续，严格单调，且 f(a) · f(b) < 0，则[a,b]为f (x) = 0的一个有根区间。 基本思想： 用对分区间的方法根据分点处函数f(x)值的符号逐步将有根区间缩小，使在足够小的区间内，方程有且仅有一个根null记a0=a,b0=b。用中点x0=(a0+b0)/2将区间[a0,b0] 分成2个小区间：[a0,x0]和[x0,b0]； 计算f(x0)，若f(x0)=0，则x0为f(x0)=0的根，计算结束。否则f(a0) f(x0)<0与f(x0) f(b0)<0两式中有且仅有一式成立。 若f(a0) f(x0)<0，令a1=a0，b1=x0，若f(x0) f(b0)<0，令a1=x0，b1=b0； 于是[a1,b1]为新的有根区间，[a0,b0]  [a1,b1]，且后者长度为前者的一半。具体方法：null对新的有根区间[a1,b1]施行同样的手续，于是得到一系列有根区间[a0,b0]  [a1,b1]  [a2,b2] ……  [ak,bk] 其中每一个区间的长度都是前一个区间长度的一半，最后一个区间的长度为 bk-ak=（b-a）/2k 如果取最后一个区间[ak,bk]的中点xk=(ak+bk)/2作为f(x)=0根的近似值，则有误差估计式 |xk-x*|≤ (bk-ak)/2=（b-a）/2k+1nullabb1a1x0null例3 用二分法求方程 在区间[0,1]内的1个实根，要求有3位有效数字。 计算结果计算结果二分法的优点与缺点二分法的优点与缺点优点： 计算简单，方法可靠 缺点： 不能求偶数重根； 不能求复根； 收敛速度慢2.3 简单迭代法2.3 简单迭代法一 迭代格式的构造及其敛散性条件： 已知方程 f (x) = 0 在区间[a,b]内有1个根x*。在区间[a,b]将其改写成同解方程 x=φ(x) 迭代函数迭代法是数值计算中的一种典型方法，不仅用于方程求根，而且用于方程组求解、矩阵求特征值等方面null取x0∈[a,b]，用递推公式 xk+1=φ(xk) k=0,1,2,…… 可得到序列 x0, x1, x2 ……。如果k→∞, 序列{xk}有极限x*,且 φ(x）在x*附近连续，则对上式两边取极限，得 x*=φ(x*) 因而x*是方程x=φ(x)的解，x*也是方程的根 迭代格式迭代序列null例 f（x）=x2 – 2x - 3 = 0 它在区间[2,4]内有唯一根x*。方程可以改写为多种等价形式，如： 1） 此时 取x0=4，得迭代公式 当k越来越大，xk趋近精确根 x*=3null2） 此时 仍然取x0=4，得迭代公式 当k越来越大，xk离精确根越来越远 问题如何判断所构造的迭代函数x=φ(x) 使得迭代序列{xk}收敛或发散？怎样估计误差？问题定理若迭代法中的迭代函数g(x)在区间[a,b]上具有一阶连续的导数，且满足如下2个条件； 对任意x∈[a,b]，a≤g(x)≥b; 在区间[a,b]上g’(x)存在，且| g’(x)| ≤L<1. 则有如下结论： （1）对于任意初始近似值x0∈[a,b]，迭代法xk+1=g(xk)产生的迭代序列{xk}都收敛于方程x=g(x)在区间[a,b]上的唯一实根x*; （2）定理拉格朗日中值定理拉格朗日中值定理 设函数 y= f (x) 在闭区间a,b 上连续，在开区间(a,b)内可导，则在(a,b)内至少有一点ξ，使得 二 迭代法的收敛速度二 迭代法的收敛速度定义： 设序列{xk}收敛于x*，并记ek=xk-x*(k=0,1,2,…) 。如果存在非零常数p，使得 则称序列{xk}是p阶收敛的。 当p=1，且0<|c|<1，称为线性收敛； 当P>1，称为超线性收敛。特别，当p=2，称为平方收敛2.4 牛顿法与割线法2.4 牛顿法与割线法一 牛顿迭代公式 null设 xk是f(x)=0的一个近似根，把f(x)在xk处作一阶Taylor展开于是： 设f’(xk)≠0，则近似解为： 取xk+1为原方程新的近似根 ，得到牛顿迭代公式二 牛顿法的局部收敛性定义: 对于方程x= φ(x)，若在x*的某个邻域 S={x|x∈[x*-δ, x*+δ]}内，对任意初始值x0∈S，迭代格式 xk+1=φ(xk) k=0,1,2,…… （3.14） 都收敛，则称该迭代格式在x*的附近是局部收敛的。 定理: 设方程x= φ(x)有根x*，且在x*的某个邻域 内φ(x)存在一阶连续的导数，则 （1）当|φ’(x)|<1时，迭代格式（3.14）局部收敛 （2）当|φ’(x)|>1时，迭代格式（3.14）发散二 牛顿法的局部收敛性二 牛顿法的局部收敛性二 牛顿法的局部收敛性对φ(x)求导牛顿法的迭代函数为由于f’(x*)≠0，因此 φ(x*)=0，由局部收敛定理得知，牛顿迭代法是局部收敛的。null 而且，无论当x*是f(x)的单根还是重根，牛顿法均为局部收敛。 需要注意的是：初值x0需要足够靠近x* 牛顿法的收敛阶数牛顿法的收敛阶数又由牛顿迭代公式得将f’(x*)在xk处泰勒展开，得代入上式，有牛顿法的收敛阶数牛顿法的收敛阶数即，令k∞，由局部收敛性得知： xkx*时，从而xkx*，所以牛顿迭代法至少为平方收敛null例 用牛顿法求方程 f(x)=x(x+1)2-1=0 ,在0.4附近的根，精确至4位有效数字 解: 对f(x)求导得 f’(x)=(x+1)(3x+1) 牛顿迭代格式为取 x0=0.4, 计算结果为 k 0 1 2 3 xk 0.4 0.47013 0.46559 0.46557 因此 x*≈0.4656null1 割线法几何意义 四 割线法null切线斜率　　割线斜率割线法用差商代替求导，减少了牛顿法的计算量，但是需要2个初值 x0 和 x1。null例 用弦割法求方程解：因为f(1)=-1<0, f(1.5)=0.875>0，且f(x)为单调连续函数，所以f(x)=0在[1，1.5]内有唯一的实根。 取x0 =1， x1=1.5,可采用弦割法计算。在[1，1.5]附近的根作业作业 7.3，7.6 7.5