`
128kj
  • 浏览: 600295 次
  • 来自: ...
社区版块
存档分类
最新评论

迭代算法

阅读更多
利用迭代算法解决问题,需要做好以下三个方面的工作:
  一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。
  二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方

法来完成。
  三、对迭代过程进行控制。在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。


示例1:斐波那契数列的非递归实现:
斐波那契数列是从第0项和第1项开始,之后的项等于其前面相邻两项之和。
F(n)=F(n-1)+F(n-2),F(0)=0,F(1)=1。

int Fibs(int n) {   
   if(n < 0) {   
    throw new IllegalArgumentException(" the parameter is valid!");   
    }   
    int n1 = 0;//F(n-2),迭代变量
    int n2 = 1;//F(n-1),迭代变量
    int r = n1;//F(n)   
    if(n == 1) {   
        r = n2;   
    }   
    for (int i = 2; i <= n; i++) {   //用循环控制迭代过程
       //迭代关系式
        r = n1 + n2 ;//F(n)=F(n-1)+F(n-2)   
        n1 = n2;   
        n2 = r;   
    }   
    return r;   
}  


示例2:牛顿迭代法求平方根(Newton's Method)。 
  
/**  
* 求平方根  
* @param d 待开方数  
* @param precision 算术平方根的精度  
* @return  
*/  
double sqrt(double d,double precision) {   
    double x1 = d/2, x2 =(x1 + d/x1)/2;   
    while(Math.abs(x2 -x1)>precision) {   
        x1 = x2;   
        x2 =(x1 + d/x1)/2;   
    }   
    return x1;   
}  

示例3:辗转相除法求最大公约数
long gcd(long x,long y) {   
    if(x < y) {   
        long m = x;   
        x = y;//x存储较大的一个数   
        y = m;   
    }   
    long k = 0;   
    while(y != 0) {   
        k = x%y;   
        x = y;   
        y = k;   
    }   
    return  x;   
}  


示例4:迭代法解方程
  迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行:
  (1) 选一个方程的近似根,赋给变量x0;
  (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;
  (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。
  若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。

【算法】迭代法求方程的根
{  
  x0=初始近似根; 
  do { 
    x1=x0; 
    x0=g(x1);   /*按特定的方程计算新的近似根*/ 
    } while ( Math.abs(x0-x1)>精度); 
  System.out.printf(“方程的近似根是%f\n”,x0); 
} 
例1:解方程:x*x*x-x-1=0

public class Test2{
 
  public static double f(double x){
   double y;
   y=x*x*x-x-1;   //计算
   return(y);
 }
  public static void main(String args[]){
   double x0=1.5,x1=1.5;
   do{
    x1=x0;
    x0=Math.pow((1+x1),1/3.0);
   }while(Math.abs(x0-x1)>1e-7);
   System.out.println(f(x0));
   System.out.printf("方程的近似根是%f\n",x0); 
   }
}


示例5:使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根
f(x)=f(x0)+f'(x0)*(x-x0)+…
若上面方程有根x,使得f(x)=0,取前两项得x=x0-f(x0)/f'(x0)
迭代关系式:

例:求方程f(x) = cos(x)-x^3的根.
f'(x) =-sin(x)-3x^2
方程的根位于0和1之间,x0=0.5
import static java.lang.Math.*;
public class Test1{
 
  public static double f(double x){
   double y;
   y=x-(cos(x)-pow(x,3))/(-sin(x)-3*pow(x,2));   //计算
   return(y);
 }
  public static void main(String args[]){
   double x0=0.5;
   double x1=x0;
   do{
    x1=x0;
    x0=f(x1);
   }while(Math.abs(x0-x1)>1e-7);
    
   System.out.printf("方程的近似根是%f\n",x0); 
   System.out.printf("cos(x)-x^3="+(cos(x0)-pow(x0,3)));
   }
}
  • 大小: 2.1 KB
分享到:
评论

相关推荐

    Jacobi迭代算法_jacobi迭代_Jacobi迭代法_SOR迭代法_Gauss-Seidel迭代法_迭代法_

    在本主题中,我们将详细探讨Jacobi迭代法、Gauss-Seidel迭代法以及SOR(Successive Over-Relaxation)迭代法这三种常见的迭代算法,并结合MATLAB语言进行实现。 1. Jacobi迭代法: Jacobi迭代法是由德国数学家Carl...

    迭代算法_迭代法——Matlab中实现_

    迭代算法在计算机科学和数学中占据着核心地位,特别是在数值分析和优化问题中。迭代法是一种通过反复应用某个过程来逼近解的方法,通常用于解决非线性方程组或优化问题。在Matlab中,迭代算法可以方便地实现,因为其...

    计算方法导引_牛顿迭代法_雅可比迭代算法_

    牛顿迭代法和雅可比迭代算法是其中两种常用的数值求解方法,尤其在处理方程求根和线性系统求解的问题上。 首先,让我们深入理解牛顿迭代法。这是一种用于找到函数零点的迭代方法,由英国数学家艾萨克·牛顿提出。该...

    数值迭代算法及其Matlab实例

    数值迭代算法是解决数学方程组或非线性问题的一种常用方法,特别是在计算机科学和工程领域。这种方法通过一系列近似步骤逐步逼近问题的精确解。在本教程中,我们将深入探讨数值迭代的基本概念,以及如何在强大的编程...

    倒数的迭代算法

    倒数迭代算法是一种用于快速计算一个数的倒数的方法,适用于计算机硬件中的除法运算。假设需要计算一个正值\( x &gt; 0 \)的倒数\( \frac{1}{x} \),可以通过迭代的方式逐步逼近这个值。 - **初始近似值的选择**:选择...

    Jacobi迭代算法的Python实现详解

    ### Jacobi迭代算法的Python实现详解 #### 一、引言 在数值分析与线性代数领域,求解线性方程组是常见的任务之一。对于大型稀疏矩阵而言,迭代方法通常比直接求解法更为高效。其中,Jacobi迭代法是一种简单且有效的...

    MATLAB SOR迭代法求解方程

    Young于20世纪70年代提出逐次超松弛(Successive Over Relaxation)迭代法,简称SOR方法,是一种经典的迭代算法。它是为了解决大规模系统的线性等式提出来的,在GS法基础上为提高收敛速度,采用加权平均而得到的新...

    迭代法-穿越沙漠问题 迭代法-穿越沙漠问题

    在给定的“迭代法-穿越沙漠问题”中,我们可以理解这是一个基于迭代算法的编程挑战,可能是为了模拟或解决某种涉及到多步骤决策的问题,比如在资源有限的情况下找到穿越沙漠的最短路径。 迭代法的基本思想是通过...

    MATLAB迭代法收敛判断

    在数值分析领域,迭代法是一种求解线性方程组的有效方法。在MATLAB中,我们可以利用编程实现这些算法,以便于理解...在实际编程中,我们不仅需要实现迭代算法,还需要设计合适的收敛判断机制,以确保计算的效率和精度。

    matlab迭代法自动阈值分割算法

    常见的迭代算法有Otsu's方法、Kittler-Illingworth方法等。这些方法通常从一个初始阈值出发,计算当前阈值下的图像分割效果,然后根据某种准则(如方差最大化、熵最大化等)更新阈值,直到满足停止条件为止。 在...

    Newton迭代法浅析.doc

    Newton迭代法是一种广泛应用于数值分析和优化问题的迭代算法。下面是对Newton迭代法的浅析: 第一章 绪 论 Newton迭代法是一种基于泰勒展开式的迭代算法,用于寻找非线性方程的解。该算法于17世纪由英国数学家...

    [转载]迭代算法 1.0

    1. 数值计算:如解微分方程、积分计算等,通常采用迭代法求解近似解。 2. 机器学习:在训练神经网络时,梯度下降法是常用的优化算法,通过迭代更新权重和偏置来最小化损失函数。 3. 图论问题:如最短路径问题...

    汉诺塔层次迭代算法和分析

    ### 汉诺塔问题迭代算法与分析 #### 引言 汉诺塔问题是一个经典的计算机科学问题,通常被用来教授递归的概念。长久以来,人们普遍认为递归是解决汉诺塔问题的最佳方法。然而,近年来研究者们发现迭代算法也可以...

    高斯赛德尔迭代算法 C语言

    高斯赛德尔迭代算法 C语言实现 高斯赛德尔迭代算法是一种常用的迭代方法,用于解决线性方程组的问题。该算法具有程序简单、存储量小的优点,特别适用于求解系数矩阵为大型稀疏矩阵的方程组。 高斯赛德尔迭代算法的...

    MATLAB实现Jacobi 迭代法,Gauss-Seidel 迭代法,逐次超松弛迭代法,共轭梯度法

    求解线性⽅方程组 Ax=b,其中 A 为 ...比较 Jacobi 迭代法、Gauss-Seidel 迭代法、逐次超松弛迭代法、 共轭梯度法与高斯消去法、列主元消去法的计算时间。改变逐次超松弛迭代法的松弛因⼦, 分析其对收敛速度的影响。

    交直流配电网潮流计算matlab程序统一求解法和交替迭代法

    交直流配电网潮流计算matlab程序统一求解法和交替迭代法 本文主要介绍了交直流配电网潮流计算的matlab程序实现,涵盖了统一求解法和交替迭代法两种方法。通过对给定的算法和程序进行分析,我们可以了解到交直流配电...

    不动点迭代法_迭代法_不动点迭代法_

    MATLAB是一种强大的数值计算和可视化工具,它提供了丰富的内置函数和脚本环境,非常适合于实现各种迭代算法。在MATLAB中实现不动点迭代法,我们需要定义迭代函数,初始化迭代起点,并设定停止条件,如达到一定的精度...

    QR迭代法求矩阵特征值1

    QR迭代法是一种高效计算矩阵特征值的数值方法,尤其适用于大型稀疏矩阵。该方法基于矩阵的QR分解和正交变换,能够逐步将矩阵转化为更简单的形式,从而求得其特征值。以下是QR迭代法求解矩阵A特征值的详细步骤和相关...

    迭代法计算信道容量的matlab实现

    迭代法计算信道容量的matlab实现。取初始分布为均匀分布。IU和IL是迭代的两个边界值。

    解线性方程组的迭代法_Matlab解线性方程组的迭代法_JOR迭代_JOR迭代法_processegz_

    解线性方程组的迭代法汇总:rs里查森迭代法求线性方程组Ax=b的解crs里查森参数迭代法求线性方程组Ax=b的解grs里查森迭代法求线性方程组Ax=b的解jacobi雅可比迭代法求线性方程组Ax=b的解gauseidel高斯-赛德尔迭代法求...

Global site tag (gtag.js) - Google Analytics