用牛顿法求解非线性方程

实验七实验七 非线性方程求根非线性方程求根 一 一 实验目标实验目标 1 掌握常用的非线性方程求根算法 二分法 不动点迭代法与 Newton 法 及加速技 术 Aitken 加速与 Steffsen 加速 2 会编写计算机程序实现给定迭代函数的迭代算法及其加速 掌握迭代算法的精度控 制方法 二 二 实验问题实验问题 求代数方程 的实根 053 3 xxxf 三 三 实验要求实验要求 1 方程有一个实根 将方程以下面六种不2 27902 2 215215 3 33 x 同方式等价地改写 构造迭代格式 计算 x a b c 2 53 x x x 3 5 3 x x 3 53 xx d e f 3 5 2 x x x x 5 3 1 53 3 1 2 3 x xx xx 2 对每一种迭代格式 编制一个程序进行运算 观察每种格式的敛散情况 用事后误 差估计来控制迭代次数 并且输出迭代的次数 观察不同初值 6 1 10 toltolxx kk 的结果 3 从理论上分析各种格式的收敛性及收敛阶 4 将收敛较慢的一种格式分别用 Atken 方法及 Steffsen 方法加速 通过输出结果了 解加速效果 5 将一种不收敛的方法用 Steffsen 方法加速得到收敛的迭代 数值分析实验指导数值分析实验指导 第第 1 页页 附录一 数值分析数值分析 实验报告 模板 实验报告 模板 实验课题实验课题 用牛顿迭代法求非线性方程根 实验目标实验目标 明确实验目标 1 掌握常用的非线性方程求根算法 二分法 不动点迭代法与 Newton 法 及加速技 术 Aitken 加速与 Steffsen 加速 2 会编写计算机程序实现给定迭代函数的迭代算法及其加速 掌握迭代算法的精度控 制方法 3 探索不同方式改写方程的收敛程度 理论概述与算法描述理论概述与算法描述 1 牛顿法 设已知方程 f x 0 有近似根 xk 将函数 f x 在点 xk 展开 有 f x f xk f xk x xk 于是方程可表示为 f xk f xk x xk 0 这是个线性方程 记其根为 x k 1 则 x k 1 xk f xk f xk 这就是牛顿迭代法求根 2 埃特金加速收敛方法 设 0 x 是根 x 的某个近似值 用迭代一次得 10 xx 而由微分中值定理 有 100 xxxxxx 其中 介于 x 和 0 x 之间 假设 x 改变不大 近似地取某个近似值 L 则有 10 xxL xx 若将校正值 10 xx 再迭代一次 又得 21 xx 由于 21 xxL xx 将它与前面的式子联立 消去未知的 L 有 01 21 xxxx xxxx 由此推知 22 02110 0 210210 22 x xxxx xx xxxxxx 记 数值分析实验指导数值分析实验指导 第第 2 页页 2 1 1 12 kk k k kkk xx xx xxx 称为埃特金加速方法 3 斯特芬森迭代法 将埃特金加速技巧与不动点迭代结合 则可得到如下的迭代法 2 1 2 kkkk kk kk kkk yxzy yx xx zyx 即为斯特芬森迭代法 实验问题实验问题 1 求代数方程 的实根 053 3 xxxf 2 方程有一个实根 将方程以下面六种不2 27902 2 215215 3 33 x 同方式等价地改写 构造迭代格式 计算 x a b c 2 53 x x x 3 5 3 x x 3 53 xx d e f 3 5 2 x x x x 5 3 1 53 3 1 2 3 x xx xx 3 对每一种迭代格式 编制一个程序进行运算 观察每种格式的敛散情况 用事后误 差估计来控制迭代次数 并且输出迭代的次数 观察不同初值 6 1 10 toltolxx kk 的结果 4 从理论上分析各种格式的收敛性及收敛阶 5 将收敛较慢的一种格式分别用 Atken 方法及 Steffsen 方法加速 通过输出结果了 解加速效果 6 将一种不收敛的方法用 Steffsen 方法加速得到收敛的迭代 实验过程与结果实验过程与结果 1 用用 matlab 编程计算代数方程的根编程计算代数方程的根 2 分别编写分别编写 6 个迭代法编程 对结果进行分析个迭代法编程 对结果进行分析 结果分析 讨论与结论结果分析 讨论与结论 迭代公式 1 x1 数值分析实验指导数值分析实验指导 第第 3 页页 2 0000 1 5000 2 0000 1 5000 2 0000 1 5000 2 0000 1 5000 2 0000 1 5000 2 0000 1 5000 2 0000 1 5000 2 0000 1 5000 2 0000 1 5000 2 0000 1 5000 迭代公式 2 x2 1 0e 142 0 0000 0 0000 0 0000 0 0000 0 0000 0 0000 0 0000 0 0000 0 0000 1 4947 Inf Inf Inf Inf Inf Inf Inf Inf Inf 数值分析实验指导数值分析实验指导 第第 4 页页 Inf 迭代公式 3 x3 2 0000 3 3166 3 8665 4 0743 4 1500 4 1773 4 1871 4 1906 4 1919 4 1923 4 1925 4 1926 4 1926 4 1926 4 1926 4 1926 4 1926 4 1926 4 1926 4 1926 迭代公式 4 x4 2 0000 5 0000 0 2273 1 6959 40 3095 0 0031 1 6667 22 5018 0 0099 1 6667 22 5185 0 0099 1 6667 22 5185 0 0099 1 6667 22 5185 数值分析实验指导数值分析实验指导 第第 5 页页 0 0099 1 6667 22 5185 迭代公式 5 x5 2 0000 2 3452 2 2654 2 2819 2 2784 2 2791 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 迭代公式 6 x6 2 0000 2 3333 2 2806 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 数值分析实验指导数值分析实验指导 第第 6 页页 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 从上述的运算结果可以看出 迭代公式 1 2 4 不收敛 3 虽然收敛 但与其他迭代 法的结果差异太大 对 5 和 6 分别用埃特金加速和斯特芬森迭代得到结果如下 对于 5 埃特金加速结果 B 2 0000 2 2804 2 2791 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 0 斯特芬森迭代结果 x 2 0000 2 1547 2 2792 2 2790 2 2790 2 2790 数值分析实验指导数值分析实验指导 第第 7 页页 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 2 2790 对于 6 埃特金加速结果 B 2 0000 2 2878 2 2790 2 2790 2 2790 2 2790 斯特芬森迭代结果 x 2 0000 2 1544 2 2838 2 2790 2 2790 从以上结果可以看出 埃特金加速方法和斯特芬森迭代法确实可以加快收敛速 度 且在此题的情况下 两种方法的加速效果差不多 但埃特金加速方法较斯特芬森迭代 法来说更为简单易理解 运算步骤也少一些 因此对于此题 我们可以选用埃特金加速方 法 附程序附程序 function k x da g newton x0 tol k 1 g1 fun1 x0 g2 fun2 x0 x1 x0 g1 g2 while abs x1 x0 tol 数值分析实验指导数值分析实验指导 第第 8 页页 x0 x1 g1 fun1 x0 g2 fun2 x0 k k 1 x1 x0 g1 g2 end k x x1 da abs x1 x0 2 g fun1 x end function g1 fun1 x g1 x 3 3 x 5 end function g2 fun2 x g2 3 x 2 3 end function g1 fun1 x g1 x 3 3 x 5 end function x Aitken A n length A x zeros n 1 t 0 x 1 A 1 for i 1 n 2 x i 1 A i A i 1 A i 2 A i 2 A i 1 A i 2 end function x Steffsen A B n length B x zeros n 1 x 1 B 1 for i 2 n x i A i B i 1 A i 2 B i 2 B i 1 A i end 构造迭代算法 x 3 x 5 x 2 function x diedai1 x0 tol N 数值分析实验指导数值分析实验指导 第第 9 页页 x0 是初值 tol 为迭代精度 N 是迭代最大次数 x zeros N 1 x 1 x0 k 1 t 0 while k N for i 2 N x i 3 x i 1 x i 1 2 end k k 1 t x i x i 1 if abs t tol break end end 构造迭代算法 x x 3 5 3 function x diedai2 x0 tol N x0 是初值 tol 为迭代精度 N 是迭代最大次数 x zeros N 1 x 1 x0 k 1 t 0 while k N for i 2 N x i x i 1 3 5 3 end k k 1 t x i x i 1 if abs t tol break end end 构造迭代算法 x 3 x 5 1 3 function x diedai3 x0 tol N x0 是初值 tol 为迭代精度 N 是迭代最大次数 x zeros N 1 x 1 x0 k 1 t 0 while k N for i 2 N x i 3 x i 1 5 1 2 数值分析实验指导数值分析实验指导 第第 10 页页 end k k 1 t x i x i 1 if abs t tol break end end 构造迭代算法 x 5 x 2 3 function x diedai4 x0 tol N x0 是初值 tol 为迭代精度 N 是迭代最大次数 x zeros N 1 x 1 x0 k 1 t 0 while k N for i 2 N x i 5 x i 1 2 3 end k k 1 t x i x i 1 if abs t tol break end end 构造迭代算法 x sqrt 3 5 x function x diedai5 x0 tol N x0 是初值 tol 为迭代精度 N 是迭代最大次数 x zeros N 1 x 1 x0 k 1 t 0 while k N for i 2 N x i sqrt 3 5 x i 1 end k k 1 t x i x i 1 if abs t tol b