《數(shù)值分析》筆記

使用教材：《數(shù)值分析》李慶揚(yáng)较坛，王能超，易大義編客冈。
大致梳理整本書的內(nèi)容和重點(diǎn)。

第1章數(shù)值分析與科學(xué)計(jì)算引論

本章是介紹性質(zhì)的稳强，主要說了數(shù)值分析（乃至計(jì)算數(shù)學(xué)）在學(xué)什么场仲，解決什么問題。
內(nèi)容上退疫，需要掌握誤差的幾個(gè)種類渠缕，絕對/相對誤差（限）的計(jì)算，有效數(shù)字褒繁。
1.3節(jié)“誤差定性分析與避免誤差危害”：了解數(shù)值穩(wěn)定亦鳞、病態(tài)問題、條件數(shù)的概念。尤其是條件數(shù)的意思燕差，在后續(xù)數(shù)值線性代數(shù)中也會(huì)用到遭笋。避免誤差危害的方法：避免兩相近數(shù)相減，避免用絕對值小的數(shù)做除數(shù)徒探，注意運(yùn)算次序和減少運(yùn)算次數(shù)瓦呼。
了解一些古典的數(shù)值計(jì)算思想：秦九韶算法，迭代法测暗，以直代曲央串，加權(quán)平均的松弛技術(shù)（感覺類似外推法？）
本章內(nèi)容淺顯零散偷溺，了解即可蹋辅。

第2章插值法

注意區(qū)分插值和擬合：插值函數(shù)一定確保已有的數(shù)據(jù)點(diǎn)完全擬合，一般維數(shù)（比如多項(xiàng)式次數(shù)）較高挫掏；擬合則不需要侦另，一般維數(shù)較低。

2.1 引言

差值問題的提出：略
多項(xiàng)式擬合：對于n+1個(gè)數(shù)據(jù)點(diǎn)(x,y)尉共，用多項(xiàng)式擬合褒傅，則使用n次多項(xiàng)式剛好保證存在唯一。（代數(shù)方法證明）
雖然結(jié)果唯一袄友，但插值多項(xiàng)式系數(shù)的求法有許多種殿托，這里介紹拉格朗日插值和牛頓插值。

2.2 拉格朗日插值

思路：基函數(shù) $l_k(x)$ （線性插值基函數(shù)）：滿足 $l_j(x_j)=1,l_j(x_i)=0,i\neq j$ 的n+1次多項(xiàng)式（顯然唯一）剧蚣。插值多項(xiàng)式 $L(x)=\sum y_kl_k(x)$ 為基函數(shù)的線性組合支竹，系數(shù)由數(shù)據(jù)點(diǎn)確定。
基函數(shù)方法是將插值問題劃歸于特定條件下容易實(shí)現(xiàn)的插值問題鸠按，本質(zhì)上是廣義的坐標(biāo)系方法礼搁。
插值余項(xiàng)：若 $f^{(n+1)}(x)$ 存在，則 $R_n(x)=f(x)-L(x)=\frac{f^{(x+1)(\xi)}}{(n+1)!}\prod_{i=0}^n (x-x_i)$ 目尖。
使用中值定理證明馒吴。（中值定理和泰勒展開在數(shù)值分析中用處很多）。由插值余項(xiàng)的公式得瑟曲，要保證多項(xiàng)式插值與原函數(shù)較為接近饮戳，最好原函數(shù)的n+1次導(dǎo)數(shù)有界。
拉格朗日插值法思路清晰洞拨，公式漂亮扯罐，但若數(shù)據(jù)點(diǎn)變化需要重新計(jì)算。下面的牛頓插值多項(xiàng)式解決了這個(gè)問題烦衣。

2.3 均差與牛頓插值多項(xiàng)式

引入“均差”（差商）概念篮赢，類比導(dǎo)數(shù)齿椅。
牛頓法思路：利用均差琉挖，依次添加數(shù)據(jù)點(diǎn)启泣，每添加一個(gè)數(shù)據(jù)點(diǎn)插值多項(xiàng)式 $P(x)$ 會(huì)增加一項(xiàng)。
對數(shù)據(jù)點(diǎn)的順序沒有要求示辈。
牛頓插值法在添加數(shù)據(jù)點(diǎn)時(shí)計(jì)算量較小寥茫，但公式?jīng)]那么漂亮。

2.4 埃爾米特插值

拉格朗日插值和牛頓插值僅保證數(shù)據(jù)點(diǎn) $f(x_i)=y_i$ 矾麻，沒有導(dǎo)數(shù)信息。埃爾米特插值用于一些 $f^{(k)}(x_i)=y_i^k$ 的需求。
計(jì)算方法類似牛頓插值酱畅，必要時(shí)可用待定系數(shù)法则拷。
書中僅討論了兩個(gè)典型的埃爾米特插值的計(jì)算。
注意兩點(diǎn)三次埃爾米特插值和三次樣條插值的區(qū)別：兩者都是用三次多項(xiàng)式對兩點(diǎn)做插值甩牺，但前者是為了保證 $f(x_1),f(x_2),f'(x_1),f'(x_2)$ 均與數(shù)據(jù)相同蘑志，后者僅保證 $f(x_1),f(x_2)$ 與數(shù)據(jù)相同，導(dǎo)數(shù)的條件是為了保證 $f$ 的光滑性贬派。

2.5 分段低次插值

了解高次插值的病態(tài)性質(zhì)：龍格現(xiàn)象急但，高次插值沒有收斂性。
通過分段搞乏，降低次數(shù)波桩，減少病態(tài)現(xiàn)象。
常用的：分段線性插值请敦，分段三次埃爾米特插值镐躲，三次樣條插值。
分段插值具有一致收斂性侍筛。

2.6 三次樣條插值

保證數(shù)據(jù)點(diǎn)的同時(shí)插值函數(shù)具有二階光滑性萤皂，在很多實(shí)際問題中有應(yīng)用。
思路：對于 $n+1$ 個(gè)數(shù)據(jù)點(diǎn)勾笆，分成n段三次多項(xiàng)式敌蚜，共需 $4n$ 個(gè)參數(shù)。限制條件：每個(gè)數(shù)據(jù)點(diǎn)吻合窝爪， $2n$ 個(gè)方程弛车；為保證光滑性，每個(gè)連接點(diǎn)兩邊的一階導(dǎo)數(shù)蒲每、二階導(dǎo)數(shù)相同纷跛， $2(n-1)$ 個(gè)方程；還差2個(gè)方程邀杏，一般為兩個(gè)端點(diǎn)的條件（邊界條件）贫奠，可根據(jù)實(shí)際問題要求給定唬血。
到此為止已經(jīng)列出了一個(gè)線性方程組，解法看書即可唤崭，最終化成三對角矩陣的線性方程組拷恨，使用追趕法求解。
性質(zhì)：插值函數(shù)及其一階導(dǎo)數(shù)谢肾、二階導(dǎo)數(shù)均一致收斂與數(shù)據(jù)的原函數(shù)腕侄。

