《数字分析》PPT课件.ppt

第七章非线性方程求根 7 1方程求根与二分法7 2迭代法及其收敛性7 3迭代法收敛的加速方法7 4牛顿法7 5弦截法与抛物线法7 6解非线性方程组的牛顿迭代法 本章讨论非线性方程的求根问题 其中一类特殊的问题就是多项式方程的求根 方程的根又称为的零点 它使若可表示为 其中为正整数 且 当时 称为单根 若称为重根 或的重零点 若是的重零点 且充分光滑 则 7 1方程求根与二分法 当为代数多项式时 根据代数基本定理可知 次方程在复数域有且只有个根 因此可利用迭代法求代数方程的根 二分法若 且 根据连续函数性质可知在内至少有一个实根 此时称为方程若可表示为 其中为正整数 且 当时 称为单根 若称为重根 或的重零点 若是的重零点 且充分光滑 则 7 1方程求根与二分法 7 1方程求根与二分法 当为代数多项式时 根据代数基本定理可知 次方程在复数域有且只有个根 因此可利用迭代法求代数方程的根 二分法若 且 根据连续函数性质可知在内至少有一个实根 此时称为方程的有根区间 例 求方程的有根区间 解 通过计算部分点的函数值 得到如下结果 由此得到方程的有根区间为 7 1方程求根与二分法 二分算法设已找到有根区间 满足 且在上只有一个零点 步骤如下 1 先设对于一般的区间 设其中点为 2 检验的符号 若与同号 就取 的有根区间 例 求方程的有根区间 解 通过计算部分点的函数值 得到如下结果 由此得到方程的有根区间为 7 1方程求根与二分法 二分算法设已找到有根区间 满足 且在上只有一个零点 步骤如下 1 先设对于一般的区间 设其中点为 2 检验的符号 若与同号 就取 否则取这样必有所以就是新的有根区间 继续此过程 即可得到结果 算法 1 令 2 若或 则输出 结束 3 若 则令 否则令 4 转向1 7 1方程求根与二分法 这样 我们得到了一个序列 为确定的收敛性我们有如下的定理 定理 设则二分算法产生的序列满足其中为方程的根 证明 因为由对分得到 所以对否则取这样必有所以就是新的有根区间 继续此过程 即可得到结果 算法 1 令 2 若或 则输出 结束 3 若 则令 否则令 4 转向1 7 1方程求根与二分法 这样 我们得到了一个序列 为确定的收敛性我们有如下的定理 定理 设则二分算法产生的序列满足其中为方程的根 证明 因为由对分得到 所以对区间长度而 且 所以故当时 且有误差估计式 7 1方程求根与二分法 例 已知在有一个零点 用二分法计算的结果如下 区间长度而 且 所以故当时 且有误差估计式 7 1方程求根与二分法 例 已知在有一个零点 用二分法计算的结果如下 7 1方程求根与二分法 另外 如果要求 可以从令 可得 即计算17次即可 7 2迭代法及其收敛性 不动点迭代法将方程改写成等价的形式 则的根也满足方程 反之亦然 称为的不动点 而求的根的问题就成为求的不动点问题 选取初值 以公式进行迭代 称为迭代函数 若收敛到 则就是的不动点 这种方法就称为不动点迭代法 将转化为的方法可以是多种多样的 例 在上可有以下方法 1 2 3 4 取 有的收敛 有的发散 有的快 有的慢 7 2迭代法及其收敛性 迭代过程的几何表示方程的求根问题在平面上就是要确定曲线与直线的交点 对于的某个近似值 在曲线上可确定一点 它的横坐标为而纵坐标为 过引轴的平行线 交于迭代函数 若收敛到 则就是的不动点 这种方法就称为不动点迭代法 将转化为的方法可以是多种多样的 例 在上可有以下方法 1 2 3 4 取 有的收敛 有的发散 有的快 有的慢 7 2迭代法及其收敛性 迭代过程的几何表示方程的求根问题在平面上就是要确定曲线与直线的交点 对于的某个近似值 在曲线上可确定一点 它的横坐标为而纵坐标为 过引轴的平行线 交于 然后过再作轴的平行线 它与的交点记作 则的横坐标为 而纵坐标为 按图中箭头所示路经继续做下去 在曲线上得到点列其横坐标分别为按公式求得的迭代值如果点列趋向于点 则相应的迭代值收敛到所求的根 7 2迭代法及其收敛性 7 2迭代法及其收敛性 例3 求方程在附近的根 解 将方程改写为 由此建立迭代公式 计算结果如下表 这是一个收敛的例子 也有不收敛的迭代公式 如我们对于同样的问题 如果将方程改写为令一种迭代公式 仍取初值 则迭代发散 为此 我们要研究存在性及迭代法的收敛性 7 2迭代法及其收敛性 定理1 存在性 设满足以下两个条件 1 对任意的 有 2 存在 使对任意都有则在上存在唯一的不动点 证明 先证不动点的存在性 若或 则或就是不动点 因此由可设及 定义函数 显然且满足由函数的连续性可知存在使 即 即为的不动点 7 2迭代法及其收敛性 再证唯一性 设及都是的不动点 则由定理的条件 2 得到矛盾 故的不动点是唯一的 证毕 定理2 收敛的充分条件 设满足定理1的两个条件 则对任意 由得到的迭代序列收敛到的不动点 并有误差估计证明 设是在上的唯一不动点 由条件1可知 再由条件2得因 故当时 序列收敛到 7 2迭代法及其收敛性 由迭代公式可得据此反复递推 得到于是对任意正整数 有在上式令 注意到即得到结果 证毕 7 2迭代法及其收敛性 根据定理2的结论 对于给定的计算精度 迭代次数是可以预先确定的 但由于公式中含有常数 使得计算迭代次数较为复杂 根据估计式我们得到 令 得到由此可知 只要相邻两次计算结果的偏差足够小即可保证近似值有足够的精度 7 2迭代法及其收敛性 对于定理中的条件2 在实际使用时 如果且对任意的有则由中值定理可知有它表明定理中条件2可由替代 7 2迭代法及其收敛性 局部收敛性前面讨论的收敛性称为全局收敛性 现在我们讨论局部收敛性 定义1 设有不动点 如果存在的某个领域 对任意 迭代公式产生的序列且收敛到 则称该迭代法局部收敛 定理3 设为的不动点 在的某个领域连续 且 则迭代法收敛 证明 由连续函数的性质 存在的某个领域 使对任意成立 此外 对于任意 总有 这是因为于是依据定理2可断定迭代过程对于任意的初值收敛 7 2迭代法及其收敛性 关于收敛速度问题的例用不同的方法求方程的根 解 这里 可改写为各种不同的等价形式 1 2 3 4 取 对上述4种迭代法 计算三步所得结果如下 7 2迭代法及其收敛性 注意 从计算结果看到迭代法 1 和 2 均不收敛 且它们均不满足定理3种的局部收敛条件迭代法 3 和 4 均满足局部收敛条件 且 4 比 3 快 这是因为 4 的 为了衡量收敛速度 可以给出如下的定义 7 2迭代法及其收敛性 定义2设迭代过程收敛于方程的根 如果迭代误差当时成立下列渐进关系式则称该迭代过程是阶收敛的 特别地 时称线性收敛 时称超线性收敛 时称平方收敛 定理4对于迭代过程 如果在所求根的邻近连续 并且 则该迭代过程在点邻近是阶收敛的 证明 由于 据定理3立即可以断定迭代过程具有局部收敛性 再将在根处做泰勒展开 利用条件 得到 7 2迭代法及其收敛性 在与之间 注意到由上式得到因此对迭代误差 当时有这表明迭代过程确实为阶收敛 证毕 定理说明 迭代过程的收敛速度依赖于迭代函数的选取 如果 则迭代过程只可能时线性收敛 在例4中 迭代法 3 的 故它只是线性收敛 迭代法 4 的 但 故为2阶 7 3迭代法收敛的加速方法 埃特金加速收敛方法有的迭代过程虽然收敛 但速度很慢 因此迭代过程的加速是一个重要课题 设是根的某个近似值 用迭代公式校正一次得 而有微分中值定理 有其中介于与之间 假设改变不大 近似地取某个近似 则有若将校正值再校正一次 又得 由于在两式中消去 得到 由此推得 7 3迭代法收敛的加速方法 在计算了及之后 可用上式右端作为的新近似 记作 一般情形是由计算 记该方法称为埃特金加速方法 可以证明 它表明序列的收敛速度比的收敛速度快 7 3迭代法收敛的加速方法 斯蒂芬森迭代法埃特金方法不管原序列是怎样产生的 对进行加速计算 得到序列 如果把埃特金加速技巧与不动点迭代结合 则得到如下的迭代法 称为斯蒂芬森迭代法 它可以这样理解 我们要求的根 令已知的近似值及 其误差分别为通过把误差外推到零 即过及两点做线性插值函数 它与轴的交点就是迭代法的结果 7 3迭代法收敛的加速方法 即方程的解 实际上就是将两个步骤合成一个步骤 如果把它看成一个不动点迭代 则 关于上述不动点迭代法有以下的局部收敛性 定理5若为 定义的迭代函数的不动点 则为的不动点 反之 若为的不动点 设存在 则是的不动点 且斯法是2阶的 7 3迭代法收敛的加速方法 证明 设是的不动点 即 则有 即 所以 即是的不动点 反之 若是的不动点 且设 则故与有相同的不动点 现设且 则此时 若收敛 且只是一阶的 但却可以是二阶的 7 3迭代法收敛的加速方法 因为 取 即有 故 回到一般的 即有 所以 即具有二阶收敛性 证毕 7 3迭代法收敛的加速方法 例5用斯蒂芬森迭代法求解方程 解 前面的例3中已经指出迭代格式是发散的 现用斯蒂芬森迭代法 取 则有迭代公式 取 得到 书上的方法是通过得到的 结果一致 特别注意 对于发散的算法 斯蒂芬森迭代法仍可能收敛 进一步还可证明斯蒂芬森迭代法的收敛阶可以高一阶 7 4牛顿法 牛顿法对于方程 如果是线性函数 则它的求根是容易的 牛顿法就是一种将非线性方程逐步线性化的方法 设已知方程有近似根 假定 将函数在点展开 有 于是方程可近似地表示为 这是一个线性方程 记其根为 则的计算公式为这就是牛顿迭代法 7 4牛顿法 牛顿法的几何意义方程的根在几何上就是曲线与轴的交点的横坐标 设是根的某个近似值 通过曲线上横坐标为的点引切线 切线方程为 令 解得 将其作为下一个近似值就得到牛顿法 因此 牛顿法在几何上可以解释为将近似值处曲线上对应点的切线与轴的交点作为的新的近似值 注意到切线方程的形式 我们可以将牛顿法称为切线法 7 4牛顿法 关于牛顿法的收敛性 由于迭代函数为 由于假定是的一个单根 即 则由上式知 于是可得牛顿法在根的附近是平方收敛的 又因故可得 7 4牛顿法 例 用牛顿法解方程解 迭代公式为 取初值 迭代结果为 如果用格式 采用不动点迭代法 则要17次迭代才能得到同样的结果 7 4牛顿法 牛顿法的计算步骤 1 准备 确定初始值 计算 2 迭代 按公式迭代那一次 得到新的近似值 计算 3 控制 如果满足或 则终止迭代 以作为所求的根 否则转步骤4 此处的是允许误差 而 4 修改 若 或 则停止 否则转 2 7 4牛顿法 牛顿法应用举例 应用牛顿法解二次方程 计算公式为 可以证明 这个迭代公式对于任意的初值均收敛 求 应用上述公式 取 计算3次即得到较高精度 7 4牛顿法 简化牛顿法与牛顿下山法牛顿法需要计算 计算量较大 可能不收敛 为克服这两个缺点 通常采用下述方法 1 简化牛顿法迭代函数 若 即取在根附近成立 则该迭代法局部收敛 若取 则称为简化牛顿法 这类算法计算量小 单只有线性收敛 7 4牛顿法 2 牛顿下山法牛顿法收敛依赖于初始值 因此可能发散 为防止迭代发散 我们对迭代过程附加一个要求 即满足这项要求的算法称为下山法 我们将牛顿法和下山法结合起来 即在下山法保证函数值稳定下降的前提下 用牛顿法加快速度 为此我们构造迭代公式 即 称为牛顿下山法 其中称为下山因子 下山因子的选择取进行试算 逐次减半 直到下山条件成立 7 4牛顿法 重根情形设 整数 则为方程的重根 此时有 只要 就可以用牛顿迭代法继续计算 此时迭代函数的导数为 且 所以牛顿迭代法求重根只是线性收敛 改进方案一取 则 用迭代法求重根 则具有2阶收敛 但需要预先知道重数 7 4牛顿法 改进方案二令 若是的重根 则对于它用牛顿法 其迭代函数为 从而可构造迭代法它是一个2阶的方法 7 4牛顿法 例9 方程的根是二重根 用上述三种方法求根 解 三种方法的迭代公式分别为 1 2 3 取初值 得到如下结果 1 为线性收敛 精度不高 2 3 为2阶收敛 精度高已有10位有效数字 而方法 1 要30次才达同样精度 7 5弦截法与抛物线法 为回避在牛顿法中需计算的 设法用函数值来代替 下面介绍两种常用方法 弦截法设是的近似根 我们利用构造一次插值多项式 并用的根作为的新的近似根 由于因此有 这个结果其实可以看成牛顿公式中导数用差商来代替 7 5弦截法与抛物线法 弦截法的几何意义 7 5弦截法与抛物线法 抛物线法设已知方程的三个近似根 构造二次插值多项式 并以的一个零点作为新的近似值 设为 它有两个零点 式中 为了保证精度 我们选接近的为 为此选根号前的符号与的符号一致 7 6解非线性方程组的牛顿迭代法 考虑方程组 其中均为的多元函数 若用向量记号 可记为 当且中至少有一个是自变量的非线性方程时 称 为非线性方程组 非线性方程组的