计算方法-迭代法讲义

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

设方程为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）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。

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:max1P(k) = feval('f1021', P(k-1));k, err = abs(P(k) - P(k-1))p = P(k);if(err<tol),break;endif k == max1disp('maximum number of iterations exceeded');endendP=P;****************************************************************************例2.1 用上述程序求方程0sin 2=-x x 的一个近似解，给定初始值5.00=x ，误差界为510-。

常用算法——迭代法迭代法是一种常见的算法设计方法，它通过重复执行一定的操作来逐步逼近问题的解。

迭代法是一种简单有效的求解问题的方法，常用于求解数值问题、优化问题以及函数逼近等领域。

本文将介绍迭代法的基本概念、原理以及常见的应用场景。

一、迭代法的基本概念迭代法的思想是通过反复应用一些函数或算子来逐步逼近问题的解。

对于一个需要求解的问题，我们首先选择一个初始解或者近似解，然后通过不断迭代更新来逼近真实解。

迭代法的核心是找到一个递推关系，使得每次迭代可以使问题的解越来越接近真实解。

常见的迭代法有不动点迭代法、牛顿迭代法、梯度下降法等。

这些方法的求解过程都是基于迭代的思想，通过不断逼近解的过程来得到问题的解。

二、迭代法的原理迭代法的基本原理是通过不断迭代求解迭代方程的解，从而逼近问题的解。

迭代法的求解过程通常分为以下几个步骤：1.选择适当的初始解或者近似解。

初始解的选择对迭代法的收敛性和效率都有影响，一般需要根据问题的特点进行合理选择。

2.构建递推关系。

通过分析问题的特点，构建递推关系式来更新解的值。

递推关系的构建是迭代法求解问题的核心，它决定了每次迭代如何更新解的值。

3.根据递推关系进行迭代。

根据递推关系式，依次更新解的值，直到满足收敛条件为止。

收敛条件可以是解的变化小于一定阈值，或者达到一定的迭代次数。

4.得到逼近解。

当迭代停止时，得到的解即为问题的逼近解。

通常需要根据实际问题的需求来判断迭代停止的条件。

三、迭代法的应用迭代法在数值计算、优化问题以及函数逼近等领域有广泛的应用。

下面将介绍迭代法在常见问题中的应用场景。

1.数值计算：迭代法可以用于求解方程的根、解线性方程组、求解矩阵的特征值等数值计算问题。

这些问题的解通常是通过迭代的方式逼近得到的。

2.优化问题：迭代法可以应用于各种优化问题的求解，如最大值最小化、参数估计、模式识别等。

迭代法可以通过不断调整参数的值来逼近问题的最优解。

3.函数逼近：迭代法可以应用于函数逼近问题，通过不断迭代来逼近一个函数的近似解。

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

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

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

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

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

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

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

二、建立迭代关系式。

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

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

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

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

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

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

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

例 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.分析：程序采用逐位分离的方法。