非线性方程与非线性方程组的迭代解法(一)

第四章非线性方程与非线性方程组的迭代解法一、非线性方程（组）的近似求解的必要性（1）单个方程情形：在非线性方程的求解中，多项式求根是常见且最简单的情形。根据代数基本定理，在复数域内，n次多项式至少有一个根，而由Galois（伽罗华）理论，5次以上（含5次）的多项式无根式求解。从而近似求解方程就成为必需的了。除多项式求根以外，更多的是超越方程求根问题。例如天体力学中有如下Kepler（开普勒）方程：10,0sinxtx其中t表示时间，行星运动的轨道x是t的函数。该方程不能精确解出运动轨道位置x(t)。（2）多个方程情形：在用数值方法求解常微分方程组时经常遇到非线性方程组求根问题。二、非线性方程（组）求解研究的难点（1）解的存在性、唯一性不易确定；（2）迭代解法求解；（3）迭代法的收敛性往往为局部收敛。三、求解非线性方程的近似解的步骤（1）判断根的存在性；（2）确定根的分布区间；（3）根的精确化。问题：设有非线性方程0xf（1）其中xf为一元非线性函数。若常数s使得0sf，则称s是方程（1）的根（或xf的零点）。若xgsxxfm其中0sg，则称s是（方程1）的m重根（或xf的m重零点。当m=1时，s称为方程（1）的单根或xf的单零点。4.1对分法和简单迭代法一、对分法基本思想：对有根区间不断进行对分，即逐渐二分有根区间，得一系列有根区间001111,,,,babababakkkk，当k充分大时，取kkba,的中点作为根的近似值。。对分法具体算法流程参并且设67,0,,pagebfafbaCxf122,2,,,kkkkkkkkkababsxbaxbasNksxkklim优点：算法简单方便，其收敛性总能保证；缺点：可能漏根。例1：求1222xxxf的根。二、简单迭代法及其收敛性1、基本思想将方程（1）改写成等价形式xx（2）构造迭代公式Rxkxxkk01,2,1,0,（3）由此产生一迭代序列1kkx。在一定的条件下我们希望该序列是收敛的，于是当k充分大时，可取kx作为方程（1）的近似根。迭代法（3）称为求解方程（1）的简单迭代法，x称为迭代函数。。不动点是迭代函数即两边取极限注：xsssxxkk,,,1故简单迭代法又称为不动点迭代法。收敛情形不收敛情形问题1：这样求根的近似值的理论依据是什么？问题2：怎样构造等价方程？问题3：序列1kkx是否收敛？收敛的条件是什么？且满足以下条件内可导在：设函数定理,,,,1.4babaCx；时当）（baxbax,,,1则有如下结论：；上有唯一的根）在区间方程（sba,2)1(,,3,,200baxbaxkk）产生的序列简单迭代法（对任取的）（；且收敛于s成立误差估计式)3(011xxLLxskk11kkkxxLLxs2、收敛条件为一常数；其中时当）（LLxbax,1,,2,,,)1(11baxxxkkk若的。的迭代格式称为是适定：满足条件注于自身。也可理解为映射。条件其迭代过程进行不下去则babaxk,)1(,,1是的迭代函数故满足条件中由于：条件注xyxyx)2(,)2(2上的一个压缩映射。ba,利用第一式可求第二式称为后验估计。的第一式称为先验估计：结论注,)3(3终止的条件。利用第二式可给出迭代所需的最少迭代次数出达到指定精度;此时收敛缓慢；还可能很大但误差很小即使时：注,,,141kkkxsxxL收敛愈快。愈小kxL,例2：用简单迭代法求上的根。，在3,2523xxxf5)3(52)2(52131131kkkkkkkxxxxxxx）（解：迭代格式k迭代格式（一）迭代格式（二）迭代格式（三）022212.0800842.121320122.0923512.087348-532.0942172.096517-12542.0945012.094017-195300552.0945432.0946971810449207.7则如果的某个开区间内连续在包含：设定理,1,,2.4ssxssssxssxk,)3(,,,00产生的序列由简单迭代法时当存在。且收敛于s3、收敛阶如果存在常。并且收敛于：设序列定义,2,1,0,0,1kxsesxkkk)(,lim,011某个正整数或者使得当成立使得和常数数Kkceecrrkkkkkrkkxrsxcee阶收敛速度，简称且具有收敛于则称序列成立有时,,1。收敛因子称为渐近收敛常数常数阶收敛的是)(,crr=1；r=2；r1；时当）（baxbax,,,1且满足以下条件：设函数定理,,,,3.4baCxbaCx为一常数；其中时当）（LLxxbax,1,0,,2收敛于所产生的序列由简单迭代法则对任取的kxbax)3(,,0是线性时并且当区间内的唯一的根在方程kxsxsba,,,)2(0收敛的。,,)2(4.4ssmsxm的某个开区间内连续在包含：设定理ssxsmismi,,0,0,1,,2,1,00当则存在如果。阶收敛速度收敛于以产生的序列由简单迭代法时但smxsxk)3(,0例题3：3,2,523xxxxf313152,52)1(xxxxkk迭代格式31321392,052231Lxxxxxxkk52,52)2(21迭代格式2125,055221222Lxxx5,5)3(3331xxxxxxkkk迭代格式26,13323Lxx一阶一阶0,23526,2352223231sxxxxxxxxkkk2352,5223,05223333xxxxxxxx至少二阶收敛速度。例2的改进：4、迭代法收敛的加速Steffensen迭代法Aitken迭代法