機(jī)器學(xué)習(xí)先導(dǎo)課《數(shù)值分析》（1）——緒論及誤差分析

數(shù)值分析——緒論及誤差分析

數(shù)值分析——緒論及誤差分析

全文目錄

數(shù)值分析的作用及其學(xué)習(xí)工具使用

數(shù)值分析方法是在解決科學(xué)研究和實(shí)踐中遇到的各種奇怪復(fù)雜問題時(shí)掘剪，構(gòu)建一種簡(jiǎn)單的數(shù)學(xué)物理模型來進(jìn)行研究，最終得到我們需要的解。例如對(duì)于一個(gè)無法求得原函數(shù)的積分丐谋，我們可以用足夠多的曲邊梯形面積和進(jìn)行求解芙盘÷呈唬或者對(duì)于一個(gè)高次方程椅文，我們也無法直接求得它的零點(diǎn)冒晰，那么這個(gè)時(shí)候蛉加，我們建立對(duì)應(yīng)的數(shù)值分析模型時(shí)非常有必要的蚜枢。

數(shù)值分析常用工具

對(duì)于本系列課程缸逃，建議讀者對(duì)包括但不限于以下三種語言有一定的了解：C#、Matlab厂抽、Python 需频，本系列文章將用以下三種語言對(duì)其中涉及的算法進(jìn)行Coding和解析。同時(shí)推薦安裝以下庫(kù)及應(yīng)用程序：

應(yīng)用程序：

Visual Studio Code：當(dāng)今最強(qiáng)大的支持拓展的編輯器筷凤，適合各種語言的開發(fā)工作昭殉。強(qiáng)力建議安裝。
Visual Studio 2022：宇宙第一IDE藐守，微軟出品的最強(qiáng)開發(fā)套件挪丢，配合C#如虎添翼事半功倍，建議使用C#的同學(xué)們安裝
Pycharm：JB公司出品的Python IDE卢厂，適合于大型Python項(xiàng)目開發(fā)使用乾蓬。如果只是寫寫小算法小程序，此軟件過于龐大足淆，吃性能巢块。
Matlab：科學(xué)計(jì)算、建模第一開發(fā)工具巧号，其中各種庫(kù)可以有效的支撐你的需求族奢，非常強(qiáng)大的一款工具軟件，但是軟件收費(fèi)且非專業(yè)人員許多功能用不上
Octave：你可以理解為一個(gè)開源免費(fèi)的Matlab丹鸿，沒有了商業(yè)用途的各種工具庫(kù)越走，只留下了最基礎(chǔ)的一些科學(xué)計(jì)算和Matlab語言，在科學(xué)計(jì)算方面非常不錯(cuò)靠欢，吳恩達(dá)在機(jī)器學(xué)習(xí)教程中也使用這款工具廊敌，推薦使用。
GeoGebra全家桶：科學(xué)計(jì)算门怪、2骡澈、3D繪圖最好用的工具之一。

庫(kù)及SDK：

.NET 6（C#）：微軟最新的開發(fā)框架掷空，性能速度以及語法已經(jīng)達(dá)到了前幾名的位置肋殴，單論語言執(zhí)行速度效率已經(jīng)在前幾名，支持U3d坦弟，web护锤、ML等各種開發(fā)。單獨(dú)拎出來是因?yàn)槲④浧煜聨?kù)版本眾多酿傍，這里推薦最新的.NET6
MathNet.Numerics：C#.NET上最強(qiáng)大的科學(xué)計(jì)算工具烙懦，在nuget中可以進(jìn)行下載。
NPlot：C#.NET上一個(gè)優(yōu)秀的繪圖工具庫(kù)
Numpy：python上一個(gè)優(yōu)秀的科學(xué)計(jì)算庫(kù)
Matplotlib：python上用于函數(shù)赤炒、數(shù)據(jù)等繪圖的工具庫(kù)氯析。

數(shù)值分析的具體實(shí)例（多項(xiàng)式簡(jiǎn)化求值）

對(duì)于一個(gè)復(fù)雜多項(xiàng)式的計(jì)算亏较，我們往往需要花費(fèi)巨大的人力逐次計(jì)算，比如求：

$f(x)=3x^4-2x^3+4x^2+5x-1魄鸦，求f(\frac{1}{2})$

最最直接的方法就是進(jìn)行計(jì)算

$3\times\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}-2\times\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}+4\times\frac{1}{2}\times\frac{1}{2}+5\times\frac{1}{2}-1$

我們計(jì)算了10次的乘法宴杀，同時(shí)還計(jì)算了四次加減法運(yùn)算，這實(shí)在是太復(fù)雜了拾因，那么我們?cè)囍?yōu)化一下，倘若我將 $a=\frac{1}{2}\times\frac{1}{2}$ 記錄一下,那么式子就可以變成

$3\times a\times a-2\times a\times\frac{1}{2}+4\times a+5\times\frac{1}{2}-1$

這樣旷余，我們包含計(jì)算a在內(nèi)大概需要計(jì)算7次乘法绢记，四次加減法運(yùn)算。很明顯我們減少了不少的計(jì)算步驟正卧，那么繼續(xù)試試是否又其他的做法蠢熄？

