08-课件：55.2 迭代法

迭代法
迭代法也叫辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。

对非线性方程，利用递推关系式，从开始依次计算，来逼近方程的根的方法，若仅与有关，即，则称此迭代法为单步迭代法，一般称为多步迭代法；对于线性方程组，由关系从开始依次计算来过近方程的解的方法。

若对某一正整数，当时，与k 无关，称该迭代法为定常迭代法，否则称之为非定常迭代法。

称所构造的序列为迭代序列。

求通项公式的方法（用迭代法）已知数列{An},a1=2,an=2a(n-1)-1(n>或=2）求通项公式
an=2a(n-1)-1 an-1=2(a(n-1)-1 ) n>或=2
所以an-1 为等比数列
an-1=(a1-1)*2^(n-1)
an-1=2^(n-1)
an=2^(n-1)+1
牛顿迭代法求开方
数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。

方法使用函数的泰勒级数的前面几项来寻找方程的根。

牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收
敛。

另外该方法广泛用于计算机编程中。

用迭代法求平方根
对于A>1,求其平方根可构造用如下公式迭代：
f(x)=(1/a)(x+a/x),a=A/(A-1),迭代初值x0=[√A]+1,[x]为x的取整.如想求70的平方根,可令初值x0=9.
对于A1,用如上方法求出平方根后,在成10^(-n),即得结果.。

第三章 线性代数方程组数值解法（迭代法）迭代法是解线性方程组的另一类方法，特别是适用于解大型稀疏线性方程组，如由某些偏微分方程数值解法中转化来的高阶线性代数方程组。

事实上，迭代法是求解多种数值问题的基本方法。

迭代法作为一种求解数值问题的通用方法，其基本思想是针对求解问题预先设计好某种迭代格式，从而产生求解问题的近似解的迭代序列，在迭代序列收敛于精确解的情况下，按精度要求取某个迭代值作为问题解的近似值，这就是求解数值问题的迭代法。

在这一章，我们的求解问题是线性方程组，下一章是非线性方程和非线性方程组，在不少其他问题中还会用到。

迭代法的内容包括下述两个主要方面： ① 针对具体问题构造具体的迭代格式。

② 研究迭代格式(序列)的收敛性并作误差分析。

3.1 解线性方程组迭代法的基本概念和基本迭代公式解线性代数方程组 b Ax = （3.1.1） (nn RA ⨯∈非奇异,0),,,(21≠=T n b b b b , Tn x x x x ),,,(21 =为解向量 )的迭代法的具体做法是： 把方程组(3.1.1)变形为等价形式)(x F x =我们这里只研究如上式的线性的形式 f Bx x +=(其中nn R B ⨯∈，nR f ∈ )例如把A分解为nn R M N M A ⨯∈-=,则（ b M Nx Mx b x N M 11)(--+=→=- ）如果令 N M B 1-=， b M f 1-= 这就是前面的迭代格式 f Bx x +=。

（对应的迭代公式是： ),,2,1,0()()1(n k f Bx xk k =+=+ 其中每一步迭代值仅依赖于前一步的迭代值。

称为单步迭代。

） 如果{)(k x }当 ∞→k 时有极限*x 存在， *)(lim x xk k =∞→则称迭代公式是收敛的；3.2 Jacobi 迭代法/Gauss —Seidel 迭代法这是解线性方程组的两种基本的方法。

1. Jacobi 迭代公式设方程组b Ax =中 nn ij Ra A ⨯∈=)(，ni R b b ∈=且 ),,2,1(0n i a ii =≠。

常用算法——迭代法一、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。

设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：（1）选一个方程的近似根，赋给变量x0；（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。

若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。

上述算法用C程序的形式表示为：【算法】迭代法求方程的根{ x0=初始近似根；do {x1=x0；x0=g(x1)；/*按特定的方程计算新的近似根*/} while ( fabs(x0-x1)>Epsilon)；printf(“方程的近似根是%f\n”，x0)；}迭代算法也常用于求方程组的根，令X=（x0，x1，…，xn-1）设方程组为：xi=gi(X) (I=0，1，…，n-1)则求方程组根的迭代算法可描述如下：【算法】迭代法求方程组的根{ for (i=0;i<n;i++)x=初始近似根;do {for (i=0;i<n;i++)y=x;for (i=0;i<n;i++)x=gi(X);for (delta=0.0,i=0;i<n;i++)if (fabs(y-x)>delta) delta=fabs(y-x)；} while (delta>Epsilon)；for (i=0;i<n;i++)printf(“变量x[%d]的近似根是%f”，I，x)；printf(“\n”)；}具体使用迭代法求根时应注意以下两种可能发生的情况：（1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；（2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。

迭代法编辑迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法，即一次性解决问题。

迭代法又分为精确迭代和近似迭代。

“二分法”和“牛顿迭代法”属于近似迭代法。

迭代算法是用计算机解决问题的一种基本方法。

它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

目录1算法▪确定迭代变量▪建立迭代关系式▪对迭代过程进行控制▪举例2递归的基本概念和特点1算法编辑迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法（Iterative Method）。

一般可以做如下定义：对于给定的线性方程组x=Bx+f（这里的x、B、f同为矩阵，任意线性方程组都可以变换成此形式），用公式x(k+1）=Bx(k)+f（括号中为上标，代表迭代k次得到的x，初始时k=0)逐步带入求近似解的方法称为迭代法（或称一阶定常迭代法）。

如果k趋向无穷大时limx（k）存在，记为x*，称此迭代法收敛。

显然x*就是此方程组的解，否则称为迭代法发散。

跟迭代法相对应的是直接法（或者称为一次解法），即一次性的快速解决问题，例如通过开方解决方程x +3= 4。

一般如果可能，直接解法总是优先考虑的。

但当遇到复杂问题时，特别是在未知量很多，方程为非线性时，我们无法找到直接解法（例如五次以及更高次的代数方程没有解析解，参见阿贝耳定理），这时候或许可以通过迭代法寻求方程（组）的近似解。

最常见的迭代法是牛顿法。

其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、线性规划、非线性规划、单纯型法、惩罚函数法、斜率投影法、遗传算法、模拟退火等等。

利用迭代算法解决问题，需要做好以下三个方面的工作：确定迭代变量在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。

迭代法又分为精确迭代和近似迭代。

“二分法”和“牛顿迭代法”属于近似迭代法。

迭代算法是用计算机解决问题的一种基本方法。

它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

例 1 ：一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。

如果所有的兔子都不死去，问到第12 个月时，该饲养场共有兔子多少只？分析：这是一个典型的递推问题。

我们不妨假设第 1 个月时兔子的只数为u 1 ，第 2 个月时兔子的只数为u 2 ，第 3 个月时兔子的只数为u 3 ，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有u 1 ＝ 1 ，u 2 ＝u 1 ＋u 1 ×1 ＝ 2 ，u 3 ＝u 2 ＋u 2 ×1＝ 4 ，……根据这个规律，可以归纳出下面的递推公式：u n ＝u n － 1 × 2 (n ≥ 2)对应u n 和u n － 1 ，定义两个迭代变量y 和x ，可将上面的递推公式转换成如下迭代关系：y=x*2x=y让计算机对这个迭代关系重复执行11 次，就可以算出第12 个月时的兔子数。

大连理工大学罗晓芳算法思想:利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，每次执行这组指令(或步骤)时，都从变量原值推出一个新值。

关键步骤：1、确定迭代变量:也就是直接或间接地不断由旧值递推出新值的变量。

2、建立迭代关系式: 指如何从变量的前一个值推出其下一个值的公式(或关系)。

3、对迭代过程进行控制。

在什么时候结束迭代过程?迭代算法一般结构小猴在一天内摘了若干个桃子，当天吃掉一半多一个；第二天吃掉剩下的一半桃子多一个；以后每天都吃尚存桃子的一半零一个。

直到第7天早上要吃时，只剩下一个了，问小猴共摘了多少个桃子？例4：小猴吃桃子问题问题分析：先从最后一天推出倒数第二天的桃子，再从倒数第二天推出倒数第三天的桃子，……设第n天的桃子为x,它是前一天的桃子数的一半少一个x n = xn-1/2-1前一天的桃子数为：xn-1=(xn+1)×2(递推公式）设迭代变量x x=(x+1)*2#include "stdio.h"int main(){int i, x;x=1；printf("第7 天的桃子数为：1只\n");for(i=6; i>=1; i--){x=(x+1)*2;printf("第%d 天的桃子数为：%d 只", i , x);printf("\n");}return 0;小猴吃桃子问题迭代关系，迭代:原值推出新值//迭代变量赋初值思考:小猴在一天内摘了94个桃子，当天吃掉一半多一个；以后每天都吃尚存桃子的一半多一个，问小猴直到第几天早上要吃时只剩下一个了？例5：用迭代法求a 的算术平方根。

公式：x n =0.5*(x n-1+a/x n-1)确定初值为x0,新值为x1 取a/2为x0的初值，迭代结束条件:|x1-x0|<=10-5.#include <stdio.h>#include <math.h>int main( ){ float a, x0, x1;scanf("%f",&a);x0=a/2; x1=(x0+a/x0)/2; while (fabs(x1-x0)>1e-5){x0=x1;x1=(x0+a/x0)/2; }printf("sqrt(a)=%f\n", x1);零非零|x1-x0|>10-5？x0=x1x1=(x0+a/x0)/2x0=a/2x1=(x0+a/x0)/2输出a ，x1迭代:原值推出新值// 迭代变量赋初值//新值变原值//将循环结束条件取反1.分析：程序采用逐位分离的方法。