简单迭代运算

**迭代（辗转法）**是一种不断用变量的旧值递推新值的过程

分类

• 精确迭代：杨辉三角、内在移动算法等
• 近似迭代：二分法和牛顿迭代法等

设计方法

1. 确定迭代模型
   根据问题描述，抽象出当前值和下一个值的迭代关系。这一迭代关系应该最终收敛于所期望的目标。迭代模型时解决迭代问题的关键。
2. 控制迭代过程
   迭代模型会包含期望的目标，根据这一目标控制迭代的次数，并最终结束算法。迭代过程的控制通常分为两种情况：一种是已知或可以计算出来迭代的次数，这时可以构建一个固定次数的循环来实现对迭代过程的控制。另一种是所需的迭代次数无法确定，需要分析出迭代过程的结束条件，还要考虑有可能得不到目标解（迭代不收敛）的情况，避免出现迭代过程的死循环。

例题

1

【例题1】输出杨辉三角形
问题分析
利用一个n*n的矩阵存储信息。如下

有$a_{i,j} = a_{i-1,j-1} + a_{i-1,j}$ai,j​=ai−1,j−1​+ai−1,j​
计算模型
$\left\{ \begin{array}{lr} a_{i,i} = 1& & \\ a_{i,0}=1\\ a_{i,j} = a_{i-1,j-1}+a_{i-1,j}&i>1且 1\leq j<i & \end{array} \right.$⎩⎨⎧​ai,i​=1ai,0​=1ai,j​=ai−1,j−1​+ai−1,j​​i>1且1≤j<i​​
算法设计与描述
输入：$n$n
输出：杨辉三角
step1: 输入$n$n，定义一个n$\times$×n的存储矩阵$a$a
step2: 令$a_{0,0} = 1,a_{1,0} = 1,a_{1,1} = 1$a0,0​=1,a1,0​=1,a1,1​=1, 定义$i = 2$i=2
step3: 令$a_{i,0} = 1,a_{i,i} = 1$ai,0​=1,ai,i​=1，定义$j = 1$j=1
step4: 令$a_{i,j} = a_{i-1,j-1}+a_{i-1,j},j = j + 1$ai,j​=ai−1,j−1​+ai−1,j​,j=j+1,若$j<i$j<i,转step4
step5: 令$i = i + 1$i=i+1，若$i < n$i<n 转step3
step6: 打印输出矩阵$a$a，算法结束
算法分析

1. 输入$n$n，规模为$n$n
2. 核心操作：$a_{i,j} = a_{i-1,j-1}+a_{i-1,j}$ai,j​=ai−1,j−1​+ai−1,j​
3. 得出$T(n) = \sum_{i=2}^{n-1}(2 + \sum_{j=1}^{i-1}1)+3 = \Theta(n^2)$T(n)=∑i=2n−1​(2+∑j=1i−1​1)+3=Θ(n2)

2

【例题2】内存移动问题：数组中有n个数据，要将它们顺序循环向后移k位，即前面的元素向后(右)移k位，后面的元素则循环向前移k位，例：0、1、2、3、4、5循环移3位后为： 3、4、5、0、1、2。考虑到n会很大，不允许用2*n及以上个空间来完成此题。
问题分析
设原数列为$a[n]$a[n]，移动k次。

1. 建立一个数列$b[n]$b[n],令$b[(k+i)\;mod\;n] = a[i] , i \in [0,n-1]$b[(k+i)modn]=a[i],i∈[0,n−1]
   此时，时间复杂度为$O(n)$O(n),空间复杂度为$O(2n)$O(2n),不符合题目要求。
2. 建立临时变量$tmp$tmp，令$tmp = a[n-1]$tmp=a[n−1]，然后从$a[n-2]$a[n−2]开始所有位右移一位，最后，令$a[0]=tmp$a[0]=tmp,实现右移一位，循环实现右移k位。
   此时，时间复杂度为$O(k\times n)$O(k×n)，空间复杂度为$O(n+1) = O(n)$O(n+1)=O(n)
3. 如果按照2的方法将元素直接移动至指定位置，那么时间复杂度为$O(n)$O(n)，空间复杂度为$O(n)$O(n)。
   如：n = 6，k = 3的情况，将$a[0]\to a[3]$a[0]→a[3],$a[3]\to a[0]$a[3]→a[0];$a[1]\to a[4]$a[1]→a[4],$a[4]\to a[1]$a[4]→a[1],$a[2]\to a[5]$a[2]→a[5],$a[5]\to a[2]$a[5]→a[2]，共需要移动3轮，每轮移动元素个数为2。
   不难发现，此时
   $移动轮数 = gcd(n,k)$移动轮数=gcd(n,k)
   下面给出证明：
   令$gcb(n,k) = q$gcb(n,k)=q，每轮最少移动元素个数为$r$r
   从而有：$n = q \times n_1 , k = q \times n_2\quad n_1,n_2\in Z$n=q×n1​,k=q×n2​n1​,n2​∈Z 且 $gcb(n_1,n_2) = 1$gcb(n1​,n2​)=1
   由每轮第一次移动的元素要和最后一次移动到的元素相同可得：$(k\times r)\; mod\; n = 0$(k×r)modn=0
   从而推出：$(n_2\times r)\; mod\; n_1 = 0$(n2​×r)modn1​=0
   由$gcb(n_1,n_2) = 1$gcb(n1​,n2​)=1可得：$gcb(n_1,r) = n_1$gcb(n1​,r)=n1​
   $r$r 为每轮最小移动次数，取 $n_1$n1​，此时移动轮数为$n/r = q$n/r=q

下文主要讲述第三种方法
计算模型

1. 求出最大公约数，由欧几里得
   $\left\{ \begin{array}{lr} a,b = b,a & 若b>a& 初始化\\ r = a\; mod\; b & & 进入循环 \\ gcd(a,b) = gcb(b,r) &r \not= 0&判断\\ gcd(a,b) = b &r = 0& 结束 \end{array} \right.$⎩⎪⎪⎨⎪⎪⎧​a,b=b,ar=amodbgcd(a,b)=gcb(b,r)gcd(a,b)=b​若b>ar​=0r=0​初始化进入循环判断结束​
2. 令$q = gcb(a,b)$q=gcb(a,b) [上一步所求出来的], 移动次数：$i = n/q$i=n/q
3. 计算元素移动位置：$x_i = (x_m + i\times k)\; mod\; n\quad 0\leq i<n/q \quad 0 \leq x_m < q$xi​=(xm​+i×k)modn0≤i<n/q0≤xm​<q
   说明：初始元素为$x_m$xm​，第$i$i次移动实现$a[x_{i-1}]\to a[x_i]$a[xi−1​]→a[xi​] ,共移动$q$q轮

算法设计与描述

算法分析

注：可以进行改进，减少内层循环次数。

【例题3】求n!(n<=100)
问题分析
int整数表示的范围为：-2147483648 —— -2147483647，显然不能直接处理规模为100的阶乘计算。所以需要借助一个int型数组a，设定每个元素存储6位整数，由式子$log(n!) = \Theta(n\log n)$log(n!)=Θ(nlogn)可得数组中约需要34个元素。
计算方法：模拟竖式乘法
计算模型
设存储大数结果的数组为$a[m]$a[m]，$m = n (\log n)/6$m=n(logn)/6
初始化$a[0] =1，a[i] = 0 (i\not=0)$a[0]=1，a[i]=0(i​=0)
$\left\{ \begin{array}{lr} b = a[j] \times i + d & 1\leq j\leq m,1<i\leq n&b为每个数组元素相乘的实际结果 \\ a[j] = b \; mod\; 1000000 & 1\leq j\leq m& 乘了之后，对a[j]重新赋值 \\ d = \dfrac{b}{1000000}&&下一次元素的进位，切除小数位 \end{array} \right.$⎩⎪⎨⎪⎧​b=a[j]×i+da[j]=bmod1000000d=1000000b​​1≤j≤m,1<i≤n1≤j≤m​b为每个数组元素相乘的实际结果乘了之后，对a[j]重新赋值下一次元素的进位，切除小数位​
算法设计与描述

算法分析

1. 问题规模：n次乘法
2. 核心语句：内层的竖式乘法
3. 算法时间复杂度：
   $T(n) = \sum_{i=2}^{n}\sum_{j=1}^{m}C=C(n-1)m = C(n-1)\Theta(n\log n)/6 = O(n^2\log n)$T(n)=i=2∑n​j=1∑m​C=C(n−1)m=C(n−1)Θ(nlogn)/6=O(n2logn)

方程求解

非线性方程

非线性方程的收敛性及其迭代速度

定义1： 设$x_k$xk​是方程$f(x)=0$f(x)=0的根，若存在$x_k$xk​的一个邻域$\Delta$Δ，当初值以属于$\Delta$Δ时，迭代收敛，则称该迭代过程具有局部收敛性。
定义2：设$\epsilon_k=x^*-x_k$ϵk​=x∗−xk​为第$k$k次迭代的迭代误差，若
$\lim_{k \to \infty}\dfrac{|\epsilon_{k+1}|}{|\epsilon_{k}|^p}=c\not =0$k→∞lim​∣ϵk​∣p∣ϵk+1​∣​=c​=0
则称迭代是p阶收敛的。称c为渐进误差常数。
定义3：称$EI=p^{\frac{1}{\theta}}$EI=pθ1​为效率指数，其中，$\theta$θ表示每次迭代的计算量，$p$p表示迭代的收敛阶。
定理1：：若当$x\in [a,b]$x∈[a,b]时，$\phi(x)$ϕ(x)满足$|\phi'(x)|\leq L <1,x \in [a,b]$∣ϕ′(x)∣≤L<1,x∈[a,b]，则迭代收敛域唯一的根。

建立迭代方程

1. 选取适当的初值x0
2. 建立迭代方程，将方程f(x)=0转换成x=φ(x)的等价形式。
3. 运用迭代方程x=φ(x)，反复计算，如x1=φ(x0), x2=φ(x1),…,xn=φ(xn-1)，得到x的序列，若该数列收敛，则最终可以得到满足一定精度ε的解，即有|xn-xn-1|<ε。有时候也会用f(xn)<= ε或f(xn)=0来判断。

【例题1】：求$9x^2-\sin x-1=0$9x2−sinx−1=0，在$(0,1)$(0,1)之间的解，要求$| 9x^2-\sin x-1|<0.00001$∣9x2−sinx−1∣<0.00001
数学模型
$x_{i+1}=\frac{\sqrt{\sin x_i +1}}{3}，取x_0=0.4和0.5$xi+1​=3sinxi​+1​​，取x0​=0.4和0.5
算法设计与描述

二分法

若f(x)在区间[a, b]上连续，则在此区间上任取两点x1、x2，若f(x1)*f(x2)<0，则在（x1,x2）间必有解。其求解步骤为：

1. f(x1)*f(x2)<0，方程有解，继续 (2)，否则无解；
2. 令x=(x1+x2)/2，代入方程f(x)=0，则x即为所求，算法结束。否则进行(3)；
3. f(x1)*f(x)<0，与x2同侧令x2=x，若f(x1)*f(x)>0，则与x1同侧，令x1=x，继续步骤(2)。

渐进时间复杂性
设根在区间$[a_k,b_k]$[ak​,bk​]，取$x_k=(a_k+b_k)/2$xk​=(ak​+bk​)/2作为根的一个近似，按上述算法框架，不断二分，则可以获得一个近似根的序列${x_0,x_1,x_2,…,x_k}$x0​,x1​,x2​,…,xk​，该序列必以根$x^*$x∗为极限。那么，误差可以表示为：$|x^*-x_k|≤(b_k - a_k)/2=(b-a)/2^{k+1}$∣x∗−xk​∣≤(bk​−ak​)/2=(b−a)/2k+1
对于给定精度$ε$ε，只需取$k$k满足$(b-a)/2k+1≤ε$(b−a)/2k+1≤ε，可得$k≥(\ln(b-a)-\lnε)/\ln2 -1$k≥(ln(b−a)−lnε)/ln2−1。
【例题2】用二分法求$9x^2-\sin x-1=0$9x2−sinx−1=0，在$(0,1)$(0,1)之间的解，要求$| x_k-x_{k-1}|<0.00001$∣xk​−xk−1​∣<0.00001。
计算模型
初始化：$x_1 = 0,x_2=1$x1​=0,x2​=1
$\left\{ \begin{array}{lr} f(x) = 9 x^2 - \sin x -1&&\\ x = \dfrac{x_1+x_2}{2}&&\\ x_1 = x&f(x) f(x_1) < 0&\\ x_2 = x&f(x)f(x_1) > 0&\\ \end{array} \right.$⎩⎪⎪⎪⎨⎪⎪⎪⎧​f(x)=9x2−sinx−1x=2x1​+x2​​x1​=xx2​=x​f(x)f(x1​)<0f(x)f(x1​)>0​​
算法设计与描述

牛顿法

设待解方程为$f(x)$f(x)，其一个解为$x$x。
设过点$(x_0,y_0)$(x0​,y0​)的切线斜率为$f’(x_0)$f’(x0​)，则其切线方程为：
$f(x)=f(x_0)+f’(x_0)(x-x_0)$f(x)=f(x0​)+f’(x0​)(x−x0​)
当其与$x$x轴相交时，$f(x)=0$f(x)=0。则可以得到 $x=x_0-f(x_0)/f’(x_0)$x=x0​−f(x0​)/f’(x0​)可以做为迭代公式，反复使用，求出迭代数列$x_1,x_2,…, x_n$x1​,x2​,…,xn​，直到满足精度为止。

牛顿法时间复杂度分析

太麻烦了。后面想起来再整理吧。
【例题3】：用牛顿法求$9x^2-\sin x-1=0$9x2−sinx−1=0，在$(0,1)$(0,1)之间的解，要求$| x_k-x_{k-1}|<0.00001$∣xk​−xk−1​∣<0.00001。
计算模型
令$f(x) = 9x^2-\sin x-1$f(x)=9x2−sinx−1，则$f'(x) = 18x-\cos x$f′(x)=18x−cosx
迭代公式为：
$x_{k}=x_{k-1}-(9x_{k-1}^2-\sin(x_{k-1})-1)/(18x_{k-1}-\cos( x_{k-1}))$xk​=xk−1​−(9xk−12​−sin(xk−1​)−1)/(18xk−1​−cos(xk−1​))
算法设计与描述

线性方程组的近似解法

雅克比算法&&高斯赛德尔算法

计算模型

算法设计与描述

线性规划*

ppt上有不过带星号，不太想整理了。。。