计算方法第二章.ppt

软件学院 张奕韬 第2章 非线性方程求根 §1 二分法 原理 设[a, b]是方程f(x)=0的一个有根区间，取 以[a2, b2]取代[a1, b1]，继续以上过程，得到[a3, b3]……, 直到某一xk时， ，使f(xk)=0，则xk是f(x)=0 的根；若不存在这样的xk，能得到一系列闭区间： 表明存在x*， f(x*)=0 ， x* ?[ak , bk]，因此{ak }单调上升，有上界x* ， {bk }单调下降，有下界x* ，且这二个序列均存在极限，因为： 定 理2.1 误差 分析： 二分法求根算法 例 §3 迭代法 迭代法的几何意义 方程x = g (x)的求根问题，在几何上就是确定xy平面内直线y = x和y = g (x)的交点p*。 定理2.2 示例 §4 牛顿法 牛顿法的几何意义 定理2.5 定理2.6 示例 ? 正割法 示例 ? 下山法 原理： 例： 求f(x)=x3-x-1在1.5附近的根 如果初值取1.5，则： f(1.5)0, f’(x)=3x2-1!=0, f’’(x)=6x, f’’(1.5)0 所以满足收敛条件。 若取x0=0.6,得x1=17.9, 与可能值相差很大。 即使能收敛也很慢，改用下山法。 设下山因子λ §5 迭代法的收敛阶 * * 非线性方程 含有指数和余弦的超越方程 高次代数方程和超越方程统称为非线性方程。 对于非线性方程f(x)=0，既无直接法可言，也无一定章程可循。 非线性方程的解称为方程的根或函数的零点。 非线性方程的根不止一个。在求解非线性方程时，要给定初始值或求解范围。 非线性方程求解的基本思想 确定非线性方程实根范围的方法 图解法： 计算机比较难实现，对人使用方便。 逐步扫描法： 便于计算机实现。 2. 对方程根进一步精确化的方法 二分法，迭代法，Newton迭代法 依据：若 f ?C[a, b]，且 f (a) · f (b) 0，则 f 在 (a, b) 上必有一根。此时[a, b]称为有根区间。 是[a1, b1]的中点。 若f(x1) = 0，则x1是f(x) = 0的一个根， 若f(x1) f(a1) 0，则取a2=x1，b2=b1，否则取a2=a1，b2=x1 得到[a2, b2]，满足： 若 f ?C[a, b]，且 f (a) · f (b) 0，则由二分法产生的序列{xk} 收敛于f (x) =0的一个根x*，且 a b x1 x2 a b When to stop? 或 不能保证 x 的精度 x* ?2 x x* f(x)在根的附近变化非常缓慢，|f(x)|很小，而x距离精确解还有相当的距离 为了避免无休止的计算，给出两个适当小的正数?1，?2 第1步产生的 有误差 第 k 步产生的 xk 有误差 对于给定的精度 ? ,可估计二分法所需的步数 k ： ①简单; ② 对f (x) 要求不高(只要连续即可) . ①无法求复根及多个根 ② 收敛慢 注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用有哪些信誉好的足球投注网站程序，将[a, b]分为若干小区间，对每一个满足 f (ak)·f (bk) 0 的区间调用二分法程序，可找出区间[a, b]内的多个根，且不必要求 f (a)·f (b) 0 。 例 所以?(x)的近似解为 f (x) = 0 x = g (x) 等价变换 f (x) 的根 g (x) 的不动点 思路 从一个初值 x0 出发，计算 x1 = g(x0), x2 = g(x1), …, xk+1 = g(xk), … 若 收敛，即存在 x* 使得 ，且 g 连续，则由 可知 x* = g(x* )，即x* 是 g 的不动点，也就是f 的根。 我不相信如此简单， 问题究竟是什么？ 如何保证它的收敛性？ x y y = x x* y=g(x) x0 p0 x1 p1 Q1 Q2 p2 x2 如此继续，曲线y = g (x)得到点列p1,p2,…其横坐标分别为x1,x2,…如果点列{pk}趋向于p*,则相应的迭代值xk收敛到所求的根x*。 可是这样做一定会收敛吗？ x y y = x x y y = x x y y = x x y y = x x* x* x* x* y=g(x) y=g(x) y=g(x) y=g(x) x0 p0 x1 p1 ? x0 p0 x1 p1 ? x0 p0 x1 p1 ? x0 p0 x1 p1 ? 考虑方程 x = g(x), g(x)