第3章函數(shù)逼近與快速傅里葉變換

3.1 函數(shù)逼近的基本概念

函數(shù)逼近問題就是：在區(qū)間 $[a,b]$ 上用簡單函數(shù)逼近已知復(fù)雜函數(shù)的問題，簡單函數(shù)一般是n次多項(xiàng)式芦疏、有理函數(shù)冕杠、分段低次多項(xiàng)式等。（可以理解為酸茴，從任意函數(shù)構(gòu)成的空間到多項(xiàng)式函數(shù)空間的投影分预？）
維爾斯特拉斯定理：閉區(qū)間上連續(xù)函數(shù)，均可用有限維的多項(xiàng)式任意逼近（一致范數(shù)）薪捍。證明方法用到伯恩斯坦多項(xiàng)式笼痹，這是一個(gè)理論上對 $[0,1]$ 上連續(xù)函數(shù) $f$ 任意逼近的多項(xiàng)式，但實(shí)際上收斂速度慢飘诗。

介紹范數(shù)與賦范線性空間与倡，用來描述逼近的程度。引入內(nèi)積昆稿、正交纺座、施瓦茨不等式、權(quán)函數(shù)溉潭、函數(shù)內(nèi)積净响、函數(shù)范數(shù)等概念。

最佳逼近：對于某個(gè)函數(shù)空間H喳瓣，某個(gè)范數(shù)馋贤，找出H中與目標(biāo)函數(shù)f的差的范數(shù)最小的函數(shù)P*，為最佳逼近函數(shù)畏陕。
$||f(x)-P*(x)||=min_{P\in H_n}||f(x)-P(x)||$

若取P為多項(xiàng)式配乓，范數(shù)為一致范數(shù)，則為最佳一致逼近多項(xiàng)式惠毁；若范數(shù)取二范數(shù)犹芹，則為最佳平方逼近多項(xiàng)式；若 $f(x)$ 為列表函數(shù)（離散情況）鞠绰，范數(shù)取二范數(shù)腰埂，則為最小二乘擬合。

3.2 正交多項(xiàng)式

正交多項(xiàng)式是函數(shù)逼近的重要工具蜈膨，在數(shù)值積分中也有重要應(yīng)用屿笼。
正交多項(xiàng)式可以理解為多項(xiàng)式內(nèi)積空間中的正交基牺荠？

概念：帶權(quán) $\rho (x)$ 正交，正交函數(shù)族驴一，標(biāo)準(zhǔn)正交函數(shù)族休雌，施密特正交化，正交多項(xiàng)式的遞推關(guān)系式蛔趴，正交多項(xiàng)式零點(diǎn)的定理挑辆。

勒讓德多項(xiàng)式 $P_n(x)$ ：區(qū)間為 $[-1,1]$ ，權(quán)函數(shù) $\rho \equiv1$ 時(shí)孝情，由 $\{1,x, \cdots ,x^n,\cdots \}\$ 正交化得到的多項(xiàng)式。
性質(zhì)：正交性洒嗤，奇偶性箫荡，遞推關(guān)系，n個(gè)不同零點(diǎn)渔隶。

切比雪夫多項(xiàng)式 $T_n(x)$ ：區(qū)間為 $[-1,1]$ 羔挡，權(quán)函數(shù) $\rho = \frac{1}{\sqrt{1-x^2}}$ 時(shí)，由 $\{1,x, \cdots ,x^n,\cdots \}\$ 正交化得到的多項(xiàng)式间唉。另一個(gè)比較直觀的表示：若令 $x=cos\theta$ 绞灼，則 $T_n(x)=cos(n\theta),0 \le \theta\ \le \pi$ 。
性質(zhì)：遞推關(guān)系呈野，（帶權(quán)）正交性低矮，奇偶性，n個(gè)零點(diǎn)被冒，首項(xiàng)系數(shù)军掂，最佳一致逼近多項(xiàng)式，切比雪夫多項(xiàng)式零點(diǎn)插值（通過改變插值點(diǎn)的選位昨悼，從等距點(diǎn)改為切比雪夫多項(xiàng)式零點(diǎn)蝗锥，可避免龍格現(xiàn)象）

一些其他有用的正交多項(xiàng)式：第二類切比雪夫多項(xiàng)式，蓋拉爾多項(xiàng)式率触，埃爾米特多項(xiàng)式终议。

正交函數(shù)族的優(yōu)勢在下面一節(jié)中就有體現(xiàn)。

3.3 最佳平方逼近

數(shù)學(xué)表達(dá)式：
$||f(x)-S*(x)||_2^2=min_{S(x)\in \varphi} ||f(x)-S(x)||_2^2$
連續(xù)形式： $min_{S(x)\in \varphi} \int_a^b \rho(x)[f(x)-S(x)]^2dx$
對多項(xiàng)式空間葱蝗，等價(jià)于求多元函數(shù)的最小值： $I(a_0,a_1,\cdots,a_n) = \int_a^b \rho(x) \left [ \sum_{j=0}^n a_j \varphi_j(x) - f(x) \right ]^2 dx$
這是一個(gè)分析性質(zhì)比較好的函數(shù)穴张，求最小值只要求某個(gè)點(diǎn)對所有變量的偏導(dǎo)數(shù)等于0，剛好是一個(gè)線性方程組垒玲，稱為法方程陆馁。這樣看起來是找到了解析解，只要用數(shù)值方法求解線性方程組就可以合愈，但直接取 $\varphi_k(x)=x^k$ 時(shí)叮贩，系數(shù)矩陣為希爾伯特矩陣击狮，是一個(gè)條件數(shù)大的矩陣，對它解線性方程組得到的誤差較大益老。

