常用算法程序集（C++描述）（第7版）

目錄

第1章基本運算1

1.1復數運算1

1.2實系數多項式運算9

1.2.1實系數多項式類9

1.2.2實系數多項式求值11

1.2.3實系數多項式相乘12

1.2.4實系數多項式相除14

1.3復系數多項式運算16

1.3.1復系數多項式類16

1.3.2復系數多項式求值18

1.3.3復系數多項式相乘20

1.3.4復系數多項式相除21

1.4隨機數23

1.4.1隨機數類23

1.4.2產生0～1均勻分布的一個隨機數24

1.4.3產生給定區間［a，b］上均勻分布的一個隨機整數24

1.4.4產生給定均值μ與方差σ2的正態分布的一個隨機數25

1.5特殊函數27

1.5.1特殊函數類27

1.5.2伽馬函數28

1.5.3不完全伽馬函數30

1.5.4誤差函數33

1.5.5第一類整數階貝塞爾（Bessel）函數34

1.5.6第二類整數階Bessel函數39

1.5.7變型第一類整數階Bessel函數44

1.5.8變型第二類整數階Bessel函數48

1.5.9不完全貝塔（beta）函數51

1.5.10正態分布函數54

1.5.11t分布函數56

1.5.12χ2分布函數57

1.5.13F分布函數58

1.5.14正弦積分60

1.5.15余弦積分61

1.5.16指數積分63

1.5.17第一類橢圓積分65

1.5.18第二類橢圓積分68

第2章矩陣運算71

2.1實矩陣運算71

2.1.1實矩陣運算類71

2.1.2實矩陣相乘74

2.1.3實矩陣求逆75

2.1.4對稱正定矩陣的求逆78

2.1.5托伯利茲矩陣求逆的特蘭持方法80

2.1.6求行列式的值83

2.1.7求矩陣的秩85

2.1.8對稱正定矩陣的喬裏斯基分解87

2.1.9實矩陣的三角分解89

2.1.10實矩陣的QR分解91

2.1.11實矩陣的奇異值分解94

2.1.12求廣義逆的奇異值分解法105

2.2復矩陣運算107

2.2.1復矩陣運算類107

2.2.2復矩陣相乘110

2.2.3復矩陣求逆112

2.3矩陣特征值與特征向量114

2.3.1矩陣特征值類114

2.3.2約化對稱矩陣為對稱三對角陣的豪斯荷爾德變換法116

2.3.3求對稱三對角陣的全部特征值與特征向量120

2.3.4約化一般實矩陣為赫申伯格矩陣的初等相似變換法123

2.3.5求赫申伯格矩陣全部特征值的QR方法126

2.3.6求實對稱矩陣特征值與特征向量的雅可比法131

2.3.7求實對稱矩陣特征值與特征向量的雅可比過關法137

2.3.8乘冪法140

第3章線性代數方程組144

3.1實系數線性代數方程組144

3.1.1線性方程組類144

3.1.2求解方程組的全選主元高斯消去法147

3.1.3求解方程組的全選主元高斯約當消去法150

3.1.4求解三對角線方程組的追趕法153

3.1.5求解對稱方程組的分解法155

3.1.6求解對稱正定方程組的平方根法158

3.1.7求解托伯利茲方程組的列文遜方法160

3.1.8高斯賽德爾疊代法165

3.1.9求解對稱正定方程組的共軛梯度法167

3.1.10求解病態方程組170

3.2復系數線性代數方程組173

3.2.1復系數方程組類173

3.2.2全選主元高斯消去法176

3.2.3全選主元高斯約當消去法179

3.3求解線性最小二乘問題181

3.3.1線性最小二乘問題類181

3.3.2求解線性最小二乘問題的豪斯荷爾德變換法183

3.3.3求解線性最小二乘問題的廣義逆法186

第4章非線性方程與方程組的求解188

4.1非線性方程188

4.1.1非線性方程類188

4.1.2方程求根的埃特金疊代法188

4.1.3方程求根的牛頓疊代法190

4.1.4方程求根的試位法192

4.2非線性方程組194

4.2.1非線性方程組類194

4.2.2求非線性方程組一組實根的梯度法195

4.2.3求非線性方程組一組實根的擬牛頓法197

4.2.4求非線性方程組最小二乘解的廣義逆法202

4.3代數方程206

4.3.1代數方程類206

4.3.2求實系數代數方程全部根的QR方法207

4.3.3求復系數代數方程全部根的牛頓下山法209

4.4蒙特卡洛法214

4.4.1蒙特卡洛法類214

4.4.2求非線性方程一個實根的蒙特卡洛法215

4.4.3求非線性方程組一組實根的蒙特卡洛法217

4.4.4求實函數或復函數方程一個復根的蒙特卡洛法219

