计算方法引论-薇第十章

计算方法引论：数值代数解线性方程组的直接法解线性方程组最小二乘问题解线性方程组的迭代法矩阵特征值和特征向量的计算非线性方程及非线性方程组解法计算方法引论(第三版)第十章非线性方程解法局部收敛的阶对分区间套法迭代法Newton法弦位法抛物线法非线性方程组Newton法和拟Newton法最速下降法计算方法引论(第三版)非线性方程求解求非线性函数方程f(x)=0根(求非线性函数f(x)零点)ξ解法迭代法:给出一个近似解序列收敛判据可用误差,相对误差或函数值接近零否局部收敛

在准确解附近给出一个收敛的近似解序列{xn}p阶收敛:若xn→ξ并且存在p≥1,c>0,使

线性收敛p=1(c<1)超线性收敛p>1计算方法引论(第三版)对分区间套法根据函数f(x)在[a,b]连续,

f(a)f(b)<0则在[a,b]内有根解法迭代:取其中点为近似根,记为x0,其误差限(b-a)/2.若误差符合要求或其函数值接近零x0便可接受.否则取a,b中函数值与x0的函数值异号者跟x0构成新的求根区间,记为[a1,b1].重复以上做法得新近似根x1,…这样不断将区间分半,得到一系列区间[an,bn],和近似根(区间中点)xn,n=0,1,2,3…xn误差为(b-a)/2n+1,区间[an,bn]长的一半,xn→ξ.有根区间以1/2的比率缩小,我们也称它是线性收敛的.计算方法引论(第三版)对分区间套法算例例1. 求f(x)=x3-x-1在[1,1.5]的零点.f(1)<0,.f(1.5)>0x6=1.3242,误差限0.00390625(真值ξ=1.3247…,误差e*=-0.0005…).有三位有效数字.实际上x5就有三位有效数字了.计算方法引论(第三版)迭代法求非线性连续函数f(x)零点ξ化成x=

φ(x),ξ=φ(ξ)迭代取初始近似x0计算 xn+1=φ(xn), n=0,1,2,…直到∣xn+1-xn∣≤ε(∣(xn+1-xn)/xn+1∣≤ε)若xn→ξ,则ξ

=φ(ξ),

φ(x)的不动点.故亦称不动点迭代法计算方法引论(第三版)迭代法算例例2求f(x)=x3+2x2+10x+20在[1,1.5]的零点.取x0=1,迭代公式为xn+1=2-(xn3+2xn2)/10,则算得1.7,0.9307,1.74614,0.857796,…发散.取x0=1,迭代公式为xn+1=20//(xn2+2xn+10),计算结果如表,收敛于根计算方法引论(第三版)迭代法几何解释几何解释x=φ(x)的不动点ξ是y=x和y=

φ(x)两条曲线的交点.迭代从x0出发向上到达y=φ(x)上点(x0,φ(x0)),由此点再沿水平线到达y=x上点(φ(x0),φ(x0)),其横坐标即x1.如此做下去得一条阶梯形或环形折线,或向交点接近(收敛),或远离交点而去(不收敛).0<φ'<1-1<φ'<00<φ'<1-1<φ'<0φ'>1φ'>1φ'<-1φ'<-1计算方法引论(第三版)迭代法收敛性不动点原理加于φ(x)的条件称Lipshitz条件(L称Lipshitz常数)它强于连续性.实践中常用∣φ′(x)∣≤L<1,从画图看出的规律.这儿φ(x)定义在(-∞,∞).换成φ：[a,b]→[a,b],定理亦成立.这儿得到误差估计照例偏于保守.可在计算时用估计式: ∣xn+1-ξ∣≤L/(1-L)∣xn+1-xn∣习题2,3的结果也是很有用的:计算方法引论(第三版)不动点原理证明不动点原理证明计算方法引论(第三版)收敛性判定讨论例2中迭代的收敛性φ(x)=2-(x3+2x2)/10,

φ

′(1.5)=-1.275,φ′(1.3)=-1.027在[1.3,1.5]有

∣φ′(x)∣>1,不收敛.φ(x)=20/(x2+2x+10)在[1,2

]有0<∣φ′(x)∣<1,局部收敛.实际上φ:

[1,2]→[1,2].计算方法引论(第三版)收敛性改进可以改进迭代法收敛性乃至变发散为收敛松弛法λn=φ′(xn

)(≠-1)ωn=(1+λn)-1xn+1=(1-ω)xn+ωn

φ(xn),Aitken法un+1=φ(xn)vn+1=φ(un+1)xn+1=xn-(un+1-xn)2/(vn+1-2un+1+xn) =vn+1-(vn+1-un+1)2/(vn+1-2un+1+xn)计算方法引论(第三版)松弛法算例例3.同例2,取x0=1,φ(x)==20//(x2+2x+10).计算方法引论(第三版)Aitken方法算例例3(续).同例2,取x0=1,φ(x)=