為了解決上面的問題彪蓬，可以用正交函數(shù)族作最佳平方逼近，參考傅里葉級(jí)數(shù)捺萌，由正交性質(zhì)档冬，系數(shù)矩陣是對角陣，因此在計(jì)算傅里葉級(jí)數(shù)的系數(shù)時(shí)不需要解線性方程組桃纯。在上面的例子中將 $x^k$ 換成勒讓德多項(xiàng)式 $P_k(x)$ 就能解決問題酷誓。這就體現(xiàn)出正交函數(shù)族對于數(shù)值逼近的優(yōu)勢。

切比雪夫級(jí)數(shù)：將函數(shù) $f$ 按切比雪夫多項(xiàng)式展開态坦，得到切比雪夫級(jí)數(shù)盐数，可作為 $f$ 在 $[-1,1]$ 上的近似最佳一致逼近多項(xiàng)式。

3.4 曲線擬合的最小二乘法

類似于最佳平方逼近的離散形式伞梯，在科學(xué)實(shí)驗(yàn)中對實(shí)驗(yàn)數(shù)據(jù)的處理（曲線擬合）經(jīng)常用到玫氢。
數(shù)學(xué)表達(dá)式： $min_{S(x)\in \varphi } \sum_{i=0}^m [S(x_i) - y_i]^2$
方法與最佳平方逼近類似，法方程谜诫，解線性方程組漾峡，用正交多項(xiàng)式解決病態(tài)系數(shù)矩陣問題。略喻旷。

3.5 有理逼近

前面的多項(xiàng)式逼近對于有界連續(xù)函數(shù)逼近效果較好生逸，現(xiàn)在對于在某點(diǎn)附近無界的情況，用有理函數(shù)逼近效果較好掰邢。
有理函數(shù)： $R_{nm}(x)=\frac{P_n(x)}{Q_m(x)} = \frac{\sum_{k=0}^n a_kx^k}{\sum_{k=0}^m b_kx^k}$ 牺陶，即兩個(gè)多項(xiàng)式的比。這樣可以得到比如 $\frac{1}{x}$ 這樣的可以趨于無窮的函數(shù)逼近辣之。
計(jì)算方法是利用連分式掰伸。

帕德逼近：如果有理函數(shù) $R_{nm}(x)$ 逼近 $f(x)$ 且 $R_{nm}^{(k)}(0)=f^{(k)}(0),k=0,1,\cdots,(n+m)$ ，則稱 $R_{nm}(x)$ 為 $f(x)$ 在 $x=0$ 處的 $(n,m)$ 階帕德逼近怀估。這個(gè)逼近的好處個(gè)人沒用過不太清楚狮鸭，略。

3.6 三角多項(xiàng)式逼近與快速傅里葉變換

在模型數(shù)據(jù)具有周期性時(shí)多搀，用三角函數(shù)特別是正弦函數(shù)和余弦函數(shù)作為基函數(shù)是合適的歧蕉。
最佳平方三角逼近：傅里葉級(jí)數(shù)
快速傅里葉變換：略。

評(píng)注

正交多項(xiàng)式中的勒讓德多項(xiàng)式和切比雪夫多項(xiàng)式是兩個(gè)十分重要且經(jīng)常使用的正交多項(xiàng)式康铭，應(yīng)引起高度關(guān)注惯退。
當(dāng)模型為多項(xiàng)式時(shí)法方程是病態(tài)的，為此推薦用正交化方法避免解法方程从藤。
如果數(shù)據(jù)是周期的催跪，使用三角最小二乘或三角插值是合適的锁蠕，計(jì)算用快速傅里葉變換（FFT），它是節(jié)省計(jì)算量的一個(gè)范例懊蒸。

第4章數(shù)值積分與數(shù)值微分

4.1 數(shù)值積分概論

一般的數(shù)值積分： $\int_a^b f(x) dx \approx \sum_{k=0}^n A_k f(x_k)$
其中 $x_k$ 為求積節(jié)點(diǎn)荣倾， $A_k$ 為求積系數(shù)，即節(jié)點(diǎn) $x_k$ 的權(quán)重骑丸。
代數(shù)精度：描述求積公式的誤差的階數(shù)舌仍，計(jì)算方法為計(jì)算 $f(x) = x^k$ 的情況的誤差。
插值型求積公式：先求 $f(x)$ 的插值多項(xiàng)式 $L_n(x)$ 通危，再用 $I_n := \int_a^b L_n(x) dx$ 作為 $I := \int_a^b f(x) dx$ 的近似值铸豁，其誤差可用插值多項(xiàng)式的誤差計(jì)算： $R[f] = \int_a^b [ f(x) - L_n(x) ] dx = \int_a^b R_n(x) dx$ 。
求積公式是插值型的黄鳍，當(dāng)且僅當(dāng)其至少有n次代數(shù)精度推姻。

收斂性：只要插值點(diǎn)充分密集，數(shù)值積分就會(huì)充分接近真實(shí)值框沟。
穩(wěn)定性：插值點(diǎn)數(shù)據(jù) $(x_k,f(x_k))$ 可能存在誤差，穩(wěn)定性是指增炭，只要誤差充分小忍燥，數(shù)值積分就會(huì)充分接近真實(shí)值。反之隙姿，稱為對誤差敏感梅垄。

4.2 牛頓-柯特斯公式

先默認(rèn)選取等距節(jié)點(diǎn)，因?yàn)楹唵问溏瑁藭r(shí)的公式 $I_n = (b-a) \sum_{k=0}^n C_k^{(n)} f(x_k)$ 稱為牛頓-柯特斯公式队丝， $C_k^{(n)}$ 稱為柯特斯系數(shù)。

對于 $[a,b]$ 欲鹏，選取a机久、b兩點(diǎn)插值(n=1)，稱為梯形公式赔嚎；選取a膘盖、b、(a+b)/2三點(diǎn)(n=3)尤误，稱為辛普森公式侠畔，5個(gè)點(diǎn)(n=4)稱為柯特斯公式。9點(diǎn)以上的牛頓柯特斯公式穩(wěn)定性差损晤，不用软棺。

當(dāng)n為偶數(shù)，牛頓柯特斯公式至少具有n+1階代數(shù)精度尤勋。

4.3 復(fù)合求積公式

類似分段低階插值喘落，先分段再用低階求積公式茵宪，稱為復(fù)合求積公式。常用的揖盘，復(fù)合梯形公式（折線段）眉厨，復(fù)合辛普森公式。

4.4 龍貝格求積公式

