非线性方程组的数值解法.pptx

《非线性方程组的数值解法.pptx》由会员分享，可在线阅读，更多相关《非线性方程组的数值解法.pptx（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Th2.10 局部收敛性局部收敛性 设设 表示区间表示区间 ，x*为方程为方程 f(x)=0的根，的根，函数函数f(x)在在 中有中有足够阶连续导数足够阶连续导数，且且 满足满足 则对则对 ，由割线法产生的序列，由割线法产生的序列 都收敛于都收敛于x*，且，且(i)(ii)(iii)其中其中收敛速度介于收敛速度介于Newton and Bisection 之间之间 证明详证明详见见林成林成森森编写编写的数值的数值计算方计算方法法第1页/共34页Corollary(推论推论)设设 x*为方程为方程 f(x)=0的一个根，的一个根，且且 在在 x*的附近连续，则的附近连续，则 使得使得 由由Sec

2、ant Method产生的序列产生的序列 都收敛于都收敛于x*。例例2 证明方程证明方程 在区间在区间 内有内有唯一唯一根根 ，且，且使得对任意的初始值使得对任意的初始值 ，由，由割线法割线法产生的序列产生的序列 都收敛于都收敛于 。证明：证明：令令方程方程存在存在根根方程存在方程存在唯一唯一根根且且在在 附近连续附近连续由由推论推论知，由知，由割线法割线法产生的序列产生的序列 都收敛于都收敛于 。第2页/共34页 6 非线性方程组的解法非线性方程组的解法 /*The Solutions for Systems of Nonlinear Equations*/一、基本概念一、基本概念(/*Ba

3、sic Concepts*/)n个方程的个方程的n元非线性方程组的一般形式：元非线性方程组的一般形式：其中其中 是定义在区域是定义在区域 上的上的n元实值函数，且元实值函数，且 中至少有一个是中至少有一个是非线性函数非线性函数。如如第3页/共34页是是向量向量n个方程的个方程的n元非线性方程组的元非线性方程组的向量向量形式：形式：令令方程组方程组(*)(*)可表示成向量形式可表示成向量形式 其中其中 是定义在区域是定义在区域 上的上的n维维实向量值实向量值函数函数如果如果 使使 则称则称 是方程组（是方程组（*）的解。）的解。设设 若存在向量若存在向量 ，满足，满足则称则称 在在 处处可微可微

4、，向量，向量 称为称为 在在 处的处的导数导数，记为，记为若若 是开区域且是开区域且 在在 内每点处都可微，则称内每点处都可微，则称 在在 可微。可微。（n元实值函数的可微性元实值函数的可微性）/*Real Valued Function of n variables*/第4页/共34页证明：证明：令令Th2.11 （导数的求法导数的求法）若若 在在 处可微，则处可微，则 在在 处关于处关于各自变量各自变量的偏导数的偏导数 存在，且有存在，且有 /*Differentiate*/第5页/共34页 第6页/共34页Frechet导数导数（n元向量函数的可微性元向量函数的可微性）记记 ，若存在矩阵

5、，若存在矩阵 ，满足，满足则称则称 在在 处可微，矩阵处可微，矩阵 称为称为 在在 处的导数，记为处的导数，记为 。若。若 是开区域且是开区域且 在在 内每点都可微，则称内每点都可微，则称 在在 上可微上可微。/*Vector Function*/注：注：多元实值函数多元实值函数 的导数实际上就是函数的导数实际上就是函数 的梯度的梯度 。第7页/共34页Th2.12 （Frechet导数的计算导数的计算）设设 ，在在 处可微的充要条件是处可微的充要条件是的所有分量的所有分量 在在 处可微；若处可微；若 在在 处可微，则处可微，则第8页/共34页证明：证明：在在 处可微处可微所以存在所以存在向量

6、向量等价于等价于其中其中即即 是是 在在 处可微的处可微的充要条件充要条件 在在 处可微处可微Th2.11第9页/共34页所以所以称为称为Jacobi矩阵矩阵第10页/共34页（收敛阶收敛阶/*the order of Convergence*/)设向量序列设向量序列 收敛于向量收敛于向量 ，若存在实数，若存在实数 及常数及常数 ，满足，满足 或者或者满足当满足当 （某个正整数）时，（某个正整数）时，则称序列则称序列 是是 阶收敛的。当阶收敛的。当 且且 时，称时，称为线性收敛，为线性收敛，为超线性收敛，为超线性收敛，时为平方或二次收敛时为平方或二次收敛第11页/共34页二、二、Newton迭

