计算机工程应用02-非线性方程2

1计算机工程应用第一章代数方程的计算机方法重点与难点：计算机数学概念的理解、计算机数学分析方法的应用、实际问题的计算机求解算法的实现2第一章代数方程的计算机方法第一节问题的引出

在实际工程问题中，我们进行了大量的试验，从中得到了一个关于某个现象出现规律的描述方程，或者说借鉴了前人或其它人的研究成果，即

，其中：来描述某个现象的规律，并从这种规律中找出影响该现象最大值或最小值的因素。从数学上讲，求出某函数的最大或最小值，就要对某个函数进行一次微分，即：这时方程就变成了：（1）要想求解出x，就得求解这个方程。

3第一章代数方程的计算机方法又例如：描述材料的某个性能与因变量的关系方程式为：我们要从这个规律中找影响性能最大值的因素，就得求解这个方程的极值，即：

即方程变为：

（2）

解这个方程，求出的x便是这个影响性能极值的因素。以上（1）、（2）这些形式的方程都是典型的代数方程。从前解法是试算法，即代入一个假设x值，计算结果，看是否满足方程，如果满足方程，其解就是极值。否则，重新假设一个x值代入方程进行计算，如此反复直至达到满足方程要求为止。这种方法的缺点是：（1）

x值的假设是随意的，没有一个规律可循。（2）

用手工进行计费时费力。4第一章代数方程的计算机方法那么什么方法有效呢？这就引出了代数方程式的计算机解法问题第二节代数方程式的计算机解法

1、迭代法迭代法对以上（1）、（2）这些形式的方程的求解特别有效，也是一种常用的方法。对于函数

求解来说，思路简单，逻辑严密。它是基于使用一个固定的公式，反复校正根值的近似值，使之逐步精确化，最后，达到满意的结果。其具体方法是：对于一般方程首先将其变形为：

（3）式（3）称为迭代函数。从式（3）中看出：方程的两边都5第一章代数方程的计算机方法含有未知量x，是一个隐函数，是不能直接求解的，所以，要事先假设一个初值x0

，并将其代入（3）中，使方程变为：

(4)式中：x1——为计算值

x0——为假设初值然后比较

‌

(5)或者是否x1充分接近x0

？如果是就结束计算，则x0或x1就是方程的根，如果不是充分的接近则继续按式（4）进行计算。不过，这时代入的初值不是x0而是x1。此时，计算公式为：

如此反复，其迭代过程中的计算公式就可以用下式表达：

（6）6

并反复进行检验

（7）直到迭代值xn有极限存在，即：

从上面的讨论过程看，整个过程用的某一个固定公式的形式就是（6）式，即：

那么，这个公式具有什么意义？如何理解它呢？我们可以试想着将公式（6）看成

:

也就是说有两个函数：

（a）

(b)第一章代数方程的计算机方法7第一章代数方程的计算机方法图1迭代法的几何表示存在，且相等。如果用几何图形来表示的话，式（a）、(b)在x-y坐标图上必然有一个交点，如图1所示。

x0x1x2x*y=xyx0Q1P0P1P2Q2P*y=φ(x)8交点处的x*就是该迭代方程式的解，其迭代过程如图中所示。这说明了这种迭代过程的优点是：只要迭代函数选取的得当（有效），其迭代过程必然有解，而且迭代值逐渐逼近真值——根，与试算法相比，每一次的初值x0的选取是有规律可循的，但其缺点和试算是一样的，要经过反复计算才行。第一章代数方程的计算机方法那么在什么样的条件下，才能使迭代函数有效，也就是说迭代函数具有收敛性？首先来考察一下迭代函数为线性时的简单情况。假设迭代函数为：

为了直观，将函数用图示的方法来表示，先令：

然后，在x-y坐标上通过改变φ(x)中的系数k做出不同的y=x

、y=φ(x)两条直线

,见下页图9第一章代数方程的计算机方法K<-1图ay=xy=φ(x)yx0x0x2x1X*图byy=φ(x)x0y=x-1<K<0X*x1x0x2yy=φ(x)x0y=x0<K<1图cX*x0x1x2yy=φ(x)x0y=xK>1图dx0x1x2X*图2发散收敛收敛发散10第一章代数方程的计算机方法由图2可以看出，若使y=φ(x)在迭代过程中有近似根存在，须使。进而，我们考察一般情况，设x*为方程x=φ(x)根，如果有根值存在的话，在迭代过程中会有：

x*-xn+1=φ(x*)-φ(xn)(8)根据微分中值定理，上式可以用下式进行表示：

x*-xn+1=φ(x*)-φ(xn)=φ’(ξ)（

x*-xn）（9）式中：ξ——是x*与x之间的某一值由此得知，如果存在一个正数L<１，那么对于任意x∈［a，b］成立：

