数值计算方法 第3章-简单迭代法

f ( x)
连续，对
2 简单迭代法及其收敛性
迭代法是数值计算中一类典型方法，不仅用
于方程求根，而且用于方程组求解，矩阵求特征 值。 迭代法的基本思想是一种逐次逼近的方法， 首先给定一个粗糙的初值，然后用同一个迭代公
式，反复校正这个初值，直到满足预先给出的精
度要求。
下面的各种求根方法，实质上就是如何构造
lim xk x 故有 k
（3）设 m>k，则有 xm xk ( xi 1 xi )
i k
使 x1 g ( x1 ) ， x2 g ( x2 )
则由微分中值定理和定理条件有
( ) x1 x2 x x g(x ) g(x ) g 1 2 1 2 L x1 x2 x1 x2
x1 与 x2 之间。 其中ξ 在 上式出现的矛盾说明 x1 x2
可以看出，迭代序列收敛。 当 k 越来越大时， xk 接近方程的近似根
3 （2） x x3 1 ，这时 g ( x) x 1
x* 1.32472
。
仍取初值 x0 1.5 ，得迭代公式 xk 1 xk 1
3
k 1, 2,3
x1 2.375 x2 12.3965 x3 1904.01 x4 6.90252 109
迭代序列发散。
按这一迭代公式计算下去，当 k 变大时， xk 远离的 f ( x) 0 精确根。
用迭代法求方程近似根的基本问题 就是 g ( x)如何构造才能使迭代序列 {xk } 收敛。 迭代法的几何意义 求方程（2）的根，实质上就是求直线 y x 与曲线 y g ( x) 的交点 P 的横坐标 x* ，如图。 从图可以看出： （1）如果迭代公式 xk 1 g ( xk ) 收敛，则迭代函数 y g ( x) 曲线走势平坦，即 g ' ( x ) 1 （2）如果迭代公式 xk 1 g ( xk ) 发散，则迭代函数 y g ( x)曲线走势陡峭，即 g ' ( x) 1

简单迭代法求解线性方程组1．原理：将原线性方程组Ax=b中系数矩阵的主对角线移到一边并将其系数化为一，然后在给定迭代初值的情况下通过迭代的方法求解线性方程组的值。

2．C语言实现方式：(1)计算迭代矩阵：将系数矩阵的所有值分别处以各自所在行的主对角线值，然后将主对角线赋值为0。

(2)输入迭代初值，进行迭代将迭代初值存入y[n]矩阵，然后利用迭代式nn=nn+x[i][j]*y[j];y[i]=nn+b[i];经过有限次迭代得到误差要求以内的值3．源程序如下：#include<iostream>#include<math.h>#include<iomanip>using namespace std;#define kk 50 //定义最大方程元数int n,i,c,j,hh,gg,mm;double A[kk][kk],x[kk][kk],b[kk],y[kk],a[kk],z[kk],m,nn,d,e=1,w,fff ;void main(){cout<<"输入的方程元数"<<endl; //数据的输入cin>>n;cout<<"请输入方程系数矩阵:"<<endl;for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>A[i][j];cout<<"请输入右边向量:"<<endl;for(i=0;i<n;i++)cin>>b[i];cout<<"输入你想要的迭代精度(建议1e-5以上)！"<<endl; cin>>fff;cout<<"输入最大迭代次数（建议300次以上）！"<<endl; cin>>mm;//计算出迭代矩阵for(i=0;i<n;i++){b[i]=b[i]/A[i][i];for(j=0;j<n;j++){if(i==j){x[i][i]=0;}else{x[i][j]=-A[i][j]/A[i][i];}}}//输出迭代矩阵cout<<"计算出迭代矩阵为："<<endl;for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<x[i][j]<<" ";cout<<b[i]<<" ";cout<<endl;}//赋迭代初值cout<<"输入迭代初值"<<endl;for(i=0;i<n;i++)cin>>y[i];int f=1;//简单迭代法cout<<" ";for(i=1;i<n+1;i++)cout<<'\t'<<"X["<<i<<"]"<<" "<<'\t';cout<<"精度";cout<<endl;cout<<"迭代初值为： ";cout<<setiosflags(ios::fixed);for(i=0;i<n;i++)cout<<y[i]<<" ";cout<<endl;while(e>fff){for(i=0;i<n;i++){z[i]=y[i];nn=0;for(j=0;j<n;j++){nn=nn+x[i][j]*y[j];y[i]=nn+b[i];}e=fabs(z[0]-y[0]);if(fabs(z[i]-y[i])>e)e=fabs(z[i]-y[i]);if(i==0){cout<<setiosflags(ios::fixed);cout<<"第"<<setw(3)<<setprecision(3)<<f++<<"次迭代"<<" "; }cout<<setiosflags(ios::fixed);cout<<setw(8)<<setprecision(8)<<y[i]<<" ";}cout<<e;cout<<endl;if(f>mm){cout<<"迭代次数大于"<<mm<<"次"<<endl;cout<<"认为方程发散，迭代不收敛"<<endl;exit(1);}}cout<<endl;cout<<endl;cout<<"方程迭代了"<<f-1<<"次,达到你所要求的精度"<<fff<<endl;cout<<"最后结果为："<<endl;cout<<endl;for(i=0;i<n;i++){cout<<"X"<<"["<<i+1<<"]"<<"="<<y[i];cout<<endl;}exit(1);}4．实验数据和结果：按照提示依次输入方程元数，系数矩阵，右边向量和迭代初值。

