2 迭代法
2.1 迭代法的一般概念
迭代法是数值计算中一类典型方法，不仅用于方程求根，而且用于方程组求解，矩阵求特征值等方面。迭代法的基本思想是一种逐次逼近的方法。首先取一个精糙的近似值，然后用同一个递推公式，反复校正这个初值，直到满足预先给定的精度要求为止。
对于迭代法，一般需要讨论的基本问题是：迭代法的构造、迭代序列的收敛性天收敛速度以及误差估计。这里，主要看看解方程迭代式的构造。
对方程(1.1)，在区间],[b a 内，可改写成为：
)(x x ?= (2.1)
取],[0b a x ∈，用递推公式：
)
(1k k x x ?=+, Λ,2,1,0=k
(2.2)
可得到序列：
∞
==0210}{,,,,k k k x x x x x ΛΛ
(2.3) 当∞→k 时，序列∞=0}{k k x 有极限x ~，
且)(x ?在x ~附近连续，则在式(2.2)两边极限，得，
)~(~x x ?=
即，x ~为方程(2.1)的根。由于方式(1.1)和方程(2.1)等价，所以，
x x ~
*= 即，
*lim x x k k =∞
→ 式(2.2)称为迭代式，也称为迭代公式；)(x ?可称为迭代函数。称求得的序列∞
=0
}{k k x
为迭代序列。
2.2 程序和实例
下面是基于MATLAB 的迭代法程序，用迭代格式)(1n n x g p =+，求解方程)(x g x =，其中初始值为0p 。
**************************************************************************
function[p,k,err,P]=fixpt(f1021,p0,tol,max1)
% f1021是给定的迭代函数。
% p0是给定的初始值。
% tol 是给定的误差界。
% max1是所允许的最大迭代次数。
% k 是所进行的迭代次数加1。
% p 是不动点的近似值。
% err 是误差。
% P = {p1,p2,…,pn}
P(1) = p0;
for k = 2:max1
P(k) = feval('f1021', P(k-1));
k, err = abs(P(k) - P(k-1))
p = P(k);
if(err break; end if k == max1 disp('maximum number of iterations exceeded'); end end P=P; **************************************************************************** 例2.1 用上述程序求方程0sin 2=-x x 的一个近似解，给定初始值5.00=x ，误差界为510-。 解：先用m文件先定义一个名为f1021.m的函数文件。 function y = f1021(x) y = sin(x)/x; 建立一个主程序prog1021.m clc clear all fixpt('f1021',0.5,10^(-5),20) 然后在MATLAB命令窗口运行上述主程序，即：>> prog1021 计算结果如下。 k = 2 err = 0.4589 k = 3 err = 0.1052 k = 4 err = 0.0292 k = 5 err = 0.0078 k = 6 err = 0.0021 k = 7 err = 5.7408e-004 k = 8 err = 1.5525e-004 k = 9 err = 4.1975e-005 k = 10 err = 1.1350e-005 k = 11 err = 3.0688e-006 P = Columns 1 through 6 0.5000 0.9589 0.8537 0.8829 0.8751 0.8772 Columns 7 through 11 0.8766 0.8768 0.8767 0.8767 0.8767 ans = 0.8767 2 迭代法 迭代法是计算数学中的一种重要方法，用途很广，求解线性方程组和矩阵特征值时也要用到它。这里结合非线性方程的迭代法求解，介绍一下它的基本原理。 迭代法基本原理 迭代法的基本原理就是构造一个迭代公式，反复用它得出一个逐次逼近方程根的数列，数列中每个元素都是方程根的近似值，只是精度不同。 迭代法求解方程 f ( x ) = 0 （1） 时，先把方程等价地变换成形式 f ( x ) = x －g(x) = 0 ， （2） 移项得出： x = g(x) ( 3 ) 若函数g (x ）连续，则称（3）为迭代函数。用它构造出迭代公式： x k+1= g ( x k ） , k = 0 , l , 2 ， … ( 4 ) 从初始值 x 0出发，便可得出迭代序列： { x k ｝= x 0, x 1, x 2,….x k ,….. （ 5 ） 如果迭代序列（5 ）收敛，且收敛于x*，则由式（4）有： ()()()()()0***lim 1==-=-+∞ →x f x x g x x g k k 可见 x*便是方程（l ）的根。 迭代法几何意义： 如下图所示，解方程f ( x ) = 0可以等价地变换成求解 x = g ( x )， 图 4 - 2 方程求根迭代法原理示意图 在几何上，就等价求曲线y ＝x 和y ＝g ( x ）交点P*的坐标 x*。求迭代序列（5) ，就等于从图中x 0点出发，由函数y ＝g ( x 0）得出y ＝P 0，代入函数y ＝x 中得出 Q 1，再把Q 1的x 坐标 x 1代入方程y= g ( x ）得出P 1，如此继续下去，便可在曲线y ＝g ( x )上得到一系列的点P 0，P 1， … ，P k ， … ，这些点的x 坐标便是迭代数列 x l , x2 ， … ， x k ， … ，它趋向于方程（l ) 的根 x*，数列的元素就是方程根的近似值。数列的收敛就等价于曲线y ＝x 和y ＝g ( x ）能够相交于一点。 迭代公式收敛定理 要想用迭代法求出方程根的近似值，迭代序列（4 - 5）必须收敛。下面的定理给出了迭代法的收敛条件，同时也给出了迭代公式的误差。 收敛定理：方程 x = g ( x ）在（ a , b ）内有根 x*，如果： ① 当x ∈[a,b]时，g( x ）∈[a,b]; ② g ( x ）可导，且存在正数 q < 1，使得对于任意x ∈[a,b]都有|g ’( x )|≤ q < 1，则有以下结论。 ① 方程x = g ( x ）在（a , b ）内有唯一的根x*。 ② 迭代公式 x k+1 = g ( x k ）对（a , b ）内任意初始近似根 x 0均收敛于x*。 ③ 近似根 x k 的误差估计公式为： 011*x x q q x x k n --≤- (4 - 6) 2. 迭代法 a) 松弛法：由方程()0f x =构造一个等价方程 ()x x φ=． 则迭代方程是： 1(1)()k k k k k x x x ωωφ+=-+，1/(1'())k k x ωφ=-，其中'()1x φ≠． 松弛法的加速效果是明显的 (见附录4)，甚至不收敛的迭代函数经加速后也能获得收敛． b) Altken 方法： 松弛法要先计算'()k x φ，在使用中有时不方便，为此发展出以下的 Altken 公式： (1)()k k x x φ= ； (2)(1)()k k x x φ=； (2)(2)(1)2(2)(1)1()/(2)k k k k k k k x x x x x x x +=---+，ΛΛ,2,1,0=k 这就是Altken 公式，它的加速效果也是十分明显的，它同样可使不收敛的迭代格式获得收敛(见附录5)． 具体实验2：普通迭代法 采用迭代过程：1()k k x x φ+=求方程3310x x -+=在 0.5 附近的根，精确到第 4 位小数． 构造等价方程：3(1)/3x x =+ 用迭代公式： 31(1)/3k k x x +=+，ΛΛ,2,1,0=k 具体实验3：迭代法的加速1——松弛迭代法 3()(1)/3x x φ=+，2()'x x φ=，21/(1)k k x ω=- 迭代公式为 31(1)(1)/3k k k k k x x x ωω+=-++ clc;x=[];w=[]; x(1)=1;w(1)=1/(1-x(1)); for i=1:10 w(i)=1/(1- x(i)); x(i+1)=(1-w(i))*x(i)+ w(i)*(x(i)^3+1)/3; end x 另外有程序可以参考，详见参见附录4． 具体实验4：迭代法的加速2——Altken 迭代法 迭代公式为： (1)3(1)/3k k x x =+，(2)(1)3(1)/3k k x x =+ (2)(2)(1)2(2)(1)1()/(2)k k k k k k k x x x x x x x +=---+，ΛΛ,2,1,0=k %（符号计算） syms x fx gx; gx=(x^3+1)/3;fx=x^3-3*x+1; disp('k x x1 x2') x=0.5;k=0; ffx=subs(fx, 'x', x); while abs(ffx)>0.0001; u=subs(gx, 'x', x);v=subs(gx, 'x', u); disp([num2str(k), ' ', num2str(x), ' ', num2str(u), ' ', num2str(v)]) x=v-(v-u)^2/(v-2*u+x);k=k+1;ffx=subs(fx, 'x', x); end disp([num2str(k), ' ', num2str(x), ' ', num2str(u), ' ', num2str(v)]) %（数值计算） function [y,p]=althken() % 求方根的迭代程序 clc,format long e, x(1)=6; i=1;p=[];ezplot('x^3-3*x+1',[x(1)-9,x(1)+1]);hold on plot([x(1)-20,x(1)+2],[0,0]) while abs(f(x(i)))>=10^(-5) plot(x(i),0,'*') t1=phi(x(i));t2=phi(t1); x(i+1)=t2-(t2-t1)^2/(t2-2*t1+x(i)+eps); p=[p;[i, x(i),t1,t2]]; i=i+1; pause(0.1) end p,y=x(i), i, format function u=phi(x) u=(x^3+1)/3; end function u=f(x) u=x^3+1-3*x; end end 第二章 迭代法的一般原理 非线性方程组无论从理论上还是计算方法上，都比线性方程组复杂得多。一般的非线性方程组很难求出解析解，往往只能求出其数值解，且往往只能借助于迭代法。本章我们将讨论迭代法的一般原理、迭代法的一般构造及迭代收敛速度的衡量标准。 2-1 迭代法与不动点定理 设n n R R D →?:f ，考虑方程 ()0=x f (2-1) 若存在D *∈x ，使()0=*x f ，则称*x 为方程(2-1) 的解。 用迭代法求解(2-1) ，先将(2-1)化为等价的方程 ()x g x = (2-2) 这里映象n n R R D →?:g 。 方程(2-2)的解*x (即()**x g x =)称为映象g 的不动点。因此用迭代法解方程(2-1)，就是求(2-2)中映象g 的不动点。这样以及g 是否存在不动点自然就是我们关心的问题。 定理2-1 若n n R R D →?:g 为有界闭集D D ?0上的严格非膨胀映象，()00D D ?g ，则g 在0D 内有唯一不动点。 证 唯一性 设g 在0D 内至少有两个不动点1x ，2x ，则 ()() 2121x x x g x g x x 21-≤-=-α 因1<α，所以由上式推得21x x =。唯一性得证。 记()()x g x x -=?，由g 及泛数的连续性可知1:R R D n →??连续。因0D 为有界闭集，故?在0D 上有最小值。设0D *∈x 为最小点，即 ()()x g x x -=∈min 0 D x *? 则*x 为g 的不动点。因为若不然，则有()**x g x ≠，再由g 严格非膨胀，可得 ()()()()()***x g g x g x g -=?()()***x x g x ?=-< 这与*x 为?的最小点相矛盾，故*x 为g 的不动点。 注 定理中0D 的有界闭性、g 的压缩性和g 映0D 入自身，此3个条件缺一不可。例如，()x x x g 1+=在[)+∞=,D 10上严格非膨胀，但它在0D 中却没有不动点。 下面我们介绍在应用上非常广泛的不动点定理。 定理2-2 (Brouwer 不动点定理) 设n n R R D →?:g 在有解闭凸集D D ?0上连续，且()00D D G ?，则g 在0D 至少有一个不动点。 本定理在一维情形下叙述为：[]b a f ,: []b a ,→则f 在[]b a ,中至少有一个不动点。几何解释见图2-1。 x b a 图2-1 一维Brouwer 定理 “牛顿迭代法”最新进展文献综述牛顿法是一种重要的迭代法，它是逐步线性化的方法的典型代表。牛顿迭代法又称为牛顿-拉夫逊方法，它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根。另外该方法广泛用于计算机编程中。 介绍一下牛顿迭代法研究的前沿进展，1992年南京邮电学院基础课部的夏又生写的一篇题名一类代数方程组反问题的牛顿迭代法，对一类代数方程组反问题提出了一个可行的迭代解法。从算法上看,它是一种解正问题—迭代—解正问题迭代改善的求解过程。湖南师范大学的吴专保;徐大发表的题名堆浸工艺中浸润面的非线性问题牛顿迭代方法，为了研究堆浸工艺的机理,用牛顿迭代公式寻求浸润面的非线性方程的数值解,经过14次迭代的误差达到了,说明此算法收敛有效。浙江大学电机系的林友仰发表的牛顿迭代法在非线性电磁场解算中的限制对非线性电磁场解算中的限制做了分析，求解非线性方程组时迭代法是不可避免的。牛顿—拉斐森迭代法由于它的收敛速度快常被优先考虑。应用这个方法的主要问题是求雅可比矩阵。因为雅可比矩阵元素的计算非常费时。然而,本文要说明的是当利用以三角形为单元的有限元法求解非线性方程组时,应用牛顿法其雅可比矩阵容易求得,并且它保持了原系数的对称性和稀疏性,因而节省了时间。与此相反,若在差分法中应用牛顿迭代,并且按习惯用矩形网格进行剖分,则雅可比阵的计算很费时,而且不再保持原有对称性,这就使得存贮量和计算时间大为增加。南株洲工学院信息与计算科学系的吕勇;刘兴国发表的题名为牛顿迭代法加速收敛的一种修正格式，主要内容牛顿迭代法是求解非线性方程的一种重要的数值计算方法,在通常情况下,它具有至少平方收敛。本文利用文献[4]所建立的迭代格式xn+1=xn-αf(xfn)(x+n)f′(xn),对迭代格式中的参数α的讨论,实现了牛顿迭代法加速收敛的一种修正格式。 习题二 3、证明：当X 0=1.5时，迭代法X k+1=Xk +410和X k+1=21k X 310-都收敛于方程f(x)=x 3+4x 2-10=0在区间[1,2]内唯一实根x *，并分别用上述迭代法求满足于精度要求︱X k+1-X k ︱≤10-5的近似根。 解：证明：{先用迭代法求f(x)=x 3+4x 2-10=0的根。 （a ）对x 3+4x 2-10=0变形有：4x 2=10-x 3 所以：X=21310X - 则相应的迭代公式为：X k+1=21k X 310- 取：X 0=1.5，根据计算可以看出看，我们认为得到的迭代序列是 收敛的。}（此行可忽略） { 由 f(x)=x 3+4x 2-10=0得迭代方程：X=21310X -=g （x ） 先证明在区间【1,2】上x=g （x ）有实根。由于[1,2]上g ‘（x ）存在，所以g （x ）连续。作Q （x ）=x-g(x),则Q(x)在[1,2]上也连续。由定理1条件2有：Q （1）=1-g （1）≤0，Q （,2）=1-g （2）≥0 故存在x *∈[1,2]使Q *（x ）=0，即x *= Q *（x ） 又因为，x *是方程f(x)=x 3+4x 2-10=0在区间[1,2]内的唯一实根，（由定理一条件 2）对任意的x 0∈[1,2]时，X k ∈[1,2]（k=0,1,2,3…） 因为：x *- X k+1=g （x *）-g （X k ）=g ‘（h k ）（x *- X k ）故由条件1知： ︱X *-X k+1︱≤L ︱X *-X k ︱（k=0,1,2,3…）于是有：0≤︱X *-X k ︱≤L k ︱X *-X 0︱,0＜L ＜1，立即可知：lim （k 趋于无穷）︱X *-X k ︱=0,从而lim （k 趋于无穷）X k= X *。所以当X 0=1.5时，迭代法X k+1=Xk +410和X k+1=21k X 310-都是由迭代法X k+1=g （X k ）产生的迭代序列{ X k }收敛于方程f(x)=x 3+4x 2-10=0在区间[1,2]内唯一实 根x *。 正解如下： (1) （牛顿迭代法）： 证明：对方程f(x)=x 3+4x 2-10=0在区间[1,2]内， （a ） f ‘(x)=3x 2+8x ，f ’‘(x)=6x+8，f ’‘(x)在区间[1,2]内连续； （b ） f （1）=-5，f （2）=14，f （1）f （2）＜0； （c ） 对于任意的x ∈[1,2]，都有f ‘(x)=/(不等于)0； （d ） f ’‘(x)在[1,2]上保号； 综上所述，当X 0=1.5时，迭代法X k+1=Xk +410和X k+1=21k X 310-都收敛于方程f(x)=x 3+4x 2-10=0在区间[1,2]内唯一实根x *。 （2）用牛顿迭代法求近似根。 方程f(x)=x 3+4x 2-10=0有唯一实根x *∈[1,2]，容易验证，f(x)=x 3+4x 2-10在[1,2] 牛顿迭代法 李保洋 数学科学学院信息与计算科学学号：060424067 指导老师：苏孟龙 摘要：牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，即牛顿迭代法.迭代法是一种不断用变量的旧值递推新值的过程.跟迭代法相对应的是直接法或者称为一次解法，即一次性解决问题.迭代法又分为精确迭代和近似迭代.“牛顿迭代法”属于近似迭代法，本文主要讨论的是牛顿迭代法，方法本身的发现和演变和修正过程，避免二阶导数计算的Newton迭代法的一个改进，并与中国古代的算法，即盈不足术，与牛顿迭代算法的比较. 关键词：Newton迭代算法；近似求解；收敛阶；数值试验；中国古代数学； 九章算术；Duffing方程；非线性方程；收敛速度；渐进性 0 引言： 迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法或者称为一次解法，即一次性解决问题.迭代法又分为精确迭代和近似迭代.“二分法”和“牛顿迭代法”属于近似迭代法. 迭代算法是用计算机解决问题的一种基本方法.它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值.具体使用迭代法求根时应注意以下两种可能发生的情况： (1)如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制. (2)方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败. 所以利用迭代算法解决问题，需要做好以下三个方面的工作： 1、确定迭代变量.在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量. 2、建立迭代关系式.所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式(或关系).迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成. 3、对迭代过程进行控制，在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题.不能让迭代过程无休止地重复执行下去.迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来;另一种是所需的迭代次数无法确定.对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况，需要进一步分析出用来结束迭代过程的条件. 1牛顿迭代法： 迭代法 对于两端固定的单跨超静定粱，有转角位移方程如下： F AB AB AB B A AB AB M L i i i M +?-+=6 24?? （F AB M 为A 端的固端弯矩，如在均布荷载作用下2 12 1ql M F AB -=） 令' =AB A AB M i ?2，'=BA B AB M i ?2，L i M AB AB AB ?-="6 所以：F AB AB BA AB AB M M M M M +"+'+'=2 （'AB M 近端转角弯矩，' BA M 远端转角弯矩） 对于框架横梁，AB ?=0，所以0=" AB M ， F AB BA AB AB M M M M +'+'=2 即('++?? ? ??'+'=AB F AB BA AB AB M M M M M ) （1） 对于一点A ，AB M +AC M +AD M =0，有02,,,,,,=+ ' + ' ∑∑∑===D C B i F Ai D C B i iA D C B i Ai M M M ，可以得 到： ??? ? ??+'-=' ∑∑∑===D C B i F Ai D C B i iA D C B i Ai M M M ,,,,,,21， 其中： ???? ??+'- =' ∑∑∑===D C B i F Ai D C B i iA D C B i Ai Ai Ai M M i i M ,,,,,,2 1 （2） （2）式得到的' Ai M 为近似值，需要经过多次的迭代才满足精度，迭代的同时， 'iA M 也进行了迭代。这两个值趋近于准确解。 最后：根据（1）式，F Ai iA Ai Ai M M M M +'+'=2。 （3） 迭代法的步骤： 1. 计算固端弯矩F Ai M 和结点不平衡弯矩 ∑=D C B i F Ai M ,,，并设1=-2ik ik ik i i i μ' ∑初始值为 零。 2. 计算分配系数：∑=- D C B i Ai Ai i i ,,2 1，算出与结点相关杆件的弯矩分配系数。 3. 计算结点各杆件的近端转角弯矩：公式（2） ??? ? ??+'-='∑∑∑===D C B i F Ai D C B i iA D C B i Ai Ai Ai M M i i M ,,,,,,21 4. 多次迭代，保证精度。 5. 得到杆端最后弯矩：公式（3），F Ai iA Ai Ai M M M M +'+'=2 举例： 基于牛顿迭代法的圆形断面临界水深直接计算 学院：建筑工程学院学号：2111206052 姓名：王瑞峰 一、问题来源 圆形断面由于具有受力条件好、适应地形能力强、水力条件好等优点，已成为农田灌溉、城市给水排水等工程较常采用的断面形式。而临界水深的计算则是进行圆形断面水力计算的关键，但其计算较繁杂，要求解高次隐函数方程，且未知量包含在三角函数中，求解难度大。自20世纪90年代，对圆形断面临界水深的计算进行了大量研究，获得了较多成果。鉴此，本文应用牛顿迭代算法，得到一种较简洁且可提供高精度算法程序的近似计算公式。 二、数学模型 相应于断面单位能量最小值的水深称为临界水深，其计算公式为： 需满足的临界流方程为： 其中 式中，d为洞径；为临界水深对应的圆心角，rad；n为流速分布不均匀系数(不特殊说明时取1.0)；Q为流量，m3Is；g为重力加速度(通常取9.81 m/s2)；分别为临界流对应的过水断面面积和水面宽度。 无压流圆形断面的水力要素见图1 将式(1)、(3)、(4)代入式(2)得： 将式(5)整理即得临界水深的非线形方程： 由此可知．式(6)为临界水深h。的高次隐函数方程，且未知量包含在三角函数中。 即圆形断面临界水深的求解即为式(6)的求根问题。在现行工程实际中计算临界水深时均采用近似公式或试算法，所得结果精度不高且效率较低。 三、方法选择 牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根。 解非线性方程f(x)=0的牛顿法是把非线性方程线性化的一种近似方法。把f(x)在x0点 附近展开成泰勒级数f(x) = f(x0)+(x－x0)f'(x0)+(x－x0)^2*f''(x0)/2! +… 取其线性部分，作为非线性方程f(x) = 0的近似方程，即泰勒展开的前两项，则有f(x0)+f'(x0)(x－ x0)=f(x)=0 设f'(x0)≠0则其解为x1=x0－f(x0)/f'(x0) 这样，得到牛顿法的一个迭代序列：x(n+1)=x(n)－f(x(n))/f'(x(n))。 在对式(6)的求解方法中，应首选牛顿迭代法，因为牛顿迭代法可快速求解出其他方法求不出或难以求出的解。 引入无量纲参数k： 将式(7)代入式(6)得： 的一阶、二阶导函数分别为： 由牛顿迭代法可得： 式中，=0，1，2…为迭代次数；为的初值。 将式(8)、(9)代入式(10)，可得相应于式(6)临界水深对应中心角的牛顿迭代公式： 由式(11)迭代计算出临界水深对应的中心角后，代入式(1)即可得临界水深。 根据文献，为避免渡状水面有可能接触洞顶引起水流封顶现象。洞内水面线以上的空间不宜小于隧洞断面面积的15％，且高度不小于0.4m。可得临界水深对应的中心角的最大值一般不超过4.692，相应可得无量纲参数值的上限为0.5044。故取值范围为[O.000 0,0.504 4]。 查阅文献与的近似公式： 若将式(12)视为初值函数，代入式(11)进行一次迭代计算，不仅得到了直接计算的公式，且提高了计算结果的精度。 其中 将式(13)代入式(1)即得圆形断面临界水深。 计算实例： 某引水式电站输水隧洞为圆形断面，已知洞径d=3.0 m，试确定设计流量Q=8.0m3/s时的临界水深。 四、编程实现 本文采用Fortran软件求解，程序的代码如下： 本科生课程设计报告实习课程数值分析 学院名称管理科学学院 专业名称 学生姓名 学生学号 指导教师 实验地点 实验成绩 二〇一六年六月 填写说明 1、专业名称填写为专业全称，有专业方向的用小括号标明； 2、格式要求：格式要求： ①用A4纸双面打印（封面双面打印）或在A4大小纸上用蓝黑色水笔书写。 ②打印排版：正文用宋体小四号，1.5倍行距，页边距采取默认形式（上下 2.54cm，左右2.54cm，页眉1.5cm，页脚1.75cm）。字符间距为默认值（缩 放100%，间距：标准）；页码用小五号字底端居中。 ③具体要求： 题目（二号黑体居中）； 摘要(“摘要”二字用小二号黑体居中，隔行书写摘要的文字部分，小4 号宋体)； 关键词（隔行顶格书写“关键词”三字，提炼3-5个关键词，用分号隔开，小4号黑体)； 正文部分采用三级标题； 第1章××(小二号黑体居中，段前0.5行) 1.1 ×××××小三号黑体×××××（段前、段后0.5行） 1.1.1小四号黑体（段前、段后0.5行） 参考文献（黑体小二号居中，段前0.5行），参考文献用五号宋体，参 照《参考文献着录规则（GB/T 7714－2005）》。 迭代初值及公式对迭代收敛速度影响 摘要 迭代收敛速度受到迭代函数和初始迭代值的影响。 本实验在于体会在非线性方程求根的迭代法中，迭代函数和初始迭代值的选取对迭代收敛性的影响，sttefensen加速的效果，并试图总结一些规律。 关键词： sttenfensen加速；迭代初值；收敛速度 目录 第1章前言............................................................... 1.1 内容及要求.......................................................................................... 1.2 研究思路及结构安排 .......................................................................... 第2章相关理论知识........................................................ 2.1 迭代法 ................................................................................................. 2.2 迭代收敛 ............................................................................................. 第3章算法分析............................................................ 3.1 单一迭代算法步骤及流程图 .............................................................. 第4章算法实现............................................................ 4.1程序总体结构....................................................................................... 4.2 源程序清单.......................................................................................... 4.3程序运行 .............................................................................................. 第5章结果分析............................................................ 参考文献................................................................... 非线性方程组的牛顿迭代法的应用 CENTRAL SOUTH UNIVERSITY 数值分析实验报告 非线性方程组的牛顿迭代法的应用 一、问题背景 非线性是实际问题中经常出现的，并且在科学与工程计算中的地位越来越重要，很多我们熟悉的线性模型都是在一定条件下由非线性问题简化的，为得到更符合实际的解答，往往需要直接研究非线性科学，它是21世纪科学技术发展的重要支柱，非线性问题的数学模型有无限维的如微分方程，也有有限维的。道遥咏计算机进行科学计算都要转化为非线性的单个方程或方程组的求解。从线性到非线性是一个质的变化，方程的性质有本质不同，求解方法也有很大差别。本文主要介绍的是非线性方程组的牛顿迭代法的数值解法。 二、数学模型 对于方程()0=x f ，如果()x f 湿陷性函数，则它的求根是容易的。牛顿法实质上是一种线性化方法，其基本思想是将线性方程()0=x f 逐步归结为某种线性方程来求解。 设已知方程()0=x f 有近似根k x （假定()0'≠k x f ），将函数()x f 在点k x 展开，有 ()()()()k k k x x x f x f x f -+≈'， 于是方程()0=x f 可近似地表示为 ()()()0'=-+k k k x x x f x f 这是个线性方程，记其根为1+k x ，则1+k x 的计算公式 () () k k k k x f x f x x ' 1- =+， ,1,0=k 这就是牛顿法。 三、算法及流程 对于非线性方程 ()()()???? ????????=n n n n x L x x f M x L x x f x L x x f f ,,,,,,,,,2 12 12211 在()k x 处按照多元函数的泰勒展开，并取线性项得到 用牛顿迭代法求近似根 ————————————————————————————————作者：————————————————————————————————日期： 第四题 题目：用Newton 法求方程在 74 28140x x -+= （0.1，1.9）中的近似根（初始近似值取为区间端点，迭代6次或误差小于0.00001）. 解：此题是用牛顿迭代法求解近似根的问题 1. Newton 迭代法的算法公式及应用条件： 设函数在有限区间[a,b]上二阶导数存在，且满足条件 ⅰ. ()()0f a f b <; ⅱ. ()''f x 在区间[a,b]上不变号； ⅲ. ()'0f x ≠; ⅳ. ()()'f c f c b a ≤-，其中c 是a,b 中使()()''min(,)f a f b 达到的一个. 则对任意初始近似值0[,]x a b ∈，由Newton 迭代过程 ()()() 1'k k k k k f x x x x f x +=Φ=-，k=0，1，2… 所生成的迭代序列{ k x }平方收敛于方程()0f x =在区间[a,b]上的唯一解а. 对本题： )9.1()9.1(0 )8(4233642)(0 )16(71127)(0 )9.1(,0)1.0(,1428)(3225333647>?''<-=-=''<-=-='<>+-=f f x x x x x f x x x x x f f f x x x f Θ 故以1.9为起点 ?? ???='-=+9.1)()(01x x f x f x x k k k k 2. 程序编写 #include 姓名 实验报告成绩 评语： 指导教师（签名） 年 月 日 说明：指导教师评分后，实验报告交院（系）办公室保存。 实验一 方程求根 一、 实验目的 用各种方法求任意实函数方程0)(=x f 在自变量区间[a ，b]上，或某一点附近的实根。并比较方法的优劣。 二、 实验原理 (1)、二分法 对方程0)(=x f 在[a ，b]内求根。将所给区间二分，在分点 2a b x -=判断是否0)(=x f ；若是，则有根2a b x -=。否则，继续判断是否0)()( +)(0x f 0))(('0=-x x x f 设0)('0≠x f ,则=x -0x )(') (00x f x f 。取x 作为原方程新的近似根1x ，然后将1x 作为0x 代入上式。迭代公式为：=+1 k x -0x )(')(k k x f x f 。 三、 实验设备：MATLAB 软件 四、 结果预测 （1）11x = （2）5x = （3）2x =0,09052 五、 实验内容 （1）、在区间[0,1]上用二分法求方程0210=-+x e x 的近似根，要求误差不超 过3105.0-?。 （2）、取初值00=x ，用迭代公式=+1 k x -0x )(') (k k x f x f ，求方程0210=-+x e x 的近似根。要求误差不超过3105.0-?。 （3）、取初值00=x ，用牛顿迭代法求方程0210=-+x e x 的近似根。要求误差 不超过3105.0-?。 六、 实验步骤与实验程序 （1） 二分法 第一步：在MATLAB 软件，建立一个实现二分法的MATLAB 函数文件如下： function x=agui_bisect(fname,a,b,e) %fname 为函数名，a,b 为区间端点，e 为精度 fa=feval(fname,a); %把a 端点代入函数，求fa fb=feval(fname,b); %把b 端点代入函数，求fb if fa*fb>0 error('两端函数值为同号'); end 线性方程组的迭代法应用及牛顿迭代法的改进 摘要: 迭代解法就是通过逐次迭代逼近来得到近似解的方法。由于从不同 的问题而导出的线性代数方程组的系数矩阵不同，因此对于大型稀疏矩阵所对应线性代数方程组，用迭代法求解。本文论述了Jacobi 法，Gauss-Seidel 法，逐次超松弛法这三种迭代法，并在此基础上对牛顿型的方法进行了改进，从而使算法更为精确方便。 关键词:线性方程组，牛顿迭代法，Jacobi 法，Gauss-Seidel 法，逐次超松弛 法 1.线性方程组迭代法 1.1线性方程组的迭代解法的基本思想 迭代法求解基本思想:从某一初始向量X （0）=[x 1(0) ,x 2(0) ,……………x n (0) ]出发，按某种迭代规则，不断地对前一次近似值进行修改，形成近似解的向量{X (k)}。当近似解X (k) =[x 1(k) ,x 2(k) ,……………x n (k) ]收敛于方程组的精确解向量X* =[x 1*,x 2*,……………x n *]时，满足给定精度要求的近似解向量X (k)可作为X*的数值解。 1.2 线性方程组的迭代法主要研究的三个问题 (1) 如何构造迭代公式 (2) 向量数列{X (k)}的收敛条件 (3) 迭代的结束和误差估计 解线性方程组的迭代解法主要有简单迭代法、 Gauss-Seidel 法和SOR 法。简单迭代法又称同时代换法或Jacobi 法，是最简单的解线性方程组的迭代解法也是其他解法的基础。 1.3Jacobi 迭代法 设方程组点系数矩阵n n j A ai R ???=∈??满足条件0ii a ≠，i=0,1,2, …n 。把A 分解为 A=D+L+U CENTRAL SOUTH UNIVERSITY 数值分析实验报告 非线性方程组的牛顿迭代法的应用 一、问题背景 非线性是实际问题中经常出现的，并且在科学与工程计算中的地位越来越重要，很多我们熟悉的线性模型都是在一定条件下由非线性问题简化的，为得到更符合实际的解答，往往需要直接研究非线性科学，它是21世纪科学技术发展的重要支柱，非线性问题的数学模型有无限维的如微分方程，也有有限维的。道遥咏计算机进行科学计算都要转化为非线性的单个方程或方程组的求解。从线性到非线性是一个质的变化，方程的性质有本质不同，求解方法也有很大差别。本文主要介绍的是非线性方程组的牛顿迭代法的数值解法。 二、数学模型 对于方程()0=x f ，如果()x f 湿陷性函数，则它的求根是容易的。牛顿法实质上是一种线性化方法，其基本思想是将线性方程()0=x f 逐步归结为某种线性方程来求解。 设已知方程()0=x f 有近似根k x （假定()0'≠k x f ），将函数()x f 在点k x 展开，有 ()()()()k k k x x x f x f x f -+≈'， 于是方程()0=x f 可近似地表示为 ()()()0'=-+k k k x x x f x f 这是个线性方程，记其根为1+k x ，则1+k x 的计算公式 ()() k k k k x f x f x x ' 1- =+， ,1,0=k 这就是牛顿法。 三、算法及流程 对于非线性方程 ()()()???? ????????=n n n n x L x x f M x L x x f x L x x f f ,,,,,,,,,2 1212211 在()k x 处按照多元函数的泰勒展开，并取线性项得到 线性方程组的迭代法及程序实现 学校代码:11517 学号:200810111217 HENAN INSTITUTE OF ENGINEERING 毕业论文 题目线性方程组的迭代法及程序实现 学生姓名 专业班级 学号 系 (部)数理科学系 指导教师职称 完成时间 2012年5月20日河南工程学院 毕业设计(论文)任务书 题目:线性方程组的迭代法及程序实现专业:信息与计算科学学号 : 姓名一、主要内容: 通过本课题的研究,学会如何运用有限元方法来解决线性代数方程组问题,特别是Gaussie-Seidel迭代法和Jacobi迭代法来求解线性方程组。进一步学会迭代方法的数学思想,并对程序代码进行解析与改进,这对于我们以后学习和研究实际问题具有重要的意义。本课题运用所学的数学专业知识来研究,有助于我们进一步掌握大学数学方面的知识,特别是迭代方法。通过这个课题的研究,我进一步掌握了迭代方法的思想,以及程序的解析与改进,对于今后类似实际问题的解决具有重要的意义。 二、基本要求: 学会编写规范论文,独立自主完成。 运用所学知识发现问题并分析、解决。 3.通过对相关资料的收集、整理,最终形成一篇具有自己观点的学术论文,以期能对线性方程组迭代法的研究发展有一定的实践指导意义。 4.在毕业论文工作中强化英语、计算机应用能力。 完成期限: 2012年月指导教师签名:专业负责人签名: 年月日 目录 中文摘要....................................................................................Ⅰ英文摘要 (Ⅱ) 1 综述 1 2 经典迭代法概述 3 2.1 Jacobi迭代法 3 2.2 Gauss?Seidel迭代法 4 2.3 SOR(successive over relaxation)迭代法 4 2.4 SSOR迭代法 5 2.5 收敛性分析5 2. 6 数值试验 6 3 matlab实现的两个例题8 3.1 例1 迭代法的收敛速度8 3.2 例 2 SOR迭代法松弛因子的选取 12致谢16参考文献17附录19 第4章解线性方程组的迭代法 用迭代法求解线性方程组与第4章非线性方程求根的方法相似，对方程组进行等价变换，构造同解方程组(对可构造各种等价方程组， 如分解，可逆，则由得到)，以此构造迭代关系式 （4.1） 任取初始向量，代入迭代式中，经计算得到迭代序列。 若迭代序列收敛，设的极限为，对迭代式两边取极限 即是方程组的解，此时称迭代法收敛，否则称迭代法发散。我们将看到，不同于非线性方程的迭代方法，解线性方程组的迭代收敛与否完全决定于迭代矩阵的性质，与迭代初始值的选取无关。迭代法的优点是占有存储空间少，程序实现简单，尤其适用于大型稀疏矩阵；不尽人意之处是要面对判断迭代是否收敛和收敛速度的问题。 可以证明迭代矩阵的与谱半径是迭代收敛的充分必要条件，其中是矩阵的特征根。事实上，若为方程组的解，则有 再由迭代式可得到 由线性代数定理，的充分必要条件。 因此对迭代法(4.1)的收敛性有以下两个定理成立。 定理4.1迭代法收敛的充要条件是。 定理4.2迭代法收敛的充要条件是迭代矩阵的谱半径 因此，称谱半径小于1的矩阵为收敛矩阵。计算矩阵的谱半径，需要求解矩阵的特征值才能得到，通常这是较为繁重的工作。但是可以通过计算矩阵的范数等方法简化判断收敛的 工作。前面已经提到过，若||A||p矩阵的范数，则总有。因此，若，则必为收敛矩阵。计算矩阵的1范数和范数的方法比较简单，其中 于是，只要迭代矩阵满足或，就可以判断迭代序列 是收敛的。 要注意的是，当或时，可以有，因此不能判断迭代序列发散。 在计算中当相邻两次的向量误差的某种范数小于给定精度时，则停止迭代计算，视为方程组的近似解（有关范数的详细定义请看3.3节。） 4.1雅可比（Jacobi）迭代法 4.1.1 雅可比迭代格式 雅可比迭代计算 元线性方程组 （4.2） 写成矩阵形式为。若将式（4.2）中每个方程的留在方程左边，其余各项移到方程右边；方程两边除以则得到下列同解方程组： 记，构造迭代形式 编号 毕业设计（论文）题目 Newton Raphson 算法及其应用 二级学院数学与统计学院 专业信息与计算科学 班级108010101 学生姓名侯杰学号10801010106 指导教师职称 时间 目录 摘要 (3) Abstract (3) 一、绪论 (4) 1.1 选题的背景和意义 (4) 1.2 牛顿迭代法的优点及缺点 (4) 二、Newton Raphson 算法的基本原理 (5) 2.1 Newton Raphsn算法 (5) 2.2 一种修正的Newton Raphsn算法 (7) 2.3 另外一种Newton Raphsn算法的修正 (11) 三、Newton Raphson 算法在计算方程中的应用 (18) 四、利用牛顿迭代法计算附息国债的实时收益率 (21) 4.1附息国债实时收益率的理论计算公式 (22) 4.2附息国债实时收益率的实际计算方法 (22) 4.3利用牛顿迭代法计算 (23) 五、结论 (26) 致谢 (27) 参考文献 (28) 摘要 牛顿在17世纪提出的一种近似求解方程的方法，即牛顿拉夫森迭代法.迭代法是一种不断的用变量的旧值递推新值的过程.跟迭代法相对应的是直接法或被称为一次解法，即一次性解决的问题.迭代法又分为精确迭代以及近似迭代.“牛顿迭代法”就属于近似迭代法，本文主要讨论的就是牛顿迭代法，方法本身的发现到演变到修正的过程，避免二阶导数计算的Newton迭代法的一个改进，以及用牛顿迭代法解方程，利用牛顿迭代法计算国债的实时收益率。 关键词：Newton Raphson迭代算法；近似解；收益率； Abstract In the 17th century，Newton raised by an approximate method of solving equations，that is Newton Iteration，a process of recursion new value constantly with the old value of variable. Correspond with the iterative method is a direct method or as a solution，that is a one-time problem solving. Iteration is divided into exact iterative and approximate iterative. "Newton Iterative Method" are approximate iterative method. This article mainly focuses on the Newton Iteration. The main contents of this article include the discovery，evolution and amendment process of this methods; an improve of avoiding calculating Newton Iteration with second-order derivative; Newton Raphson iterative method of solving equations and Calculating the real-time yield of government bonds. Keywords: Newton Iterative Algorithm; approximate solution; Yield； 郑州师范学院 毕业论文 题目迭代法及其在数值求解 线性方程组中的应用 姓名陈丹丹 学号124103052041 院系数学与统计学院 专业数学与应用数学 年级班级B12数应2班 指导教师王明建 2016年5月20 日 毕业论文作者声明 本人郑重声明：所呈交的毕业论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。 本人完全了解有关保障、使用毕业论文的规定，同意学校保留并向有关毕业论文管理机构送交论文的复印件和电子版。同意省级优秀毕业论文评选机构将本毕业论文通过影印、缩印、扫描等方式进行保存、摘编或汇编；同意本论文被编入有关数据库进行检索和查阅。 本毕业论文内容不涉及国家机密。 论文题目：迭代法及其在数值求解线性方程组中的应用 作者单位：郑州师范学院 作者签名： 目录 摘要 (1) 引言 (3) 1.预备知识 (3) 1.1迭代法的基本形式 (3) 1.2Jocabi迭代法 (4) 1.2.1分量形式的Jacobi迭代法 (4) 1.2.2矩阵形式的Jacobi迭代法 (5) 1.2.3Jacobi迭代法的算法实现步骤 (6) 1.3Gauss-Seidel迭代法 (6) 1.3.1分量形式的Gauss-seidel迭代法 (6) 1.3.2矩阵形式的Gauss-seidel迭代法 (6) 1.3.3Gauss-Seidel迭代法的算法实现步骤 (7) 1.4超松弛迭代法（SOR迭代法） (7) 1.4.1分量形式的SOR方法 (7) 1.4.2矩阵形式的SOR方法 (8) 1.4.3SOR迭代法的算法实现步骤 (9) 1.5迭代法的收敛性 (9) 2. 数值求解线性方程组 (10) 2.1用Jacobi迭代法求解 (10) 第二章迭代法得一般原理 非线性方程组无论从理论上还就是计算方法上,都比线性方程组复杂得多。一般得非线性方程组很难求出解析解,往往只能求出其数值解,且往往只能借助于迭代法。本章我们将讨论迭代法得一般原理、迭代法得一般构造及迭代收敛速度得衡量标准。 2-1 迭代法与不动点定理 设,考虑方程 (2-1) 若存在,使,则称为方程(2-1) 得解。 用迭代法求解(2-1) ,先将(2-1)化为等价得方程 (2-2) 这里映象。 方程(2-2)得解(即)称为映象g得不动点。因此用迭代法解方程(2-1),就就是求(2-2)中映象g得不动点。这样以及g就是否存在不动点自然就就是我们关心得问题。 定理2-1若为有界闭集上得严格非膨胀映象,,则g在内有唯一不动点。 证唯一性设g在内至少有两个不动点,,则 因,所以由上式推得。唯一性得证。 记,由g及泛数得连续性可知连续。因为有界闭集,故?在上有最小值。设为最小点,即 则为g得不动点。因为若不然,则有,再由g严格非膨胀,可得 这与为?得最小点相矛盾,故为g得不动点。 注定理中得有界闭性、g得压缩性与g映入自身,此3个条件缺一不可。例如,在上严格非膨胀,但它在中却没有不动点。 下面我们介绍在应用上非常广泛得不动点定理。 定理2-2 (Brouwer不动点定理)设在有解闭凸集上连续,且,则g在至少有一个不动点。 本定理在一维情形下叙述为: 则f在中至少有一个不动点。几何解释见图2-1。 2-2 迭代格式得构造 前一节我们谈到,用迭代法求解方程(2-1),就是先将这个方程化为等价得方程(2-2),然后求映象g 得不动点,通常(也就是最简单得情形)构造如下迭代序列: , (2-3) 我们希望这个迭代序列收敛到g 得不动点,亦即方程得解。如果g 就是压缩得,可望迭代序列收敛。图2-2展示了一维迭代收敛得一种情形。 对于(2-3) f 与。如果 g 不依赖于迭代步k 只依赖于,k ,则迭代形式可表示为 (2-4) 并称之为,这时得迭代为多步迭代。例如,则迭代可写为 (2-5) 称这种迭代为m 步迭代。类似地有m 步非定常迭代。 通常称g 或为迭代函数。用不同得方法构造得迭代函数可得到不同得得到法。设,如果一个迭代法得到得序列则称得到序列就是适定得,适定性就是迭代法得起码要求。 若就是方程(2-1)得解,且序列满足 则称迭代序列收敛于。 定义2-1 设,就是方程得一个解。若存在得一个邻域,使对任何初始值(对于m 步迭代法,初值为 ),迭代序列总就是适定得且收敛于,则称就是迭代序列得吸引点。 不少迭代法都就是设法使迭代函数g 就是压缩得,这时迭代序列得吸引点恰就是g 得不动点。有时候也可使g 具有某种单调性,构成单调单调法。 2-3 迭代法得收敛性与收敛阶 前面谈到,一个迭代法,当其产生得迭代序列在适定与收敛时才有意义。单步迭代格式(2-3)在实际中被采用得最多,这里,我们不加证明地给出三个与(2-3)格式有关得收敛性定理。 定理2-4 设就是方程得解,。若存在一个开球S = 与常数,使得对一切,有 x 021(x ) 图2-2 迭代序列收敛第二章 迭代法的一般原理
牛顿迭代法文献综述
数值计算迭代法
牛顿迭代法
迭代法与D值法使用
Newton迭代法实例
迭代初值及公式对迭代收敛速度影响
非线性方程组的牛顿迭代法的应用
用牛顿迭代法求近似根
MAAB计算方法迭代法牛顿法二分法实验报告
线性方程组的迭代法应用及牛顿迭代法的改进
非线性方程组的牛顿迭代法的应用
线性方程组的迭代法及程序实现
数值计算_第4章 解线性方程组的迭代法
牛顿迭代法及其应用教学提纲
迭代法及其在数值求解线性方程组中的应用
第二章 迭代法得一般原理
相关主题
文本预览