7、代法迭代法令令设方程组（设方程组（*）存在解）存在解 在在 的某个开邻域的某个开邻域 内可微内可微设设 是方程组（是方程组（*）的第）的第 次近似解次近似解Taylor公式展开公式展开1、Newton迭代格式迭代格式第12页/共34页写成写成向量向量形式形式用该线性方程组的解作为非线性方程组（用该线性方程组的解作为非线性方程组（*）的第）的第k+1k+1次近似解次近似解从而得到从而得到Newton迭代格式：迭代格式：注：注：Newton迭代格式中迭代格式中每迭代一步每迭代一步都要求矩阵的都要求矩阵的逆运算逆运算，计算量大，应该想办，计算量大，应该想办法法避免避免。第13页/共34页Newton

8、迭代方法在实际计算时，转化为求迭代方法在实际计算时，转化为求方程组的解方程组的解缺陷缺陷每每迭代一次需要计算迭代一次需要计算Jacobi矩阵，计算量仍然很大矩阵，计算量仍然很大 需要进一步改进需要进一步改进第14页/共34页 算法算法:Newton迭代迭代给定初始近似值给定初始近似值 x(0)，求非线性方程，求非线性方程F(x)=0 的解的解.输入输入:初始近似值初始近似值 x(0);容许误差容许误差 TOL;最大迭代次数最大迭代次数 Nmax.输出输出:近似解近似解 x*或失败信息或失败信息.Step 1 Set k=1;Step 2 While(k Nmax)do steps 3-7Ste

9、p 3 计算计算 和和Step 4 求解线性方程组求解线性方程组 Step 5 If|x x(0)|/|x(0)|TOL then Output(x);/*成功成功*/STOP;Step 6 Set k+;Step 7 Set x(0)=x;/*更新更新 x(0)*/Step 8 Output(The method failed after Nmax iterations);/*不成功不成功*/STOP.第15页/共34页解：解：例例5：用用Newton迭代法求解下列方程组，要求迭代法求解下列方程组，要求选取选取解方程组解方程组即即最终结果见教材最终结果见教材P35表表2-6第16页/共34页

10、2、Newton迭代的局部收敛性迭代的局部收敛性Th2.13（压缩映射原理（压缩映射原理/*Compression Mapping Principle*/）设设 为为 中的一个闭集，中的一个闭集，为压缩映射，即它满足条件：为压缩映射，即它满足条件：则下列结论成立：则下列结论成立：（1 1）对任意的对任意的 ，由，由Newton法法产生的迭代序列产生的迭代序列 都有都有 （2 2）在在 上有唯一的不动点上有唯一的不动点 ，且，且 ；（3 3），即，即 至少线性收敛；至少线性收敛；（4 4）有估计式有估计式证明详证明详见见3第17页/共34页证明见证明见P P124124引理引理2（Lemma 2

11、）引理引理1（Lemma 1）设设 ，且，且 ，则，则 非奇异且非奇异且 。设设 ，为开凸集，为开凸集，在在 上可导。若存在常数上可导。若存在常数 ，使得，使得对对 ，都有，都有 则成立则成立第18页/共34页证明：证明：第19页/共34页Th2.14（Newton迭代的局部收敛性）迭代的局部收敛性）设设 是方程组（是方程组（*）的解，）的解，在包含在包含 的某个开区间的某个开区间 内连续内连续可微，且可微，且 非奇异，则存在闭球非奇异，则存在闭球 使对任意的使对任意的 ，由，由Newton法法产生的序列产生的序列 超线性收敛超线性收敛于于 ；若还有；若还有常数常数 使得使得 则牛顿迭代序列则

