非线性方程与方程组的数值解法数值分析ppt课件.ppt

2020 3 29 1 第7章非线性方程与方程组的数值解法 7 1方程求根与二分法 7 1 1引言 方程求根的一般形式 其中 如果实数满足 则称是 或称是函数的零点 2020 3 29 2 若可分解为 其中为正整数 且 则称为方程的重根 或为的重零点 时为单根 若为的重零点 且充分光滑 则 2020 3 29 3 方程性质不同 求解方法也有很大差异 如果函数是多项式 其中 为实数 则称方程为次代数方程 次代数方程在复数域有且只有个根 含重根 当时不能用公式表示方程的根 只能数值求解 2020 3 29 4 有根区间 设函数在上连续 则方程在区间内一定有实根 称为方程的有根区间 对于超越方程 例如 在整个轴上有无穷多个解 取值范围不同 解也不同 超远方程只能通过数值求解 2020 3 29 5 逐次搜索法 设连续函数存在有根区间 将等分 步长 端点 检查节点函数值 若 则可确定有根区间 2020 3 29 6 P213例1求方程的有根区间 解 在区间内至少有一个实根 取步长 进行搜索计算 方程的有根区间为 2020 3 29 7 7 1 2二分法 计算方法 计算区间中点函数值 若 则根为 计算区间端点函数值 否则 时 时 2020 3 29 8 反复计算 直到 预定的精度 最终取值 误差 取有根区间的中点 二分次数 作为近似根 则 特点 算法简单 可保证收敛 但收敛太慢 用于求近似解 2020 3 29 9 P214例2求方程在区间内的一个实根 要求准确到小数点后的第二位 解 注 即 2020 3 29 10 7 2不动点迭代法及其收敛性 7 2 1不动点与不动点迭代法 将方程改写成等价形式 若要求满足 则 反之亦然 称为函数的一个不动点 因此 求的零点就等价于求的不动点 2020 3 29 11 选择一个初始近似值 代入迭代函数 将新值作为近似值 再次代入迭代函数 反复迭代 迭代方程 迭代存在极限 不动点迭代法 则称迭代方程收敛 且为的不动点 2020 3 29 12 实质 将隐式方程 通过迭代逐步显式化 逐次逼近法 几何意义 直线与曲线 其交点横坐标就是方程的根 逐次逼近 迭代收敛 2020 3 29 13 P215例3求方程在附近的根 解 迭代公式 注意 如果迭代公式为 则迭代发散 2020 3 29 14 7 2 2不动点的存在性与迭代法的收敛性 定理1设函数满足以下两个条件 1 对于任意 有 2 存在正常数 使对任意都有 迭代函数在上 迭代函数的增量小于自变量的增量 则在上存在唯一的不动点 2020 3 29 15 证明 先证不动点存在性 若 或 则在上存在不动点 不动点特点 因 以下设及 定义 显然 且满足 由连续函数性质可知 存在使 即 为的不动点 2020 3 29 16 再证唯一性 设及都是的不动点 则 引出矛盾 故的不动点只能是唯一的 在的不动点唯一的情况下 可得到迭代法收敛的充分条件 2020 3 29 17 收敛到的不动点 并有误差估计 定理2设函数满足以下两个条件 1 对于任意 有 2 存在正常数 使对任意都有 则对任意 由得到的迭代序列 2020 3 29 18 证明 设是在上的唯一不动点 由定理条件 1 可知 由定理条件 2 可得 反复应用上述结论 因 故当时 序列收敛到 2020 3 29 19 再由定理条件 2 得 如此反复递推得 于是对于任意正整数有 在上式令 注意到 2020 3 29 20 讨论一 因正常数未知 上述误差估计无法使用 对于任意正整数有 令可得 即 只要相邻两次计算结果的偏差足够小 就能保证近似值具有足够的精度 2020 3 29 21 讨论二 在某些情形下可求得 如果且对任意有 则 由中值定理可得 对有 因此 可将上述定理和定理中的条件 2 改为 2020 3 29 22 P215例3求方程在附近的根 例如 1 当时 在区间有 由定理2可得 迭代法是收敛的 2 当时 在区间有 不满足定理的条件 无法保证迭代收敛 2020 3 29 23 7 2 3局部收敛性与收敛阶 对于区间上的任意 所产生的迭代序列都收敛 称为全局收敛 实际应用时 通常只在不动点邻居考察其收敛性 称为局部收敛 定义1设有不动点 如果存在的某个领域 对任意 迭代产生序列 且收敛到 则称迭代法局部收敛 2020 3 29 24 且 则迭代法局部收敛 定理3设为的不动点 在的某个领域连续 证明 由连续函数的性质 存在的某个领域 使对于任意有下式成立 此外 对于任意 总有 这是因为 依据定理2 迭代过程对于任意均收敛 2020 3 29 25 P218题4用不同方法求方程的根 解 这里 可改写成不同的等价形式 其不动点为 1 2 2020 3 29 26 3 4 取 对上述4种迭代法 计算三步的结果如下表 2020 3 29 27 说明 精确值 迭代法 1 和 2 不收敛 迭代法 3 和 4 收敛 迭代法 4 中比迭代法 3 小 迭代法 4 比迭代法 3 收敛速度快 2020 3 29 28 定义2设迭代过程收敛于方程的根 如果当时迭代误差满足渐进关系式 常数 则称该迭代过程是阶收敛的 特别地 时称为线性收敛 时为超线性收敛 时为平方收敛 2020 3 29 29 定理4对于迭代过程及正整数 如果在所求根的邻近连续 且 则该迭代过程在点邻近是阶收敛的 证明 由于 根据定理3可得 迭代过程具有局部收敛性 2020 3 29 30 再将在根处泰勒展开 利用定理条件 在与之间 注意到 因此对迭代误差 当时有 这表明迭代过程确实为阶收敛 2020 3 29 31 迭代过程的收敛速度依赖于迭代函数的选取 说明 定理表明 如果时 则该迭代过程只可能是线性收敛的 在例4中 迭代法 3 的 故它只能是线性收敛 迭代法 4 的 迭代为二阶收敛 2020 3 29 32 7 3迭代收敛的加速方法 7 3 1埃特金加速收敛方法 设是根的某个近似值 用迭代公式迭代一次 由微分中值定理 在与之间 假定变化不大 2020 3 29 33 将校正值再迭代一次 因而有 消去 可推得 注意 上式是对两次迭代值加权平均后的结果 可加速迭代 适用任何求根序列 不只局限于不动点迭代序列 2020 3 29 34 已知求根序列 其三个相邻值为 埃特金加速法 加速法 加速计算 得到新值 点的一阶差分 点的二阶差分 可以证明 新序列的收敛速度比的收敛速度快 2020 3 29 35 7 3 2斯特芬森迭代法 把埃特金加速法与不动点迭代结合 就可得到斯特芬森迭代法 斯特芬森迭代法是将两步迭代合成一步得到的 2020 3 29 36 斯特芬森迭代法思路 为求解的根 令 已知的近似值及 其误差分别为 把误差 外推到零 即过及两点做线性插值函数 它与轴交点就是 2020 3 29 37 即求解方程 其解为 即 2020 3 29 38 定理5对于斯特芬森迭代法 若为迭代函数的不动点 则也为的不动点 反之 若为的不动点 设存在 则也是的不动点 且斯特芬森迭代法是二阶收敛的 2020 3 29 39 P221例5用斯特芬森法求解方程 解 用迭代公式求解方程是发散的 改进上述迭代公式 斯特芬森迭代法 2020 3 29 40 因 P222例6求方程在中的解 解 由方程得 并取对数 可构造迭代法 且时 由定理2此迭代法是收敛的 若取迭代16次得 有六位有效数字 若用斯特芬森迭代法加速 2020 3 29 41 7 4牛顿法 7 4 1牛顿法及其收敛性 牛顿法基本思想 将非线性方程转化线性方程求解 设已知方程有近似根 将函数在点展开 于是方程可近似表示为 这是个线性方程 其根为 牛顿法 2020 3 29 42 牛顿法的几何解释 方程的根为 曲线与轴交点的横坐标 设是根的某个近似值 过曲线上点引切线 切线与轴交点的横坐标作为新解 切线方程 点斜式方程 其根为牛顿法的近似解 切线法 2020 3 29 43 讨论 牛顿法的收敛性 假定是的一个单根 代入上式 可得 因此 牛顿法在根邻近是平方收敛的 2020 3 29 44 P223例7用牛顿法解方程 解 牛顿公式为 取迭代初值 2020 3 29 45 牛顿法计算步骤 第一步准备 选定初值 计算 第二步迭代 迭代一次 计算 第三步控制 计算迭代误差 控制常数 当时 当时 2020 3 29 46 否则以代替 或者 则方法失败 第四步修改 如果迭代次数达到预先指定的次数 如果满足 或 允许误差 则迭代收敛 以作为所求的根 否则转第四步 转第二步继续迭代 2020 3 29 47 7 4 2牛顿法应用举例 对于给定正数 开方计算 转变为应用牛顿法解方程 可以证明 对于任意初值迭代都收敛 2020 3 29 48 证明 由迭代公式 两式相除 反复递推 2020 3 29 49 假设 解出 因此 对于任意 总有 当时 即迭代过程恒收敛 2020 3 29 50 迭代函数为 要求 7 4 3简化牛顿法与牛顿下山法 牛顿法缺点 每次迭代都要计算及 有时计算困难 初始值在根附近才能保证收敛 取值不合适可能不收敛 1 简化牛顿法 平行弦法 迭代公式为 其中常量 并保证迭代收敛 即 若上式在根附近成立 则该迭代法局部收敛 2020 3 29 51 若取为处之值 则有简化牛顿法 特点 节省了计算量 但只有线性收敛 几何意义 用斜率为的平行弦 与轴的交点作为的近似 2020 3 29 52 2 牛顿下山法 问题 牛顿法的收敛性依赖于初值 例如 用牛顿法求解方程 公式 如果 取迭代初值 如果 取迭代初值 结果偏离了根 2020 3 29 53 为防止迭代发散 要求迭代过程具有单调性 下山法 牛顿下山法 下山法保证函数值稳定下降 牛顿法加速收敛 先用牛顿法初步迭代 在将近似值与加权平均 其中下山因子 2020 3 29 54 下山因子选择 从开始 逐次减半试算 直到满足下山法要求 例如 求解方程 牛顿下山法公式为 当 时 求得 且 结果不满足下山法要求 无法继续迭代 需改进值 2020 3 29 55 逐次对减半试算 当时 求得 以为初值 取 迭代收敛 注意 下山因子减半试算 只为确定使迭代收敛的初值 2020 3 29 56 7 4 4重根情形 设 整数 则为方程的重根 此时有 方法1 只要仍可用牛顿法 此时迭代函数为 其导数为 且 所以牛顿法求重根只是线性收敛 2020 3 29 57 改进迭代函数 此时有 因此 用改进的迭代公式求重根具有二阶收敛性 改进的迭代公式为 缺点 需要知道的重根数 2020 3 29 58 方法2 重新构造求重根的迭代法 令 若是的重根 故是的单根 由此应用牛顿法 迭代函数为 从而可构造二阶收敛的迭代法 特点 无需知道值 但要计算 2020 3 29 59 P227例9方程的根是二重根 用上述三种方法求根 解 三种方法的迭代公式为 1 牛顿法 2 改进法 3 重构法 2020 3 29 60 取初值 计算结果如下 注意 方法 2 和 3 均达到10位有效数字 而牛顿法达到同样精度需迭代30次 2020 3 29 61 7 5弦截法与抛物线法 7 5 1弦截法 牛顿法问题 每步需计算 当函数复杂时较困难 设 是的近似根 由 构造一次插值多项式 用的根作为的新的近似根 2020 3 29 62 代入牛顿公式 即得弦截法结果 用差商取代导数 弦截法几何意义 过曲线上横坐标为的两点 作弦线 其方程为 弦线与轴交点的横坐标即为 2020 3 29 63 P229例10用弦截法解方程 解 迭代公式为 选取开始值为 注意 弦截法比牛顿法收敛速度快 计算时要用到前两步的结果 2020 3 29 64 弦截法具有超线性的收敛性 定理6假设在根的邻域 内 具有二阶连续导数 且对任意有 又初值 那么当邻域充分小时 弦截法将按阶收敛到 这里是方程的正根 2020 3 29 65 7 5 2抛物线法 设已知方程的三个近似根 以这三点为节点构造二次插值多项式 适当选取的一个零点作为新的近似根 抛物线法 密勒法 几何意义 过节点 作抛物线 抛物线与轴的交点 即为根的近似值 2020 3