φ’(x)≤L则有：│x*-xn+1│

=Ｌ│x*-xn│

(10)11第一章代数方程的计算机方法对用en=│x*-xn│表示迭代误差时其迭代误差有：en

=Lne所以，当n→∞时，en→0，迭代收敛。需要指出的是：在上述的论证过程中，应当保证一切迭代值xn全部落在[a,b]内，为此，要求对任意x∈[a,b]，总有：

φ（x）∈[a,b]综上所述，我们有结论：定理1

设φ（x）在[a,b]上具有连续的一阶导数，且（1）对任意x∈[a,b]，总有φ（x）∈[a,b]

（2）存在0≤L<1，使对任意x∈[a,b]成立

│φˊ

(x*)│<L12第一章代数方程的计算机方法则迭代过程xn+1=φ（xn）对任意初值x∈[a,b]均收敛于方程x=φ（xn）的根x*。且有下列估计式：

│x*-xn+1│≤│xn+1-xn│

（11）

│x*-xn│≤│x1-x0│

（12）（证明从略）据估计式（11、12）只要相邻两次迭代值xn,xn+1的偏差充分小就能保证迭代值xn(或xn+1)足够精确，因此，可用│xn+1-xn│来控制迭代过程是否结束。迭代法的一个突出优点就是算法逻辑结构简单，图3详细的描述了迭代过程。图3中x0，x1分别表示每次迭代的初值和终值。ε为精度，N为最大迭代次数。13第一章代数方程的计算机方法开始读入x0

、ε、Nn=n+1(初值为0)输出迭代失败标记xn+1=φ(xn)‌|xn+1-xn|‌‍‌‌<εn等于N？结束输出xn+1YNNY图3迭代法的计算机解法流程图14第一章代数方程的计算机方法

迭代法的另一个关键是如何寻找一个迭代函数。具体的做法是根据定理1要求去做。即，保证：│φˊ

(x*)│<L例1：求x3-x-1=0的唯一正根。解：首先要考察这个方程式的根存在的范围。从图4可以看出，要找出根值存在的范围，必需使f(x)的值出现异号。在这个例子中，根值存在于x∈[1,2]图4函数根值存在的示意图yxy=f(x)x*15第一章代数方程的计算机方法其次是寻找适当的迭代函数。根据迭代函数的要求，要将原函数变成迭代函数。对于这个问题，则要变x3-x-1=0成为能够迭代的形式。有下面几种变法：

a变成：x=x3-1，根据收敛定理要求这个迭代函数在x∈[1,2]内，其导数要小于1，则有：φˊ(x)=(x3-1)ˊ=3x2

当x=1，迭代函数φˊ(x)

=3>1，当x=2时，迭代函数为=12>1，所以这样的变换是不行的。

b变成：x3=x+1即：x=(x+1)1/3,

则：φˊ(x)=((x+1)1/3)ˊ=1/3(x+1)-2/3根据收敛定理要求，这个迭代函数在x∈[1,2]内当x=1时，迭代函数φˊ(1)

=0.20999<1，当x=2时，迭代函数φˊ(2)

=0.16025<1。即符合定理要求，所以，选取这个作为迭代函数是合理的。

16第一章代数方程的计算机方法在这个迭代函数的基础上，按照图3的流程图用VB及C语言进行编程取初值为1.5运算，所得到的结果见表1nxnnxnnxn01.531.3258861.3247311.3572141.3249471.3247221.3308651.3247681.3247217第一章代数方程的计算机方法求x3-x-1=0的唯一正根，迭代公式用

x=(x+1)1/3

VBA程序演示：18第一章代数方程的计算机方法C程序清单：19在实际应用迭代法时，通常首先在根x*的邻近考察，如果存在邻域，迭代过程对于任意初值

均收敛，这种在根的邻近具有的收敛性称作局部收敛性

定理2

设在根邻近有连续的一阶导数，且：

则迭代过程

具有局部收敛性。例2：求方程在x=0.5附近一个根，要求e=10-5。所求的准确值为0.567143。第一章代数方程的计算机方法20第一章代数方程的计算机方法解:在x=0.5附近一个根，要求e=10-5，VBA程序演示：21第一章代数方程的计算机方法例2的C程序清单：22第一章代数方程的计算机方法nxnnxnnxn00.50000060.564863120.56706710.60653170.568438130.56718620.54523980.566409140.56711930.57970390.567560150.56715740.560065100.566907160.56713550.571172110.5670277170.56714823第一章代数方程的计算机方法例3：为求方程在x0=1.5附近的一个根，现将方程改写成下列等价形式，且建立相应的迭代公式：试分析每一种迭代公式的收敛性；任取一种收敛的迭代公式计算1.5附近的根，要求|xk+1-xk|<10-624第一章代数方程的计算机方法

