數(shù)值分析讀書(shū)筆記（1）導(dǎo)論

1.數(shù)學(xué)問(wèn)題與數(shù)值計(jì)算問(wèn)題

一般來(lái)說(shuō)，解決實(shí)際問(wèn)題的第一步是將實(shí)際問(wèn)題轉(zhuǎn)換為數(shù)學(xué)問(wèn)題施籍，接著建立數(shù)學(xué)模型來(lái)解決這個(gè)數(shù)學(xué)問(wèn)題居扒，而理論解或者解析解通常難以求得，于是數(shù)值計(jì)算的方法應(yīng)運(yùn)而生

首先我們要將一個(gè)數(shù)學(xué)問(wèn)題轉(zhuǎn)化成數(shù)值問(wèn)題

數(shù)值問(wèn)題是指輸入數(shù)據(jù)與輸出數(shù)據(jù)之間函數(shù)關(guān)系的一個(gè)確定而無(wú)歧義的描述

按照建立數(shù)值問(wèn)題的基本形式丑慎，數(shù)學(xué)問(wèn)題可以分為兩大類(lèi)

• 包含非有理函數(shù)或未知函數(shù)
• 主要是代數(shù)問(wèn)題

這一本書(shū)面向數(shù)值計(jì)算的三大類(lèi)計(jì)算任務(wù)

• 求值（計(jì)算機(jī)實(shí)現(xiàn)計(jì)算過(guò)程中遇到的問(wèn)題）
• 方程求解
  • 數(shù)值方程
    • 代數(shù)方程
    • 超越方程
    • 差分方程（組）
  • 函數(shù)方程
• 函數(shù)逼近

數(shù)學(xué)與科學(xué)喜喂，工程中的大量問(wèn)題，最后歸結(jié)為數(shù)值線(xiàn)性代數(shù)問(wèn)題竿裂，這一大類(lèi)問(wèn)題通常和矩陣有關(guān)玉吁，故又稱(chēng)為矩陣計(jì)算
數(shù)值線(xiàn)性代數(shù)包括

• 規(guī)范線(xiàn)性方程組問(wèn)題
• 非規(guī)范線(xiàn)性方程組問(wèn)題
• 矩陣的特征值問(wèn)題(包括廣義特征值)
• 矩陣的奇異值問(wèn)題

2.數(shù)值計(jì)算的基本數(shù)學(xué)思想與方法

構(gòu)造數(shù)值計(jì)算方法的基本途徑是近似

由于是導(dǎo)論，故不深入探討腻异，這里列出幾種思想

• 等價(jià)變換思想（相似變換處理矩陣）
• 逐次逼近思想（不動(dòng)點(diǎn)迭代）
• 逐步逼近思想
• 以直代曲思想
• 轉(zhuǎn)換問(wèn)題類(lèi)型思想
• 外推思想（Richardson 外推法）

數(shù)值計(jì)算的幾種方法

• 直接法（不考慮舍入誤差的情況下进副，有限步得到精確解）
• 間接法（迭代過(guò)程，讓近似解逼近精確解）

數(shù)值方法的評(píng)價(jià)標(biāo)準(zhǔn)

• 計(jì)算效果（精度或者誤差）
• 計(jì)算效率（算法復(fù)雜度或者收斂率）

3.計(jì)算誤差的基本概念以及誤差分析

數(shù)值計(jì)算的誤差是指數(shù)學(xué)模型的真解和由數(shù)值方法得到的近似解之間的偏差

誤差按來(lái)源可以這樣分類(lèi)

