太理水利工程计算及设计第三章 非线性方程.ppt

第一节 二分法 第二节 牛顿法 第三节 修正的牛顿法 第四节 弦截法 第五节 迭代法 第六节 求[a,b]区间上全部实根的方法 迭代法的局部收敛性定义 误差估计及结束迭代的条件 2. 迭代法的几何解释 x y y = x x* y=g(x) P* 方程的根就是曲线y=g(x）与直线y=x的交点p*的横坐标。 迭代的发展过程 x y y = x x* y=g(x) x0 p0 x1 p1 x2 P* 举例 用简单迭代法求方程 在x=0.5附近的根。 解: 方程的等价形式 简单迭代格式 取初值x0=0.5, 结果见表3-3。 迭代次数为14次。 二、收敛性与收敛速度 1. 收敛性 x y y = x x* y=g(x) x0 p* x1 x2 迭代过程是发散的 x y y = x x* y=g(x) x0 p0 x1 p1 x2 P* 迭代过程是收敛的 不同的迭代格式 方程 收敛的 发散的 迭代序列的收敛性与迭代函数g(x)的构造有关。 设g(x)满足条件 （1）当x?[a, b]时，g(x)?[a, b]。 （2）存在正数L 1，使对任意x?[a, b] 则x = g(x)在[a, b]上有唯一的根x*, 且对任意初值x0?[a, b]，迭代序列xn+1=g(xn) (n = 0, 1, 2…)收敛于x*。 简单迭代法收敛性定理 证明：（根的存在性） 由于在[a,b]上 存在，所以g(x)连续。令 故存在x* ?[a,b], 使 故 在[a,b]上连续。由条件(1)， （根的唯一性） 若有另一 , 由微分中值定理及条件（2）， 即 。 使 但0L1，故 即 。 方程有唯一根。 （根的收敛性） 又由 因L1，故知 在实际求根时，如果迭代函数g(x) 在根x*的某领域R内，满足 ，且迭代值xn仍在领域R内，则迭代序列对任意初始值x0 ?R，都收敛于根x*，这就是简单迭代法的局部收敛性。 对于任意正整数p，有 令p??，得 可见，只要 足够小，就能保证近似根xn有足够的精度。因此，设给定允许误差ε，则条件 可用来控制迭代过程的结束。 另两种结束迭代的条件 迭代次数n达到用户给定的最大允许迭代次数； 函数值满足 。 2. 收敛速度 衡量迭代法优劣的一个重要标志。 定义 现假定 是收敛于x*的序列，记 如果存在实数P和非零常数C，使得 则称序列是p阶收敛的，或者说序列收敛的阶数是p。这时的g(x)就是p阶迭代函数。特别地，p=1时是线性收敛，p=2时为平方收敛。P1为超线性收敛。 收敛阶越大，收敛越快。 对简单迭代法，通常假定 连续且不为零。 这说明对简单迭代法，相邻两次迭代的误差变化仅成线性关系，所以，简单迭代法为线性收敛的。 简单迭代法的收敛速度 牛顿迭代法的收敛速度 若f(x)连续，将f (x)在xn处按泰勒级数展开，并将x*代替x可得到 用 除等式两端得 即 可得到 弦截法收敛的阶是1.618。 牛顿迭代法是平方收敛的。 题4 用简单迭代法求方程 在[1,2]内的一个实根，取初始近似值x0=1.5。 假定 连续，则 在x*附近变化不大，故可取 设有迭代过程x=g(x), x*是所求的根。令 是xn的迭代值，故有 三、迭代过程的加速 1. 线性加速迭代法 加速算法 由微分中值定理，得 式（3-24）可写作 （3-24） （3-26） 用这样的估计值改进 ，可望得到更好的近似值，即有 考虑到迭代的收敛性，应有 。 由式（3-26）可得 其中 从而 （3-29） 式（3-29）就是迭代过程的一种线性加速算法。 线性加速迭代法总结如下: 2. 埃特金（Aitken）法 设xn是根x*的某次近似值。连续迭代两次，得到 故有 消去an，有 * * 第三章 非线性方程的数值方法 本章内容 重点 非线性方程求根的二分法、