2-(x3+2x2)/10.取x0=1,φ(x)==20//(x2+2x+10).计算方法引论(第三版)Newton法方法取初始近似x0迭代 n=0,1,2,…

xn+1=xn-f(xn)/f′(xn)直到∣xn+1-xn∣≤ε和(或)∣(xn+1-xn)/xn+1∣≤ε1, ∣f(xn+1)∣≤ε2导出‘以线性函数代非线性函数’在初始近似xn作Taylor展开线性部分零点xn+1‘以直代曲’由(xn,f(xn))作f(x)的切线交x轴于xn+1.因此Newton法也叫切线法

y=f(x)

x0x1(x0,f(x0))计算方法引论(第三版)Newton法算例例4.例2,取x0=1,.用Newton法.结果见下表左栏.

计算方法引论(第三版)Newton法收敛性定理

注Newton迭代法也可视为不动点迭代法

φ(x)=x-f(x)/f′(x)单根的假设是必要的.例如,求(x-1)2=0的二重根1.Newton迭代是线性收敛的: xn+1-1=(xn-1)/2计算方法引论(第三版)Newton法变形几个方法简化Newton法.为减少计算导数的化费,可只求f′(x0)以后所有导数不另求.这相当于第一次作切线,以后作其平行线.当然,这样收敛要慢些.还可以取折衷方案,隔几步计算一下导数Newton-下山法.每次迭代在改变量前加一因子以保证收敛: xn+1=xn-λnf(xn)/f′(xn) 这儿λn在0,1间,可用各种方法搜索,例如用分半法取1,1/2,1/4,…试探,使 ∣f(xn+1)∣<∣f(xn)∣用差商代导数xn+1=xn-f(xn)(xn-xn-1)/(f(xn)-f(xn-1)) 它免除了计算导数

计算方法引论(第三版)综合除法多项式的情况计算可应用综合除法故再对进行上述过程即得f′(c)

计算:

例如，设,求

其中又因计算方法引论(第三版)弦位法方法(也叫割线法)取初始近似x0,x1迭代 n=1,2,…

xn+1=xn-f(xn)(xn-xn-1)/ (f(xn)-f(xn-1))直到∣xn+1-xn∣≤ε和(或) ∣(xn+1-xn)/xn+1∣≤ε1, ∣f(xn+1)∣≤ε2导出‘以线性函数代非线性函数’取线性插值函数零点xn+1‘以直代曲’作弦交x轴于xn+1.

(x1,y1)

x0x2x1

(x0,,y0)计算方法引论(第三版)弦位法收敛性定理例5.同例2,弦位法

.x0=1,x1=1.5,计算结果见Newton法算例.注:弦位法较Newton法收敛慢,但每步不必计算导数,总计算量也有可能低于Newton法.因此,弦位法颇具竞争力.变形:试位法.保证收敛.取二初始值,其上函数值变号.算出新值后,取代与之函数值同号的旧值再算新值.与对分区间套法一样每次迭代所用二值都分居于根的两侧.是线性收敛的计算方法引论(第三版)抛物线法方法(Muller法)取初始近似x0,x1,x2迭代 n=2,3,…

求λ2,δ2,a,b,c求λ3,

及xn+1,yn+1

直到∣xn+1-xn∣≤ε和(或)

∣(xn+1-xn)/xn+1∣≤ε1,

∣f(xn+1)∣≤ε2导出过三点作抛物线,与x轴一交点为xn+1例6.同例2,抛物线法

.x0=1,x1=1.5,x2=1.25计算结果见Newton法算例.收敛性计算方法引论(第三版)非线性方程组Newton法二元情况方程方法取初值x0,y0迭代

n=0,1,2,…解方程组求Δx,Δy计算 xn+1=xn+Δx,yn+1=yn+Δy

直至改变量合乎要求导出:Taylor公式线性化计算方法引论(第三版)算例例7计算方法引论(第三版)非线性方程组Newton法(续)一般情况方程方法计算方法引论(第三版)拟Newton法差商代替导数Newton法:k=0由Newton法求x1:

A0=f′(x(0))k=1取可逆A1并令A1满足拟Newton方程其中A1有很多选择,每一种选择都规定了一种拟Newton法.Broyden秩1修改法希望对A0作适当修改就得到A1:由,,可推得,计算方法引论(第三版)Broyden秩1修改法算法

注计算方法引论(第三版)Broyden法算例例8同例7用Broyden方法计算结果列于下表.收敛慢于Newton法

计算方法引论(第三版)Broyd