方程组的迭代解法.ppt

也称为埃特金(Aitken)外推法.可以证明:为线性收敛,则埃特金法为平方收敛；这个加速迭代法也可写成下面格式若为p(p1)阶收敛，导数连续，则埃特金法为2p–1阶收敛.的p阶若第62页,共86页，星期六，2024年，5月例题求方程x=e–x在x=0.5附近的根.解取x0=0.5,迭代格式x25=x26=0.5671433若对此格式用埃特金法,则得第63页,共86页，星期六，2024年，5月仍取x0=0.5,得由此可见,埃特金法加速收敛效果是相当显著的.第64页,共86页，星期六，2024年，5月3.4牛顿法3.4.1牛顿法及其收敛性对于方程f(x)=0，如果f(x)是线性函数，则它的求根是容易的.牛顿法实质上是一种线性化方法，其基本思想是将非线性方程f(x)=0逐步归结为某种线性方程来求解.设已知方程f(x)=0有近似根x0，且在x0附近f(x)可用一阶泰勒多项式近似，表示为一、牛顿迭代法第65页,共86页，星期六，2024年，5月当f?(x0)≠0时，方程f(x)=0可用线性方程(切线)近似代替，即f(x0)+f?(x0)(x-x0)=0.(3.4.1)解此线性方程得得迭代公式此式称为牛顿(Newton)迭代公式.第66页,共86页，星期六，2024年，5月牛顿法有显然的几何意义，方程f(x)=0的根x*可解释为曲线y=f(x)与x轴交点的横坐标.设xk是根x*的某个近似值，过曲线y=f(x)上横坐标为xk的点Pk引切线，并将该切线与x轴交点的横坐标xk+1作为x*的新的近似值.注意到切线方程为这样求得的值xk+1必满足(3.4.1),从而就是牛顿公式(3.4.2)的计算结果.由于这种几何背景，所以牛顿迭代法也称切线法.xyx*xky=f(x)xk+1PkPk+1xk+2第67页,共86页，星期六，2024年，5月二、牛顿法的收敛性定理4：设f(x)在[a,b]上存在二阶连续导数且满足下列条件： （1）f(a)?f(b)0； （2）f’(x)?0； （3）f?(x)在区间[a,b]上不变号； （4）取x0?[a,b]，使得f?(x)?f(x0)0则由（2）（3）确定的牛顿迭代序列{xk}二阶收敛于f(x)在[a,b]上的唯一单根x*。第68页,共86页，星期六，2024年，5月第69页,共86页，星期六，2024年，5月牛顿法收敛性依赖初值x0的选取,如果x0偏离所求根x*较远,则牛顿法可能发散.x*x0?x0?x0第70页,共86页，星期六，2024年，5月例如，用牛顿法求解方程x3-x-1=0.此方程在x=1.5附近的一个根x*.设取迭代初值x0=1.5，用牛顿迭代法公式计算得x1=1.34783,x2=1.32520,x3=1.32472.迭代3次得到的结果x3有6位有效数字.但是，如取x0=0.6，用上式迭代1次得计算得x1=17.9.这个结果反而比x0=0.6更偏离了所求的根x*=1.32472.第71页,共86页，星期六，2024年，5月由此得到，当x*为单根时，牛顿迭代法在根x*的邻近是二阶(平方)收敛的.定理(局部收敛性)设f?C2[a,b],若x*为f(x)在[a,b]上的根，且f?(x*)?0，则存在x*的邻域U,使得任取初值x0?U，牛顿法产生的序列{xk}收敛到x*，且满足即有下面的局部收敛性定理.第72页,共86页，星期六，2024年，5月设x*是f(x)的一个单根，即f(x*)=0，f?(x*)≠0,有牛顿迭代法的迭代函数为第73页,共86页，星期六，2024年，5月对于给定的正数C，应用牛顿法解二次方程我们现在证明，这种迭代公式对于任意初值x00都是收敛的.可导出求开方值的计算程序3.4.2牛顿法应用举例第74页,共86页，星期六，2024年，5月事实上，对(3.4.3)式施行配方整理，易知以上两式相除得据此反复递推有第75页,共86页，星期六，2024年，5月记整理(3.4.4)式，得对任意初值x00，总有|q|1，故由上式推知，当k→∞时，即迭代过程恒收敛