计算方法ch2资料课件

分章测试笔试。课件或课后题。上机。分组。讲解。计入期末成绩。30%—50%课后习题1、2、5、7、8、9编程二分法、一般的迭代法第2章一元非线性方程的解法2.1初始近似根的确定2.2二分法2.3迭代法的一般知识2.4牛顿迭代法（切线法）2.5弦截法（割线法）2.6埃特金（Aitken）迭代法引言本章讨论：求一元非线性方程f(x)=0的根的近似值。引言例如e-x-x=0,x8-x3+5x-3=0,x-sinx=0,等等求根的大致步骤：(1)判定根的存在性。(2)确定根的初始近似值(初始近似根)。(3)根的精确化。如果f(x*)=f′(x*)=f″(x*)=……=f(m-1)(x*)=0,但f(m)(x*)≠0,其中m是正整数，则称x*为方程f(x)=0的m重根-------函数f(x)的m重零点。如果f(x*)=0,则x*是方程f(x)=0的根,也称它是函数f(x)的零点。方程的1重根称为单根，这时f(x*)=0而f′(x*)≠0。第2章一元非线性方程的解法2.1初始近似根的确定2.2二分法2.3迭代法的一般知识2.4牛顿迭代法（切线法）2.5弦截法（割线法）2.6埃特金（Aitken）迭代法引言从有限区间的左端点出发，按预定的步长h一步一步地向右跨，每跨一步进行一次根的“搜索”，即检查所在节点上的函数值的符号，一旦发现其与左端的函数值异号，则可确定一个缩小了的有限区间，其宽度等于预定的步长h。然后，再对新的有限区间，取新的更小的预定步长，继续“搜索”，直到有限区间的宽度足够小。称这种方法为逐步搜索法。逐步搜索法(1)x0←a;(2)若f(x0)f(x0+h)≤0则结束；否则做下步。

(3)x0←x0+h，转(2)（其中h为预选的步长）求初始近似根的逐步扫描法：（设(a,b)内有根）

定理

如果函数f(x)在区间[a,b]上连续，严格单调，且f(a)f(b)<0，则在(a,b)内方程有且仅有一个实根。2.1初始近似根的确定第2章一元非线性方程的解法2.1初始近似根的确定2.2二分法2.3迭代法的一般知识2.4牛顿迭代法（切线法）2.5弦截法（割线法）2.6埃特金（Aitken）迭代法引言二分法的基本思想和计算过程近似根的误差估计二分法的计算流程二分法举例2.2二分法二分法的基本思想将含方程根的区间平分为两个小区间，然后判断根在哪个小区间，舍去无根的区间，而把有根的区间再一分为二，再判断根属于哪个更小的区间，如此周而复始，直到求出满足精度要求的近似根。条件：函数f(x)在[a,b]上连续，严格单调，且f(a)f(b)<0，这时方程在区间内有且仅有一个实根x*。二分法的基本思想和计算过程具体计算过程第1次二分，取中点若f(a)f(x0)<0，则x*∈(a,x0)，令a1=a,b1=x0；令a1=x0,b1=b。新的有根区间为(a1,b1)，长度是原来的一半。否则x*∈(x0,b)，x*x*第2次二分，取中点若f(a1)f(x1)<0，则x*∈(a1,x1)，令a2=a1,b2=x1；否则令a2=x1,b2=b1

。新的有根区间为(a2,b2)。如此反复，有∈(ak,bk),k=0,1,2,…..二分法的基本思想和计算过程近似根的误差估计二分法的计算流程二分法举例2.2二分法近似根xk的误差估计

x*l

m|—————|—————|ak

xk

bk

二分法的基本思想和计算过程近似根的误差估计二分法的计算流程二分法举例2.2二分法例求方程

要求用二分法，取四位小数计算，精确到10-2。

解a=1,b=1.5,f(1)=-1<0,f(1.5)>0.在区间(1,1.5)内的根。所以f(x)在(1,1.5)内有且仅有一个实根。(1)证明根的存在性例求方程