$f(x)=3x^4-2x^3+4x^2+5x-1\\ =x(5+4x-2x^2+3x^3)-1\\ =x(5+x(4-2x+3x^2))-1\\ =x(5+x(4+x(3x-2)))-1$

通過這個(gè)變換（稱為霍納方法、嵌套乘法）炉旷，我們只需要進(jìn)行4次乘法和4次加法签孔，計(jì)算的時(shí)候從內(nèi)往外計(jì)算。一般而言窘行，任意一個(gè)n次多項(xiàng)式都可以通過n次乘法和n次加法求得饥追。

這個(gè)例子展示了科學(xué)計(jì)算的主題特征，簡(jiǎn)單計(jì)算的速度總是比復(fù)雜的計(jì)算快得多罐盔，同一個(gè)問題當(dāng)我們采取不同的方法時(shí)可能可以有效的提升我們的效率和速度但绕。這也是為什么數(shù)值分析（計(jì)算方法）顯得尤為重要的原因。

計(jì)算機(jī)數(shù)值誤差產(chǎn)生機(jī)理

計(jì)算機(jī)的數(shù)值存儲(chǔ)方式

這里我們直接對(duì)計(jì)算機(jī)數(shù)值存儲(chǔ)方式進(jìn)行講解而不作過多的展開惶看。詳細(xì)的內(nèi)容可以參考我《.NET Guide》—— 基本數(shù)據(jù)類型及其存儲(chǔ)方式 #5.2

計(jì)算機(jī)誤差產(chǎn)生原因

數(shù)值分析是一門建立在計(jì)算機(jī)計(jì)算的基礎(chǔ)上的學(xué)科捏顺，我們需要詳細(xì)解釋一下在計(jì)算機(jī)中，是什么導(dǎo)致了誤差的出現(xiàn)纬黎。首先拋出一個(gè)問題幅骄，為什么計(jì)算機(jī)會(huì)存在精度問題？或者換句話說本今，任何非0拆座、5結(jié)尾的小數(shù)在計(jì)算機(jī)中都不是一個(gè)精確值？

上述問題是一個(gè)非常有建設(shè)意義的問題诈泼，我們知道計(jì)算機(jī)時(shí)使用二進(jìn)制進(jìn)行數(shù)據(jù)的運(yùn)算和存儲(chǔ)的懂拾，那么根據(jù)二進(jìn)制的計(jì)算法則，浮點(diǎn)數(shù)的二進(jìn)制表示應(yīng)當(dāng)是 $\sum i*2^{-n},i \in \{0,1 \},n \in N^+$ 铐达，根據(jù)這個(gè)式子不難看出對(duì)于二進(jìn)制而言岖赋，并不能用有限的位數(shù)表示所有的浮點(diǎn)數(shù)。舉個(gè)淺顯的例子瓮孙，例如十進(jìn)制數(shù) $(\frac{1}{3})_{10}=0.\dot{3}$ 唐断，無論我們?cè)趺磳懚紵o法用有限的十進(jìn)制位數(shù)寫出準(zhǔn)確的數(shù)值选脊，只能通過近似的值進(jìn)行描述，當(dāng)我們采用三進(jìn)制數(shù)脸甘，我們就能用有限小數(shù) $(0.1)_3$ 進(jìn)行描述恳啥。

因此對(duì)于二進(jìn)制存儲(chǔ)信息的計(jì)算機(jī)來說，數(shù)據(jù)的存儲(chǔ)位數(shù)總是有限度的丹诀，我們不可能準(zhǔn)確的表述每一個(gè)浮點(diǎn)數(shù)钝的，于是，對(duì)于那些無法表示的數(shù)值铆遭，我們只能采取近似的手段進(jìn)行擬合硝桩，誤差就出現(xiàn)了。

誤差

誤差限與精度

首先我們給出這樣一個(gè)定義枚荣，設(shè) $x^*$ 是某量的一個(gè)精確值碗脊，而 $x$ 是此量的近似值，那么我們將 $e = |x^*-x|$ 定義為值的 絕對(duì)誤差橄妆，也就是誤差衙伶。

不過在工程實(shí)踐中，我們往往是不知道實(shí)際值 $x^*$ 的害碾，同時(shí)誤差e也并不是已知量矢劲，我們只能設(shè)法在計(jì)算過程中采取某些手段，對(duì)誤差進(jìn)行一個(gè)估計(jì)蛮原。這個(gè)估計(jì)是一個(gè)區(qū)間范圍卧须，那么給出下面條件
$have \ \epsilon>0 \\ |e| = |x^*-x| \leq\epsilon$

若上式成立，我們則給出了 $x-\epsilon\leq x^*\leq x+\epsilon,x\in[x-\epsilon,x+\epsilon]$ 儒陨，于是我們稱 $\epsilon$ 為絕對(duì)誤差限花嘶，又稱為精度。它描繪了我們近似值與絕對(duì)值的相似程度蹦漠，給出了誤差的最大值椭员。