分析判断一个迭代公式是否收敛，可用迭代法的局部收敛性定理或整体收敛性定理．若有几个迭代式都收敛，应取中L较小的那个迭代法进行计算。解：取x0=1.5的邻域[1.3，1.6]来考察。25第一章代数方程的计算机方法＞26第一章代数方程的计算机方法取第二种迭代式，x0=1.5，计算结果如下表：kxkkxk01.581.46563446511.48124803491.46559999621.472705730101.46558431631.468817314111.46557718441.467047973121.46557393951.466243010131.46557246361.465876820141.46557179271.46571024115由于|x14-x13|=0.671*10-6<10-6,故可取x*≈x14=1.46557179227第一章代数方程的计算机方法例4对方程3x2-ex=0,确定迭代函数φ(x)及区间[a，b]，使对均收敛，并求该解，要求|xk+1-xk|<10-5分析这样的题有难度，一般应知道函数f(x)的图形及根x*的大概位置，才能确定有根区间及该区间上的迭代函数.因为,f(x)可能在其定义域内有多个根，所以,在没有指明求哪个根的情况下，就应全部求出.根据3x2和ex的图形知f(x)=3x2-ex=0有三个根，分别位于区间(-1,0)，(0,1)，(3,4)内28第一章代数方程的计算机方法29代数方程的计算机方法取x0=-0.5，计算结果如下表：kXkKxk0-0.54-0.4590751311-0.4496408415-0.4589363682-0.4611063516-0.4589682113-0.4584705047-0.45896090330第一章代数方程的计算机方法kxkkxk10.74133242080.90937571820.83640700690.90972012130.877127740100.90987679040.895169427110.90994806850.903281143120.90998049860.906952162130.90999525370.908618410140.91000196731第一章代数方程的计算机方法3x3x32第一章代数方程的计算机方法kxkkxk13.60413822693.73217014823.662777674103.73259203633.695055862113.73281810543.712603634123.73293923453.722079126133.73300413263.727177123143.73303890273.729914576153.73305753183.731382952163.73306751133第一章代数方程的计算机方法2牛顿法牛顿法也是一种求解代数方程式的数学迭代方法。它的基本思想是：为了把根夹住，先找到两个异号的值在两个异号的值之间选取方程f(x)=0根的一个估计值x0

，然后将f(x)=0在x0处进行泰勒展开：

f(x1)=f(x0)+f’(x0)(x1-x0)+1/2f”(x0)(x1-x0)2+…=0

因为x0是在f(x0)的根值附近，所以，令：h=x1-x0是一个很小值则h2更是一个极小值，所以将泰勒展开式的右边的第三项以后的项都有忽略（作为误差来处理）34第一章代数方程的计算机方法也即： 移项得：得到35第一章代数方程的计算机方法yxy=f(x)x*x0x1x2图4牛顿法的几何解释36第一章代数方程的计算机方法写成通式，从而得到牛顿迭代公式：

(13)这里xn+1是在x=xn

处曲线的切线与x轴的交点。由于曲线f(x)不是直线，f(xn+1)就不可能是真正的零。因此，就必须以xn=xn+1作为新的基点，重复以上步骤，直至f(xn+1)充分小牛顿法的实质是沿着曲线上的一点切线作外推，而不是在两个函数之间作内插。这可以从图4中看出:？切线与X轴的交点37第一章代数方程的计算机方法从图4中很明显的看出，起点位置的选择会显著的影响收敛速度。另外，这种方法的缺点是：

1、在迭代过程中，一但曲线的斜率f’(x)=0，就无法迭代下去了。

2、还可以证明当f’’(x)趋于无穷大时，牛顿法也将失效。其证明可以直接从函数的泰勒展示式中得到。即：当f’’(x)趋于无穷大时

f(x1)=f(x0)+f’(x0)(x1-x0)+1/2f”(x0)(x1-x0)2+…=0就不能简化成为：

f(x1)=f(x0)+f’(x0)(x1-x0)=038第一章代数方程的计算机方法也就不能有：

存在。

牛顿法的好处在于，不用对原函数f(x)的代数方程进行迭代变换，所用的固定公式简单。所以，用牛顿法进行编程时，编程也简单，这可从图5的流程图中看出：

