C语言编程牛顿迭代法求方程1

1、牛顿迭代公式设r是f(x)=(的根，选取x0作为r初始近似值，过点(xO,f(xO)做曲线y=f(x)的切线L,L的方程为y=f(x0)+f(x0)(x-x0),求出L与x轴交点的横坐标x1=x0-f(x0)/f(x0),称x1为r的一次近似值。过点(xl,f(xl)做曲线y=f(x)的切线，并求该切线与x轴交点的横坐标x2=xl-f(xl)/f(xl),称x2为r的二次近似值。重复以上过程,得r的近似值序列,其中x(n+l)=x(n)f(x(n)/f(x(n)，称为r的n+1次近似值，上式称为牛顿迭代公式。解非线性方程f(x)=0的牛顿法是把非线性方程线性化的一种近似方法。把f(x)在x0点

2、附近展开成泰勒级数f(x)=f(x0)+(xx0)f(x0)+(xx0)人2*f(x0)+.取其线性部分，作为非线性方程f(x)=0的近似方程，即泰勒展开的前两项，则有f(x0)+f(x0)(x-x0)-f(x)=0设f(x0)#0则其解为xl=x0f(x0)/f(x0)这样，得到牛顿法的一个迭代序列：x(n+l)=x(n)f(x(n)/f(x(n)。牛顿迭代法又称牛顿切线法，它采用以下方法求根：先任意设定一个与真实的根接近的值X0作为第一个近似根，由x0求出f(x0),过(x0,f(x0)点做f(x)的切线，交X轴于X,把它作为第二次近似根，再由X求出f(X),再过(X,f(X)点做f(x)

3、的切线，交X轴于X2，再求出f(x2)，再作切线如此继续下去，直到足够接近真正的X*为止。2八x0)=f八x0)=0-xxl0因此，x=x一l0就是牛顿迭代公式。例用牛顿迭代法求方程2x3-4x2+3x-6=0在.5附近的根。本题中，f(x)=2x3-4x2+3x-6=(2x-4)x+3)x-6f(x)=6x2-8x+3=(6x-8)x+3#includestdio.h#includemath.hvoidmain()floatx1,x0,f,f1;x1=1.5;dox0=x1;f=(2*x0-4)*x0+3)*x0-6;f1=(6*x0-8)*x0+3;x1=x0-f/f1;while(fab

4、s(x1-x0)=1e-5);printf(THerootofequationis%5.2fn,x1);例题2#includemain()floatx,x0,d,f,fd;x0=0;dof=2*x0*x0*x0-4*x0*x0+3*x0-6;fd=6*x0*x0-8*x0+3;d=f/fd;x=x0-d;x0=x;while(fabs(d)1e-3);printf(x=%fn,x);X+=X-=X*X赋值表达式此表达式为自右向左赋值，如X的初值为12,此表达式赋值步骤如下：先进行“X-=X*X”的运算，它相当于X=X-X*X,X的值为12-144=-132再进行“X+=-132”的运算，相当于

5、X=X+(-132),X的值为-132-132=264。直接选择排序的具体算法如下：选择排序(SelectionSort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。voidSelectSort(SeqListR)inti，j，k；for(i=1;ivn;i+)做第i趟排序(Isisn-1)k=i；for(j=i+1;jv=n;j+)/在当前无序区Ri.n中选key最小的记录Rkif(Rj.keyvRk.key)k=j;/k记下目前找到的最小关键字所在的位置if(k!=i)交换Ri和R

6、kRO=Ri；Ri=Rk；Rk=R0；/R0作暂存单元/endif/endfor/SeleetSort选择排序法选择排序的基本思想是：每一趟在n-i+1(i=l,2，n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。我们主要介绍简单选择排序、树型选择排序和堆排序。简单选择排序的基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行iT趟比较，直到所有记录排序完成为止。例如：进行第i趟选择时，从当前候选记录中选出关键字最小的k号记录，并和第i个记录进行交换。图9.5给出了一个简单选择排序示例，说明了前三趟选

7、择后的结果。当前已经排好序的记录。图中大括号内为当前候选记录，大括号外为排序示例，说明了前三趟选择后的结果。当前已经排好序的记录。图中大括号内为当前候选记录，大括号外为48623548623577551435981462357755483598ik1435627755483598ffik选择排序示例fikfffik1435357755486298简单选择排序的算法具体描述如下voidSelectSort(RecordTyper,intlength)/*对记录数组r做简单选择排序，length为数组的长度*/n=length;for(i=1;i=n1;+i)k=i；for(j=i+1;j=n;+

8、j)if(rj.keyrk.key)k=j；if(k!=i)x=ri；ri=rk；rk=x;/*SelectSort*/编辑本段编辑本段算法简单选择排序算法分析：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3(n-1)。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是工=(n-l)+(n-2)+2+l=n(n-l)/2,即

9、进行比较操作的时间复杂度为0(n2)。选择排序法是对定位比较交换法的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解，设有10个数分别存在数组元素a0a9中。定位比较交换法是由大到小依次定位a0a9中恰当的值(和武林大会中的比武差不多)，a9中放的自然是最小的数。如定位a0,先假定a0中当前值是最大数，a0与后面的元素比较，如果a4更大，则将a0、a4交换，a0已更新再与后面的a5a9比较，如果a8还要大，则将a0、a8交换，a0又是新数，再与a9比较。一轮比完以后，a0就是最大的数了，本次比武的武状元诞生了，接下来从a1开始，因为状元要休息了，再来一轮a1就是次大的数

10、，也就是榜眼，然后从a2开始，比出探花，真成比武大会了，当比到a8以后，排序就完成了。下面给大家一个例子：main()inta10;inti,j,t;for(i=0;i10;i+)scanf(%d,&ai);/*输入10个数，比武报名，报名费用10000*/for(i=0;i9;i+)for(j=i+1;j10;j+)if(aiaj)t=ai;ai=aj;aj=t;/*打不过就要让出头把交椅，不过ai比较爱面子，不好意思见aj，让t帮忙*/for(i=0;i10;i+)printf(%4d,ai);/*显示排序后的结果*/好啦，啰嗦了半天总算把定位比较排序法讲完了，这个方法不错，容易理解，就是

11、有点麻烦，一把椅子换来换去，哎所以就有了下面的选择排序法，开始的时候椅子谁也不给，放在一边让大家看着，找个人k记录比赛结果，然后发椅子。具体来讲呢就是，改进定位比较排序法，但是这个改进只是一部分，比较的次数没变，该怎么打还是怎么打，就是不用换椅子了。每次外循环先将定位元素的小标i值记录到K，认为ak是最大元素其实k=i还是ai最大，ak与后面的元素一一比较，该交换的也是也不换，就是把K的值改变一下就完了，最后在把ak与ai交换，这样a就是最大的兀素了。然后进入下一轮的比较。选择排序法与定位比较排序法相比较，比的次数没变，交换的次数减少了。下面也写个例子：由大到小时：main()inta10;inti,j,t,k;for(i=0;i10;i+)scanf(%d,&ai);输/*入10个数，比武报名，报名费用10000Y八*/for(i=0;i9;i+)k=i;/*裁判AND记者实时追踪报道比赛情况/for(j=i+1;j10;j+)if(akaj)k=j;if(k！=i)t二ai;ai=ak;ak=t;/*发放奖品*/for(i=0;i10;i+)printf(%4d,ai);显/*示排序后的结果*/由小到大时：main()inta10;inti,j,t,k;for(i=0;i10;i+)scanf(%d,&ai);输/*