通常，在同一范圍或數(shù)量級(jí)內(nèi)笛园，誤差限越小隘击，也就是我們的數(shù)據(jù)越精確。當(dāng)逾越這條線的時(shí)候研铆，絕對(duì)誤差限就顯得心有余而力不足了埋同。例如數(shù)字的近似值是9999，精確值是10000棵红，它的誤差限是1凶赁；若近似值是9，精確值是10，誤差限也是1虱肄，很明顯前者的擬合效果要好于后者致板。我們稱前者是99.99%的吻合度，而后者的吻合度是90%咏窿。

上述式子很明顯是因?yàn)楸容^的數(shù)量級(jí)不同而導(dǎo)致的斟或，為了更好的描述，我們采用相對(duì)誤差及相對(duì)誤差限進(jìn)行描述集嵌。相對(duì)誤差定義為 $e_r=\frac{e}{x^*}=1-\frac{x}{x^*}$ 萝挤，根據(jù)量綱的計(jì)算法則，很明顯相對(duì)誤差區(qū)別于絕對(duì)誤差的地方就在于相對(duì)誤差是一個(gè)無量綱常量根欧，通常也采用百分比作為表示平斩。

與絕對(duì)誤差一樣，我們通常無法直接得出 $e_r$ 的值咽块，精確值往往也是未知的，同樣的欺税，我們使用相對(duì)誤差限去給出一個(gè)區(qū)間估計(jì)侈沪。

$|e_r| = |\frac{e}{x^*}|\leq \epsilon_r$

這里我們可以給出任意數(shù)值的誤差估計(jì)方法，如下式所示：

設(shè)有精確值 $x^*_1$ ,估計(jì)值 $x_1$ 晚凿，構(gòu)造函數(shù) $y=f(x),f(x_1)$ 在 $x^*_1$ 處Taylor展開得：

$f(x_1) = f(x^*_1)+(\frac{df}{dx_1})^*(x_1-x^*_1)+\frac{1}{2!}(\frac{d^2f}{d^2x_1})^*(x_1-x^*_1)^2+\frac{1}{3!}(\frac{d^3f}{d^3x_1})^*(x_1-x^*_1)^3+\dotsb$

同時(shí)我們知道估計(jì)值和精確值的差即為誤差 $e(x_1)$ 亭罪，且為無窮小量,那么上述式子化為

$f(x_1)=f(x^*_1)+e(x_1)(\frac{df}{dx_1})^*+\dotsb\\ 故e(f(x))=f(x)-f(x^*)=f(x_1)-f(x^*_1)\approx e(x_1)(\frac{df}{dx_1})^*$

因此我們得出了誤差的一個(gè)分析式， $(\frac{df}{dx_1})^*$ 則稱為絕對(duì)誤差增長(zhǎng)因子歼秽，表示誤差經(jīng)過運(yùn)算 $f$ 后變化的速率或倍數(shù)应役。

同時(shí)給出相對(duì)誤差估計(jì)推導(dǎo)：

$e(f(x))_r=\frac{e(f(x))}{f(x^*_1)}=(\frac{df}{dx_1})^* \cdot \frac{e(x_1)}{f(x_1^*)}\\ =\frac{x_1^*}{f(x_1^*)}(\frac{df}{dx_1})^*\cdot e_r(x_1)$

同樣的， $\frac{x_1^*}{f(x_1^*)}(\frac{df}{dx_1})^*$ 則稱為相對(duì)誤差增長(zhǎng)因子燥筷，表示誤差經(jīng)過運(yùn)算 $f$ 后變化的速率或倍數(shù)箩祥。

更一般的，給出任意函數(shù)的誤差分析式：

$絕對(duì)誤差：e(f)\approx\sum_{i=1}^n \left [\left( \frac{\partial f}{\partial x_i}\right)\cdot e(x_i)\right]\\ 相對(duì)誤差：e_r(f)\approx\sum_{i=1}^n \left [\left( \frac{x_i^*}{f(\dotsb)}\cdot\frac{\partial f}{\partial x_i}\right)\cdot e_r(x_i)\right]$

模型誤差

模型誤差往往是建模過程中肆氓，忽略了那些影響細(xì)微的次要因素袍祖，最終在要求精度的情況下，出現(xiàn)了模型的誤差谢揪。例如我們初高中學(xué)過的公式 $G=mg$ 蕉陋，我們往往會(huì)有一句g取9.8N/kg，數(shù)學(xué)模型描述就為 $G=9.8m$ 拨扶，這里的g就是一個(gè)近似值凳鬓，而我們知道重力加速度在不同的地方是會(huì)受到高度、海拔患民、地殼密度分布等等因素影響的缩举，由于我們的重力加速度取了近似值，因此這個(gè)模型也是一個(gè)近似模型，而這里必然會(huì)產(chǎn)生誤差蚁孔，由于近似模型導(dǎo)致的誤差我們就稱為模型誤差奶赔。

觀測(cè)誤差

觀測(cè)誤差往往是因?yàn)閿?shù)據(jù)的來源受到主觀因素的影響，假設(shè)我有一個(gè)絕對(duì)精準(zhǔn)的彈簧式重力計(jì)杠氢，我們用它去測(cè)量物體重量的時(shí)候必須通過肉眼去讀取儀器上的刻度數(shù)字站刑，在這里我們因讀數(shù)不準(zhǔn)產(chǎn)生的誤差就是觀測(cè)誤差”前伲或者同上面的質(zhì)量和重量的方程中绞旅，假設(shè)我們知道了G，通過計(jì)算得出了質(zhì)量m温艇，它與實(shí)際質(zhì)量的差值就是觀測(cè)誤差因悲。