要求用二分法，取四位小数计算，精确到10-2。

解得k=6满足要求，二分7次计算到x6即可。x0==1.25,f(1.25)<0,f(1)f(1.25)>0,得有根区间[1.25,1.5];x1=f(1.375)>0,f(1.25)f(1.375)<0,得有根区间[1.25,1.375];在区间(1,1.5)内的根。(2)求近似根如此继续，计算结果见列表：kakbkxkf(xk)的符号011.51.25－11.251.51.375＋21.251.3751.3125－31.31251.3751.3438＋41.31251.34381.3282＋51.31251.32821.3204－61.32041.32821.3243－得x6=1.3243,所以根x*≈1.32例：利用计算器，求方程在[2,3]上的近似解,（精确到0.1）。解得k=4满足要求，二分5次计算到x4即可。(2)kakbkxkf(xk)的符号0232.5＋122.52.25－22.252.52.375－32.3752.52.4375＋42.3752.43742.40625－得x4=2.40625,所以根x*≈2.4二分法的基本思想和计算过程近似根的误差估计二分法的计算流程二分法举例2.2二分法二分法的计算流程#include<stdio.h>#include<math.h>#definef(x)((x*x+10)*x-20)#defineeps0.005

二分法的C程序main(){floata,b,y,x;intk=0;

clrscr();

printf("\nepsilon=%f\n",eps);

printf("\na=");scanf("%f",&a);

printf("\nb=");scanf("%f",&b);do{y=f(a);x=(a+b)/2;k++;if(y*f(x)<0){b=x;}elsea=x;}

while((b-a)>=eps);printf("\nTherootisx=%f,k=%d\n",x,k);getch();}求方程

取四位小数计算，精确到10-2。

在区间(a,b)内的根。要求用二分法，第2章一元非线性方程的解法2.1初始近似根的确定2.2二分法2.3迭代法的一般知识2.4牛顿迭代法（切线法）2.5弦截法（割线法）2.6埃特金（Aitken）迭代法引言2.3.1迭代法的基本思想及几何意义2.3.2迭代法的收敛条件及误差估计式2.3迭代法的一般知识2.2.3局部收敛性与迭代法收敛的阶1.迭代法的基本思想2.3.1迭代法的基本思想及几何意义2.迭代法的几何意义方程f(x)=0化为等价形式的方程x=g(x)

