在学习与研究算法的过程中，发现迭代思想很是常用。通俗的说，迭代思想，就是设定一个评判准则，然后通过一次次迭代直到符合评判准则，最后输出结果信息。
   这种思想，我们的生活里面也比比皆是。比方说，每个人都对自己有个期望标准。接下来，就是采用迭代的方式去满足这个期望。当然了，这个期望与标准更多是动态的、变化的。因而所采用迭代的方式也更复杂、更灵活。但是，万变不离其宗。迭代是手段，目的是优化。换句话说，就是越来越好。
   

迭代器
1、什么是迭代器
​	  迭代器指的是迭代取值的工具，迭代是一个重复的过程，每次重复都是基于上一次的结果而继续的，单纯的重复并不是迭代
2、迭代器应用场景
​    迭代器是用来迭代取值的工具，优点在于能够不依赖与索引进行循环取值
3、迭代器的使用
可迭代对象
# 凡是内置有__iter__方法的都称之为可迭代对象
# 调用可迭代对象下的__iter__方法会将其转换成迭代器对象
# 常见的可迭代对象包括：列表、字符串、元组、集合、字典、文件

迭代器方法遍历字典
#!/usr/bin/env python3
# -*- coding:utf-8 -*-


dic = {
	'a': 1,
	'b': 2,
	'c': 3
}
dic_iter = dic.__iter__()

while True:
	try:
		print(dic_iter.__next__())
	except StopIteration:
		break


迭代器与for循环的工作原理
for循环工作原理：
1. 调用对象下的__iter__()方法得到一个迭代器对象
2. 调用迭代器对象下的__next__()方法拿到一个返回值,然后赋值
3. 循环往复步骤2，直到抛出异常StopIteration，捕捉异常然后结束循环


即for循环是上部分代码实现的功能的简化

迭代器优缺点
**优点：**1、可以遍历无索引数据	2、节省内存(同一时间内存中只有调用时的值)
**缺点：**1、无法如索引取值一样精准定位取值	2、生命周期短(取完即销毁)
生成器（yield）
1、什么是生成器
​	生成器是自定义的迭代器，本质就是生成器
​	在函数内一旦存在yield关键字，调用函数并不会执行函数体代码，会返回一个生成器对象
2、生成器应用场景
​	将函数挂起，适用于大多数并发编程中
3、生成器案例
基础生成器案例
#!/usr/bin/env python3
# -*- coding:utf-8 -*-


def my_range(begin, end, step=1):
	print('start...')
	while begin < end:
		yield begin
		begin += step
	print('over...')


gen = my_range(1, 10)
for i in my_range(1, 10):
	print(i)



生成器用法一
通过yield挂起函数为函数内部变量传值
#!/usr/bin/env python3
# -*- coding:utf-8 -*-


# 生成器用法一： 通过yield挂起函数为函数内部变量传值
def shopping(name):
	print('{}去商场扫货啦！'.format(name))
	while True:
		good = yield
		print('{}把{}买下来啦！'.format(name, good))


fan = shopping('小范')    # 获取生成器对象
fan.send(None)      # 初始化，将函数挂起，yield开始等待接受值
fan.send('耐克球鞋')    # 传入值给yield 再通过yield赋值给good
fan.send('旺仔牛奶')    # 传入值给yield 再通过yield赋值给good


生成器用法二： 通过yield挂起函数并返回值
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

def shopping(name):
	good_list = []
	print('{}去商场扫货啦！'.format(name))
	while True:
		good = yield good_list
		print('{}把{}买下来啦！'.format(name, good))
		good_list.append(good)


fan = shopping('小范')  # 获取生成器对象
res = fan.send(None)  # 初始化，将函数挂起，yield开始等待接受值
print('现在购物车里有:{}'.format(res))
res = fan.send('耐克球鞋')  # 传入值给yield 再通过yield赋值给good 最后通过res接受yield的返回值
print('现在购物车里有:{}'.format(res))
res = fan.send('旺仔牛奶')  # 传入值给yield 再通过yield赋值给good 最后通过res接受yield的返回值
print('现在购物车里有:{}'.format(res))

