《数值分析与算法》第二讲非线性方程求根

1、数数 值值 分分 析析 (2)Numerical AnalysisWenjian Yu2第二章第二章 非线性方程求根非线性方程求根n引言引言n二分法二分法n不动点迭代法不动点迭代法n牛顿迭代法牛顿迭代法n牛顿法的改进牛顿法的改进n有关的实用技术有关的实用技术Wenjian Yu3引言引言Wenjian Yu4非线性方程基本理论非线性方程基本理论nWenjian Yu5非线性方程基本理论非线性方程基本理论n(绝对条件数绝对条件数)Wenjian Yu6二分法二分法Wenjian Yu7二分法二分法nWenjian Yu 8二分法二分法n算法稳定性算法稳定性: 运算简单运算简单, 误差逐渐缩小误差

2、逐渐缩小, 因此稳定因此稳定Wenjian Yu9二分法二分法n相邻的两个浮点数相邻的两个浮点数(format hex按按16进制显示进制显示)(定理定理2.22.2)Wenjian Yu10二分法的总结二分法的总结nWenjian Yu11不动点迭代法不动点迭代法Wenjian Yu12不动点迭代不动点迭代n推出迭代法推出迭代法:x* x计算过程的几何含义计算过程的几何含义为什么？为什么？x0 x1x2Wenjian Yu13不动点迭代不动点迭代n关键问题：如何判断收敛性？关键问题：如何判断收敛性？(5位有效数字不变位有效数字不变)(计算量较小计算量较小)Wenjian Yu14全局收敛的充

3、分条件全局收敛的充分条件n唯一性的证明用反证法唯一性的证明用反证法Wenjian Yu15全局收敛的充分条件全局收敛的充分条件n(条件条件(1)是算法执行的前提是算法执行的前提)Wenjian Yu16全局收敛的充分条件全局收敛的充分条件n这就是这就是定理定理2.5为什么可以换？为什么可以换？便于使用便于使用Wenjian Yu17全局收敛的充分条件全局收敛的充分条件n, 满足条件满足条件(2) !不满足条件不满足条件(1), 无法无法说明是否收敛说明是否收敛思考思考: 从图形角度从图形角度, 举不满足条件举不满足条件(1), (2)但收敛的例子但收敛的例子Wenjian Yu18局部收敛局部

4、收敛n(强调存在某个邻域)(利用定理利用定理2.5)满足条件满足条件(1). 根据定理根据定理2.5, 收敛收敛！Wenjian Yu19局部收敛局部收敛n误差有放大的趋势误差有放大的趋势可能可能Wenjian Yu20稳定性与收敛阶稳定性与收敛阶n(合理设置判停准则合理设置判停准则, 稍后讲牛顿法时介绍稍后讲牛顿法时介绍)线性线性平方平方(超线性超线性)Wenjian Yu21稳定性与收敛阶稳定性与收敛阶nWenjian Yu22稳定性与收敛阶稳定性与收敛阶n方法方法q阶收敛阶收敛. 矛盾矛盾!Wenjian Yu23牛顿法牛顿法Wenjian Yu24牛顿法牛顿法nx* xxkxk+1=0

5、Wenjian Yu25牛顿法牛顿法n(请自行推导请自行推导)Wenjian Yu26牛顿法牛顿法n(课本课本2.4.2小节小节)Wenjian Yu27迭代法的判停准则迭代法的判停准则n判停准则决定了解的准确判停准则决定了解的准确度、及迭代步数度、及迭代步数(计算量计算量)相比二分法相比二分法, 较难设置较难设置敏感问题敏感问题Wenjian Yu28牛顿法的问题牛顿法的问题n一阶导数不连续一阶导数不连续!Wenjian Yu29割线法与抛物线法割线法与抛物线法Wenjian Yu30割线法与抛物线法割线法与抛物线法nx* x(超线性超线性)xk-1xkxk+1Wenjian Yu31割线法

6、与抛物线法割线法与抛物线法n抛物线抛物线xk+1 0 xyxk xk-1 xk-2Wenjian Yu32实用的求根技术实用的求根技术Wenjian Yu33实用的方程求根技术实用的方程求根技术n阻尼牛顿法阻尼牛顿法n多项式方程求根多项式方程求根 (2.6.2小节不要求小节不要求)n通用求根算法通用求根算法zeroin (简略简略)Wenjian Yu34阻尼牛顿法阻尼牛顿法nWenjian Yu35通用求根算法通用求根算法zeroinnWenjian Yu36通用求根算法通用求根算法zeroinn纠正纠正上一上一步解步解的偏的偏离离Wenjian Yu37通用求根算法通用求根算法zeroinn详细的详细的Matlab算法程序见课本算法程序见课本p