版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://ligang.blog.csdn.net/article/details/83348765
迭代法(Iteration)是一种不断用变量的旧值递推出新值的解决问题的方法。迭代算法是用计算机解决问题的一种基本方法,一般用于数值计算。累加、累乘都是迭代算法的基础应用。典型案例:牛顿迭代法”。
步骤:
经典案例:
示例: 斐波那契数列:1、1、2、3、5、8、13、21、34
function fibonacci(n) {
let a = 1, b = 1, c = 1
for(let i = 2; i <= n; i++) {
c = a + b
a = b
b = c
}
return c
}
对于斐波那契数列,当n趋于无穷时,数列最后的两项的商 (xn-1/xn) 趋于黄金分割数0.618
示例: 最大公约数,采用辗转相除法(欧几里得算法)
定理:两个整数的最大公约数等于其中较小的那个数,和两数相除余数的最大公约数。
gcd(a, b) = gcd(a, a mod b)
function gcd (a, b) {
if (a < b) {
[a, b] = [b, a]
}
let temp
while (b > 0) {
temp = a % b
a = b
b = temp
}
return a
}
示例: 牛顿迭代法
一种在实数域和复数域上近似求解方程的方法,其比一般的迭代法有更高的收敛速度。
首先,选择一个接近函数 f(x) 零点的点,如图为 $ (x_n, f(x_n)) $ ,计算相应的切线斜率 $ {f^{’}(x_n)} $ ,$ k = tan\alpha = \frac{y_2 - y_1}{x_2 - x_1}$ 得到如下方式 y=f(xn)+f′(xn)(xn+1−xn) y = f(x_n) + f'(x_n)(x_{n+1} - x_n) y=f(xn)+f′(xn)(xn+1−xn) 和 x 轴的交点坐标,也就是下面方式的解: f(xn)+f′(xn)(xn+1−xn)=0 f(x_n) + f'(x_n)(x_{n+1} - x_n) = 0 f(xn)+f′(xn)(xn+1−xn)=0 通常 xn+1x_{n+1}xn+1 会比 xnx_nxn 更接近方程的解,接下来继续迭代,直到达到要求的精度即可。
xn+1=xn−f(xn)f′(xn) \mathbb{x_{n+1} = x_n - \frac{f(x_n)}{f^{'}(x_n)}} xn+1=xn−f′(xn)f(xn) 例: 求 ax3+bx2+cx+d=0ax^3 + bx^2 + cx + d = 0ax3+bx2+cx+d=0 方程的根,系数分别是1,2,3,4。求x在1附件的一个实根。
function f(a, b, c, d) {
let x0, x1 = 1, f0, f1
do {
x0 = x1
f0 = a * Math.pow(x0, 3) + b * Math.pow(x0, 2) + c * x0 + d
// 求导后函数
f1 = 3 * a * Math.pow(x0, 2) + 2 * b * x0 + c
x1 = x0 - f0/f1
} while (Math.abs(x1 - x0) >= Math.pow(Math.E, -4))
return x1
}
例:求根号x的近似值 x2=nx2−n=0f(x)=x2−n x^2 = n\\ x^2 - n = 0\\ f(x) = x^2 - n x2=nx2−n=0f(x)=x2−n 我想求根号2等于多少,我猜测值为4,根据牛顿迭代定律: x_{n+1} = x - \frac{x^2 - n}{2x} = \frac{1}{2}(x + \frac{n}{x}) 12(4+24)=2.2512(2.25+22.25)=1.5694412(1.56944+21.56944)=1.4218912(1.42189+21.42189)=1.41423 \frac{1}{2}(4 + \frac{2}{4}) = 2.25\\ \frac{1}{2}(2.25 + \frac{2}{2.25}) = 1.56944\\ \frac{1}{2}(1.56944 + \frac{2}{1.56944}) = 1.42189\\ \frac{1}{2}(1.42189 + \frac{2}{1.42189}) = 1.41423 21(4+42)=2.2521(2.25+2.252)=1.5694421(1.56944+1.569442)=1.4218921(1.42189+1.421892)=1.41423
function mySqrt (num) {
let x0, x1 = 4, f0, f1
do {
x0 = x1
f0 = Math.pow(x0, 2) - num
// 求导后函数
f1 = 2 * x0
x1 = x0 - f0/f1
} while (Math.abs(x1 - x0) >= Math.pow(Math.E, -4))
return x1
}
引深:
物体直线运动时,路程 s 与时间 t 的函数关系为 s=f(t)s = f(t)s=f(t) ,且 f(t)f(t)f(t) 在 t=t0t = t_0t=t0 时的导数 f′(t0)f'(t_0)f′(t0) 存在;则在物理上,f′(t0)f'(t_0)f′(t0) 表示物体在时刻 $ t_0$ 的瞬时速度 v(t)v{(t)}v(t),而v′(t)v'{(t)}v′(t) 为加速度,即时间 f’′(t)f’'(t)f’′(t) 为加速度!