非线性方程的牛顿法

数值分析非线性方程的牛顿法 NewtonMethodofNonlinearEquations 内容提纲 Outline 牛顿法及其几何意义收敛性及其收敛速度计算实例及其程序演示 取x0作为初始近似值 将f x 在x0做Taylor展开 重复上述过程 作为第一次近似值 一 牛顿法及其几何意义 Newton迭代公式 基本思路 将非线性方程f x 0线性化 牛顿法的几何意义 x1 x2 牛顿法也称为切线法 局部收敛性定理 设f x C2 a b 若x 为f x 在 a b 上的根 且f x 0 则存在x 的邻域使得任取初始值 Newton法产生的序列 xk 收敛到x 且满足 至少平方收敛 二 牛顿法的收敛性与收敛速度 在x 的附近收敛 由Taylor展开 令k 由f x 0 即可得结论 证明 Newton法实际上是一种特殊的迭代法 设x 是f的m重根 则令 且 Answer1 有局部收敛性 Answer2 线性收敛 注 Newton法的收敛性依赖于x0的选取 x 有根 根唯一 全局收敛性定理 定理4 7 设f x C2 a b 若f a f b 0 则由Newton法产生的序列 xk 单调地收敛到f x 0在 a b 的唯一根x 且收敛速度至少是二阶的 保证Newton迭代函数将 a b 映射于自身 将f x 在xk处作Taylor展开 对迭代公式两边取极限 得 说明数列 xk 有下界 故 xk 单调递减 从而 xk 收敛 令 三 计算实例及其程序演示 辅助工具 VC程序设计语言Matlab数学软件 1 选定初值x0 计算f x0 f x0 计算步骤 2 按公式迭代得新的近似值xk 1 3 对于给定的允许精度 如果则终止迭代 取 否则k k 1 再转步骤 2 计算 允许精度 最大迭代次数 迭代信息 例题1 用Newton法求方程的根 要求 取初值x0 0 0 计算如下 对迭代格式一 theiterativenumberis27 thenumericalsolutionis0 442852706对迭代格式二 theiterativenumberis3 thenumericalsolutionis0 442854401 例题2 求函数的正实根精度要求 从图形中我们可以看出 在x 7和x 8之间有一单根 在x 1和x 2之间有一重根 用Matlab画图 查看根的分布情形 初值x0 8 0时 计算的是单根 Theiterativenumberis28 Thenumericalsolutionis7 600001481初值x0 1 0 计算的是重根 Theiterativenumberis1356 Thenumericalsolutionis1 198631981 例3 设C为正实数 导出用牛顿法求的公式 并证明 解 设 则于是有由于所以在内有一正根 又在内 根据定理得牛顿迭代格式为 迭代序列的误差满足 因为 所以注意 由上式可得 即该迭代格式是2阶收敛的 例4求方程的解 解 设 则f 0 1 f 2 1 在 0 2 内 f x 0 f 0 f 0 0 所以迭代格式为 MATLAB程序为 function x k Newton x0 dx eps eps tolerancek 0 whiledx epsx k 1 x0 exp x0 4 2 x0 1 exp x0 4 x0 6 4 dx abs x k 1 x0 x0 x k 1 k k 1 end 取x0 0及x0 3 计算结果比较精确 如果改写x0 8 又会怎样呢 计算结果如下 x 1 8 fork 2 3x k x k 1 2 x k 1 exp x k 1 4 1 exp x k 1 4 x k 1 6 4 endxx 8 000034 7781869 1528 定理4 7指出 x0的选取是很要紧的 例如此例 选x0 0则完全符合定理条件 可确保迭代格式收敛 选x0 3也可收敛 说明定理条件是充分条件 但如果选x0 8则发散 小结 1 当f x 充分光滑且x 是f x 0的单根时 牛顿法在x 的附近至少是平方收敛的 2 当f x 充分光滑且x 是f x 0的重根时 牛顿法在x 的附近是线性收敛的 3 Newton法在区间 a b 上的收敛性依赖于初值x0的选取 重根 multipleroot 加速收敛法 Q1 若 Newton sMethod是否仍收敛 设x 是f的n重根 则 且 因为Newton sMethod事实上是一种特殊的不动点迭代 其中 则 A1 有局部收敛性 但重数n越高 收敛越慢 Q2 如何加速重根的收敛 A2 将求f的重根转化为求另一函数的单根 令 则f的重根 的单根 正割法 SecantMethod Newton sMethod一步要计算f和f 相当于2个函数值 比较费时 现用f的值近似f 可少算一个函数值 切线 tangentline 割线 secantline 切线斜率 割线斜率 需要2个初值x0和x1 收敛比Newton sMethod慢 且对初值要求同样高 下山法 DescentMethod Newton sMethod局部微调 原理 若由xk得到的xk 1不能使 f 减小 则在xk和xk 1之间找一个更好的点 使得 注 1时就是Newton sMethod公式 当 1代入效果不好时 将 减半计算 Algorithm Newton sDescentMethodFindasolutiontof x 0givenaninitialapproximationx0 Input initialapproximationx0 f x andf x minimumstepsizeofxmin toleranceTOL1forx toleranceTOL2for maximumnumberofiterationsNmax Output approximatesolutionxormessageoffailure Step1Setk 1 Step2While k Nmax dosteps3 10Step3Set 1 Step4Set computexk Step5If x x0 TOL2thenGOTOStep4 computeabetterxi Step9Setx0 x0 xmin moveforwardanywaytoavoiddeadlock Step10Setk Step11Output MethodfailedafterNmaxiterations STOP unsuccessful 计算量未见得减小 求复根 FindingComplexRoots Newton公式中的自变量可以是复数 记z x iy z0为初值 同样有 设 代入公式 令实 虚部对应相等 可得 解非线性方程组的牛顿法 将非线性方程组线性化 得到 其中F xk 为F x 在xk处的Jacobi矩阵 例 用牛顿法解方程组 取初始值 1 1 1 计算如下 Nxyz01 00000001 00000001 000000002 18932601 59847511 39390061 85058961 44425141 27822401 78016111 42443591 23929241 77767471 42396091 23747381 77767191 42396051 23747111 77767191 42396051 2374711 练习 3 New