非线性方程及方程组的数值解法ppt课件

浙江大学研究生学位课程 1 第四章非线性方程和非性方程组的解法 4 1非线性方程的解法4 2非线性方程组的线性化解法4 3非线性方程组的极值求解法4 4最速下降法4 5共轭梯度法4 6牛顿过程及变度量法4 7直接法4 8方法的选择与总结 浙江大学研究生学位课程 2 非线性方程的解法 非线性方程组的线性化解法 牛顿迭代法 非线性方程组的极值求解法 最速下降法 单纯形法 共轭梯度法 Powell方法 变尺度法 可变矩阵方法 直接法DFP方法 浙江大学研究生学位课程 3 1引言在科学研究中 常常会遇到非线性方程或非线性方程组的问题 例如解方程或一般的 我们记非线性方程为 浙江大学研究生学位课程 4 4 1非线性方程组的一般形式是 其中fi i 1 2 n 是n维实空间 n上的实值函数 用向量形式表示 这里均是n维向量 为了方便计 还是用分别表示上述向量 简记为 浙江大学研究生学位课程 5 4 1 c a d c a d b 图4 1非线性方程求根示意图 浙江大学研究生学位课程 6 4 1 方程的解亦称方程的根或函数的零点 根可能是实数或复数 若则称为单根 若而 则称为k重根 常见的求解问题有两种 1 要求定出在给定范围内的某个解 2 要求定出在给定范围内的全部解 非线性问题 除少数情况外 一般不能不利用公式求解 而要采用某种迭代解法 即构造出一近似值序列逼近真解 浙江大学研究生学位课程 7 4 1 迭代过程的收敛性一般与初值的选取和方程的性态有关 某些解法仅与初值有关 收敛速度一般由迭代方法所决定 方程的性态也会起一些作用 本章主要介绍非线性方程组的解法 而方程的解法用较少的篇幅在4 2中扼要介绍 解非线性方程和方程组有很大区别 后者要困难得多 主要的区别在于一维情形可以找到一个根的范围 然后缩小 最终找到根 而多维情况则很难确定根的存在 直到你求得它的解 浙江大学研究生学位课程 8 4 2非线性方程的解法 4 2 1二分法对于连续函数 如果在和处异号 则在内至少有一个根 浙江大学研究生学位课程 9 4 2 1用图来表示这个过程 y x a b a b a b 确定根所在的范围 a b 对有的函数也是一件困难的事 所幸的是 在实际应用中 根据其物理或工程的背景 在绝大部分场合是不困难的 对给定的函数也有确定范围的方法 图4 2二分法方程求根 浙江大学研究生学位课程 10 a b b a x1 x1 x2 x3 d c f c 4 2 1 图4 3寻找隔根区间示意1 浙江大学研究生学位课程 11 a c b 4 2 1 图4 4寻找隔根区间示意2 图4 5寻找隔根区间示意3 浙江大学研究生学位课程 12 例如 在 a b 之间寻找f x 可能有的根可以用等分试探法 a b 4 2 1 图4 6等分试探法寻找隔根区间示意 浙江大学研究生学位课程 13 用二分法求函数FUNC位于 x1 x2 之间的根 准确性为 XACC FUNCTIONRTBIS FUNC X1 X2 XACC PARAMETER JMAX 40 FMID FUNC X2 F FUNC X1 IF F FMID GE 0 PAUSE 函数FUNC在x1 x2处不异号 IF F LT 0 THENRTIBIS X1DX X2 X1ELSERTBIS X2DX X1 X2ENDIFDO11J 1 JMAXDX DX 0 5XMID RTBIS DXFMID FUNC XMID IF FMID LE 0 RTBIS XMIDIF ABS DX LT XACC OR FMID EQ 0 RETURN11CONTINUEPAUSE 迭代次数越界 END 4 2 1 浙江大学研究生学位课程 14 FUNCTIONFF X FF X X 2 5 X 0 5 SIN X ENDPROGRAMROOTFINDEXTERNALFFX1 1 0X2 0 0ROOT RTBIS FF X1 X2 1 0E 5 PRINT 方程在 1 0 区间内有一个根 X ROOTSTOPEND 4 2 1 浙江大学研究生学位课程 15 4 2 2线性插值法 又称弦位法 x f x 图4 7SecantMethod 浙江大学研究生学位课程 16 4 2 2 浙江大学研究生学位课程 17 4 2 2 浙江大学研究生学位课程 18 4 2 2 f x x 1 4 3 2 图4 8线性插值法求根示意 浙江大学研究生学位课程 19 4 2 2 f x x 1 3 4 5 图4 9线性插值法发散示例 浙江大学研究生学位课程 20 4 2 3Newton法 F x x 图4 10Newton法示意 浙江大学研究生学位课程 21 4 2 3 F x x 图4 11导数变化对算法的影响 浙江大学研究生学位课程 22 每次函数求值相当的收敛阶为 b 求fk 有时工作量大 甚至不可能 4 选用收敛域较大的方法 如二分法 先进行迭代 然后再用Newton法 组合方法 4 2 4二次插值法设f x 0的三个近似解及函数值构造二次函数g y 使得 浙江大学研究生学位课程 23 4 2 4 浙江大学研究生学位课程 24 4 2 4 F x x g x f x 图4 12二次插值法求根示意 浙江大学研究生学位课程 25 4 2 4 1 要有三个初始值 2 当 且收敛速度是1 84阶 单根 二重根的收敛阶是1 23 3 4 发生超射 越界 表4 1各种插值方法的比较 浙江大学研究生学位课程 26 4 2 5组合方法 BrentMethod 能否有一种方法综合上述方法的优点呢 Brent做了一些工作 Brent把二分法和二次插值法结合起来 一定收敛 收敛速度至少线性 在解附近足够光滑时 收敛速度将是1 84或1 23 有关多项式的求根还有一些特殊方法 浙江大学研究生学位课程 27 4 3非线性方程组及牛顿法 非线性方程组的向量形式可表示为 解法 1 几乎不可能用直接法2 线性化 迭代逼近 牛顿法3 最优化 求函数极小值 下降法 例如 求的极小值点 最速下降法 共轭梯度法 变尺度方法 浙江大学研究生学位课程 28 4 3 1牛顿法为方便计 用二维情形来讨论 假定 4 6 的解 作线性函数 Taylor展开 取一阶精度 浙江大学研究生学位课程 29 4 3 1在内用线性函数 4 7 代替非线性方程组 4 6 中的f1 f2 从而 如果在中矩阵 称Jacobi矩阵 非奇异 则可解出 浙江大学研究生学位课程 30 4 3 1 浙江大学研究生学位课程 31 4 3 1 浙江大学研究生学位课程 32 4 3 1 浙江大学研究生学位课程 33 4 3 2牛顿法的改进改进 带松弛因子的牛顿迭代格式改善了对初始值近似程度的要求 浙江大学研究生学位课程 34 4 3 2 4 10 中引入了松弛因子 有 浙江大学研究生学位课程 35 4 3 2 图4 13凸函数示例 浙江大学研究生学位课程 36 4 3 2 浙江大学研究生学位课程 37 4 3 2 图4 140 618法搜索极小点过程 浙江大学研究生学位课程 38 4 3 2 2 二次插值法求一维函数极小值 图4 15二次插值法进行一维极小点搜索 浙江大学研究生学位课程 39 4 3 2改进 带阻尼因子的牛顿迭代格式克服了矩阵的奇异或病态 4 10 中引入阻尼因子 的选取可以在满足 4 12 的前提下取很大值 改善对初值的要求 当 时为牛顿法 收敛最快 为满足 4 12 实际上需要多次试算 工作量大 改进3 修正牛顿法尽可能减少矩阵求逆次数 浙江大学研究生学位课程 40 4 3 2一种简单的办法是每次使用同一个Jacobi矩阵的逆 但大大影响收敛速度 另一种办法是若干次迭代后求一个矩阵逆 它减少了矩阵求逆 又保证了收敛 换一个角度看 如果说它的求逆次数与牛顿法相同 k次 则它的收敛阶为m 1 浙江大学研究生学位课程 41 4 3 2 或 迭代格式 4 15 具有 阶收敛速度 对一维情况 Newton法在几何上表现为m步迭代过程保持斜率f xk 不变 如图4 16 f x x 0 图4 16m 2的迭代效果 作为特例 取m 2 浙江大学研究生学位课程 42 4 3 2非线性代数方程组求解问题1 Newton Raphson迭代法2 极值化求解 问题的转化 浙江大学研究生学位课程 43 4 4最速下降法 4 4 1极值化求解 的零极值点 求解 4 16 的极值点也是一个无约束的最优化问题 浙江大学研究生学位课程 44 4 4 1求解最优化问题 通常采用下降法 下降法一般描述如下 浙江大学研究生学位课程 45 4 4 1下降法的迭代步骤 浙江大学研究生学位课程 46 4 4 1最速下降法取因此 浙江大学研究生学位课程 47 4 4 1 等高线图 f x Cif x1 x2 Ci 图4 17等高线 图4 18偏导数示意 浙江大学研究生学位课程 48 4 4 2讨论与改进优点 程序简单 每步迭代计算量少 存储省 对于不太好的初始点x0 往往也能收敛 缺点 最速下降法是名不符实的 一般来说 它只有线性的收敛速度 浙江大学研究生学位课程 49 4 4 2 图4 19锯齿形搜索路径情况 浙江大学研究生学位课程 50 4 4 2 浙江大学研究生学位课程 51 4 4 2 浙江大学研究生学位课程 52 4 4 2一般来说 开始几步下降速度较快 但越靠近极小值点越慢 改进 浙江大学研究生学位课程 53 4 4 2最速下降法算法框图 停 停 图4 20最速下降法算法框图 浙江大学研究生学位课程 54 4 4 2 图4 21搜索路径示意 浙江大学研究生学位课程 55 4 5共轭梯度法 ConjugateGradientMethods 4 5 1共轭方向 图4 22共轭方向 浙江大学研究生学位课程 56 4 5 1 浙江大学研究生学位课程 57 4 5 1 浙江大学研究生学位课程 58 4 5 1 图4 23二次函数的共轭方向 图4 24二次函数 浙江大学研究生学位课程 59 4 5 1 浙江大学研究生学位课程 60 4 5 1 浙江大学研究生学位课程 61 4 5 1 浙江大学研究生学位课程 62 4 5 2共轭梯度法ConjugateGradientMethod利用共轭方向 对二次型求极值问题可以得到n步收敛的结果 现在的问题是 1 如何构造n个共轭方向 2 对一般的非线性函数f x 怎么办 3 由于舍入误差等影响 n次迭代不收敛时怎么办 浙江大学研究生学位课程 63 4 5 2 浙江大学研究生学位课程 64 4 5 2 浙江大学研究生学位课程 65 4 5 10 浙江大学研究生学位课程 66 4 5 2 浙江大学研究生学位课程 67 4 5 2共轭梯度法是从梯度向量出发构造共轭向量 由于误差积累等因素 对二次型 迭代n次也未能达到极小点 F R方法和P R方法的区别在于它们对二次型是一样的 而对一般函数用P R方法可能更合适 共轭梯度法具有二次收敛速度 那么对一般的函数的共轭梯度法又是怎样的呢 浙江大学研究生学位课程 68 4 5 2在极小值点附近进行二次逼近 浙江大学研究生学位课程 69 4 5 2但是求导数 f xk 是必须的 另外 我们总假定f x 在极值点附近性质足够好 满足各种要求 对一般函数f x 共轭梯度法 4 23 有限步收敛几乎是不可能的 如果迭代k步达到精度 k n 则xk就作为x 的近似 当经过n步迭代仍不可能满足要求时 令再进行第二次循环 但是 实际计算中 不一定迭代k n步才进行 重置 浙江大学研究生学位课程 70 4 5 2 1 在极小点附近是一个高度偏心的二次函数 则进行 m n 次迭代 m n 就收敛了 而进行k次迭代 k n 就重置的话 有可能会不收敛 2 在极小点附近或稍远处不是二次函数 此时称 扭曲 现象 则留有非二次函数的痕迹 故可能对收敛很有害 此时最好重置 浙江大学研究生学位课程 71 4 5 2共轭梯度法ConjugateGradientMethods算法框图 图4 25共轭梯度法算法框图 浙江大学研究生学位课程 72 4 5 2 3 如何判别是高度偏心的二次函数还是扭曲的函数呢 启发性的办法是 对一般非二次函数 若x0离x 较远 则迭代n次不收敛时 就重置 但以后不再重置 对既高度偏心 又严重扭曲的函数 则经常性的重置是有好处的 浙江大学研究生学位课程 73 4 5 2它在点 1 1 处有极小值4 其图象为 图4 26函数等高线图 浙江大学研究生学位课程 74 4 5 2表4 3最速下降法计算结果 浙江大学研究生学位课程 75 4 5 2表4 4各种重置循环的共轭梯度法计算结果 浙江大学研究生学位课程 76 4 6牛顿过程及变度量法 4 6 1Newton Raphson迭代把函数f x 在第k次近似解xk附近进行Taylor展开 浙江大学研究生学位课程 77 4 6 1 浙江大学研究生学位课程 78 4 6 1 浙江大学研究生学位课程 79 4 6 1 图4 27初值对Newton Raphson方法的影响 浙江大学研究生学位课程 80 4 6 1 浙江大学研究生学位课程 81 然而这个方法的致命弱点是要计算Jk 1 4 2提供的办法 即迭代若干次修改一次Jk 1 是一种方案 但不是最好的 4 6 2变量的尺度变换为改变函数的偏心程度 从而改变极小化方法的收敛性质 采用变量替换是个很好的措施 浙江大学研究生学位课程 82 4 6 2 浙江大学研究生学位课程 83 4 6 2 图4 28函数进行尺度变换的效果 浙江大学研究生学位课程 84 4 6 2尺度变换目的是把函数的偏心程度降到最低限度 它放大或缩小各个坐标 但并不能完全消除偏心问题 把尺度变换应用于各种算法 都有一定效果 一般地 浙江大学研究生学位课程 85 4 6 2即变换后的二次函数偏心率为 它是圆 它用最速下降法一步可以达到极小点 现在希望直接处理原来的函数 而定义一个算子 用它产生通过极小点的向量 考虑这样的 从Newton Raphson过程 浙江大学研究生学位课程 86 4 6 2 浙江大学研究生学位课程 87 4 6 3变尺度法 DFP方法 BFGS方法常用的度量是 浙江大学研究生学位课程 88 4 6 3 浙江大学研究生学位课程 89 4 6 3 浙江大学研究生学位课程 90 4 6 3 浙江大学研究生学位课程 91 4 6 3 浙江大学研究生学位课程 92 4 6 3 浙江大学研究生学位课程 93 4 6 3 浙江大学研究生学位课程 94 4 6 3 浙江大学研究生学位课程 95 4 6 3 浙江大学研究生学位课程 96 4 6 3变尺度法VariableMatrixMethods算法框图 图4 29变尺度法算法框图 浙江大学研究生学位课程 97 4 6 3 浙江大学研究生学位课程 98 4 6 3 浙江大学研究生学位课程 99 4 6 3 浙江大学研究生学位课程 100 4 6 3 浙江大学研究生学位课程 101 4 6 3 表4 5各种方法比较 浙江大学研究生学位课程 102 4 7直接法 Simplex Powell 大量的目标函数是很复杂的 有时连解析式都没有 因而它的导数 f x 很难求 有时甚至不存在 4 7 1单纯形法SimplexMethodNelder Mead 1965 提出这种简单的方法 它不需要求导数 梯度 对变元不多的情况是有效的 程序简单 浙江大学研究生学位课程 103 4 7 1单纯形的思想是在n维空间的 n 1 个点 它们构成单纯形 上引进函数值比较 丢弃最坏的点并代之以新点 它们仍然构成单纯形 以此逐步逼近极小点 浙江大学研究生学位课程 104 4 7 1 图4 30单纯形法中的反射 浙江大学研究生学位课程 105 4 7 1 图4 31单纯形法中的延伸 浙江大学研究生学位课程 106 4 7 1 浙江大学研究生学位课程 107 4 7 1 图4 32单纯形法中的收缩 浙江大学研究生学位课程 108 4 7 1e 缩小边长 图4 33单纯形法中的缩小边长 浙江大学研究生学位课程 109 4 7 1单纯形法 Simplex 框图 解x x0 图4 34单纯形法计算框图 浙江大学研究生学位课程 110 以上的迭代过程直到满足精度为止 精度 则x0作为所求的近似解 4 7 2Powelll方法Powelll方法是一种不依赖于目标函数梯度的直接搜索法 它逐步构造共轭方向并作为搜索方向 因此Powell方法也是一种共轭方向法 它的基本过程如下 浙江大学研究生学位课程 111 4 7 2 图4 35Powell搜索路径 表4 6Powell方法解题过程 5 0 2 5 浙江大学研究生学位课程 112 4 7 2 浙江大学研究生学位课程 113 4 7 2Powell方法过程图示 图4 36Powell方法计算过程图示 浙江大学研究生学位课程 114 4 7 2 循环上面 1 3 直至P0点函数值不再减小为止 当循环k次 k n 以后 un与它前面的k 1个向量un k 1 un 1共轭 因此对于二次函数 理论上只要循环n次即可求得极小值 即具有二次收敛性 事实上 因为P0和Pn是沿相同方向un求得的极小值 所以Pn P0与un方向共轭 图4 37共轭方向 浙江大学研究生学位课程 115 4 7 2 图4 38Powell方法计算过程示意 浙江大学研究生学位课程 116 4 7 2 表4 7Powell方法第一次循环计算结果 浙江大学研究生学位课程 117 图4 39单纯形法求一维极值示意图 1 4 7 2 浙江大学研究生学位课程 118 图4 40单纯形法求一维极值示意图 2 4 7 2 浙江大学研究生学位课程 119 4 7 2 但是 实际计算中对二次函数也不能保证n步内达到极小值点 因为每一循环都用Pn P0 挤掉 u1 所以新的向量系ui I 1 n 有可能线性相关 例如 某一循环中 如果 1 则这样 u2 u3 Pn P0是线性相关的 当发生这种情况时 以后的搜索就在n维的子空间中进行 最后的解就不正确 解决的办法是Pn P0不是挤掉u1