迭代

迭代法的基本思想

迭代法（Iterative Method），也称辗转法

• 通过迭代函数（迭代关系式、迭代公式）
• 由迭代变量旧值（前一个值）推出新值（下一个值），在不断用新值取代旧值
• 反复校正迭代变量的值
• 通过反复迭代，缠身一个数列： $x_0,x_1,x_2,x_n$,直到逐步逼近问题的解

$$x_{n+1} = g(x_n)$$

迭代法的基本步骤

1. 确定迭代变量

   在可用迭代法求解的问题中，应至少存在一个可直接或间接地不断由旧值推出新值的变量——迭代变量

2. 建立迭代函数

   解决迭代问题的关键

3. 确定迭代结束条件（收敛判据）

   1. 所需的迭代次数是已知的确定的值——计数控制循环
   2. 所需的迭代次数无法确定——条件控制的循环

精确迭代

通过迭代能过得到精确解

• 计算两个正整数的商和余数
  • 商和余数的关系： $x = q * y + r$
  • 迭代变量：r
  • 迭代关系式：$r = r - y$
  • 迭代结束条件：$r < y$

st1=>start: 开始
in=>inputoutput: 输入x和y
op1=>operation: q = 0, r = x
cond1=>condition: r >= y 
op2=>operation: r = r - y
op3=>operation: q = q + 1
out=>inputoutput: 输出q和r
en=>end: 结束
st1->in->op1->cond1
cond1(yes)->op2->op3(left)->cond1
cond1(no)->out->en

近似迭代

近似迭代

• 从一个初始估值出发迭代产生一些列离解越来越近的近似解
  • $$x_{n+1} = g(x_n) $$ $$x_0,x_1,x_2...,x_n$$
• 近似求解非线性方程的根
  • 利用求根公式——直接求解方程的精确解
  • 但非线性方程很难直接求解得到精确的数值解，往往只要求得到满足一定精度要求的近似解
• 直接迭代法就是最简单的迭代法——简单迭代法

直接迭代法

直接迭代法求方程$f(x) = 0$的根的基本思路

• 确定迭代变量：x
• 建立迭代函数：$x = g(x)$
  • $$f(x) = 0 $$ －＞ $$x = g(x)$$
  • 求$f(x)$ 的根－＞求$x = g(x)$的根

牛顿迭代法

直接迭代法

• 迭代函数可从方程直接导出,迭代函数的构造有多种方法
• 并非所有的都能使迭代收敛

牛顿迭代法

• 牛顿在17世纪提出的一种在实数域和复数域上近似求解非线性方程的方法

• 实质:以直代曲

• 优点:

  • 收敛很快,在单根附近二阶收敛,在重根附近线性收敛
  • 可求复根

• 缺点

  • 对重根收敛较慢
  • 要求函数的一阶导数存在,并且不能为0