12、牛顿迭代序列 至少至少二阶二阶收敛于收敛于 。2 2、收敛条件、收敛条件:1 1、超线性收敛：、超线性收敛：映内性映内性 压缩性压缩性第20页/共34页收敛速度收敛速度快快，可以达到，可以达到二次二次收敛（但效率并不高）。收敛（但效率并不高）。每每迭代一次需要计算迭代一次需要计算Jacobi矩阵，计算量大；矩阵，计算量大；每每迭代一次迭代一次需要需要求解线性方程组，当求解线性方程组，当n很大时，很大时，工作量巨大。工作量巨大。另外：另外：另外：另外：一方面，一方面，一方面，一方面，用用Newton迭代迭代求非线性方程组的解，初值的选择往往比较困难；求非线性方程组的解，初值的选择往往比较困难；另

13、一方面，迭代过程中如果出现另一方面，迭代过程中如果出现Jacobi矩阵矩阵非奇异的情况，则非奇异的情况，则Newton迭代无法迭代无法进行下去进行下去。优点优点缺点缺点第21页/共34页3、Newton格式的变形（格式的变形（/*Modified Newton Method*/）带阻尼因子的带阻尼因子的Newton格式格式/*Damped Newton Method*/避免避免Jacobi矩阵矩阵 的奇异性或病态程度的奇异性或病态程度思思 想想措措施施在迭代格式中引入在迭代格式中引入阻尼因子阻尼因子注：注：注：注：的选择的选择的选择的选择要保证每次迭代产生的要保证每次迭代产生的要保证每次迭代产

14、生的要保证每次迭代产生的Jacobi矩阵非奇异且病态程度不十矩阵非奇异且病态程度不十分严重；适当的分严重；适当的 可使阻尼可使阻尼Newton法法是线性收敛的。是线性收敛的。第22页/共34页例例6：用用Newton法和阻尼法和阻尼Newton法求解方程法求解方程解：解：方程的精确解为方程的精确解为第23页/共34页阻尼阻尼Newton法法计算结果见计算结果见P38表表2-7第24页/共34页下降下降Newton格式格式（/*Descent Newton Method*/）减小对减小对初始向量值初始向量值的严格限制的严格限制引入引入下降因子下降因子思想思想措施措施的选取原则：的选取原则：优点：

15、优点：优点：优点：具有大范围收敛性。具有大范围收敛性。具有大范围收敛性。具有大范围收敛性。简化简化Newton格式格式/*Simplified Newton Method*/第25页/共34页修正的修正的Newton方法方法(/*Modified Newton Method*/)每次迭代要调用简化每次迭代要调用简化Newton格式格式m次次第26页/共34页离散的离散的Newton方法方法(/*Discrete Newton Method*/)思想思想避免避免Jacobi矩阵矩阵 中导数的计算中导数的计算方法方法第27页/共34页拟拟Newton方法方法(/*Quasi-Newton Meth

16、od*/)一、基本思想和拟牛顿方程一、基本思想和拟牛顿方程前面所讨论的牛顿法的这些变形，都可以写成如下形式：前面所讨论的牛顿法的这些变形，都可以写成如下形式：如如Newton方法中方法中为非奇异矩阵为非奇异矩阵其中其中为了提高为了提高计算效率计算效率，令，令或者或者称之为拟称之为拟Newton方程方程第28页/共34页如果取如果取 为为一元函数一元函数则上式中则上式中 表示过两点表示过两点 的的割线斜率割线斜率割线法割线法假设假设 已知，上述方程为已知，上述方程为n个变量、个变量、n2个未知数的方程，需要添加辅助条个未知数的方程，需要添加辅助条件才能得到件才能得到 .的的计算方法计算方法其中其

17、中 是是秩秩为为m的的增量增量矩阵矩阵由此得到的迭代法由此得到的迭代法(*)(*)称为拟称为拟Newton法法第29页/共34页二、二、Broyden秩秩1方法方法其中其中 为为n维列向量维列向量记记选择选择 、满足满足当当 时时由由 唯一确定唯一确定第30页/共34页的一种自然选取方法的一种自然选取方法Broyden秩秩1方法的迭代公式：方法的迭代公式：求逆运算求逆运算第31页/共34页引理引理3（Lemma 3）如果矩阵如果矩阵 非奇异，则非奇异，则 非奇异的充要条件是向量非奇异的充要条件是向量 满足满足 ，且有，且有（自己证明自己证明）令令第32页/共34页Broyden秩秩1方法的迭代公式变为：方法的迭代公式变为：时引理成立时引理成立第33页/共34页感谢您的观看！第34页/共34页