迭代法s1s2二分法和迭代法原理.ppt
第三章迭代法第三章迭代法3.1 二分法二分法3.2 迭代法原理迭代法原理3.3 Newton迭代法和迭代加速迭代法和迭代加速3.4 解线性方程组的迭代法解线性方程组的迭代法 3.1 二分法二分法 根的估计根的估计 二分法二分法非线性方程的根非线性方程的根求求 f(x)=0 的根的根q 代数方程：代数方程：f(x)=a0+a1x+.+anxn超越方程：超越方程：f(x)含超越函数，如含超越函数，如 sin(x),ex,lnx 等等q 实根与复根实根与复根q 根的重数根的重数 f(x)=(x x*)m g(x)且且 g(x*)0,则称则称 x*为为 f(x)的的 m 重根重根q 有根区间：有根区间：a,b 上存在上存在 f(x)=0 的一个实根的一个实根在在有根的前提下求出方程的的前提下求出方程的近似根。研究研究 内容内容:根的估计根的估计引理引理3.1（连续函数的介值定理连续函数的介值定理）设设f(x)在在a,b上连续，且上连续，且f(a)f(b)0，则存在，则存在x*(a,b)使使f(x*)=0。例例3.1 证明证明x3 3x 1=0 有且仅有有且仅有3个实根，并个实根，并确定根的大致位置使误差不超过确定根的大致位置使误差不超过 =0.5。解解:单调性分析和解的位置单调性分析和解的位置选步长选步长h=2,扫描节点函数值扫描节点函数值异号区间内有根异号区间内有根第一节第一节 二分法二分法若若 f Ca,b，且，且 f(a)f(b)0，则，则 f 在在(a,b)上必有一上必有一根。根。p 基本原理：基本原理：p 具体方法：具体方法：通过二等分不断缩小有根区间的长度，直到满足精度为止。通过二等分不断缩小有根区间的长度，直到满足精度为止。abx0 x1x*何时终止何时终止?或或不能保证不能保证 x 的精的精度度算法算法算法 3.1(二分法二分法)给定有根区间给定有根区间 a,b(f(a)f(b)0)和和 精度要求精度要求 1.令令 x=(a+b)/22.如果如果 b a=2,停止计算，输出停止计算，输出 x,否则执行第否则执行第3步步3.如果如果 f(a)f(x)0,则令则令 b=x，否则令，否则令 a=x,返回第返回第1步步P50.Matlab源程序：源程序：nabisect.m用二分法求根，通常先给出用二分法求根，通常先给出 f(x)草图以确定根的大概位置。草图以确定根的大概位置。误差分析误差分析记记 a0=a,b0=b,第第 k 步的有根区间为步的有根区间为 ak,bk对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k：取取 简单易用简单易用 无法求复根及偶重根无法求复根及偶重根 对对 f(x)要求不高，只要连续即可要求不高，只要连续即可 收敛速度慢收敛速度慢 例例3.2 求求x3 3x 1=0在在 1,2内的根内的根两位有效数字两位有效数字 =0.5*10-1,k(ln 20/ln 2)-1,取取k=43.2 迭代法原理迭代法原理迭代法的思想迭代法的思想 不动点原理不动点原理 局部收敛性局部收敛性收敛性的阶收敛性的阶 (x)的不动点的不动点x*第二节第二节 迭代法原理迭代法原理f(x)=0 x=(x)称为迭代函数称为迭代函数等价变换等价变换p 基本思想基本思想从一个给定的初值从一个给定的初值 x0 出发，计算出发，计算 x1=(x0),x2=(x1),若若 收敛，即存在收敛，即存在 x*使得使得 ，则由，则由 的连的连续性和续性和 可得可得 x*=(x*)，即，即 x*是是 的不动点，也就是的不动点，也就是 f(x)的零点。的零点。p 具体做法：具体做法：不动点迭代f(x)的零点的零点x*p 几何含义：几何含义：求曲线求曲线 y=(x)与直线与直线 y=x 的交点的交点xk+1=(xk)xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 例例 x3 x 1=0,1,2,取取 x0=1.5迭代公式迭代公式1：迭代公式迭代公式2：计算结果：计算结果：公式公式1 1：公式公式2 2：怎么判断迭代公式收敛或发散呢？怎么判断迭代公式收敛或发散呢？精确解精确解x*=1.3247179.不动点原理不动点原理定理定理3.1设设 (x)在在a,b上连续，上连续，且一阶导数连续，若且一阶导数连续，若(2)0 L 1，使得，使得|(x)|L 对对 x a,b 成成立立则函数则函数 f(x)=x-(x)在在 a,b 中有中有唯一唯一的零点的零点 x*。(压缩映像定理，不动点原理压缩映像定理，不动点原理)x*称为称为 (x)的的不动点不动点 (x*)=x*(1)a (x)b 对一切对一切 x a,b 都成立都成立简证：简证：f(a)=a-(a)0,f(b)=b-(b)0f(x)在在a,b 上有零点。上有零点。唯一性：反证法，假设存在唯一性：反证法，假设存在 x*,y*a,b 使得使得x*=(x*)y*=(y*)矛盾！矛盾！封闭性封闭性 压缩性压缩性 收敛性分析收敛性分析定理定理3.1设设 (x)在在a,b上连续，上连续，且一阶导数连续，若且一阶导数连续，若(2)0 L 1，使得，使得|(x)|L 对对 x a,b 成成立立,(1)a (x)b 对一切对一切 x a,b 都成立都成立,则有则有(a)对任意对任意 x0 a,b，由，由 xk+1=(xk)产生的迭代序产生的迭代序列列 均收敛到均收敛到 (x)在在 a,b 中的唯一不动点中的唯一不动点 x*。(b)有如下的误差估计有如下的误差估计:可用可用|x k-xk-1|来控制收敛精度来控制收敛精度 L 越小收敛越快越小收敛越快 后验估计后验估计:先验估计先验估计:证：证：(a)由压缩映像定理可知，不动点由压缩映像定理可知，不动点 x*存在且唯一。存在且唯一。(b)又又全局收敛与局部收敛全局收敛与局部收敛p 定理的条件保证了不动点迭代的定理的条件保证了不动点迭代的全局收敛性全局收敛性。即迭代的收敛性与初始点的选取无关。即迭代的收敛性与初始点的选取无关。p 这种在这种在 x*的邻域内具有的收敛性称为的邻域内具有的收敛性称为局部收敛性局部收敛性。定理中的条件定理中的条件|(x)|L 1 可以适当放宽可以适当放宽(2)(x)在在 x*的某个邻域内连续，且的某个邻域内连续，且|(x*)|1由由 (x)的连续性及的连续性及|(x*)|1 即可推出：即可推出：定理定理3.23.2若若(x)的一阶导数连续的一阶导数连续,且满足条件且满足条件(2),则一定存则一定存在在 x*的的某个某个 邻域邻域 N(x*)=x*-,x*+,使得对使得对 x N(x*)都有都有|(x)|L 1,则由则由 x0 N(x*)开开始的迭代都收敛。始的迭代都收敛。具有局部收敛性的迭代计算上不一定收敛，它是否收敛还具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；要看初值是否取的恰当；而不具有局部收敛性的迭代对任何初值都不可能收敛。而不具有局部收敛性的迭代对任何初值都不可能收敛。例例例例 用不同方法求用不同方法求用不同方法求用不同方法求 x x2 2 3 3=0 0的根的根的根的根 ,取取取取 x x0 0=2.a=1,b=2=2.a=1,b=2讨论合理性和收敛性讨论合理性和收敛性讨论合理性和收敛性讨论合理性和收敛性迭代公式迭代公式1：迭代公式迭代公式2：迭代公式迭代公式3：迭代公式迭代公式4：计算结果：计算结果：怎么判断收敛的迭代公式的速度快慢呢？怎么判断收敛的迭代公式的速度快慢呢？精确值：精确值：1,21,2上迭代收敛性上迭代收敛性?1,21,2上迭代收敛性上迭代收敛性?收敛性的阶收敛性的阶设迭代设迭代 xk+1=(xk)收敛到收敛到 (x)的不动点的不动点 x*。记记 绝对误差绝对误差ek=xk x*，若若定义定义则称该迭代为则称该迭代为 p 阶收敛。(1)当当 p=1 时称为时称为线性收敛，此时，此时|C|1 时称为时称为超线性收敛。p 不动点迭代中，若不动点迭代中，若 迭代数列迭代数列xk收敛，且收敛，且 (x*)0，则则 取极限得取极限得(C为常数为常数)线性收敛线性收敛.p 阶收敛阶收敛设迭代设迭代 xk+1=(xk)，若，若 (p)(x)在在 x*的某邻域内连续，的某邻域内连续，则该迭代法具有则该迭代法具有 p 阶收敛的充分必要条件是阶收敛的充分必要条件是定理定理3.3并且有并且有证明：充分性充分性.根据泰勒展开有根据泰勒展开有
