数值方法 第4章　非线性方程.doc

第4章 非线性方程数值解法1引言单个变量方程其中特别此称为代数方程。当时，其根不能用和开方的有限次运算公式来表示，因此非线性方程的数值解法是迭代法对于一般的函数，若有其中为正整数，满足，那么称为的重零点，或称为方程的重根。特别，那么称为方程的单根。如果，那么有设，如果，那么方程在内至少有一个根，称为方程的有限区间。例1.1 求方程的有根区间，其中解由此看出，的三个有根区间为，可以用二分法来缩小有根区间，设取中点；若，则令新的有根区间为；若，则令；设的有根区间，即，取的中点，若，令，若，那么取，如此可以找到小的有根区间。二分法可以求方程的根的近似值，但收敛速度相当慢，一般不采用。2迭代法及其收敛性(I)不动点和不动点迭代设是一元连续函数，要解的方程是 （1）为进行迭代，把(1)变成等价形式 （2）其中是连续函数。由（1）变成等价形式(2)，不是唯一的。例2.1，令 ， 令，显然，但，都与是等价的。由可以构造迭代公式（3）称为迭代函数。如果有，由的连续性得满足方程（2），称是的一个不动点，也是方程的根，迭代方法（3）称为不动点迭代法。例2.2求方程在附近的根，其中解将方程写成等价形式取，迭代有可以看出，迭代收敛。的近似值。再将方程写成另一等价形式，, 发散，不收敛（II）整体收敛性定理2.1设如果有那么在上一定存在不动点如果满足的条件，并且存在常数使得那么在上的不动点是唯一的。证明 由于，所以有如果上两式中有一等号成立，那么在上有不动点。若两式中都为严格不等号，由的连续性，必存在使得即为的不动点。（唯一性）设有两个不动点，并且，那么得出矛盾不动点唯一。推论设，并满足；还存在常数，使得那么在上存在唯一的不动点定理2.2 设，并满足存在常数使得那么对任，由产生的序列收敛到在上的不动点，并对于整数有证明 由题设条件，在上有唯一的不动点。由条件保证，；并有递推有令有，即 令有。推论设，并，那么定理结论成立。例子2.3解方程，其中，由于，所以方程在（1,2）内有根（单根！）（i）取，如这样不能进行迭代，故不会收敛（ii），从而有，；迭代收敛（II）局部收敛性与收敛阶前面讨论了迭代法在区间上的收敛性，此收敛称为全局收敛性（整体收敛）。很多情况我们不能这样考虑。实际应用时只在不动点附近来考虑其收敛性，此称为局部收敛性。定义2.1设在区间I上有不动点，如果存在的某一邻域，对任，由迭代法产生的序列且收敛到，则称迭代法局部收敛。定理2.3设为的不动点，在的某一邻域连续，并且。则迭代法局部收敛。证明 由于在的邻域连续，所以任给，使得当时有取使，从而有其中；注意到取，那么根据定理2.2，推论知迭代法上收敛，即局部收敛。定理2.3中，导数条件可以改为。对于收敛快慢，引入收敛阶的概念定义2.2设序列收敛到，记误差。若存在实数，及非零常数c，使则称为阶收敛，c为渐近误差常数。当时分别称为线性收敛，平方收敛。定理2.4设为的不动点，整数，在的邻域上连续，且满足则由产生的序列在的邻域是阶收敛的，且有证：因定理2.3保证局部收敛性，取充分按近于的，设，有由Taylor展开在之间，利用条件 利用的连续性，两边取极限 例子2.4 讨论 在例2.3解法(ii)的收敛阶解 方法一阶3 Newton迭代法（I）Newton迭代法的计算公式为求解的根，设有一个近似值，用Taylor公式 在之间 其中假定，若，可得 若上式中右边最后一项忽略不计，作为的新近似值，有 这称Newton迭代法，也称Newton-Raphson迭代法Newton迭代为不动点迭代 定理3.1 设满足，若（表示为单根），并在的闭邻域上连续，那么Newton法 至少二阶收敛而且证：为其不动点 , 收敛至少是二阶的。Taylor展开有 即 相减有例3.1 用Newton法解方程，其中 解 有根区间，仍取，计算例3.2 用Newton法求 解： 取 当 （II）重根情况设为的重根，。对于的多重根，Newton方法仅为线性收敛。要证明线性收敛，只要证明若为的m重根，那么Newton迭代公式令 ，有 当时，Newton法对重根是线性收敛。修改： 取 满足，那么 。 （直接求）。 迭代至少是二阶的。 注意到迭代函数中含有，一般来说是未知的，因此此方法在应用上受到限制。 令 若 是的重零点，那么是的单重零点，迭代函数修改为：例3.3 解 ，其中为重根。取， ，达到，普通Newton迭代函数要迭代30次。例3.4 对于非零实数，试给出一个不用除法运算求的迭代公式，并要求迭代是二阶的。解: 设 。要求迭代是二阶的，那么应立即考虑为Newton迭代记 递推有：当，若4 迭代加速收敛的方法（I）Aitken的方法一些线性收敛的迭代方法，常常收敛很慢，所以要在这些方法的基础上考虑加速收敛的步骤。设线性收敛到，仍记。再设，当时有满足。我们可以认为近似一个几何序列，即这两个式子消去，可解得所以我们在计算了及之后，可以用上式右端作为的一个修正值。再利用差分的记号，写成是新的一个近似值，利用上式构造序列的方法称为Aitken的加速方法。定理4.1 设有序列，存在，满足而且。则由前面确定的对充分大的都存在，且有证明 设 对充分大的，(II) steffensen迭代法Aitken方法不管原序列是怎样产生的，对进行加速计算，得到序列。如果我们把关于函数的不动点迭代与加速技巧结合起来，可以得到如下的Steffensen迭代法：对上式可以作这样的理解：我们想求的不动点，满足。现在知道了的近似值和,它们对应的误差分别是，再把误差“外推到零”，即连结点和作一条直线，此直线与轴的交点就是。容易验证，如果把steffensen迭代法写成一种不动点迭代的形式 则迭代函数由下式确定定理4.2 设为的不动点，那么边为的不动点，反之也成立；若为的不动点，并在的领域内存在，那么steffesen迭代法是二阶收敛的。5 例子例1 设 ，证明迭代公式 是计算 的三阶方法证： 令 令 有 由题意 迭代公式是计算 的关于迭代收敛性 迭代收敛 收敛三阶此外，也可以考虑 收敛三阶例2 设有迭代公式 （1） 证明是其迭代函数的不动点，（2） 给出并证明该公式的收敛阶。（1） 为的不动点。（2） 收敛阶为3例3 选择使迭代过程 局部收敛于 的根，且至少二阶收敛（其中b为常数，）解 ， 无重根，那么Newton方法至少二阶Newton公式 解法2 注意 例4 试确定常数p. q. r使迭代公式 产生的序列收敛到，并使其收敛阶尽可能高。 解：迭代函数要使收敛阶尽可能高，应使 。 这三个式子来确定p, q, r应满足的方程。 由 得 得。 解3个