本科课程参见：《软件学院那些课》

牛顿迭代公式

 

设已知方程f(x)=0的近似根x0 ,则在x0附近f(x)可用一阶泰勒多项式近似代替.因此, 方程f(x)=0可近似地表示为p(x)=0。用x1表示p(x)=0的根,它与f(x)=0的根差异不大. 

设 ,由于x1满足解得



重复这一过程,得到迭代公式：



这就是著名的牛顿迭代公式,它相应的不动点方程为



 

 

Jacobi迭代公式解线性方程组

线性方程组基本解法：



若方程组可同解变形为



Jacobi迭代法的计算公式：



即 

 

算法代码

/*简单迭代法的代码实现*/
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
double e=2.718281818284;
double f(double x){
	return pow(e,-1*x);
}
void SimpleDiedai(double x,double d){
	double a=x;
	double b=f(a);
	int k=0;//记录循环的次数
	while(((a-b)>d) || ((a-b)<-1*d)){
		cout<<a<<endl;
		a=b;
		b=f(a);
		k++;
		if(k>100){
			cout<<"迭代失败！（可能是函数不收敛）"<<endl;
			return ;
		}
	}
	cout<<b<<endl;
	return;
}
int main(){
	cout<<"请输入初始值x0和要求得结果的精度：";
	double x,d;
	cin>>x>>d;
	SimpleDiedai (x,d);
	return 0;
}

/*牛顿迭代法的代码实现*/
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
double e=2.718281818284;
double f(double x){
	double a=pow(e,-1*x);
	return x-(x-a)/(1+a);
}
void NewtonDiedai(double x,double d){
	double a=x;
	double b=f(a);
	int k=0; //记录循环的次数
	while(((a-b)>d) || ((a-b)<-1*d)){
		cout<<a<<endl;
		a=b;
		b=f(a);
		k++;
		if(k>100){
			cout<<"迭代失败！（可能是函数不收敛）"<<endl;
			return ;
		}
	}
	cout<<b<<endl;
	return;
}

int main(){
	cout<<"请输入初始值x0和要求得结果的精度：";
	double x,d;
	cin>>x>>d;
	NewtonDiedai(x,d);
	return 0;
}

/*雅可比算法的代码实现*/
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
using namespace std;	  

//函数求数组中的最大值
double MaxOfList(vector<double>x){
	double max=x[0];
	int n=x.size();
	for(int i=0;i<n;i++)
		if(x[i]>max) max=x[i];
	return max;
}

//雅可比迭代公式
void Jacobi(vector<vector<double> > A,vector<double> B,int n){
	vector<double> X(n,0);
	vector<double> Y(n,0);
	vector<double> D(n,0);
	int k=0; //记录循环次数
	do{	
		X=Y;
		for(int i=0;i<n;i++){
			double tem=0;
			for(int j=0;j<n;j++){
				if(i!=j) tem += A[i][j]*X[j];
			}
			Y[i]=(B[i]-tem)/A[i][i];
			cout<<left<<setw(8)<<Y[i]<<" ";
		}
		cout<<endl;
		k++;
		if(k>100){
			cout<<"迭代失败！（可能是函数不收敛）"<<endl;
			return ;
		}
		
		for(int a=0;a<n;a++){
			D[a]=X[a]-Y[a];
		}
	}while( MaxOfList(D)>0.00001 || MaxOfList(D)<-0.00001);
	
	return ;
}