思路：實(shí)際計(jì)算時(shí)若精度不夠可將步長逐次分半兽狭，直到精度足夠?yàn)橹埂?/p>

理查森外推法：只要真值與近似值的誤差能表示成h的冪級(jí)數(shù)憾股，就能使用外推法提高精度。
例如箕慧， $T(h) = I + a_1 h^2 + a_2 h^4 + \cdots$ 服球，則可增加一些點(diǎn)將h減半得到 $T(h/2) = I + \frac{1}{4}a_1 h^2 + \frac{1}{16}a_2 h^4 + \cdots$ ，通過線性組合得到 $S(h) = \frac{4}{3} T(h/2) - \frac{1}{3} T(h) = I + b_1 h^4 + b_2 h^6 + \cdots$ 颠焦，誤差階數(shù)就從2階提高到了4階斩熊！

龍貝格算法：從復(fù)合梯形公式開始，不斷使用外推法伐庭，（計(jì)算有遞推公式）粉渠，直到精度足夠?yàn)橹埂?/p>

4.5 自適應(yīng)積分方法

回顧以上符合積分公式，對整個(gè)積分區(qū)域使用同樣的階數(shù)圾另，適用于被積函數(shù)變化不大的積分霸株。
對于在不同區(qū)域變化程度不同的函數(shù)，我們可以對不同區(qū)間使用不同的插值點(diǎn)數(shù)量（根據(jù)誤差自動(dòng)判斷集乔，龍貝格算法）去件，平坦的部分步長大，變化劇烈的部分步長小扰路，既減少運(yùn)算量又減少誤差尤溜。具體過程略。

4.6 高斯求積公式

以上我們都默認(rèn)等距節(jié)點(diǎn)汗唱，現(xiàn)在我們改變節(jié)點(diǎn)的位置宫莱，希望在不改變節(jié)點(diǎn)數(shù)量的情況下得到更高階的誤差，這就是高斯求積公式渡嚣。
如果求積公式（n+1個(gè)節(jié)點(diǎn)）具有2n+1次代數(shù)精度（n+1個(gè)節(jié)點(diǎn)的理論最高精度）梢睛，則稱其節(jié)點(diǎn)為高斯點(diǎn)，公式為高斯型求積公式识椰。

如何取高斯點(diǎn)绝葡？
由定理證明。腹鹉。藏畅。高斯點(diǎn)是正交多項(xiàng)式的零點(diǎn)。
性質(zhì)：高斯求積公式收斂，穩(wěn)定愉阎。

高斯-勒讓德求積公式：使用勒讓德多項(xiàng)式作為高斯求積公式需要的正交多項(xiàng)式绞蹦。
對于區(qū)間不是 $[-1,1]$ 的情況，做變換 $x=\frac{b-a}{2}t + \frac{a+b}{2}$ 即可榜旦。

高斯-切比雪夫求積公式：與上面類似幽七，應(yīng)對不同情況。
還有其他正交多項(xiàng)式溅呢。

注：高斯求積公式不一定要用到區(qū)間的端點(diǎn)澡屡，對一些在端點(diǎn)出趨于無窮的函數(shù)積分（反常積分）近似較好。

4.7 多重積分

寫成累次積分咐旧，化成一重積分的情況驶鹉。略。

4.8 數(shù)值微分

思路1：用差商近似導(dǎo)數(shù)铣墨，比如中點(diǎn)公式 $f'(a) \approx \frac{f(a+h) - f(a-h)}{2h}$ 室埋，誤差用泰勒展開計(jì)算。

思路2：插值型求導(dǎo)公式：先求 $f$ 的插值函數(shù) $P_n(x)$ 伊约，再用 $P'_n(x)$ 作為導(dǎo)數(shù)的近似值姚淆。

思路3：三次樣條求導(dǎo)。利用三次樣條函數(shù)導(dǎo)數(shù)值也收斂的性質(zhì)屡律，可作為數(shù)值微分的方法肉盹。

思路4：數(shù)值微分的外推算法，對思路1的改進(jìn)疹尾，略。

第5章解線性方程組的直接方法

5.1 引言與預(yù)備知識(shí)

線性方程組的系數(shù)矩陣可大致分為：低階稠密矩陣骤肛，大型稀疏矩陣（零元素多）纳本。
方法大致分兩種：直接法（對低階稠密矩陣有效），迭代法（對大型稀疏矩陣有效）腋颠。（本章只講前者）
特殊形式的矩陣（三角繁成，三對角等）有特殊方法。

概念：矩陣特征值淑玫，譜半徑巾腕，特殊矩陣，若當(dāng)型矩陣

5.2 高斯消去法

分為前代法和回代法兩步絮蒿，分別求解三角矩陣方程尊搬，LU分解（ $A=LU$ ）。具體可參考《數(shù)值線性代數(shù)》土涝。

約化的主元素都不為零（普通高斯消去法能進(jìn)行下去）的充要條件是佛寿，矩陣A的順序主子式都不為零。

對于約會(huì)的主元有零的情況：列主元消去法但壮，每次循環(huán)時(shí)增加一步行變換冀泻，可避免主元是零或接近零常侣，減少誤差。只要矩陣可逆就能計(jì)算下去弹渔，實(shí)用胳施。列主元的LU分解： $PA=LU$

5.3 矩陣三角分解法

普通的LU分解和列主元LU分解：上面提到了，具體步驟略肢专。

平方根法：對于對稱正定矩陣的專用方法舞肆。 $A=LDL^T=L_1L_1^T$ （楚列斯基分解）。具體步驟略鸟召。

追趕法：對于三對角矩陣的專用方法胆绊。具體步驟略。

特殊矩陣的專用方法比平凡的方法效果更好（時(shí)間欧募、空間復(fù)雜度低）压状，但適用范圍小。

5.4 向量和矩陣范數(shù)

度量跟继，為矩陣/向量的誤差分析做鋪墊种冬。

矩陣的算子范數(shù)/誘導(dǎo)范數(shù)：由向量范數(shù)擴(kuò)展到矩陣，具有相容性舔糖。也有不是算子范數(shù)的矩陣范數(shù)娱两，比如F范數(shù)（弗羅貝尼烏斯范數(shù)）。

有一些定理需要了解金吗。

5.5 誤差分析