第5章插值與逼近222

5.1一元插值222

5.1.1一元插值類222

5.1.2拉格朗日插值224

5.1.3連分式插值226

5.1.4埃特金逐步插值230

5.1.5埃爾米特插值232

5.1.6光滑插值234

5.2三次樣條函數插值、微商與積分238

5.2.1三次樣條插值類241

5.2.2第1種邊界條件244

5.2.3第2種邊界條件246

5.2.4第3種邊界條件249

5.3擬合與逼近253

5.3.1擬合與逼近類253

5.3.2最小二乘曲線擬合255

5.3.3切比雪夫曲線擬合260

5.3.4最佳一致逼近的裏米茲方法264

5.4二元插值與擬合268

5.4.1二元插值與擬合類268

5.4.2二元插值271

5.4.3矩形域的最小二乘曲面擬合274

第6章數值積分281

6.1一維積分281

6.1.1一維積分類281

6.1.2變步長梯形求積法282

6.1.3變步長辛蔔生求積法284

6.1.4自適應梯形求積法286

6.1.5龍貝格求積法288

6.1.6高振蕩函數求積法290

6.1.7勒讓德高斯求積法294

6.1.8拉蓋爾高斯求積法296

6.1.9埃爾米特高斯求積法298

6.1.10切比雪夫求積法300

6.1.11計算一維積分的蒙特卡洛法302

6.2多重積分303

6.2.1多重積分類303

6.2.2變步長辛蔔生二重積分法304

6.2.3計算多重積分的高斯方法307

6.2.4計算多重積分的蒙特卡洛法311

第7章常微分方程組的求解313

7.1積分一步313

7.1.1積分一步類313

7.1.2變步長歐拉方法315

7.1.3變步長龍格庫塔方法318

7.1.4變步長基爾方法320

7.1.5變步長默森方法324

7.1.6變步長特雷納方法327

7.1.7變步長維梯方法332

7.2全區間積分334

7.2.1全區間積分類334

7.2.2雙邊法337

7.2.3阿當姆斯預報校正法340

7.2.4哈明方法342

7.3剛性方程組345

7.3.1剛性方程組類345

7.3.2積分剛性方程組的吉爾方法348

7.4二階初值問題362

7.4.1二階初值問題類362

7.4.2求解二階初值問題的歐拉方法363

7.5二階邊值問題367

7.5.1二階邊值問題類367

7.5.2求解二階邊值問題的差分法368

7.5.3求解二階邊值問題的試射法371

第8章連分式算法376

8.1連分式算法類376

8.2求方程一個實根的連分式法379

8.3計算一維積分的連分式法382

8.4計算二重積分的連分式法385

8.5求解一階初值問題的連分式法389

8.6求解二階初值問題的連分式法395

8.7求解二階邊值問題的連分式法398

8.8一維極值連分式法404

8.9n維極值連分式法407

第9章數據處理與分析411

9.1隨機樣本分析411

9.2一元回歸417

9.2.1一元回歸類417

9.2.2一元線性回歸418

9.2.3半對數數據相關421

9.2.4對數數據相關422

9.3多元回歸424

9.3.1多元回歸類424

9.3.2多元線性回歸426

9.4逐步回歸430

9.4.1逐步回歸類430

9.4.2逐步線性回歸434

9.5邏輯回歸440

9.5.1邏輯回歸類440

9.5.2線性邏輯回歸443

9.5.3非線性決策邊界448

9.5.4樣本標準化452

9.6數據排序455

9.6.1數據排序類455

9.6.2冒泡排序455

9.6.3快速排序456

9.6.4希爾排序458

9.6.5堆排序459

第10章極值問題的求解465

10.1線性規劃問題465

10.1.1線性規劃類465

10.1.2不等式約束線性規劃問題467

10.2單形調優法473

10.2.1單形調優類473

10.2.2n維極值的單形調優法474

10.3復形調優法479

10.3.1復形調優類479

10.3.2約束條件下n維極值的復形調優法481

第11章數學變換與濾波489

11.1傅裏葉級數逼近489

11.1.1Fourier級數類489

11.1.2傅裏葉級數逼近算法491

11.2快速傅裏葉變換494

11.2.1Fourier變換類494

11.2.2快速傅裏葉變換算法497

11.3快速沃爾什變換503

11.3.1沃爾什變換類503

11.3.2快速沃爾什變換算法504

11.4五點三次平滑506

11.4.1平滑類506

11.4.2五點三次平滑算法508

11.5αβγ濾波509

11.5.1ABG濾波類509

11.5.2αβγ濾波算法512

11.6卡爾曼濾波515

11.6.1卡爾曼濾波類515

11.6.2離散隨機線性系統的卡爾曼濾波算法518

參考文獻524