int main(){

	int n;
	cout<<"请输入方程组未知数的个数n：";
	cin>>n;
	cout<<endl;

	vector<vector<double> >A(n,vector<double>(n,0));
	vector<double>B(n,0);
	
	cout<<"请输入方程组的系数矩阵："<<endl;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>A[i][j];
		}
	}
	cout<<endl;
	
	cout<<"请输入方程组的值向量："<<endl;
	for(int k=0;k<n;k++){
		cin>>B[k];
	}
	cout<<endl;
	
	cout<<"您输入的方程组为："<<endl;
	for(int a=0;a<n;a++){
		for(int b=0;b<n;b++){
			cout<<A[a][b]<<" ";
		}
		cout<<"    "<<B[a]<<endl;
	}
	cout<<endl;
	cout<<"由雅可比迭代公式求的方程组的解为："<<endl;
    Jacobi(A,B,n);
	return 0;
}


 

实验过程原始记录

（1）分别用简单迭代法和牛顿迭代法求方程在x=0.5附近的一个根x*，要求精度为0.00001

（输入0.5 0.000001）简单迭代法得到结果：



（输入0.5 0.000001）牛顿迭代法得到结果：

X0=0.5  x1=0.566311 x2=0.567143

 

（2）用雅可比迭代法求解方程组  



运行程序，根据提示输入 （3） （10 -1 -2 -1 10 -2 -1 -2 5）    （7.2  8.3  4.2）



 

 

实验结果及分析

1、迭代法是一种逐次逼近法，这种方法使用某个固定公式－所谓迭代公式反复校正根的近似值，使之逐步精确化，直至满足精度要求的结果。迭代法是一种求解函数方程f（x）=0的解的方法，他解决了二分法无法求解复根级偶重根的问题，而其提高了收敛速度。迭代的思想是计算方法中基础的求解问题的思想。

2、简单迭代法的求根过程分成两步，第一步先提供根的某个猜测值，即所谓迭代初值，然后将迭代初值逐步加工成满足精度要求的根。迭代法的设计思想是：f (x) = 0等价变换成 然后由迭代公式 逐步球的满足精度的解。实际迭代中不同迭代函数的求解可能影响求的精确解的运算量，甚至可能因为函数发散而无法求解。解题时可通过对导函数的判断而判断函数是否发散，而编写代码时可以通过判断循环次数——即循环过多次而不能从循环中出来时就判断为死循环，无法求得正解

3、简单迭代法往往只是线性收敛，为得出超线性收敛的迭代格式，通常采用近似替代法， 即牛顿公式。迭代函数为  - / 牛顿法是一种逐步线性化方法。由实验结果可以看到，虽然选取近似公式，但牛顿迭代法仍能得到精度很高的解，而且牛顿迭代法大大提高了收敛速度。

4、由迭代法求解线性方程组的基本思想是将联立方程组的求解归结为重复计算一组彼此独立的线性表达式，这就使问题得到了简化，类似简单迭代法转换方程组中每个方程式可得到雅可比迭代式



迭代法求解方程组有一定的局限性，例如要求方程组的系数矩阵具有某种特殊性质，以保证迭代过程的收敛性，但迭代法同时有十分明显的优点——算法简单，因而编制程序比较容易，所以在实际求解问题中仍有非常大利用价值。

 

（转载请注明作者和出处：http://blog.csdn.net/xiaowei_cqu 未经允许请勿用于商业用途）

 

之前我在博客里介绍过牛顿-拉弗逊迭代法，对数据挖掘技术熟悉的同学应该还知道有梯度下降法（其实也是一种迭代算法）。今天刚好有朋友和我讨论泊松图像融合算法，我说我过去文章里给出的是最原始、最直观的实现算法。对于理解泊松融合的原理比较有帮助，但是效率可能并不理想。印象中，泊松融合是有一个以矩阵为基础的快速算法的。但是过去我浅尝辄止了，也没深究，今天刚好再提到，小看了一下，似乎涉及高斯-塞德尔迭代法。好吧，博主君暂且把知道的这部分内容做个介绍吧。

一、雅各比迭代法


考虑如下方程组：

$4x-y+z=7\\4x-8y+z=-21\\-2x+y+5z=15$