病態(tài)方程組十兢、病態(tài)矩陣：對矩陣A或常數(shù)項(xiàng)b的變化敏感。條件數(shù)刻畫了病態(tài)程度摇庙。希爾伯特矩陣是病態(tài)矩陣旱物。若條件數(shù)計(jì)算不方便，也有幾條判斷病態(tài)的簡單方法卫袒。

面對病態(tài)問題宵呛，首先是列主元方法，若解決不了還可以采用高精度算術(shù)運(yùn)算或采用預(yù)處理方法夕凝。

第6章解線性方程組的迭代法

6.1 迭代法的基本概念

迭代法的格式： $x^{(k+1)} = Bx^{(k)} + f$ 宝穗。
先（任意）取一個(gè)初值 $x^{(0)}$ ，再有 $Ax=b$ 的A和b確定迭代格式码秉，不斷迭代逮矛，直到達(dá)到一定次數(shù)或誤差達(dá)到要求為止。
如果 $\lim _{k \rightarrow \infty } x^{(k)}$ 存在泡徙，則稱迭代法收斂橱鹏。

定義向量序列的極限和矩陣序列的極限。
$\lim _{k \rightarrow \infty }B^k=0$ 等價(jià)于 $\rho(B)<1$ 等價(jià)于B的某個(gè)范數(shù) $||B||<1$ 。

對于任意初值 $x^{(0)}$ 莉兰，迭代法 $x^{(k+1)} = Bx^{(k)} + f$ 收斂的充要條件是 $\lim _{k \rightarrow \infty }B^k=0$

迭代法收斂速度的度量：平均收斂速度挑围，漸進(jìn)收斂速度。

6.2 雅克比迭代法與高斯-賽德爾迭代法

對于 $Ax=b$ 糖荒，令 $A=D-L-U$ 杉辙，D為對角矩陣，L為下三交矩陣捶朵，U為上三角矩陣蜘矢。
則有 $Dx = (L+U)x+b$ ，即 $x = D^{-1}(L+U)x+D^{-1}b$ 综看，此為雅克比迭代法的迭代格式品腹。
用方程組表示，就是給定 $x^{(k)}$ 红碑，對每個(gè)元素 $x^{(k+1)}(i)$ 迭代時(shí)都使用 $x^{(k)}$ 的元素舞吭，全部算完再更新為 $x^{(k+1)}$ 。

類似的析珊，有 $(D-L)x = Ux+b$ 羡鸥，即 $x = (D-L)^{-1}Ux+(D-L)^{-1}b$ ，此為高斯-賽德爾迭代法的迭代格式忠寻。
用方程組表示惧浴，就是計(jì)算每個(gè)元素 $x^{(k+1)}(i)$ 盡可能使用最新的結(jié)果，即 $x^{k+1}(j)$ 和 $x^{k}(l)$ 奕剃， $\forall j<i, \forall l >i$ 衷旅。

收斂性：（可用迭代法收斂條件判斷）
概念：對角占優(yōu)矩陣，嚴(yán)格對角占優(yōu)矩陣纵朋，可約矩陣芜茵，不可約矩陣。
對角占優(yōu)定理：如果A為嚴(yán)格對角矩陣或不可約對角占優(yōu)矩陣倡蝙，則A為非奇異矩陣。
如果A為嚴(yán)格對角矩陣或不可約對角占優(yōu)矩陣绞佩，雅克比迭代法和高斯賽德爾迭代法均收斂寺鸥。

6.3 超松弛迭代法

高斯賽德爾迭代法的改進(jìn)，SOR超松弛迭代法品山。略胆建。

6.4 共軛梯度法

很重要！肘交！需要仔細(xì)看書笆载，在此就不細(xì)說了，只寫需要掌握的部分。

對于對稱正定矩陣A凉驻，考慮二次函數(shù) $\varphi:R^n \rightarrow R$
$\varphi(x) = \frac{1}{2}(Ax,x) - (b,x) = \frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n a_{ij}x_ix_j - \sum_{j=1}^n b_j x_j$
$\varphi(x)$ 是可導(dǎo)的凸函數(shù)腻要，其去最值的時(shí)候等價(jià)于梯度等于零，即 $\bigtriangledown \varphi(x) = Ax-b=0$
因此求解線性方程組的問題等價(jià)于求二次函數(shù)最小值的問題涝登，求解方法是構(gòu)造一個(gè)向量序列 $\{ x^{(k)} \}\$ 使二次函數(shù)趨向于最小值雄家。

最速下降法：每次迭代方向?yàn)?strong> $\varphi(x)$ 在 $x^{(k)}$ 處的梯度方向，確定方向后取**該方向上 $\varphi(x)$ 的最小值點(diǎn)為迭代結(jié)果 $x^{(k+1)}$ 胀滚。即以梯度方向?yàn)榈较蛱思茫儆镁€搜索確定步長。
計(jì)算：梯度：先求出梯度函數(shù)即可咽笼。線搜索：令導(dǎo)數(shù)等于零可求得步長顷编。
性質(zhì)：兩個(gè)相鄰的搜索方向正交，因此快接近最優(yōu)值時(shí)會(huì)出現(xiàn)鋸齒狀的路線剑刑，速度變慢媳纬。收斂速度與矩陣A的最大最小特征值的差有關(guān)，特征值越接近收斂速度越快叛甫。
速度并不快的方法层宫，但理論簡單，后續(xù)的方法都是在其上的改進(jìn)其监。

共軛梯度法（CG方法）：求解大型稀疏對稱正定方程組十分有效的方法萌腿。
思路：搜索方向從單純的梯度方向改進(jìn)為，在 $x^{(k)}$ 處梯度方向和上一步的收縮方向組成的平面抖苦，這樣需要兩個(gè)參數(shù)來確定步長毁菱。
性質(zhì)：誤差 $r^{(k)}:=Ax^{(k)}-b$ 序列是正交向量組，搜索方向 $p^{(k)}$ 序列是A-共軛向量組锌历。
由 $r^{(k)}$ 正交性贮庞，對n維線性方程組，理論上最多n步便可得到精確解究西，可以說CG方法是直接法窗慎；但由于舍入誤差，很難保證 $r^{(k)}$ 的正交性卤材，一般還是以誤差到達(dá)精度要求時(shí)終止遮斥，也可以說CG方法是迭代法。

共軛梯度法的細(xì)節(jié)可參考《數(shù)值線性代數(shù)》扇丛，它還有一些其他的性質(zhì)术吗。
目前討論的共軛梯度法是關(guān)于對稱正定矩陣A的，對于一般矩陣也可以稍加修改后使用帆精，具體參考《最優(yōu)化理論與方法》较屿。

