下载文档原格式
迭代法——非线性方程与方程组的数值解法7.1方程求根与二分法二分法，取中点判断左右区间[a,b]-----x 0=(b+a)/2---f(x0)是否为0是：零点为x 0；否，f(x 0)与f(a)同号，则x 0取代a ；f(x 0)与f(b)同号，则x 0取代b 重新计算区间；7.2不动点迭代法及其收敛性不动点：将f(x)=0写成隐式x=φ(x)，若x*满足f(x*)=0，则x*=φ(x*) ；反之亦然，则x*为函数φ(x)的一个不动点。
迭代函数：φ(x)选初值x 0，x 1=φ(x 0)……有x k+1=φ(x k ),k=0,1,2….。
lim k→∞x k =x ∗等价于{xk}等价于迭代方程收敛不动点存在性: φ(x)在[a,b]区间内满足：（1）任意∀x ϵ[a,b]，有a ≤φ(x)≤b ；（2）∃1>L >0，使得∀x ，y ∈ a,b 都有丨∅ x −∅ y 丨≤L 丨x −y 丨； 则φ(x)在[a,b]区间内存在唯一不动点x*收敛误差计算： 丨xk −x ∗丨≤L k1−L 丨x1−x0丨丨xk +1−xk 丨≤L k 丨x1−x0丨丨x ∗−xk 丨≤11−L 丨xk +1−xk 丨局部收敛性：φ(x)在x*的某个领域R ：丨x-x*丨≤δ，对任意x0属于R 迭代后产生的｛xk ｝属于R ，且收敛到x*则称为局部收敛。
P 阶收敛：设迭代过程x k+1=φ(x)收敛于方程x=φ(x)的根x*，如果当k →∞，则有迭代误差e k =x k -x*满足渐进关系式：e k +1e k p →C （非零常数）则称迭代过程P 阶收敛。
领域内p 阶收敛：φ（p ）在所求根x*的领域内连续，有φ’(x*)=φ”(x*)=…= φ（p-1）(x*)=0；φ（p ）(x*)≠0，则在x*领域内p 阶收敛7.3收敛加速法1．艾特金加速收敛法x*=x 2x 0−x 12x 2−2x 1+x 0=x 0−（x 1−x 0）2x 2−2x 1+x 0；x k+1=φ(x k )x k+2=φ(x k+1)X k +1 =x k −（x k +1−x k ）2x k +2−2x k +1+x k =x k -（Δx k ）2/Δ2x k2．史蒂文森迭代法y k =φ(x k )，z k =φ(y k )，x k+1=x k −（y k −x k ）2zk −2y k +x k ，k=0，1，…改写为不动点迭代法：x k+1=Ψ(x k )，k=0，1，…Ψ(x)=x-（φ（x ）−x ）2φ（φ（x ））−2φ（x ）+x若x*为Ψ(x)的不动点，则x*也是φ（x ）的不动点；反之，若x*是φ（x ）的不动点，当φ”(x)存在， φ’(x)≠1时，x*也是Ψ(x)的不动点； 史蒂文森迭代法是二阶收敛的。
一：非线性方程的基本迭代方法简单迭代法非线性方程的一般形式f(x)=0 其中f(x)是一元非线性函数。
若存在常数s 使f(s)=0，则称s 是方程的根。
把方程转化为其等价的方程)(x x ϕ=，因而有)(s s ϕ=。
选定s 的初始近似值0x ，用迭代公式)(1k k x x ϕ=+，得到}{k x 收敛于s ，就求出了方程的解。
收敛性：)(s s ϕ=,)(x ϕ'在包含s 的某个开区间内连续。
如果|)(x ϕ'|<1则存在δ>0，0x ∈[s-δ,s+δ]时，由该迭代函数产生的迭代法收敛。
收敛速度：（}{k x 收敛于s ，k e 为s 与k x 的差值绝对值，则c e e r k k k =+∞→1lim，c 是常数，则该迭代是r 阶收敛）Newton 法为了使迭代的收敛速度更快，应尽可能使)(x ϕ在s 处有更多阶的导数等于零。
令)(x ϕ=)()(x f x h x +,)(x h 为待定函数，已知)(s ϕ'=0，推出)(x h =)(1x f '-。
这就得出了牛顿法的迭代形式 )()(1k k k k x f x f x x '-=+，（k=0、1、···） 牛顿法是二阶收敛的迭代方法，但是牛顿法的是局部收敛的，因此要求初值要靠近根。
求解中，对于每一个k 都要计算)(k x f '，而导数的计算比较麻烦，否则会产生很大误差。
割线法 在牛顿法基础上，用11)()(----k k k k x x x f x f 来代替)(k x f '，其中1-x 、0x 预先给定。
得到了割线法的迭代形式 )()())((111--+---=k k k k k k k x f x f x x x f x x ，（k=0、1、···） 割线法的收敛速度至少为1.618这样就避免了牛顿法求导数的繁琐程序单点割线法单点割线法就是在割线法的基础上，用))(,(00x f x 代替))(,(11--k k x f x ，得到的迭代形式 )()()(001k k k k k x f x f x f x x x x ---=+，（k=1、2、···） 单点割线法是一阶收敛的方法，它比割线法初值要少取一个点更加容易选取初值二：非线性方程的迭代解法的拓展修正的Chebyshev 法思想：将函数)(x f 在k x 处进行泰勒展开既 +-''+-'+≈!2)()())(()()(2k k k k k x x x f x x x f x f x f ，如果)(x f ≠0，先取线性部分来代替原来函数，既)(x f =)(k x f +))((k k x x x f -'=0，得到k x x -=)()(k k x f x f '-； 再用二次多项式部分代替原函数，既!2)()())(()()(2k k k k k x x x f x x x f x f x f -''+-'+==0，合并这两次的结果得到)()()))((2)()(1(2k k k k k k x f x f x f x f x f x x ''''⋅+-=，令1+=k x x ，得到就得到了新的迭代公式，这就是Chebyshev 方法的思想，该方法的迭代公式具有三阶收敛速度。
一、考试内容线性方程组和非线性方程（组）的求解、矩阵特征值和特征向量的计算、微积分的计算、微分方程定解问题的求解等，都是工程、科技、统计等实际问题中大量碰到的数学问题，这些问题的精确解很难求出。
而《计算方法》则是一门适合于计算机计算求解的数值方法，它简单可行，能有效求出上述数学问题的近似解。
通过本课程的学习，要求学生能掌握利用计算机求解基本数学问题常用的数值计算方法，学会构造基本的计算格式，并能作一定的误差分析，使学生具备基本的科学计算能力。
主要有：1.了解计算方法的认务和特点；2.熟练掌握方程的的近似解法，包括二分法、迭代法、牛顿迭代法和弦割法3.熟练掌握线性代数方程组的解法，直接解法中的高斯消去法、矩阵的直接三角分解法，平方根分解法，解三对角方程组的追赶法；解线性方程组的迭代法，简单迭代法，雅可比迭代法，赛德尔迭代法，SOR方法及其收敛性4.熟练掌握矩特征值和特征向量的计算，乘幂法与反幂法，古典雅可比方法，雅可比过关法5.熟练掌握插值法，拉格朗日插值法，牛顿插值法，等距节点插值法，埃尔米特插值法，三次样条插值法6.熟练掌握最小二乘法与曲线拟合，掌握矛盾方程组与最小二乘法，数据的多项式拟合，可化为线性拟合模型的曲线拟合7.熟练掌握数值积分与数值微分，包括牛顿-柯特斯求积公式、复化求积公式、龙贝格求积算法、高斯型求积公式和数值微分；8. 熟练掌握常微分方程初值问题数值解法，包括欧拉法与梯形法、泰勒展开法与龙格-库塔法、线性多步法2006-2007第一学期一. 填空1） 近似数253.1*=x 关于真值249.1=x 有____位有效数字；2） 设有插值公式)()(111k nk k x f A dx x f ⎰∑-=≈，则∑=nk kA1=______；（只算系数）3） 设近似数0235.0*1=x ，5160.2*2=x 都是有效数，则相对误差≤)(*2*1x x e r ____； 4） 求方程x x cos =的根的牛顿迭代格式为______；5） 矛盾方程组⎪⎩⎪⎨⎧-=+=-=+1211212121x x x x x x 与⎪⎩⎪⎨⎧-=+=-=+121222212121x x x x x x 得最小二乘解是否相同______。
4.2 非线性方程组的迭代解法 一、 一般概念1.非线性方程组的一般形式⎪⎪⎪⎩⎪⎪⎪⎨⎧===0),,,(0),,,(0),,,(21212211x x x fx x x f x x x f n nn n⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=n x x x x 21令⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=)()()()(21x f x f x f x F n则向量形式如下：0)(=x F2.解非线性方程组的方法 （1）简单迭代法（2）线性化方法（即Newton 法）（3）求函数极小值的方法（即最速下降法） 二、简单迭代法RR nn x F →:)(把方程组：F （x ）=0 改写成等价形式，即)19.4)((0)(x G x x F =⇔=适当选取初始向量D x ∈0，利用上述的等价形式，构成迭代公式：)20.4(,2,1,0),()()1( ==+k x G xk k其中G （x ）为迭代函数 2.收敛性(1)非局部收敛定理（压缩映象原理）定理4.13 设G:R R nn D −→−⊂在闭区域D D⊂0上满足条件：（1）G 把D0映入自身， （2）G 在D0上是压缩映射，则有下列结论：（1）对任取的D x 0)0(∈,由迭代公式4.20产生的序列{}D x k 0)(∈，且收敛于方程组4.19在D0内的唯一解（2）成立误差估计式xxL x x L kk )0()1()(*1--≤- xx L xxk k kk L)1()()(*1---≤-下面给出简单迭代法（4.20）局部收敛定理定理4.14 设G:R R nn D −→−⊂，)int(*D x ∈是方程组4.19的解，G 在x *处可微。
若()xG *'的谱半径()()1*<'x G ρ,则存在开球{}D x x x D⊂<<-=0,*δδ，使对任意的D x0)0(∈，由迭代法4.20产生的序列{}D x k 0)(∈且收敛于x*。
注：（1）但是对于线性方程组来说，上述定理成为全局收敛性定理，而不是局部收敛性定理。
计算方法第六章迭代法迭代法是一种重要的数值计算方法，在数学和计算机科学中有广泛的应用。
本章将介绍迭代法的基本概念、原理和应用，以及相关的数学原理和计算技巧。
首先，我们来了解迭代法的基本概念。
迭代法是通过逐步逼近的方式得到一个问题的解。
迭代法的基本思路是从一个初始值开始，通过重复计算和更新，得到更加接近最终解的近似值。
迭代法的优点是简单和灵活，但需要注意选择合适的迭代公式和初始值，以及控制迭代的停止条件。
迭代法的原理可以用以下的一般形式表示：```x_(n+1)=f(x_n)```其中，x_n表示第n次迭代得到的近似值，x_(n+1)表示第(n+1)次迭代的近似值，f是一个函数，表示迭代公式。
迭代法的思想是通过不断迭代更新x的值，直到满足一些停止条件为止。
迭代法的应用非常广泛，特别是在求解非线性方程和优化问题方面有重要的应用。
在求解非线性方程时，我们可以将方程转化为形式为f(x)=0的等式，然后通过迭代法逼近方程的根。
在优化问题中，我们可以通过最小化或最大化一个函数来寻找最优解，也可以使用迭代法逐步逼近最优解。
在迭代法的实际应用中，我们需要注意一些数学原理和计算技巧。
首先，迭代法的收敛性是关键的，即通过迭代公式逐步逼近的值是否趋于问题的解。
在评估迭代法的收敛性时，常用的方法有判断迭代序列的极限是否存在和是否满足一些收敛条件。
其次，选择合适的迭代公式和初始值对于迭代法的成功应用非常重要。
迭代公式应该是简单和有效的，能够在迭代过程中逐步逼近问题的解。
初始值的选择也会直接影响迭代的结果，通常需要根据问题的特点和经验进行选择。
另外，迭代法的计算精度和计算效率也是需要考虑的问题。
在迭代过程中，我们需要根据问题的要求不断调整迭代的次数和迭代的停止条件，以达到较高的计算精度。
同时，我们也需要通过优化迭代公式和使用更加高效的计算技巧来提高计算的效率。
最后，迭代法的应用还可以进一步扩展到其他领域。
例如，在图像处理中，我们可以使用迭代法逐步改进图像的质量；在机器学习中，我们可以使用迭代法来调整模型的参数，以求得更好的拟合效果。
非线性方程组迭代解法不动点法( unmovepoints.m)%非线性方程组的不动点法function [x,n]=unmovepoints(fun,x0,eps)if nargin<3eps=1e-3;endx1=feval(fun,x0);n=1;while(norm(x1-x0))>=eps x0=x1;x1=feval(fun,x0);n=n+1;if n>100000disp(' 无法收敛!');breakendendx=x1;Newton 迭代法( newtons.m)% 非线性方程组的Newton 迭代法function [x,n]=newtons(fun1,fun2,x0,eps)if nargin<4eps=1e-3;endx1=x0-feval(fun1,x0)/feval(fun2,x0);n=1;while norm(x1-x0)>=epsx0=x1;x1=x0-feval(fun1,x0)/feval(fun2,x0); n=n+1;if n>100000disp(' 无法收敛!');breakendendx=x1;注：方程组的迭代与方程迭代不同之处在于收敛的判断不能用 abs 而应用norm (范数，默认值为向量各元素的平方和的开方；norm(xl-xO)即为向量x1与x0对应元素差的平方和的开方。
在对应的函数程序中应注意向量的运算与数量运算的区别。
)用以上方法求解下列非线性方程组：f 1 X =x 1 - 0.7 sinx ! -0.2cosx 2 =0 f 2 X = x 2 - 0.7 cos% 0.2sinx 2 =0函数：%非线性方程组函数(适用于不动点法) function f=non li nerequsl(x) f(1)=0.7*si n(x(1))+0.2*cos(x (2)); f(2)=0.7*cos(x(1))-0.2*si n(x (2));%非线性方程组函数(适用于Newt on 迭代法) function f=non li nerequs2(x) f(1)=x(1)-0.7*si n(x(1))-0.2*cos(x(2)); f(2)=x (2)-0.7*cos(x(1))+0.2*si n(x (2));%非线性方程组函数导数(适用于Newt on 迭代法) function f=non li nerequs3(x) f=[1-0.7*cos(x(1)),0.2*si n(x(2));0.7*si n(x(1)),1+0.2*cos(x(2))];命令：fsolve(@ non li nerequs2,[0.5,0.5])[x,n]=unmo vepo in ts( @non li nerequs1,[0,0],1e-6)[x,n]=n ewt ons(@non li nerequs2, @non li nerequs3,[0,0],1e-6)计算结果：(eps=0.000001)迭代方法X迭代次数n解析解[0.52652262191818 0.50791971903685] - fsolve[0.52652266171295 0.50791973020932] - 不动点法[0.526521300913880.50792028463452] 30 Newton 迭代法[0.526522793690200.50791961189450]16导数为f 2 f 2对多方程则类似。