x*
lim
k
x
k
1
lim
k
(
xk
)
(lim k
xk
)
( x* )
故k充分大时，xk可作为方程根的近似值
按上述方法构造迭代格式来求解方程的方法称为简单迭代法或逐
次迭代法。
不动点迭代法： 将方程 f ( x) 0 改写为: x ( x).
1 若要求x*满足f ( x* ) 0,则x* ( x* );反之亦然，
重点
实多项式方程
f ( x) a0 x n a1 x n1 an1 x an (a0 0),
的求根问题.
（其中系数ai (i 0,1,, n)为实数）
若 方程f ( x*) 0, 则x*称为函数f ( x)的零点
1
若方程 f (x) (x x* )m g(x),
其 中m为 正 整 数 ， 且g( x* ) 0.
真真解解：：xx==1.13.234274272
典型例题
例3
用不同方法求方程x2 3 0的根x* 3.
(1) xk1 xk2 xk 3,(x) x2 x 3
(2)
xk 1
3 xk
,(x)
3, x
(3)
xk 1
xk
1 4
( xk2
3), ( x)
x
1 4
(x2
3)
(4)
xk 1
1 2
典型例题
(2)
xk1
3 xk
,(x)
3, x
( x* ) 1
(3)
xk 1
xk
1 4
(
x
2 k
3),( x)
x
1 (x2 4

• 本章介绍方程的迭代解法，它既可以用来求解 代数方程，也可以用来解超越方程，并且仅限 于求方程的实根。
• 运用迭代法求解方程的根应解决以下两个问题：
• 确定根的初值; • 将进一步精确化到所需要的精度。
记笔记 第3页/共52页
7.1 二分法
二分法又称二分区间法,是求解非线性方程的近 似根的一种常用的简单方法。
第4页/共52页
确定有根区间的方法
• 为了确定根的初值，首先必须圈定根所在的范围，
称为圈定根或根的隔离。
• 在上述基础上，采取适当的数值方法确定具有一 定
精度要求的初值。
• 对于代数方程，其根的个数（实或复的）与其次 数
相同。至于超越方程，其根可能是一个、几个或
无
第5页/共52页
由高等数学知识知, 设f (x)为区间[a,b]上的 单值连续, 如果f (a)·f (b)<0 , 则[a,b]中至少 有一个实根。如果f (x)在[a,b]上还是单调地递 增或递减，则仅有一个实根。
二分法求根过程
设方程f(x)=0在区间[a,b]内有根,二分法就是逐 步收缩有根区间，最后得出所求的根。具体过程如下
① 取有根区间[a,b]之中点, 将它分为两半,分点
x0
ab 2
,这样就可缩小有根区间
y
y=f(x)
y=f(x)
a
x1
x* x0
a1
b1
a2
b2
b
a
第13页/共52页
x*
x0
x1
b
a1
再将 x1 代入式 x (x) 的右端, 得到 x2 (x1) , 依此类推, 得到一个数列 x3 (x2 ) …， 其一般表示