第7章非線性方程與方程組的數(shù)值解法

7.1 方程求根與二分法

二分法：最樸素的方法隧魄，在函數(shù)連續(xù)且端點(diǎn)函數(shù)值異號(hào)的情況下，不斷壓縮區(qū)間長度直到達(dá)到精度要求為止隘蝎。

7.2 不動(dòng)點(diǎn)迭代法及其收斂性购啄。

若 $x = \varphi(x)$ ，則稱 $x$ 是 $\varphi(x)$ 的不動(dòng)點(diǎn)末贾。若迭代法收斂闸溃，則最終收斂到其不動(dòng)點(diǎn)。

不動(dòng)點(diǎn)的存在性與迭代法收斂性：不動(dòng)點(diǎn)存在唯一性定理：
若 $\varphi(x)$ 在 $[a,b]$ 連續(xù)拱撵，且 $a \le \varphi(x) \le b$ 辉川，且存在正常數(shù) $L<1$ 使 $\forall x,y \in [a,b]. |\varphi(x) - \varphi(y)| \le L |x-y|$ ，則 $\varphi(x)$ 在 $[a,b]$ 上存在唯一的不動(dòng)點(diǎn) $x^*$ 拴测。

局部收斂性：若 $varphi(x)$ 有不動(dòng)點(diǎn) $x^*$ 乓旗，如果存在不動(dòng)點(diǎn)附近的鄰域，使得當(dāng)初值在此鄰域中時(shí)迭代法一定收斂到不動(dòng)點(diǎn)集索，則稱迭代法局部收斂屿愚。
局部收斂的充分條件： $\varphi'(x)$ 在不動(dòng)點(diǎn)附近連續(xù)且絕對值小于1，則局部收斂务荆。

收斂速度：迭代誤差序列（一個(gè)無窮小量）的階數(shù)妆距，p階收斂。

7.3 迭代收斂的加速方法

已有迭代格式 $\varphi$ 函匕，通過一些變形得到新的迭代格式 $\phi[\varphi]$ 娱据，使新的迭代格式收斂速度（階數(shù)）加快。
埃特金加速收斂方法盅惜，斯特芬森迭代法中剩。

7.4 牛頓法

思路：利用導(dǎo)數(shù)（梯度）信息，對原函數(shù)線性化（泰勒展開）來近似抒寂，再求零點(diǎn)结啼。
$x_{k+1} = x_k - \frac{f(x_k}{f'(x_k)}$
有幾何解釋：切線法。
至少是二階收斂屈芜，優(yōu)點(diǎn)是收斂速度快郊愧，缺點(diǎn)是每一步計(jì)算量稍大（要計(jì)算導(dǎo)數(shù)值），而且對初值有要求（不是全局收斂井佑，需要初值在不動(dòng)點(diǎn)附近）
可以擴(kuò)展到高維情況糕珊，為了克服缺點(diǎn)有一些變種（簡化牛頓法，牛頓下山法）毅糟，重根情形可通過變形加速。

7.5 弦截法與拋物線法

以上是用前一個(gè)點(diǎn)迭代后一個(gè)點(diǎn)澜公，稱為單點(diǎn)迭代法姆另。
弦截法與拋物線法使用前幾個(gè)點(diǎn)計(jì)算后一個(gè)點(diǎn)喇肋，稱為多點(diǎn)迭代法，從而可以不使用導(dǎo)數(shù)信息且保持高階收斂速度迹辐。

7.6 求根問題的敏感性與多項(xiàng)式的零點(diǎn)

知道敏感性的意思即可蝶防。

求多項(xiàng)式的全部零點(diǎn)：以上方法只能求一個(gè)零點(diǎn)∶鞣裕可以每求一個(gè)零點(diǎn)间学，利用因式分解給原方程降次。推薦使用拋物線法印荔，可求復(fù)根低葫。

7.7 非線性方程組的數(shù)值解法

在一維的基礎(chǔ)上向高維推廣。使用向量范數(shù)代替誤差仍律，使用雅可比矩陣代替一維導(dǎo)數(shù)嘿悬，多變量方程的不動(dòng)點(diǎn)迭代法，不動(dòng)點(diǎn)存在唯一性定理（壓縮映射原理）水泉，p階收斂善涨，牛頓迭代法等。

第8章矩陣特征值計(jì)算

8.1 特征值性質(zhì)和估計(jì)

特征值的基本性質(zhì)草则，略钢拧。

格什戈林圓盤定理：設(shè) $A = (a_{ij})_{n*n}$ 岖是，則 $A$ 的每一個(gè)特征值必屬于下述某個(gè)圓盤之中：
$| \lambda - a_{ii} | \leq r_i = \sum_{j=1,j\not= i}^n | a_{ij}|, \;\;\;\; i=1,2,\cdots,n$
或者說巡揍， $A$ 的特征值都在復(fù)平面上n個(gè)圓盤的并集中。
如果 $A$ 有 $m$ 個(gè)圓盤組成一個(gè)連通的并集 $S$ 揖膜，且 $S$ 與余下的 $n-m$ 個(gè)圓盤是分離的看锉，則 $S$ 內(nèi)恰包含 $A$ 的 $m$ 個(gè)特征值姿锭。

圓盤定理可初步估計(jì)特征值的范圍。

8.2 冪法及反冪法

冪法是一種計(jì)算矩陣主特征值（模最大的特征值）及其特征向量的迭代方法伯铣，適用于大型稀疏矩陣呻此。
類似的，反冪法計(jì)算模最小的特征值及其特征向量腔寡，用于計(jì)算海森伯格矩陣或三對角陣的對于一個(gè)給定近似特征值的特征向量焚鲜。

冪法：原理和編程都很簡單，看書即可放前。前提：模最大的特征值只有一個(gè)（不是重特征值）忿磅。

加速方法：
1.原點(diǎn)平移法，引進(jìn)矩陣 $B=A-pI$ 凭语，B是A的平移葱她，特征值也對應(yīng)平移且特征向量不變，可以改變模最大的特征值似扔、收斂速度吨些。缺點(diǎn)：p的確定困難搓谆。
2.瑞利商加速。

反冪法：計(jì)算 $A$ 的模最小特征值豪墅，等價(jià)于計(jì)算 $A^{-1}$ 的模最大特征值的倒數(shù)泉手。（實(shí)際上不需要計(jì)算 $A^{-1}$ ，只有解線性方程組即可）
若已知某個(gè)特征值的近似值 $p$ （由其他方法求出）偶器，可以對矩陣平移 $B=A-pI$ 斩萌，則 $B$ 就有一個(gè)接近0的特征值，可使用反冪法求這個(gè)值和特征向量屏轰，也就是求得原矩陣 $A$ 的更精確的特征值和對應(yīng)的特征向量颊郎。

8.3 正交變換與矩陣分解

正交變換是計(jì)算矩陣特征值的有力工具，一般可以先通過正交變換將矩陣變?yōu)樯先蔷仃嚮蚪粕先堑木仃囃ぜ希儆玫焖偾蟪鏊刑卣髦担≦R方法）袭艺。
本節(jié)介紹豪斯霍爾德(Householder)變換和吉文斯(Givens)變換

豪斯霍爾德變換：思路：使用反射，將 $x$ 反射到 $e_1$ 叨粘。計(jì)算量稍大猾编，但一次改變向量的所有分量。

吉文斯變換：思路：使用旋轉(zhuǎn)升敲，將 $(\cdots,x_i,\cdots,x_j,\cdots)$ 旋轉(zhuǎn)到 $(\cdots,1,\cdots,0,\cdots)$ 答倡。計(jì)算量較小，但一次只改變兩個(gè)分量驴党。

矩陣的QR分解和舒爾分解
QR分解：設(shè)n階方陣A非奇異瘪撇，則可以通過一系列變換（比如n-1次豪斯霍爾德變換）將其變?yōu)樯先顷嚕?img class="math-inline" src="https://math.jianshu.com/math?formula=PA%3DR" alt="PA=R" mathimg="1">港庄，其中P為正交矩陣倔既，R為上三角矩陣。因此令 $Q=P^{-1}$ 鹏氧，就有 $A=QR$ 的分解渤涌。我們只需再求上三角矩陣R的特征值，就可以得到A的特征值把还。
性質(zhì)：對n階非奇異方陣A实蓬，QR分解存在且當(dāng)R對角元為正時(shí)唯一。

