第一章 1.3误差定性分析与避免误差危害

1.3 误差定性分析与避免误差危害

目录

• 1.3.1 算法的数值稳定性
• 1.3.2 病态问题与条件数
• 1.3.3 避免误差伤害

1.3.1 class="superseo">算法的数值稳定性

为了更好的理解，先看两个例子：

#include 
#include 
using namespace std;

int main(){
      double e =  90.1 ;
      for(int i = 2;i<=10;i++)
      cout << pow(pow(e,i),1.0/i) << endl;
      return 0;
}

x = 90.1  
for i in range(2,1000):
    print(x ** i **(1.0/i))

可以看出，python与C++的算法是有一定差别的,假设真实值为90，观测值为90.1，可以看出，Python在计算过程中产生了较大误差，但随着计算次数变差，误差逐渐减小并接近90.1，C++在计算过程中值没有发生改变，但二者的算法都是稳定的，因为随着计算次数增多，误差没有变大。

定义3 一个算法如果输人数据有误差，而在计算过程中舍人误差不增长，则称此算法是数值稳定的；否则称此算法为不稳定的。

1.3.2 病态问题与条件数

对一个数值问题本身如果输人数据有微小扰动 (即误差), 引起输出数据 (即问题解) 相 对误差很大, 这就是病态问题. 例如, 计算函数值 f ( x ) f(x) f(x) 时, 若 x x x 有扰动 Δ x = x − x ∗ \Delta x=x-x^{*} Δx=x−x∗ , 其相对 误差为 Δ x x \frac{\Delta x}{x} xΔx​ , 函数值 f ( x ∗ ) f\left(x^{*}\right) f(x∗) 的相对误差为 f ( x ) − f ( x ∗ ) f ( x ) \frac{f(x)-f\left(x^{*}\right)}{f(x)} f(x)f(x)−f(x∗)​ . 二者的比值为：
∣ f ( x ) − f ( x ∗ ) f ( x ) ∣ ∣ Δ x x ∣ = ∣ f ( x ) − f ( x ∗ ) f ( x ) x x − x ∗ ∣ = ∣ f ( x ) − f ( x ∗ ) x − x ∗ x f ( x ) ∣ ≈ ∣ x f ′ ( x ) f ( x ) ∣ = C p , \frac{{|\frac{f(x)-f\left(x^{*}\right)}{f(x)}|} }{| \frac{\Delta x}{x} | }=|\frac{f(x)-f(x^*)}{f(x)} \frac{x}{x-x^*}|=|\frac{f(x)-f(x^*)}{x-x^*}\frac{x}{f(x)}| \approx\left|\frac{x f^{\prime}(x)}{f(x)}\right|=C_{p}, ∣xΔx​∣∣f(x)f(x)−f(x∗)​∣​=∣f(x)f(x)−f(x∗)​x−x∗x​∣=∣x−x∗f(x)−f(x∗)​f(x)x​∣≈∣ ∣​f(x)xf′(x)​∣ ∣​=Cp​,
C p C_{p} Cp​ 称为计算函数值问题的条件数.一般情况下, 条件数 C p ⩾ 10 C_{p} \geqslant 10 Cp​⩾10 就认为是病态, C p C_{p} Cp​ 越大病态越严重.注意病态问题不是算法引起的, 是数值问题自身固有的.

例1 f ( x ) = x 10 f(x)=x^{10} f(x)=x10,则 C p = ∣ x f ′ ( x ) f ( x ) ∣ = 10 C_p=\left|\frac{x f^{\prime}(x)}{f(x)}\right|=10 Cp​=∣ ∣​f(x)xf′(x)​∣ ∣​=10.
如果 x = 1 x=1 x=1, x ∗ = 1.02 x^*=1.02 x∗=1.02,并且已知 f ( 1.02 ) ≈ 1.24 f(1.02)\approx1.24 f(1.02)≈1.24，则 ε r ( x ∗ ) = 1.02 − 1 1 = 2 % \varepsilon_r(x^*)=\frac{1.02-1}{1}=2\% εr​(x∗)=11.02−1​=2%; ε r ( x ∗ 10 ) = 1.24 − 1 1 = 24 % \varepsilon_r(x^{*^{10}})=\frac{1.24-1}{1}=24\% εr​(x∗10)=11.24−1​=24%

1.3.3 避免误差伤害

根本方法：防止有效数字损失
如何防止：避免两相近数相减；用绝对值很小的数作除数；调整运算次序；减少运算次数。

例2（避免两相近数相减）：求 x 2 − 16 x + 1 = 0 x^{2}-16 x+1=0 x2−16x+1=0 的小正根.
解： x 2 = 8 − 63 ≈ 8 − 7.94 = 0.06 = x 2 ∗ , x 2 ∗ x_{2}=8-\sqrt{63} \approx 8-7.94=0.06=x_{2}^{*}, x_{2}^{*} x2​=8−63 ​≈8−7.94=0.06=x2∗​,x2∗​ 只有一位有效数字.
若改用 x 2 = 8 − 63 = 1 8 + 63 ≈ 1 15.94 ≈ 0.0627 x_{2}=8-\sqrt{63}=\frac{1}{8+\sqrt{63}} \approx \frac{1}{15.94} \approx 0.0627 x2​=8−63 ​=8+63 ​1​≈15.941​≈0.0627,具有三位有效数字.