截?cái)嗾`差

截?cái)嗾`差在計(jì)算機(jī)和生活中是一個(gè)常見誤差。我們?cè)谶M(jìn)行大筆金錢交易的時(shí)候往往會(huì)討價(jià)還價(jià)勺爱，最常見的還價(jià)就是“抹零頭”晃琳，284元的飯錢講價(jià)成280元，這就是一種截?cái)嗨雎场Ｓ?jì)算機(jī)因數(shù)據(jù)溢出而直接抹去首尾的數(shù)據(jù)時(shí)卫旱，也是一種截?cái)啵皇沁@種更多視為一種錯(cuò)誤围段，而不是誤差顾翼。

如果你對(duì)高等數(shù)學(xué)了解一些，那必然知道泰勒展開式是一個(gè)無窮級(jí)數(shù)奈泪，我們常常采用帶拉格朗日或皮亞諾余項(xiàng)去描述誤差适贸，這個(gè)誤差也是因?yàn)槲覀冎蝗×擞邢薜捻?xiàng)而導(dǎo)致了數(shù)據(jù)的不精確。

例如下列展開：

$e^x=S(x)=1+x+\frac{x^2}{2!}+\dotsb+\frac{x^n}{n!}$

因?yàn)槲覀冎徊捎们皀項(xiàng)作為計(jì)算涝桅，實(shí)際的誤差（拉格朗日余項(xiàng)）就為

$e^x-S(x) = \frac{x^{n+1}}{(n+1)!}e^{\theta x}$

舍入誤差

這是平時(shí)可能用到最多的一種誤差形式了拜姿，四舍五入就是一種常見的舍入誤差。計(jì)算機(jī)默認(rèn)就是使用舍入誤差去處理誤差的苹支。只不過計(jì)算機(jī)由于是二進(jìn)制的原因砾隅，因此它只要是1就向上進(jìn)1。采用舍入誤差有一個(gè)特性就是你的誤差絕對(duì)不會(huì)超過區(qū)間的一半债蜜。

有效數(shù)字缺失

有效數(shù)字是指數(shù)字位數(shù)里第一個(gè)非零值到最后的數(shù)字晴埂，例如0.001就具有一位有效數(shù)字。那么我們?yōu)槭裁葱枰ビ懻撚行?shù)字這個(gè)問題呢寻定？事實(shí)上儒洛，仔細(xì)想想，如果說我現(xiàn)在需要計(jì)算 $\sqrt{9.01}-3$ 狼速， $\sqrt{9.01}$ 大約是3.0016662琅锻，假定我們的計(jì)算機(jī)只能存儲(chǔ)三位有效數(shù)字，上述式子的差異卻需要在第四位有效數(shù)字的時(shí)候才取到，那么 $\sqrt{9.01}-3=3-3=0.00$ 恼蓬，我們最終得到的數(shù)據(jù)連一位有效數(shù)字都沒有惊完，而實(shí)際上我們需要存儲(chǔ)的是 $1.67\times 10^{-3}$ 即可獲得更為精確的數(shù)字，同樣是三位有效數(shù)字处硬，0的答案就是我們的有效數(shù)字缺失小槐。那么如何去避免這個(gè)問題呢？

我們?nèi)绻鱿铝凶儞Q

$\frac{(\sqrt{9.01}-3)(\sqrt{9.01}+3)}{\sqrt{9.01}+3}=\frac{9.01-9}{6.00}=1.67\times 10^{-3}$

這樣就避免了在減法過程使得我們?cè)缭绲膩G失了有效數(shù)據(jù)。

再舉一個(gè)例子，有下列式子

$E_1=\displaystyle \lim_{ x \to 0}\frac{1-cosx}{sin^2x},E_2=\displaystyle \lim_{ x \to 0}\frac{1}{1+cosx}$

如果高等數(shù)學(xué)底子好的朋友們應(yīng)該一眼就能看出這兩個(gè)式子是相等的亮蒋，結(jié)果應(yīng)當(dāng)是0.5，但是計(jì)算機(jī)會(huì)老老實(shí)實(shí)的去計(jì)算這些數(shù)據(jù)摇邦，先從分子的減法開始計(jì)算，如果x足夠的小，那么 $1-cosx$ 最終會(huì)因?yàn)橛行?shù)字過于靠后以至于計(jì)算機(jī)無法保存到有效數(shù)字從而使得 $E_1=0$ 。

如下圖所示疆栏，當(dāng)x越發(fā)減小，對(duì)整個(gè)式子結(jié)果的改變就越大：

todo 添加圖片

這不是我們希望的結(jié)果惫谤，于是我們進(jìn)行恒等變形：

$\frac{(1+cosx)(1-cosx)}{(1+cosx)sin^2x}=\frac{sin^2x+cos^2x-cos^2x}{2sin^2x}=\frac{1}{2}$