實(shí)舒爾分解：解決實(shí)矩陣的復(fù)特征值問題吊履，實(shí)矩陣可以約化為上海森伯格矩陣（上三角和對角線元素的下面一個(gè)元素可以非零安皱，其余是零）。
$Q^TAQ = R$
R為類上三角矩陣艇炎，其對角塊 $R_{ii}$ 為一階或二階方陣酌伊。一階對應(yīng)實(shí)特征值，二階對應(yīng)兩個(gè)共軛復(fù)特征值缀踪。計(jì)算Q的方法也是使用正交變換居砖。

8.4 QR方法

QR方法是一種變換方法燕锥，是計(jì)算一般矩陣（中小型矩陣）全部特征值問題的最有效按方法之一。
對一般矩陣悯蝉，先用豪斯霍爾德方法將A化為上海森伯格矩陣B，再用QR方法計(jì)算B的全部特征值（托慨，再使用反冪法提高精度并求出對應(yīng)的特征向量）鼻由。
迭代過程：對 $A_k$ 做QR分解： $A_k=Q_kR_k$ ，再令 $A_{k+1}=R_kQ_K = Q_k^T R_kQ_k$ 厚棵。

具體細(xì)節(jié)蕉世，比如迭代法何時(shí)終止的判定，略婆硬。
還有在其基礎(chǔ)上的改進(jìn)狠轻，比如帶原點(diǎn)位移的QR方法，隱式QR方法彬犯，比較復(fù)雜向楼，略。

第9章常微分方程初值問題數(shù)值方法

9.1 引言

常微分方程初值問題：
$y' = f(x,y),\;\;\;\; x\in [x_0,b] \\ y(x_0) = y_0$
稱方程的解 $y(x)$ 為積分曲線谐区。

李普希茲條件：如果存在實(shí)數(shù) $L>0$ 湖蜕，使得
$| f(x,y_1) - f(x,y_2) | \le L | y_1 -y_2|, \;\;\;\; \forall y_1,y_2 \in R$
則稱 $f$ 關(guān)于 $y$ 滿足李普希茲條件。
這個(gè)條件用于常微分方程解的存在唯一性宋列，具體參考《常微分方程》昭抒。在本章中也用于數(shù)值方法的收斂性證明。

對于常微分方程初值問題的數(shù)值方法炼杖，就是尋求一系列離散節(jié)點(diǎn) $x_1<x_2<\cdots<x_n<\cdots$ 上的近似值 $y_1<y_2<\cdots<y_n<\cdots$
為了簡便灭返，我們?nèi)?img class="math-inline" src="https://math.jianshu.com/math?formula=x_i%20%3D%20x_0%20%2B%20i*h" alt="x_i = x_0 + i*h" mathimg="1">的等距節(jié)點(diǎn)， $h$ 稱為步長坤邪。

一般使用前面的點(diǎn)（已知的或已求出近似值的）來計(jì)算后面的點(diǎn)熙含。使用前一個(gè)點(diǎn)的叫做單步法，使用前n個(gè)點(diǎn)的叫做多步法罩扇，這和7.5節(jié)中的多點(diǎn)迭代法類似婆芦。
本章我們需要研究的問題有：計(jì)算方法（公式），公式的局部階段誤差和階喂饥，誤差估計(jì)及收斂性消约，穩(wěn)定性。

9.2 簡單的數(shù)值方法

理論上有 $y_{n+1} = y_n + \int_{x_n}^{x_{n+1}} y'(x)dx = y_n + \int_{x_n}^{x_{n+1}} f(x,y(x))dx$