，若当g(x)(称为迭代函数）连续，

，则x*

即为方程的根。实际计算到|xk–xk-1|<ε（ε是预定的精度），取x*≈xk

。

1、迭代法的基本思想：取初始近似根x0,迭代计算x1=g(x0),x2=g(x1),……..

得到迭代序列{xk

},构造迭代公式

xk+1=g(xk

),k=0,1,2,……例

f(x)=xex-1=0,可化为等价形式x=e–x迭代公式xk+1=e–xk迭代法也称逐次逼近法。例

f(x)=x-2x=0,可化为等价形式x=2x迭代公式x

k+1=2xk迭代公式收敛（发散）指迭代序列

{xk

}收敛（发散）。求方程f(x)=x–10x+2=0在（0,1）的一个根，取4位有效数字计算。问题：迭代公式是否一定收敛？因f(0)=1>0,f(1)=-7<0,所以方程在（0，1）中有根。方程改写为两种等价形式：看下例：解对应的迭代公式分别为10x=x+2x=lg(x+2)用迭代公式（1）x1=lg3=0.4771,x2=lg(x1+2)=0.3939,….,x6=0.3758,x7=lg(x6+2)=0.3758,…用迭代公式（2）x1=10-2=8,x2=108-2≈108,x3=10108-2≈10108，……x6、x7重合，所以迭代公式（1）是收敛的，x*≈0.3758。迭代公式（2）发散。取x0=1,算得,x0=1,算得2.迭代法的几何意义问题：迭代函数g(x)满足什么条件时，迭代序列才收敛?x1=g(x0)x2=g(x1)2.3.1迭代法的基本思想及几何意义2.3.2迭代法的收敛条件及误差估计式2.3迭代法的一般知识2.2.3局部收敛性与迭代法收敛的阶2.3.2迭代法的收敛条件及误差估计式定理2.1

设方程x=g(x)在[a,b]上有一阶导数，如果(1)当x∈[a,b]时g(x)∈[a,b];(2)存在正数q<1，使对任意x∈[a,b]

都有

|g′(x)|≤q<1则方程x=g(x)在[a,b]上有惟一的根x*

；且对于[a,b]上任意初始近似根x0,迭代公式xk+1=g(xk)均收敛于方程的根x*;还有误差估计式证明记f(x)=x-g(x),

由条件（1）有a≤g(a)、g(b)≤b,于是f(a)≤0,f(b)≥0，由于f(x)是连续函数，故必存在x*∈[a,b]

使f(x*)=0.于是x*为方程x=g(x)的根。先证根的存在性。其次，证根的惟一性。设y*也是方程的根，则x*=g(x*),y*=g(y*),|x*-y*|=|g(x*)–g(y*)|=|g′(ξ)(x*-y*)|≤q|x*-y*|由已知条件|g′(x)|≤q<1故必有x*=y*,所以方程在[a,b]的根是惟一的。微分中值定理,ξ在x*,y*之间(1)当x∈[a,b]时g(x)∈[a,b];再证迭代公式收敛。由x0∈[a,b]

知xk∈[a,b]，k=0,1,2,……|xk+1-x*|=|g(xk)–g(x*)|=|g′(ξ)(xk-x*)|≤q|xk-x*|≤q2|xk-1-x*||xk-x*|≤q|xk-1-x*|≤q3|xk-2-x*|≤……≤qk+1|x0-x*|→0（k→∞）所以，对[a,b]上任取的x0,迭代公式xk+1=g(xk

)都收敛于x*。0<q<1,qk+1→0误差公式的证明从略。可以参看课本P16页。|xk-1-x*|≤q|xk-2-x*|(1)当x∈[a,b]时g(x)∈[a,b];2.3.2迭代法的收敛条件及误差估计式定理2.1

设方程x=g(x)在[a,b]上有一阶导数，如果(1)当x∈[a,b]时g(x)∈[a,b];(2)存在正数q<1，使对任意x∈[a,b]

都有

|g′(x)|≤q<1则方程x=g(x)在[a,b]上有惟一的根x*

；且对于[a,b]上任意初始近似根x0,迭代公式xk+1=g(xk)均收敛于方程的根x*;还有误差估计式aby=x附加定理设在区间[a,b]上方程x=g(x)有根x*,且对一切x∈[a,b]都有|g′(x)|≥1，则对于该区间上任意x0(≠x*),迭代公式xk+1=g(xk

)一定发散。证明不可能收敛于0。迭代法的计算步骤（1）确定方程f(x)=0的一个等价形式x=g(x),要求在某个含根区间[a,b]内满足|g′(x)|≤q<1。(2)构造迭代公式xk+1=g(xk)，选取初始近似根x0,进行迭代计算。(3)当|xk+1–xk

|<ε（ε是预定的精度）时停止计算，取x*≈xk+1。例方程f(x)=x3-2x-5=0在(1.5,2.5)内有一实根，分别取作为迭代函数，试判断对应的迭代公式是否收敛，并用一个收敛的迭代公式求方程的根，精度要求为ε=10-4。解(1)单调，且所以迭代公式收敛。取x0=2计算,01234522.080082.092352.09422.094492.09454

0.080080.012270.001870.000270.00005

kxk

xk-xk-1

因为|x5-x4|=0.00005<10-4所以x*≈x5=2.09454……结果列表：(2)迭代函数根据定理2.2,迭代函数对应的迭代公式是发散的。例求方程x=e–x在x=0.5附近的一个根，按5位小数计算，结果的精度要求为ε=10–3.解方程等价于f(x)=x–e–x=0.由于f(0.5)<0,f(0.6)>0,故x*∈(0.5,0.6),令g(x)=e–x,在(0.5,0.6)内,g(x)的一阶导数连续，且有所以用迭代公式xk+1=e–xk

进行计算是收敛的。根据定理2.1迭代结果:

012345

0.50.606530.545240.579700.560070.57117

0.10653

－0.061290.03446

－0.019630.01110

678910

0.564860.568440.566410.567560.56691－0.006310.00358

－0.002030.00115

－0.00065kxkxk–xk-1xk–xk-1k

xk|x10-x9|=0.00065<ε，故x*≈x10≈0.567xk+1=e–xkx0=0.5,x2=e–x1=0.54524,…….x1=e–x0=0.60653,已知方程：解：所以该迭代格式发散。判定在[1.5,3]的敛散性。利用迭代形式计算在[1.5,3]的实根。迭代三次，结果保留两位有效数字，选取初始近似根为3。迭代次数 近似根0 31 1.52 2.06253 1.983398438结果保留两位有效数字所以近似根为2.02.3.1迭代法的基本思想及几何意义2.3.2迭代法的收敛条件及误差估计式2.3迭代法的一般知识2.2.3局部收敛性与迭代法收敛的阶定义2-1的某个领域使得迭代公式对于任意初值定理2-2且2.2.3局部收敛性与迭代法收敛的阶若存在设定义2-2

定义2-2：什么是p阶收敛？线性收敛p=1(0<c<1)超线性收敛2>p>1平方收敛p＝2设迭代序列{xk}收敛于方程f(x)=0的根x*，记作

ek=xk-x*(k=0,1,2,…)为迭代误差。若存在常数p≥1,c>0,使得则称迭代序列{xn}是p阶收敛的。尤其：P的大小反映了迭代法的收敛速度。P越大，收敛速度也就越快。定义2-2线性收敛p=1(0<c<1)平方收敛定理2-3.

例2-7例2-7证明：经计算知：根据定理2-3可知，迭代公式平方收敛，得证。第2章一元非线性方程的解法2.1初始近似根的确定2.2二分法2.3迭代法的一般知识2.4牛顿迭代法（切线法）2.5弦截法（割线法）2.6埃特金（Aitken）迭代法引言2.4.1牛顿法的基本思想2.4.2牛顿法的收敛性2.4牛顿迭代法（切线法）2.4.3牛顿法的计算步骤2.4.4牛顿下山法把非线性方程线性化，用线性方程的解逐步逼近非线性方程的解。2.4.1牛顿迭代法的基本思想过曲线上的点pk(xk,f(xk))作切线，取切线与轴的交点为xk+1

。用这个迭代公式求根的方法也称牛顿迭代法、切线法。Newton迭代公式若f(xk

)≠0，则得2.4.2牛顿迭代法的收敛性:定理2-4

设x*是方程f(x)=0的单根，且f(x)在x*的某邻域有二阶连续导数，则牛顿法在x*附近局部收敛，且至少二阶收敛，有

证明：

牛顿迭代法的迭代函数由迭代公式xk+1=g(xk

)

x*是方程f(x)=0的单根则所以局部二阶或一阶收敛由定理2-2可知，牛顿迭代法在根x*附近局部收敛。又由定理2-3可知，迭代公式至少具有二阶收敛速度。且有证毕。

定理2-2且设定理2-3.

定理2-5如果在有根区间[a,b]上f(a)f(b)<0,f′(x)≠0，f″(x)连续且不变号，在[a,b]上取初始近似根

x0,使得则牛顿迭代法产生的迭代序列单调收敛于方程f(x)=0在该区间上的唯一解。

2.4.3牛顿迭代法的计算步骤(1)给出x0,ε；(2)计算(3)若则转(4)；否则，转(2);(4)输出x1,结束。例用牛顿迭代法求方程xex-1=0在x=0.5附近的根（取5位小数计算），精度要求为ε=10–3.解相应的牛顿迭代公式为取x0=0.5，经计算可得计算表格参考P21中表2-3,则x2-3=0,求等价于求方程令例用牛顿迭代法计算解的正实根。因为f′(x)=2x，由牛顿迭代公式得取初值x0=1.5，迭代5次可得≈1.732050808问题如何用牛顿法计算任意正数的算术平方根？是否还能用牛顿法计算一个正数的立方根？是否还能用牛顿法计算一个正数的n次方根？2.4.1牛顿法的基本思想2.4.2牛顿法的收敛性2.4牛顿迭代法（切线法）2.4.3牛顿法的计算步骤2.4.4牛顿下山法2.4.4牛顿下山法这种方法称为Newton下山法，例7.解:1.先用Newton迭代法x4=9.70724x5=6.54091x6=4.46497x7=3.13384x8=2.32607x9=1.90230x10=1.75248x11=1.73240x12=1.73205x13=1.73205迭代13次才达到精度要求2.用Newton下山法,结果如下k=0x0=-0.99fx0=0.666567k=1x1=32.505829f(x)=11416.4w=0.5x1=15.757915f(x)=1288.5w=0.25x1=7.383958f(x)=126.8w=0.125x1=3.196979f(x)=7.69w=0.0625x1=1.103489f(x)=-0.655k=2x2=4.115071f(x)=19.1w=0.5x2=2.60928f(x)=3.31w=0.25x2=1.85638f(x)=0.27k=3x3=1.74352f(x)=0.023k=4x4=1.73216f(x)=0.00024k=5x5=1.73205f(x)=0.00000k=6x6=1.73205f(x)=0.000000第2章一元非线性方程的解法2.1初始近似根的确定2.2二分法2.3迭代法的一般知识2.4牛顿迭代法（切线法）2.5弦截法（割线法）2.6埃特金（Aitken）迭代法引言2.5弦截法（割线法）研究目的：在牛顿法基础上，构造既有较高的收敛速度，又不须导数的迭代公式。

思想：用差商弦截迭代公式

几何意义

例用弦截迭代法求上一节的方程x=e-x在x=0.5附近的根。解:弦截迭代公式为方程化为x-e–x=0,令

kxk

01230.50.60.567540.56715弦截法的计算框图出一般迭代法、牛顿迭代法与割线法比较：

用差商牛顿迭代法与割线法都是线性化方法。牛顿法、一般迭代法在计算时只需要前一步的值，称为单点迭代法。牛顿法需要计算导数，收敛速度快割线法在计算时需要前两步的值，称为多点迭代法。计算时迭代公式

xk+1=g(xk

),k=0,1,2,……每步只需计算一次函数值。可以证明，割线法具有超线性收敛速度，收敛的阶为1.618.2.6埃特金(Aitken)迭代法研究目的：有时迭代过程收敛缓慢，如何加速？还有时普通迭代法不收敛，如何改变敛散性？埃特金迭代法的构造条件：埃特金迭代公式用埃特金迭代法求x3-x-1=0在(1,1.5)内的根。例解将方程改写成x=x3-1，建立迭代公式埃特金迭代公式为

012345

2.375001.840921.491401.347101.32518

12.39655.238882.317281.444351.327141.51.416291.355651.328951.324801.32472判定敛散性几何意义:设初值由迭代法:由三角形相似,得:过两点作直线,说明:该表达式正是埃特金加速收敛的公式,比更接近于从图中可以看出(1)这里的并不是简单收敛列中的(2)对某些不收敛的情况,用埃特金方法“加速”也有可能收敛.的交点为与第2章一元非线性方程的解法2.1初始近似根的确定2.2二分法2.3迭代法的一般知识2.4牛顿迭代法（切线法）2.5弦截法（割线法）2.6埃特金（Aitken）迭代法引言二分法一般迭代法牛顿迭代法牛