• 模型誤差
• 觀(guān)測(cè)誤差
• 截?cái)嗾`差
• 舍入誤差

這里引入絕對(duì)誤差悔常，相對(duì)誤差和有效數(shù)字的概念

首先是絕對(duì)誤差 =x-\tilde {x}$$) , 其中為x的近似值,我們可以得到絕對(duì)誤差界
 \end{vmatrix} =\begin{vmatrix} x-\tilde x \end{vmatrix} \le \Delta (x) =\Delta $)

然而絕對(duì)誤差并不能很好的表現(xiàn)數(shù)的近似程度影斑，引出相對(duì)誤差
 = \frac{e(x)}{x} =\frac{x-\tilde x}{x} $$)
自然也有相對(duì)誤差界*
![](http://www.forkosh.com/mathtex.cgi?
$$\begin{vmatrix} \epsilon ^ * \end{vmatrix} = \begin{vmatrix} \epsilon ^ * (x) \end{vmatrix} = \begin{vmatrix} \frac{e(x)}{x} \end{vmatrix}=\begin{vmatrix}\frac{x-\tilde x}{x}\end{vmatrix} \le \delta ^*(x)=\delta*$$)
注意到分母為x,而實(shí)際當(dāng)中我們經(jīng)常用來(lái)代替分母曾沈，即![](http://www.forkosh.com/mathtex.cgi?
$$\begin{vmatrix}\epsilon\end{vmatrix}= \begin{vmatrix} \epsilon (x) \end{vmatrix}= \begin{vmatrix} \frac{e(x)}{\tilde x} \end{vmatrix}=\begin{vmatrix} \frac{x-\tilde x}{\tilde x} \end{vmatrix} \le \delta(x)=\delta $$)

接下來(lái)給出有效數(shù)字的定義
如果近似值的誤差界是某一位的半個(gè)單位，且該位到近似值的第一位有n個(gè)非零數(shù)鸥昏，那么該近似值就有n位有效數(shù)字

使用四舍五入法可以使絕對(duì)誤差最小，并且利用四舍五入法來(lái)計(jì)算近似值姐帚，每一位數(shù)值都是有效可靠的

可進(jìn)一步探尋近似值和相對(duì)誤差之間的某種聯(lián)系,記
通過(guò)簡(jiǎn)單的放縮可得
 \times 10^{m-1}$$)
那么當(dāng)近似值的有效數(shù)字為n時(shí)吏垮，相對(duì)誤差的上界為
 \end{vmatrix}= \begin{vmatrix} \frac{e(x)}{\tilde x} \end{vmatrix}=\begin{vmatrix} \frac{x-\tilde x}{\tilde x} \end{vmatrix} \le \frac{0.5 \times 10^{m-n}}{a_1 \times 10^{m-1} }=\frac{1}{2a_1}\times 10^{1-n}$$)

由此可以引申出一個(gè)定理
如果x的有效數(shù)字位數(shù)為n，則有 
反之罐旗，如果}\times 10^{1-n}),則有效數(shù)字位數(shù)至少有n

討論一下函數(shù)的誤差
其中絕對(duì)誤差為

進(jìn)一步推廣至多元函數(shù)
利用Tayor展開(kāi)可知其中絕對(duì)誤差為

給出絕對(duì)誤差界

即多元函數(shù)的相對(duì)誤差界放大系數(shù)

接下來(lái)介紹減少誤差的計(jì)算法則

• 避免兩相近數(shù)做減法
• 避免大數(shù)吃掉小數(shù)
• 避免除數(shù)過(guò)小
• 簡(jiǎn)化運(yùn)算膳汪，避免重復(fù)運(yùn)算

關(guān)于數(shù)值穩(wěn)定的定義

如果一個(gè)算法經(jīng)過(guò)多次計(jì)算，將初始的誤差變大了九秀，陳該算法為數(shù)值不穩(wěn)定的遗嗽，反之為數(shù)值穩(wěn)定的

關(guān)于病態(tài)問(wèn)題的定義

如果一個(gè)數(shù)值問(wèn)題，對(duì)輸入做出輕微的擾動(dòng)會(huì)對(duì)輸出產(chǎn)生較大的影響鼓蜒，稱(chēng)該問(wèn)題為病態(tài)的

4.算法性態(tài)分析概述

一個(gè)算法的復(fù)雜度有兩種痹换，分別為

• 時(shí)間復(fù)雜度（指需要的計(jì)算機(jī)的時(shí)間資源）
• 空間復(fù)雜度（指需要的計(jì)算機(jī)的儲(chǔ)存器資源）

計(jì)算復(fù)雜度取決于被求解問(wèn)題的規(guī)模大小，輸入數(shù)據(jù)和算法本身都弹，計(jì)算復(fù)雜度用算法的基本運(yùn)算次數(shù)與基本操作量來(lái)測(cè)量

數(shù)學(xué)上用時(shí)間復(fù)雜度為問(wèn)題規(guī)模的多項(xiàng)式函數(shù)或者指數(shù)函數(shù)來(lái)作為區(qū)分算法好與壞的分水嶺娇豫，如果時(shí)間復(fù)雜度為問(wèn)題規(guī)模的多項(xiàng)式函數(shù)那么這個(gè)算法是好的，而如果是指數(shù)函數(shù)則被稱(chēng)為不好的算法

由于輸入數(shù)據(jù)的不同畅厢，時(shí)間復(fù)雜度也不同冯痢，我們引入復(fù)雜度的期望作為平均時(shí)間復(fù)雜度

我們利用算法復(fù)雜度來(lái)度量那些使用直接法的算法，對(duì)于迭代的算法我們使用收斂率來(lái)評(píng)價(jià)

由于這里沒(méi)有對(duì)向量框杜，矩陣等給出其大小的“測(cè)度”浦楣，故先討論下迭代法產(chǎn)生的實(shí)數(shù)的序列
收斂率的高低使用收斂階的大小衡量

Def:如果上述實(shí)數(shù)序列收斂于x，即咪辱，假定存在某個(gè)正數(shù),使得極限
![](http://www.forkosh.com/mathtex.cgi?$$
\lim_{k\to \infty}\frac{e_{k+1}}{e_k^r}=\lim_{k\to \infty}\frac{\begin{vmatrix} x_{k+1}-x\end{vmatrix}}{\begin{vmatrix} x_{k}-x\end{vmatrix}^r}=c_r>0$$)
存在振劳，稱(chēng)該迭代法是r階收斂

• r=1時(shí)為線(xiàn)性收斂
• r>1時(shí)為超線(xiàn)性收斂
  • r=2，平方收斂
  • r=3油狂，立方收斂

需要注意的是澎迎，若有
也稱(chēng)為超線(xiàn)性收斂
收斂階如果比較小，則需要加速选调，這是數(shù)值計(jì)算的重要研究課題