歐拉法： $y_{n+1} = y_n + hf(x_n,y_n)$ 员帮，即使用左矩形公式計(jì)算數(shù)值積分或粮， $\int_{x_n}^{x_{n+1}} f(x,y(x))dx \approx hf(x_n,y_n)$ 。
這是最簡單的思路最清晰的方法捞高，計(jì)算量小氯材，當(dāng)然誤差也比較大（截?cái)嗾`差相當(dāng)于數(shù)值積分的誤差）渣锦。
這是一個(gè)不需要解方程就可以直接計(jì)算的方法，即 $y_{n+1} = y_n + hf(x_n,y_n)$ 等號(hào)右邊沒有未知量氢哮，這樣的方法稱為顯式方法袋毙。

后退歐拉法（隱式歐拉法）： $y_{n+1} = y_n + hf(x_{n+1},y_{n+1})$ ，思路與歐拉法相同冗尤，使用右矩形公式計(jì)算數(shù)值積分听盖。此時(shí)等號(hào)右邊有未知量，需要通過解方程來求得 $y_{n+1}$ 裂七，這樣的方法稱為隱式方法皆看，類似于隱函數(shù)和顯函數(shù)的關(guān)系。
本方法的收斂性證明用到李普希茲條件
一般來說背零，隱式方法雖然計(jì)算量稍大腰吟，但穩(wěn)定性好。

梯形方法：類似的徙瓶，可以使用梯形公式計(jì)算數(shù)值積分毛雇。

改進(jìn)歐拉公式：每次遞推分成兩部：先用歐拉公式求得“預(yù)測值”，再用梯形公式求得“校正值”倍啥，將梯形公式的隱式方法改為了兩部顯式計(jì)算禾乘，減少了計(jì)算量。

局部截?cái)嗾`差：加上目前的數(shù)據(jù)是正確的虽缕，下一個(gè)節(jié)點(diǎn)的數(shù)值解和精確值的差稱為局部截?cái)嗾`差始藕，以此來度量算法的收斂性和收斂速度。一般局部截?cái)嗾`差與步長 $h$ 相關(guān)氮趋，即步長越小誤差越小伍派，若與 $h^{p+1}$ 線性相關(guān)則稱為p階精度。

9.3 龍格-庫塔方法

為了提高精度而增加了使用的點(diǎn)剩胁，增多的是 $[x_n,x_{n+1}]$ 內(nèi)的點(diǎn)诉植，不是 $x_n$ 之前的節(jié)點(diǎn)，因此還是單步法昵观。類似改進(jìn)的歐拉法晾腔，公式如下;
$y_{n+1} = y_n + h\varphi(x_n,y_n,h) \\ \varphi(x_n,y_n,h) = \sum_{i=1}^r c_i K_i \\ K_1 = f(x_n,y_n) \\ K_i = f \left (x_n+\lambda_i h, y_n+h \sum_{j=1}^{i-1}\mu_{ij}K_j \right)$
稱為 $r$ 階顯式龍格庫塔法，簡稱RK法啊犬， $c_i,\lambda_i,\mu_{ij}$ 都是常參數(shù)灼擂。其中 $r=1$ 時(shí)即為歐拉法， $r=2$ 時(shí)的一種為改進(jìn)的歐拉法觉至。

二階顯式R-K方法：以二階為例說明參數(shù)的選擇：希望確定這些參數(shù)使得p階數(shù)盡量高剔应，可使用待定系數(shù)法，使用泰勒公式并令幾個(gè)低階的誤差項(xiàng)參數(shù)為零，從而得到幾個(gè)方程峻贮，解得參數(shù)席怪。由于方程的解不一定唯一，參數(shù)不唯一纤控。
三階挂捻、四階類似。四階顯式龍格庫塔方法比較常用船万。
由于龍格庫塔方法的推導(dǎo)基于泰勒展開细层，因而它要求解具有較好的光滑性。

變步長的龍格庫塔方法：略唬涧。

9.4 單步法的收斂性與穩(wěn)定性

收斂性：步長趨于0時(shí)誤差也趨于0，則稱為具有收斂性盛撑。

定理：若單步法具有p階精度且增量函數(shù) $\varphi(x,y,h)$ 關(guān)于 $y$ 滿足李普希茲條件碎节，初值也準(zhǔn)確，則 $y(x_n) - y = O(h^p)$ 抵卫，整體截?cái)嗾`差p階收斂狮荔。
因此，一般通過判斷是否符合李普希茲條件來判斷是否收斂介粘。

穩(wěn)定性：若計(jì)算出現(xiàn)的微小誤差不會(huì)惡性增長以至于“淹沒”真解殖氏，則稱具有穩(wěn)定性。
而穩(wěn)定性不僅與方法有關(guān)姻采，有時(shí)也與h的取值范圍有關(guān)（在《偏微分方程數(shù)值解》中體現(xiàn)比較明顯雅采，有的方法是全局收斂，有的方法是條件收斂慨亲，即必須步長/步長比較小時(shí)才收斂）婚瓜，收斂時(shí)h的取值范圍叫做絕對穩(wěn)定域/絕對穩(wěn)定區(qū)間。

9.5 線性多步法

思想：充分利用前面多步的節(jié)點(diǎn)值信息來預(yù)測下一個(gè)節(jié)點(diǎn)的值刑棵，期望會(huì)獲得較高的精度巴刻。
方法：基于數(shù)值積分的方法或基于泰勒展開的方法。

線性多步法的一般公式：
$y_{n+k} = \sum_{i=0}^{k-1} \alpha_i y_{n+i} +h\sum_{i=0}^k \beta_i f_{n+i}$
類似龍格庫塔公式蛉签，可以使用待定系數(shù)法和泰勒展開確定參數(shù)胡陪。

阿當(dāng)姆斯顯式與隱式公式：公式如下
$y_{n+k} = y_{n+k-1} + h\sum_{i=0}^k\beta_if_{n+i}$
其中 $\beta_k=0$ 時(shí)為顯式方法，反之為隱式方法碍舍。也稱為阿當(dāng)姆斯-巴什福斯（AB）公式或阿當(dāng)姆斯-蒙爾頓（AM）公式柠座。可通過泰勒展開并求解線性方程組確定其系數(shù)乒验。

還有其他的線性多步法公式愚隧，比如米爾尼方法，辛普森方法，漢明方法等狂塘。

預(yù)測校正方法：類似改進(jìn)的歐拉方法录煤，分為預(yù)測（顯式公式）和校正（隱式公式）兩步的多步方法，比如阿當(dāng)姆斯四階預(yù)測校正格式(PECE)荞胡。

一般先用四階龍格庫塔方法（單步法里最常用的妈踊，效果較好但計(jì)算量大）算出開始的幾個(gè)點(diǎn)，之后使用多步預(yù)測校正方法（計(jì)算量欣崞）廊营。

9.6 線性多步法的收斂性與穩(wěn)定性

類似的，分為收斂性和穩(wěn)定性萝勤，略露筒。

9.7 一階方程組與剛性方程組

略。