1、?割线替代法：使用差商 f ( x i ) − f ( x i + 1 ) x i − x i + 1 \frac{f(x_i)-f(x_{i+1})}{x_i-x_{i+1}} xi−xi+1f(xi)−f(xi+1)替代 f ′ ( x i ) f'(x_i) f′(xi)的牛顿迭代法
2、?实现：
3、?逆二次插值 I Q I IQI IQI：计算过 x k − 2 , x k − 1 , x k x_{k-2},x_{k-1},x_k xk−2,xk−1,xk的抛物线 x = p ( y ) x=p(y) x=p(y)与x轴交点 x k + 1 = x k − r ( r − 1 ) ( x k − x k − 1 ) + ( 1 − r ) s ( x k − x k − 2 ) ( q − 1 ) ( r − 1 ) ( s − 1 ) , p = f ( x k − 2 ) f ( x k − 1 ) , q = f ( x k ) f ( x k − 1 ) , r = f ( x k ) f ( x k − 2 ) x_{k+1}=x_k-\frac{r(r-(x_k-x_{k-1})+(1-r)s(x_k-x_{k-2})}{(q-(r-(s-},p=\frac{f(x_{k-2})}{f(x_{k-1})},q=\frac{f(x_{k})}{f(x_{k-1})},r=\frac{f(x_{k})}{f(x_{k-2})} xk+1=xk−(q−(r−(s−r(r−(xk−xk−1)+(1−r)s(xk−xk−2),p=f(xk−1)f(xk−2),q=f(xk−1)f(xk),r=f(xk−2)f(xk)
4、?精度：在 n n n次二分操作后误差上限为 b − a 2 n + 1 \frac{b-a}{2^{n+1}} 2n+1b−a
5、?试位方法：同二分法类似，属于插值方法
6、?原理：零点定理： f ∈ C [ a , b ] , f ( a ) f ( b ) < 0 ⟹ ∃ c ∈ [ a , b ] , f ( c ) = 0 f\inC[a,b],f(a)f(b)<0\implies\existc\in[a,b],f(c)=0 f∈C[a,b],f(a)f(b)<0⟹∃c∈[a,b],f(c)=0
7、?根的敏感公式： f ( r ) = 0 , f ( r + Δ r ) + ϵ g ( r + Δ r ) = 0 ⟹ ϵ ≪ f ′ ( r ) , Δ r = − ϵ g ( r ) f ′ ( r ) f(r)=f(r+\Deltar)+\epsilong(r+\Deltar)=0\implies\epsilon\llf'(r),\Deltar=-\frac{\epsilong(r)}{f'(r)} f(r)=f(r+Δr)+ϵg(r+Δr)=0⟹ϵ≪f′(r),Δr=−f′(r)ϵg(r)
8、?计算机误差
9、?二次收敛： lim k → + ∞ ∣ x k + 1 − r ( x k − r ) 2 ∣ = S < + ∞ \lim\limits_{k\to+\infty}|\frac{x_{k+1}-r}{(x_k-r)^2}|=S\lt+\infty k→+∞lim∣(xk−r)2xk+1−r∣=S<+∞
10、?重根的改进迭代： x k + 1 = x k − m f ( x k ) f ′ ( x k ) x_{k+1}=x_k-\frac{mf(x_k)}{f'(x_k)} xk+1=xk−f′(xk)mf(xk)，局部二次收敛
11、?线性收敛： lim k → + ∞ ∣ x k + 1 − r x k − r ∣ = S < 1 \lim\limits_{k\to+\infty}|\frac{x_{k+1}-r}{x_k-r}|=S\lt1 k→+∞lim∣xk−rxk+1−r∣=S<收敛速度 S S S
12、?实现：
13、?原理：求解 f ( x ) + x f(x)+x f(x)+x或 x − f ( x ) x-f(x) x−f(x)或其它 x = g ( x ) x=g(x) x=g(x)的不动点
14、?原理： x k + 1 = x k − f ( x k ) f ′ ( x k ) x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)} xk+1=xk−f′(xk)f(xk)，使用切线与x轴交点逼近根
15、?后向误差： ∣ f ( x ^ ) ∣ |f(\hat{x})| ∣f(x^)∣；前向误差： ∣ x ^ − x ∣ |\hat{x}-x| ∣x^−x∣
16、?Brent方法：在有根区间依次选择使用逆二f次插值，割线方法，二分法，以确保至少使误差减少一半
17、?误差放大因子：相对前向误差与相对后向误差之比。 ∣ g ( r ) r f ′ ( r ) ∣ |\frac{g(r)}{rf'(r)}| ∣rf′(r)g(r)∣
18、?穆勒方法：计算过 ( x k − 2 , f ( x k − 2 ) ) , ( x k − 1 , f ( x k − 1 ) ) , ( x k , f ( x k ) ) (x_{k-2},f(x_{k-2})),(x_{k-1},f(x_{k-1})),(x_{k},f(x_{k})) (xk−2,f(xk−2)),(xk−1,f(xk−1)),(xk,f(xk))的抛物线 y = p ( x ) y=p(x) y=p(x)的复根，取接近 x k x_k xk的为 x k + 1 x_{k+1} xk+1
19、?迭代失败：迭代过程中出现 f ′ ( x k ) = 0 f'(x_k)=0 f′(xk)=0
20、?终止条件：不动点迭代的步数是难以确定的，且不一定收敛