例3 （避免两相近数相减）：计算 A = 1 0 7 ( 1 − cos ⁡ 2 ∘ ) A=10^{7}\left(1-\cos 2^{\circ}\right. ) A=107(1−cos2∘),其中 cos ⁡ 2 ∘ = 0.9994 \cos 2^{\circ}=0.9994 cos2∘=0.9994
直接计算 A = 1 0 7 ( 1 − cos ⁡ 2 ∘ ) = 1 0 7 ( 1 − 0.9994 ) = 6 × 1 0 3 A=10^{7}\left(1-\cos 2^{\circ}\right)=10^{7}(1-0.9994)=6 \times 10^{3} A=107(1−cos2∘)=107(1−0.9994)=6×103.只有一位有效数字.
若利用 1 − cos ⁡ x = 2 sin ⁡ 2 x 2 1-\cos x=2 \sin ^{2} \frac{x}{2} 1−cosx=2sin22x​ , 则 A = 1 0 7 ( 1 − cos ⁡ 2 ∘ ) = 2 × ( sin ⁡ 1 ∘ ) 2 × 1 0 7 = 6.13 × 1 0 3 A=10^{7}\left(1-\cos 2^{\circ}\right)=2 \times\left(\sin 1^{\circ}\right)^{2} \times 10^{7}=6.13 \times 10^{3} A=107(1−cos2∘)=2×(sin1∘)2×107=6.13×103,具有两位有效数字.

类似地， x 1 x_1 x1​与 x 2 x_2 x2​很接近时，应使用： l g x 1 − l g x 2 = l g x 1 x 2 （ 避免两相近数相减） lgx_1-lgx_2=lg\frac{x_1}{x_2} \text{（ 避免两相近数相减）} lgx1​−lgx2​=lgx2​x1​​（ 避免两相近数相减）
x x x很大时，应使用： x + 1 − x = 1 x + 1 + x （ 避免两相近数相减） \sqrt{x+1}-\sqrt x=\frac{1}{\sqrt{x+1}+\sqrt x}\text{（ 避免两相近数相减）} x+1 ​−x ​=x+1 ​+x ​1​（ 避免两相近数相减）
一般地，当 f(x) \approx f\left(x^{*}\right) 时,可用泰勒展开进行更精确的近似
f ( x ) − f ( x ∗ ) = f ′ ( x ∗ ) ( x − x ∗ ) + f ′ ′ ( x ∗ ) 2 ( x − x ∗ ) 2 + ⋯ f(x)-f\left(x^{*}\right)=f^{\prime}\left(x^{*}\right)\left(x-x^{*}\right)+\frac{f^{\prime \prime}\left(x^{*}\right)}{2}\left(x-x^{*}\right)^{2}+\cdots f(x)−f(x∗)=f′(x∗)(x−x∗)+2f′′(x∗)​(x−x∗)2+⋯

例4 计算 1 + 2 + 3 + ⋯ + 100 + 1 0 9 1 + 2 + 3 + \dots +100 +10^{9} 1+2+3+⋯+100+109,求和时应从小到大相加，可以避免“大数吃小数”，使误差减小。

#include 
#include 
using namespace std;

int main(){
      float sum_small_to_big = 0.0 ;
      float sum_big_to_small = 1000000000.0 ;

      for(int i = 1;i<=100 ; i++){
            sum_small_to_big += i;
            sum_big_to_small += (101-i);
      }
      sum_small_to_big += 1000000000;
      cout << fixed << sum_small_to_big << endl;
      cout << sum_big_to_small << endl;
}

例5 （减少运算次数） 一般来说, 计算机处理下列运算的速度为 ( + , − ) > ( × , ÷ ) > ( e x ) (+,-)>(\times, \div)>(e^x ) (+,−)>(×,÷)>(ex)
P 5 ( x ) = a 5 x 5 + a 4 x 4 + a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 P_{5}(x)=a_{5} x^{5}+a_{4} x^{4}+a_{3} x^{3}+a_{2} x^{2}+a_{1} x^{1}+a_{0} P5​(x)=a5​x5+a4​x4+a3​x3+a2​x2+a1​x1+a0​
直接计算一共需 5 + 4 + 3 + 2 + 1 5+4+3+2+1 5+4+3+2+1 次乘法,和 5 5 5次加法. 若利用公式
P 5 ( x ) = ( ( ( a 5 x + a 4 ) x + a 3 ) x + a 2 ) x + a 1 ) x + a 0 \left.P_{5}(x)=\left(\left(\left(a_{5} x+a_{4}\right) x+a_{3}\right) x+a_{2}\right) x+a_{1}\right) x+a_{0} P5​(x)=(((a5​x+a4​)x+a3​)x+a2​)x+a1​)x+a0​
则只须5次乘法和 5 次加法。