通過這個(gè)變換承边，巧妙的利用了消去可能導(dǎo)致有效位數(shù)缺失的減法操作。

誤差的產(chǎn)生和避免

我們的模型誤差石挂、觀測(cè)誤差屬于不可抗力導(dǎo)致的誤差，我們只能盡可能去優(yōu)化模型和提高精度险污，但是往往付出了極大代價(jià)卻收獲甚微痹愚。我們對(duì)于誤差的避免更多是采取減少在計(jì)算過程中產(chǎn)生的截?cái)嗪蜕崛胝`差，盡可能避免有效數(shù)字的缺失導(dǎo)致的數(shù)據(jù)丟失蛔糯。

一般而言拯腮，這些誤差產(chǎn)生通常是因?yàn)?

兩個(gè)相近的數(shù)字進(jìn)行減法導(dǎo)致了有效數(shù)字的缺失，例如剛才講到的第一個(gè)例子蚁飒，因此實(shí)際計(jì)算時(shí)我們應(yīng)當(dāng)避免過于接近的數(shù)字進(jìn)行減法动壤，如果無法避免，則通過平方和一類的公式進(jìn)行升階擴(kuò)大處理淮逻。
臨界數(shù)（接近數(shù)據(jù)存儲(chǔ)最大值）先做了加法琼懊，例如如果計(jì)算機(jī)只能存儲(chǔ)3位數(shù)字，若不考慮符號(hào)位爬早，以無符號(hào)數(shù)進(jìn)行計(jì)算哼丈，最大值應(yīng)當(dāng)是7，那么7+2-3=6很顯然是能在計(jì)算機(jī)存儲(chǔ)下的筛严，但計(jì)算機(jī)按著順序計(jì)算時(shí)會(huì)先計(jì)算7+2=9=0b1001醉旦，最高位將會(huì)被丟棄，最終卻得到了7+2=1的答案，顯然是不對(duì)的车胡，如果調(diào)整成先做減法則不會(huì)有這個(gè)問題檬输。
過于繁雜的計(jì)算步驟，當(dāng)計(jì)算步驟過多的時(shí)候匈棘，每一次運(yùn)算都會(huì)產(chǎn)生舍入誤差丧慈，這些誤差將會(huì)在后續(xù)不斷的傳播累計(jì)，最后影響結(jié)果羹饰。同時(shí)如果計(jì)算不穩(wěn)定（經(jīng)常出現(xiàn)舍入操作伊滋，例如每一次計(jì)算的尾數(shù)都大于4），也會(huì)導(dǎo)致誤差過大队秩。我們需要設(shè)計(jì)好計(jì)算簡(jiǎn)單笑旺，同時(shí)每一次舍入操作得到的舍和入都是相同結(jié)果（例如每次尾數(shù)都小于5）
極限狀態(tài)下的誤差擴(kuò)大化，例如我們的估計(jì)值和真實(shí)值很接近馍资，或者運(yùn)算中有趨近于0的數(shù)字產(chǎn)生筒主，往往就會(huì)導(dǎo)致有效位數(shù)的缺失，我們最好采用泰勒展開鸟蟹、和差化積乌妙，利用三角、對(duì)指數(shù)函數(shù)的運(yùn)算法則對(duì)其進(jìn)行處理建钥，從而避免誤差的繼續(xù)累計(jì)藤韵。
絕對(duì)值過小的數(shù)字做除數(shù)，事實(shí)上誤差有如下公式成立： $e(\frac{x}{y})\approx\frac{ye_x+xe_y}{y^2}$ ,若y過小熊经，則會(huì)導(dǎo)致誤差成平方倍擴(kuò)大泽艘。因此我們也需要避免這種情況，最簡(jiǎn)便的方法就是通過放大分子分母镐依，使得其分母可以盡可能多的保留下有效數(shù)字

誤差的傳播

和的絕對(duì)誤差即誤差的和

$f(x_1,x_2\dotsb,x_n)=\sum^n_{i=1}x_i\\ e(\sum_{i=1}^n x_i)\approx\sum_{i=1}^n e(x_i)\\ e_r(\sum_{i=1}^n x_i)\approx\sum_{i=1}^n \frac{x^*_i}{\sum_{i=1}^n x^*_i}e_r(x_i)$

由此可以看出匹涮，我們傳入的數(shù)據(jù)在進(jìn)行加法運(yùn)算時(shí)，誤差大約和各個(gè)近似值的代數(shù)和是差不多的槐壳。因此我們可以得出結(jié)論：初始輸入的近似值對(duì)于求和運(yùn)算的影響時(shí)并不大的然低。

差的絕對(duì)誤差相對(duì)而言較難估計(jì)，但是差的相對(duì)誤差與我們的初始值關(guān)系是非常大的务唐，就好比我們上文提到的雳攘，過于接近的數(shù)相減的時(shí)候，往往容易導(dǎo)致有效數(shù)字的嚴(yán)重缺失枫笛。因此我們盡可能要避免差的運(yùn)算来农。

$設(shè)f(x_1,x_2)=x_1-x_2\\ e_r(x_1-x_2)\approx\frac{x_1^*}{x_1^*-x_2^*}e_r(x_1)-\frac{x_2^*}{x_1^*-x_2^*}e_r(x_2)\\ 即e_r(x_1-x_2)\leq\left|\frac{x_1^*}{x_1^*-x_2^*}\right|e_r(x_1)+\left|\frac{x_2^*}{x_1^*-x_2^*}\right|e_r(x_2)$

從這個(gè)式子也能看出如果輸入的初始近似值過于接近，一旦做差崇堰，分母就會(huì)急劇的趨近0沃于，使得整體的誤差變大涩咖。

算數(shù)中積的誤差公式為：

$f(x_1,x_2\dotsb,x_n)=\prod_{i=1}^{n}x_i\\ e(\prod_{i=1}^{n}x_i)\approx\sum_{i=1}^n \left [\left (\prod_{j=1,j\neq i}^{n}x^*_j\right )e(x_i)\right]\\ e_r(\prod_{i=1}^{n}x_i)\approx \sum_{i=1}^n e_r(x_i)$

事實(shí)上我們換個(gè)角度，積在某種意義上就是一個(gè)累加的過程繁莹，因此誤差的累計(jì)傳播規(guī)律也類似于和的規(guī)律檩互，積的相對(duì)誤差積累是一個(gè)累加過程，但是對(duì)于絕對(duì)誤差而言咨演，積很受大數(shù)的乘法影響闸昨，例如估計(jì)值是0.9，精確值是1薄风，當(dāng)他們各自乘一百倍后饵较，相對(duì)誤差因?yàn)橹挥幸豁?xiàng)，故沒有什么變化遭赂，但是絕對(duì)誤差卻從0.1放大到了10循诉。所以如果在需要避免絕對(duì)誤差的情況之下，我們要盡可能的去避免大數(shù)去直接乘一個(gè)近似值撇他。

商的誤差就可以類比減法的誤差茄猫，直接給出我們的證明推論：

$f(x_1,x_2) = \frac{x_1}{x_2}\\ e_r(\frac{x_1}{x_2})\approx\frac{1}{x_2^*}e(x_1)-\frac{x_1^*}{(x^*_2)^2}e(x_2)=\\ \frac{x_1^*}{x^*_2}[e_r(x_1)-e_r(x2)]\approx\\ e_r(x_1)-e_r(x_2)$

不難看出，商的相對(duì)誤差就是被除數(shù)和除數(shù)的相對(duì)誤差的差困肩，乘法在某種意義上也是除法划纽，因此乘法中存在的問題在除法中也必定存在。乘法如果乘數(shù)過大會(huì)導(dǎo)致絕對(duì)誤差過大锌畸，那么乘數(shù)取倒數(shù)就成為了除法勇劣，也就是說除法中要盡可能避免過小的數(shù)作為除數(shù)，這樣才能最大的保護(hù)數(shù)據(jù)的準(zhǔn)確性潭枣。

乘方芭毙、開方帶來的誤差和乘除法類似，這里不再過多贅述卸耘，直接給出我們的公式：

$e(x^p) = p(x^*)^{p-1}e(x)\\ e_r(x^p)=pe_r(x)$

綜上所述，我們知曉了初始數(shù)據(jù)誤差對(duì)于計(jì)算結(jié)果的影響粘咖，而前文提到的誤差增長(zhǎng)因子能很好的反映處計(jì)算結(jié)果和原始數(shù)據(jù)誤差變化的情況及計(jì)算結(jié)果對(duì)于初始值的敏感程度蚣抗。如果初始近似值變動(dòng)而計(jì)算結(jié)果變化很小的時(shí)候，說明該計(jì)算是良態(tài)的瓮下。如果初始的近似值輕微擾動(dòng)翰铡，但是結(jié)果變化極大的時(shí)候，則說明我們的計(jì)算是敏感的讽坏，病態(tài)的锭魔。

算法設(shè)計(jì)的穩(wěn)定性與病態(tài)條件

病態(tài)問題

我們剛分析完了我們的算法的敏感、病態(tài)的理論路呜，這里我以一個(gè)例子來展示病態(tài)函數(shù)是如何影響我們的結(jié)果的迷捧。

$設(shè)f(x) = x^2-x-10100织咧，求f(99)的相對(duì)誤差，并討論x=99附近的性態(tài)漠秋。 \\其中99的相對(duì)誤差為1\%（即99是一個(gè)估計(jì)值,存在1\%的誤差）$

我們直接利用前文提到的泰勒展開誤差估計(jì)公式計(jì)算笙蒙，接下去分析:

$e_r(f)={f}\\'(99)\times \frac{-99}{200}\times1\%=-99\%$

這就說明當(dāng)初始輸入了一個(gè)相對(duì)誤差在1%的初始值的時(shí)候，經(jīng)過函數(shù)計(jì)算庆锦，函數(shù)值的相對(duì)誤差會(huì)放大99倍捅位。

$f(99)=-200,f(99.9)=-20.9，f(99)=10f(99.9)$

在我們初始的擾動(dòng)只有0.9的情況搂抒，經(jīng)過計(jì)算后的值卻擴(kuò)大到了10倍艇搀，按著相對(duì)誤差的計(jì)算，也就是10%的擾動(dòng)帶來了1000%的函數(shù)變化求晶。因此我們稱這個(gè)函數(shù)早x=99附近是一個(gè)病態(tài)的函數(shù)焰雕。

因此我們?cè)诜治鰡栴}的時(shí)候，要額外注意問題是否是良態(tài)的誉帅。

計(jì)算的穩(wěn)定性

計(jì)算的穩(wěn)定性主要體現(xiàn)在當(dāng)處理同一問題的時(shí)候淀散，選用不同的計(jì)算方法或算法，往往對(duì)結(jié)果有著顯著的區(qū)別蚜锨。例如下面這個(gè)例子：

$a_0 = ln6-ln5\approx0.1823档插，a_{20}\approx0.0087301587\approx0.0087\\a_n=-5a_{n-1}+\frac{1}{n},a_{10}=?$

這個(gè)題目大家一看，驚呼：真是簡(jiǎn)單亚再，直接將 $a_0$ 套進(jìn)遞推式郭膛，直接就能解出來了。但結(jié)果恰恰出乎你的預(yù)料氛悬。如果你利用題中給出的公式進(jìn)行計(jì)算则剃，會(huì)得出一個(gè)極端奇怪的答案，往往你還不自知錯(cuò)誤所在如捅。我們嘗試分析一下棍现。

得出錯(cuò)誤結(jié)論的原因很顯然是因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=a_0%3D0.1823" alt="a_0=0.1823" mathimg="1">發(fā)生了舍入誤差，如果我們?nèi)×挥行?shù)字镜遣，我們舍去了0.000022左右的大小己肮，誤差會(huì)隨著計(jì)算式不斷累積，如下

$\epsilon+0.1823=ln6-ln5\\ a_1 = -5(0.1823+\epsilon)+1\\ a_2 = -5[-5(0.1823+\epsilon)+\frac{1}{2}]\\ \dotsb\\ a_n = -5^n(0.1823+\epsilon)+\dotsb$

我們可以發(fā)現(xiàn)悲关，誤差是呈現(xiàn)指數(shù)函數(shù)的形式進(jìn)行增長(zhǎng)的谎僻，我們可以算算到了第十項(xiàng)誤差已經(jīng)達(dá)到了原始誤差的9,765,625倍，大概我們多算了214的樣子寓辱，這顯然是無法接受的答案艘绍，并且當(dāng)你寫出算法沒有第十項(xiàng)的參考數(shù)值的時(shí)候，你會(huì)無法意識(shí)到自己的錯(cuò)誤所在秫筏，因?yàn)槟愕乃惴ㄟ壿嬐耆_诱鞠，但你的錯(cuò)誤恰恰發(fā)生在了最難注意到的誤差之上挎挖。

那我們?nèi)绾稳〗鉀Q這個(gè)問題呢？很顯然對(duì)于這個(gè)遞推而言般甲，誤差永遠(yuǎn)呈現(xiàn)指數(shù)函數(shù)形式進(jìn)行變化肋乍。如果我們期許指數(shù)函數(shù)縮小，那么我們能不能試著把指數(shù)函數(shù)的底數(shù)換成一個(gè)絕對(duì)值小于1的數(shù)字呢敷存？

答案顯然是可以的墓造，如果我們將原有遞推式更改為以下這種情況：

$\frac{1}{5n}-\frac{1}{5}a_{n}=a_{n-1}$

我只是反過來求解前一項(xiàng)，我們從后往前進(jìn)行計(jì)算锚烦，那么觅闽，誤差分析式就變成了

$\epsilon+0.0087\\ a_{19} = \frac{1}{5\cdot 20}-\frac{1}{5}(\epsilon+0.0087)\\ a_{18} = \frac{1}{5\cdot 19}-\frac{1}{5}(\frac{1}{5\cdot 20}-\frac{1}{5}(\epsilon+0.0087))\\ \dotsb\\$

很顯然我們的誤差項(xiàng) $\epsilon$ 已經(jīng)是一次比一次更小，呈現(xiàn)指數(shù)函數(shù)的縮小狀態(tài)涮俄，這樣得出的值很明顯是要精確于前者的蛉拙，最終的誤差也不會(huì)超過0.000022。

通過這個(gè)例子我們可以發(fā)現(xiàn)彻亲，實(shí)際上對(duì)于同一個(gè)問題孕锄，采用的算法、分析的思路不同苞尝，帶來的結(jié)果卻天差地別畸肆。對(duì)于第一種解法，我們稱為不穩(wěn)定的算法宙址，它會(huì)導(dǎo)致我們失真轴脐。第二種解法，我們的誤差逐步在縮小抡砂，說明我們的算法是穩(wěn)定的算法大咱。

剛剛介紹的是因?yàn)樗惴ú煌恼`差擴(kuò)大化問題，還有另一種情況就是因?yàn)榉噶宋覀冎罢f過的大數(shù)吃小數(shù)的問題注益。如題