39第一章代数方程的计算机方法选择初值xn=x0计算Xn+1和f(Xn+1)Xn+1=x0‌f(xn+1)充分小？停止YN图5牛顿法的计算机解法流程图40第一章代数方程的计算机方法41第一章代数方程的计算机方法KXkKXk02.031.32580134511.54545454541.32471890521.35961491651.324717957计算结果如下表：此时以达到误差要求，即x*≈x5=1.324717957比较P16页42第一章代数方程的计算机方法43第一章代数方程的计算机方法44第一章代数方程的计算机方法注意虽然在单根附近牛顿法比一般迭代法有更快的收敛速度．但是，应该注意的是：首先牛顿法求根对迭代初值选取要求较严，初值选取不好，可能导致迭代不收敛。其次，牛顿法每迭代一次要计算f’(xk)的值.这无疑会增加很多计算量，为回避这个问题，通常并不是每次都去计算f’(xk)的值，而是用一个固定的f’(xk)迭代若干步后再求一次f’(xk)。显然这样做减少了工作量，但以降低收敛速度为代价。最后，若方程f(x)＝0中的非线性函数f(x)仅仅连续而不可微，显然不可对其求导数，即或有时f(x)虽然可求导数，但导数计算比较复杂。对于这两种情形，都可用函数在已知点xk和xk+1的差商来代替导数，这便是下节要介绍的割线法45第一章代数方程的计算机方法

3

弦割法

牛顿法的优点就是收敛速度快。但是其明显的缺点就是先要求出f’(x)的值来，如果求导不容易，这时牛顿法就变得不方便了。遇到就种情况时，我们就采用：（14）来代替导数f’(xn)，这时相应的公式就变成了：

（15）46所以，47第一章代数方程的计算机方法因为；f’(x)=如果将这个极限不让

，而是有一个微小的范围，那么上式就变为：=所以，在x变化的微小范围内，可以认为：

s(xn)≈f’(x)这种方法的几何解释如图6所示。48第一章代数方程的计算机方法yxy=f(x)x*xn+1xnxn-1图6弦割法的几何示意图pnpn-149第一章代数方程的计算机方法yxy=f(x)x*xn+1xnxn-1图6弦割法的几何示意图pnpn-1xn+2pn+150第一章代数方程的计算机方法其推导过程是：从图6看，在三角形Pn

、Xn-1

及Xn+1

中,

有:移项，将放在等式的左边，即：变为：两边同除以得：51第一章代数方程的计算机方法弦割法和牛顿法计算机逻辑流程是一样的，思路简单，如下图所示选择初值xn,xn-1计算Xn+1和f(Xn+1)Xn+1=xnXn=xn-1‌f(xn+1)充分小？停止YN图6弦割法的计算机解法流程图52第一章代数方程的计算机方法53第一章代数方程的计算机方法取初值x0=0.5，x1=0.1,计算结果如下：KXk-1xk10.50.120.10.36059530.3605950.34823740.3482370.34729150.3472910.34729660.3472960.34729654第一章代数方程的计算机方法4

二元搜索法二元搜索法是求解一元非线性方程根的常用的方法之一。这种方法也是迭代法的一种。它求解的过程是：首先按x的等距离间隔求出它的函数值f(x),直到相邻的两个函数值f(xn)和f(xn+1)具有相反的符号为止。即：f(xn)f(xn+1)<0因为对于连续的函数而言，这种函数值的不同就指明了根值的存在。这时用下列式子求出xn和xn+1的中间值xmid

(16)然后，再求出点xmid的函数值f(xmid)，若f(xmid)与f(xn)同号就以f(xmid)代替f(xn)，否则就以f(xmid)代替f(xn+1)于是含根区间就缩小为：55第一章代数方程的计算机方法（xmid，xn+1）或（xn，xmid）。当f(xmid)足够小时就终止这个过程，不然就重复以上步骤。这种迭代过程的几何意义可由图7表示。yxy=f(x)x*xn+1xnxn-1图7二元搜索法的几何示意图pnpn-1Pn+156第一章代数方程的计算机方法二元搜索法适用于：迭代函数不好找，牛顿法的f

‘(x)不好求等情况下。二元搜索法的特点是：简单、直观。二元搜索法的计算机编程流程见图857第一章代数方程的计算机方法在x的等分距上求使f(xn)到f(xn+1)异号的函数值f(xmid)与f(xn)同号？YNNY图8二元搜索法的计算机解法流程图计算xmid和f(xmid)xn+1=xmid

f(xn+1)=f(xmid)xn=xmid，f(xn)=f(xmid)f(xmid)足够小？结束58第一章代数方程的计算机方法59第一章代数方程的计算机方法n(a,b)Xnf(xn)0(0,1)0.54.6487212181(0,0.5)0.251.7840254312(0,0.25)0.1250.3831484623(0,0.125)0.0625-0.3105055394(0.0625,0.125)0.0937500.0357851395(0.0625,0.093750)0.078125-0.1374921956(0.078125,0.093750)0.0859375-0.0508867847(0.0859375,0.093750)0.089843750-0.0075591688(0.089843750,0.093750)0.0917968750.01