上述方程可表示成如下形式：

$x=\frac{7+y-z}{4} \\y=\frac{21+4x+z}{8}\\z=\frac{15+2x-y}{5}$

这样就提出了下列雅可比迭代过程：
$\begin{aligned}
x_{k+1} & =\frac{7+y_k-z_k}{4}  \\
y_{k+1} & =\frac{21+4x_k+z_k}{8} & (3) \\
z_{k+1} & =\frac{15+2x_k-y_k}{5}  
\end{aligned}$
如果从$P_0=(x_0,y_0,z_0)=(1,2,2)$开始，则上式中的迭代将收敛到解$(2,4,3)$。
将$x_0=1,y_0=2$和$z_0=2$代入上式中每个方程的右边，即可得到如下新值：

$x_1=\frac{7+2-2}{4}=1.75\\y_1=\frac{21+4+2}{8}=3.375\\z_1=\frac{15+2-2}{5}=3.00$
新的点$P_1=(1.75,3.375,3.00)$比$P_1$更接近$(2,4,3)$。使用迭代过程（3）生成点的序列{$P_0$}将收敛到解$(2,4,3)$。

这个过程称为雅可比迭代，可用来求解某些类型的线性方程组。从上表中可以看出，经过19步选代，选代过程收敛到一个精度为9 位有效数字的近似值（2.00000000， 4.00000000， 3.00000000）。但有时雅可比迭代法是无效的。通过下面的例子可以看出，重新排列初始线性方程组后，应用雅可比迭代法可能会产生一个发散的点的序列。
设重新排列的线性方程组如下：

$-2x+y+5z=15\\4x-8y+z=-21\\4x-y+z=7$
这些方程可以表示为如下形式：

$x=\frac{-15+y-5z}{2} \\y=\frac{21+4x+z}{8}\\z=\frac{7-4x+y}{5}$
这可以用如下雅可比迭代过程求解：

\begin{aligned}

x_{k+1} & =\frac{-15+y_k+5z_k}{2}  \

y_{k+1} & =\frac{21+4x_k+z_k}{8}  \

z_{k+1} & =7-4x_k+y_k

\end{aligned}
如果从$P_0=(x_0,y_0,z_0)=(1,2,2)$开始，则上式中的迭代将对解$(2,4,3)$发散。将$x_0=1$，$y_0=2$和$z_0=2$带入上式中每个方程的右边，即可得到新值$x_1$，$y_1$和$z_1$：
$x_1=\frac{-15+2+10}{2}=-1.5\\y_1=\frac{21+4+2}{8}=3.375\\z_1=7-4+2=5.00$
新的点$P_1=(-1.5,3.375,5.00)$比$P_0$更远地偏离$(2,4,3)$。使用上述迭代过程生成点的序列是发散的。


二、高斯-塞德尔迭代法


有时候通过其他方面可以加快迭代的收敛速度。观察由雅可比迭代过程（3）产生的三个序列{$x_k$}，{$y_k$}和{$z_k$}，它们分别收敛到2，4和3。由于$x_k+1$被认为是比$x_k$更好的$x$之近似值，所以在计算$y_k+1$时用$x_k+1$来替换$x_k$是合理的。同理，可用$x_k+1$和$y_k+1$计算$z_k+1$。下面的例子演示了对上述例子中给出的方程组使用上述方法的情况。
设给定上述线性方程组并利用高斯-塞德尔（Gauss-Seidel）迭代过程求解：
$x_{k+1}=\frac{7+y_k-z_k}{4}\\
y_{k+1}=\frac{21+4x_{k+1}+z_k}{8}\\
z_{k+1}=\frac{15+2x_{k+1}-y_{k+1}}{5}$
如果从$P_0=(x_0,y_0,z_0)=(1,2,2)$开始，用上式中的迭代可收敛到解$(2,4,3)$。