$求x^2-(10^9+1)x+10^9=0的根$

通過因式分解我們很容易知道答案是 $x_1=10^9,x_2=1$ 碴巾，但當(dāng)我們利用求根公式 $\frac{-b\pm\sqrt{\Delta}}{2a}$ ，我們能解出第一個(gè)更大解丑搔，但是當(dāng)我們解第二個(gè)解的時(shí)候厦瓢，由于 $-b-\sqrt{\Delta}$ 在我們計(jì)算機(jī)的字長(zhǎng)不夠時(shí)，會(huì)產(chǎn)生極為嚴(yán)重的截?cái)嗾`差低匙，最終會(huì)得出一個(gè)等于0的解，很顯然時(shí)不對(duì)的碳锈，這里犯了我們之前提到的大數(shù)和小數(shù)加減法的時(shí)候顽冶，往往會(huì)導(dǎo)致一些數(shù)據(jù)的丟失，因此我們轉(zhuǎn)變思路售碳，如果利用韋達(dá)定理：

$x_1\times x_2=\frac{c}{a}\\ x_1+x_2=-\frac强重{a}$

不僅極為有效的減少了計(jì)算量绞呈，也不會(huì)再次出現(xiàn)剛才提到的問題了。

因此對(duì)于保持算法穩(wěn)定性的原則就是间景，我們既要防止數(shù)字由于數(shù)量級(jí)相差過大佃声，從而導(dǎo)致較小的數(shù)字喪失其計(jì)算作用；也要防止數(shù)字過于接近倘要，使得有效數(shù)字缺失圾亏，產(chǎn)生不可避免的誤差。更需要注意的就是我們的算法中產(chǎn)生的誤差封拧，應(yīng)當(dāng)是越來越小且收斂的志鹃。

練習(xí)題

已知對(duì)數(shù) $lga$ 的絕對(duì)誤差限為 $0.5\times 10^{-n},求相對(duì)誤差限$

如何使得 $(\frac{1-cosx}{x}，x>>1),ln(30-\sqrt{30^2-1})$ 計(jì)算更精確

設(shè) $f(x)=x^2-\frac{log_{2}x}{x},x=4.1\pm0.05$ 泽西，若以 $u=f(4.1)$ 作為近似值曹铃，請(qǐng)問u能有幾位有效數(shù)字

用電表測(cè)得一個(gè)電阻兩端電壓和電流為 $V=220\pm 2V,I=10\pm 0.1A，求阻值R和相對(duì)捧杉、絕對(duì)誤差陕见。$ （PS:歐姆定律 $R=\frac{V}{I}$ ）

找到方程 $x^2+9^{12}x=3$ 的根

Reference

《數(shù)值分析》（原書第二版） —— Timothy Sauer

《數(shù)值計(jì)算方法》（清華大學(xué)出版社） —— 呂同富等

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市味抖，隨后出現(xiàn)的幾起案子评甜，更是在濱河造成了極大的恐慌，老刑警劉巖非竿，帶你破解...
沈念sama閱讀 217,826評(píng)論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件蜕着，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡红柱，警方通過查閱死者的電腦和手機(jī)承匣，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,968評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來锤悄，“玉大人韧骗，你說我怎么就攤上這事×憔郏” “怎么了袍暴？”我有些...
開封第一講書人閱讀 164,234評(píng)論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)隶症。經(jīng)常有香客問我政模，道長(zhǎng)，這世上最難降的妖魔是什么蚂会？我笑而不...
開封第一講書人閱讀 58,562評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任淋样，我火速辦了婚禮，結(jié)果婚禮上胁住，老公的妹妹穿的比我還像新娘趁猴。我一直安慰自己刊咳，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,611評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布儡司。她就那樣靜靜地躺著娱挨，像睡著了一般。火紅的嫁衣襯著肌膚如雪捕犬。梳的紋絲不亂的頭發(fā)上跷坝，一...
開封第一講書人閱讀 51,482評(píng)論 1贊 302
城市分裂傳說
那天，我揣著相機(jī)與錄音或听，去河邊找鬼探孝。笑死，一個(gè)胖子當(dāng)著我的面吹牛誉裆，可吹牛的內(nèi)容都是我干的顿颅。我是一名探鬼主播，決...
沈念sama閱讀 40,271評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼足丢，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼粱腻！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起斩跌，我...
開封第一講書人閱讀 39,166評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤绍些，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后耀鸦，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體柬批，經(jīng)...
沈念sama閱讀 45,608評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,814評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年袖订，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了氮帐。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,926評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡洛姑，死狀恐怖上沐，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情楞艾，我是刑警寧澤参咙，帶...
沈念sama閱讀 35,644評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站硫眯，受9級(jí)特大地震影響蕴侧，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜两入，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,249評(píng)論 3贊 329
男人毒藥：我在死后第九天來索命
文/蒙蒙一净宵、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧，春花似錦塘娶、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,866評(píng)論 0贊 22
一樁弒父案刁岸，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至她我，卻和暖如春虹曙，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背番舆。一陣腳步聲響...
開封第一講書人閱讀 32,991評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來泰國(guó)打工酝碳，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人恨狈。一個(gè)月前我還...
沈念sama閱讀 48,063評(píng)論 3贊 370
代替公主和親
正文我出身青樓疏哗，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親禾怠。傳聞我的和親對(duì)象是個(gè)殘疾皇子返奉，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,871評(píng)論 2贊 354