将$y_0=2$和$z_0=2$代入上式第一个方程可得
$x_1=\frac{7+2-2}{4}=1.75$
将$x_1=1.75$和$z_0=2$代入第二个方程可得
$y_1=\frac{21+4\times1.75+2}{8}=3.75$
将$x_1=1.75$和$y_1=3.75$代入第三个方程可得
$z_1=\frac{15+2\times1.75-3.75}{5}=2.95$
新的点$P_1=(1.75,3.75,2.95)$比$P_0$更接近解$(2,4,3)$，而且比之前例子中的值更好。用迭

代（7）生成序列{$P_k$收敛到$(2,4,3)$。

正如前面讨论的，应用雅各比迭代法计算有时可能是发散的。所以有必要建立一些判定条件来判断雅可比迭代是否收敛。在给出这个条件之前，先来看看严格对角占优矩阵的定义。

设有$N$$\times$$N$维矩阵$A$，如果


其中，$i$是行号，$j$是列号，则称该矩阵是严格对角占优矩阵。显然，严格对角占优的意思就是指对角线上元素的绝对值不小于所在行其他元素的绝对值和。
\begin{aligned}

a_{11}x_1+a_{12}x_2+…+a_{1j}x_j+…+a_{1N}x_N& =b_1  \

a_{21}x_1+a_{22}x_2+…+a_{2j}x_j+…+a_{2N}x_N& =b_2 \

…   …   \

a_{j1}x_1+a_{j2}x_2+…+a_{jj}x_j+…+a_{jN}x_N& =b_j \

…  …  \

a_{N1}x_1+a_{N2}x_2+…+a_{Nj}x_j+…+a_{NN}x_N& =b_N

\end{aligned}
设第k点为$P_k=(x_1^{(k)},x_2^{(k)},...,x_j^{(k)},...,x_N^{(k)},)$，则下一点为$P_{k+1}=(x_1^{(k+1)},x_2^{(k+1)},...,x_j^{(k+1)},...,x_N^{(k+1)},)$。向量$P_k$的上标$(k)$可用来标识属于这一点的坐标。迭代公式根据前面的值$(x_1^{(k)},x_2^{(k)},...,x_j^{(k)},...,x_N^{(k)},)$，使用上述线性方程组中第$j$行求解$x_j^{(k+1)}$。
雅可比迭代：
$x_j^{(k+1)}=\frac{b_j-a_{j1}x_1^{(k)}-...-a_{jj-1}x_{j-1}^{(k)}-a_{jj+1}x_{j+1}^{(k)}-...-a_{jN}x_N^{(k)}}{a_{jj}}$
其中$j=1,2,...,N$。

雅可比迭代使用所有旧坐标来生成所有新坐标，而高斯-塞德尔迭代尽可能使用新坐标得到更新的坐标。
高斯-塞德尔迭代：
$x_j^{(k+1)}=\frac{b_j-a_{j1}x_1^{(k+1)}-...-a_{jj-1}x_{j-1}^{(k+1)}-a_{jj+1}x_{j+1}^{(k)}-...-a_{jN}x_N^{(k)}}{a_{jj}}$
其中$j=1,2,...,N$。
下面的定理给出了雅可比迭代收敛的充分条件。

（雅可比选代） 设矩阵$A$具有严格对角优势，则$AX=B$有惟一解$X = P$。利用前面给出的迭代式可产生一个向量序列{$P_k$}，而且对于任意初始向量$P_0$，向量序列都将收敛到$P$。
当矩阵$A$具有严格对角优势时，可证明高斯-塞德尔迭代法也会收敛。在大多数情况下，高斯-塞德尔迭代法比雅可比迭代法收敛得更快，因此通常会利用高斯-塞德尔迭代法。但在某些情况下，雅可比迭代会收敛，而高斯-塞德尔迭代不会收敛。
特别说明：以上内容主要取材自《数值方法（MATLAB版）（第四版）》马修斯等著，电子工业出版社2010年出版发行。