第一章课程引言

广义地说，数值分析是数学的一个分支，是研究用计算机解决数学问题的数值方法及理论，其包含函数的数值逼近、数值微分与数值积分、数值线性代数、非线性方程（组）数值解、微分方程数值解等内容，而且在大数据和人工智能蓬勃兴起的今天，其内涵与外延越来越丰富。本章介绍《数值分析》课程开设的背景和意义，以及它在科学发展史上所起的作用，并给出一些基本概念。毋容置疑，《数值分析》课程是数学和工程类本科生和研究生一门十分重要的专业核心课程。

●1.1引言

本节介绍《数值分析》课程的背景、开课目的和在科学工程计算中其所起的作用。而广义的数值分析是研究用计算机解决数学问题的数值方法及理论。《数值分析》课程是科学计算最重要的基础课。

●1.2误差分析

在“数值分析”中，在给出求解问题的算法后，考察算法的误差十分关键。理想或者可控的误差令人“放心”，不理想或者无法控制的误差，可能带来“差之毫厘，失之千里”的错误结果，因此在算法设计中有必要分析和控制“误差”的传播！

第二章函数逼近：插值法

许多描写实际问题内在规律的数量关系都可用函数y=f(x)表示，但其具体表达式往往非常复杂，且部分函数只能通过实验或观测得到，即只能获得一系列点上的函数值 ，希望找到一个简单易算的函数P(x)，使得，若成功，则称P(x)为插值函数。根据P(x)的不同类型，插值法可分为多项式插值、分段插值、三角插值等。本章只讨论多项式插值，但对其他类型插值具有指导意义。
本章将给出多项式插值的存在唯一性、拉格朗日插值、牛顿插值、分段线性插值等，并讨论其误差估计或者收敛性。

●2.1插值的定义与插值的存在唯一性

人们习惯于用函数来表示诸多实际问题的内在联系或规律，但很多函数只能通过实验或者观测来得到某些特殊点上的值，那如何获得非观测点上的函数值呢?插值就是一种重要手段，其做法是在某个简单函数类中找到一个函数，使其恰好在各个观测点上等于观测到的函数值，若这个简单函数类是多项式集合，则称为多项式插值。当观测数据对为n+1时，可用待定系数法证明在n次多项式空间中插值的唯一性。

●2.2Lagrange插值多项式

上一节用来证明多项式插值存在唯一性的待定系数法，用来计算插值不可取，而拉格朗日插值是基于基函数法求得多项式插值的一种方式，其思想具有普适性。拉格朗日插值可以看做过两点的直线方程两点式的推广。

●2.3Lagrange插值余项

插值的表现如何？其余项是一个重要指标。本节通过反复利用Rolle定理，在被插值函数足够光滑的前提下，获得拉格朗日插值余项公式。

●2.4差商及其性质

基于过两点的直线方程点斜式，一般多项式插值的表达式如何？经过观察。引出差商的定义，并讨论起性质，给出差商表。

●2.5Newton插值多项式

基于上一个知识点中差商及其性质，推导出牛顿插值多项式。尽管由插值的唯一性，拉格朗日插值和牛顿插值相等，但后者的优势是：在增加插值点时，可以充分利用前面的结果，而且对被插值函数的光滑性和是否有解析表达式不做要求，因此从计算效率到数学要求，都比前者有较大改进。

●2.6分段线性插值多项式

基于等距节点的高次拉格朗日插值具有龙格现象，即插值多项式次数增加时计算效果未必好，而当次数趋于无穷时插值不收敛到被插值函数。为了克服这一现象，引出分段低次插值。值得指出的是：“化整为零”是数值分析中常用的手段。

第三章 函数逼近： 最佳逼近、最小二乘

自然和社会科学中经常涉及函数的计算问题，但当函数非常复杂或只是在有限点集上给定了函数值时,如何方便地计算所有点上的函数值，皆涉及在区间[a,b]上用简单函数逼近复杂函数，这就是所谓的函数逼近问题。第二章所讨论的插值法是函数逼近问题的一种，但存在“厚此薄彼”的可能和所谓的龙格现象。本章讨论的函数逼近是指：对函数类A中给定的函数f(x)，要求在另一类简单的便于计算的函数类B中求函数p(x)∈B，使p(x)与f(x)的误差在某种度量意义下最小。函数类A通常是区间[a,b]上的连续函数，记作C[a,b]，称为连续函数空间，而函数类B通常为n次多项式、有理函数或分段低次多项式的集合等。本章主要讲授最佳平方逼近、正交多项式、最小二乘拟合和快速Fourier变换。

●3.1函数逼近简介

函数逼近是数值分析的重要基础，本节介绍函数逼近的基本原理及基本概念。为了方便更精确地进行描述，需要引进范数与赋范线性空间的定义。对不同的范数（度量），逼近问题的提法有区别，但其基本思想一致。函数逼近体现了数值计算中一个重要原则：复杂的问题简单化。

●3.2内积空间

最佳平方逼近是最受欢迎的函数逼近方法，作为其铺垫，需要引进内积和内积空间，事实上其可看做解析几何中欧氏空间数量积的一个推广。连续函数空间作为内积空间，具有某些很好的性质。

●3.3函数的最佳平方逼近

本节研究最佳平方逼近问题解的存在唯一性，并证明其等价于求解一个法方程，从而归结为线性代数方程组的求解。并给出了一个重要的正交关系。

●3.4正交多项式：正交化手续

用{1, x, x2,…, xn}作基求最佳平方逼近多项式，当n较大时，系数矩阵高度病态，使得计算陷入困境。若用正交多项式作基，则可完全避免病态。那么，能否/如何由一组给定的线性无关基函数构造出正交函数族？为此，本节引入正交化手续，给出相应正交多项式的优美性质，并简单介绍几类重要的正交多项式。

●3.5正交多项式：Legendre 多项式

Legendre多项式是最简单也是最重要的一类正交多项式，本节给出其表达式和相关性质。

●3.6函数按正交多项式展开

函数按正交多项式展开得到的级数称为广义Fourier级数，其部分和即为最佳平方逼近函数。用这种方法计算最佳平方逼近不需要解线性方程组，避免病态，而且当增加基函数时，只要计算增加的那些项的系数。成功实现了算法设计的目标：既要马儿跑，又要马儿少吃草。

●3.7最小二乘拟合

考虑从一组给定数据 (xi, yi) (i = 0,1,...,m) 中寻找自变量x与因变量y之间的函数关系y = F(x)可以用插值，但存在龙格现象。由于观测数据往往不准确，因此不必强求F(x)经过所有观测点，从而造成“顾此薄彼”，而只要求在给定点{xi}上误差按Euclid范数最小，这样更加“公平”，这就是本节要讨论的最小二乘拟合问题，也被称为离散型最佳平方逼近，是工程上广泛使用的一类数值拟合方法。

●3.8离散 Fourier 变换

对于周期函数，用三角多项式比用代数多项式逼近更合理。本节讨论用三角多项式作最佳平方逼近，并介绍离散Fourier变换及其在数字信号处理中的应用。

●3.9快速 Fourier 变换

按离散Fourier变换的定义式直接计算全部系数计算复杂度为O(N2)。本节讲授实现离散Fourier变换的一类快速算法——快速Fourier变换 (FFT)，其计算复杂度降为 O(N log2 N)。

第四章数值积分与数值微分

定积分与导数的计算是微积分中两种最重要也最常用的运算，但当被积函数的解析式未知或其原函数无法解析求出时，计算定积分的牛顿-莱布尼茨公式遇到困难。本章主要基于插值的思想，讨论几类有效的数值积分和微分公式。
本章将介绍数值积分的基本思想和概念、插值型求积公式及相应的几种常用的数值求积公式，其中引进了“化整为零”的思想得到复化求积公式，而龙伯格算法源自于一种重要的数学思想--外推法，事实上外推法最早在刘徽的割圆术中已被采用，也是我国古代数学家的成就之一。此外，基于插值和泰勒展式，给出几类数值微分公式。

●4.1数值求积的基本思想与概念

本节从数学分析中计算定积分的一些直观的近似公式出发，引出数值求积公式的基本思想和可行性，给出其代数精度、收敛性和稳定性等关键概念。并通过举例说明：适当地选取求积公式中的积分点和积分系数，可有效提高相应数值求积公式精度

●4.2插值型求积公式

基于插值的思想，用被积函数的拉格朗日插值多项式来代替被积函数，从而得到一类数值求积公式，此即插值型求积公式，并进一步得到了其余项表达式，进而证明：n阶数值求积公式至少具有n次代数精度的充要条件为它是插值型的。

●4.3Newton-Cotes公式

Newton-Cotes 公式是基于等距节点的一类插值型求积公式，但有其特殊性。
本节推导其一般形式，给出Cotes系数的性质，证明了偶数阶Newton-Cotes 求积公式的一个重要性质，从而阐明了为什么实际应用中偶数阶Newton-Cotes 公式更受青睐。鉴于其简单和有效，着重介绍了梯形公式与辛普森公式及其余项表达式。

●4.4复化求积公式

既然分段插值有其独特的优势，插值型求积公式作为插值的一个应用，为提高梯形公式与辛普森公式的精度，本节同样根据“化整为零”的思想，用分段插值代替被积函数，从而引进复化求积公式，特别是给出了复化梯形公式、复化辛普森公式及其余项表达式。

●4.5Romberg算法

为进一步提高复化求积公式的精度与效率，本节首先给出逐次分半的复化梯形公式间的递推公式，以减少计算量。然后基于外推的思想，由逐次分半的复化梯形，通过外推分别得到复化辛普森公式、复化柯特斯公式等，此即龙伯格（Romberg）算法，并通过程序演示以展示Romberg 算法的效率。值得指出的是，我国古代数学家刘徽在其割圆术研究中就已采用了外推的思想。

●4.6Gauss型求积公式

本节学习具有最高阶代数精度的数值求积公式---高斯型求积公式。针对其积分点（即高斯点）用待定系数法难以获取的困难，通过证明高斯点就是某类正交多项式的零点，从而成功地将求高斯点的问题转变成计算正交多项式的零点，再次展示了正交多项式的美与有用。

●4.7Gauss公式的余项、收敛性及稳定性

衡量某种数值方法的优劣，其余项的确定至关重要，本节利用埃尔米特插值得出高斯求积公式的余项。并进一步证明了其收敛性和稳定性。至此，“高斯型求积公式是最理想的求积公式”，名至实归！

●4.8Gauss-Legendre积分公式

本节首先给出计算标准区间上的积分的高斯-勒让德求积公式，其要点是n阶高斯-勒让德公式的积分点（高斯点）是n+1次勒让德多项式的零点，而且在文献中此类公式的积分点和积分系数可以由标准的计算机程序自动产生。在此基础上讨论了一般区间上的（复化）高斯-勒让德公式，并通过具体数例展示了高斯-勒让德公式的效率。

●4.9数值微分

本节介绍差商型求导和插值型求导两种数值微分方法，对某些常用公式，两种方法殊途同归。前者基于泰勒展式，后者用拉格朗日插值多项式的各阶导数来近似函数的各阶导数，其思想与插值型求积公式如出一辙！对插值型求导，将给出带余项的两点公式、三点公式及五点公式。

第五章非线性方程的求解

自然和社会科学中的许多问题都可归结为非线性方程的求解，其中是某个非线性函数。由于采用解析方法获得非线性方程的准确解非常困难或者甚至不可能，因此发展具有理论保证的迭代法就是求解非线性方程数值解的首选。
本章主要讲授二分法、不动点迭代法、牛顿迭代法、弦截法等多种数值方法，并力图向听众传达数值计算的一种重要思想：非线性问题线性化，复杂的问题简单化。

●5.1根的搜索

二分法体现的是一种朴素的数学思想，也是一种求解非线性方程的直观方法。其基本思想是：通过判断有根区间中点的函数值符号来逐步将其分半，直到有根区间的长度缩小到给定的精度，这些区间的中点必将收敛到一点，此即为方程的一个根。

●5.2迭代法

不动点迭代法的基本思想是将f(x)=0改写为适当的等价形式x=φ(x),从而将求原方程的解转化为计算φ(x)的不动点，并以此构造不动点迭代格式，其收敛性依赖于迭代函数φ(x)和初值的选择。

●5.3Newton法

牛顿迭代法是不动点迭代，其将非线性方程f(x)=0中的非线性函数f(x)逐步线性化，从而用相应线性方程的解作为其近似解，其几何意义是“逐次用切线代替曲线，用切线与x轴的交点来逼近曲线与x轴的交点”，因此也被称为“牛顿切线法”，是一种十分有效且广受欢迎的线性化方法。

●5.4Newton法的局部收敛性

牛顿迭代法在单根附近具有二阶收敛速度，但依赖于初值的选取，且需要计算导数值，若迭代点处的导数很小甚至为零，会带来计算上的困难。

●5.5弦截法

为了避免计算函数的导数值，弦截法可看作牛顿迭代法中的导数值用差商代替的结果，从几何上看，是用弦线代替切线，也是一种有效的线性化方法。

第六章线性方程组的求解： 直接法

自然科学与工程技术领域许多问题的解决如：最小二乘法求实验数据的曲线拟合问题、差分法或者有限元法解线性微分方程等，常常归结为求解某个线性代数方程组。当线性代数方程组的系数矩阵非奇异时，由克莱姆法则可给出方程组的唯一解，但这一理论上完美的结果，在实际计算中却难有用武之地，因此建立可以在计算机上实现的有效而实用的解法，势在必行。
求解线性代数方程组的方法大致可分为两类：一类是直接法，其经过有限步算术运算，可求得方程组精确解(如果每步计算都是精确进行的话)；另一类是迭代法，是用某种极限过程去逐步逼近其精确解的方法。
本章将讲授几类经典的直接法，即高斯消去法及其变形、矩阵分解法等。

●6.1Gauss消去法

高斯消去法分为“消元”和“回代”两个过程，实质上是将系数矩阵A通过初等行变换变成一个上三角矩阵，其变换矩阵就是一个单位下三角矩阵。

●6.2列主元消去法

列主元消去法是在高斯消去法的基础上进行改进而得到的一种方法，关键步就是每次消元前选取一列中绝对值最大的元素作为主元素。用列主元消去法能比较有效地控制舍入误差的影响，且不会增加计算量。

●6.3直接三角分解法

高斯消去法的实质是直接三角分解法。直接三角分解法是直接从矩阵A的元素得到计算下三角矩阵L和上三角矩阵U的元素的递推公式，而不需任何中间步骤。

●6.4平方根法

平方根法又被称为Cholesky分解法，是求解对称正定线性代数方程组最常用的方法之一。如果系数矩阵A为n阶对称正定矩阵，则存在一个实的非奇异下三角阵L使A=LLT，当限定L的对角元素为正时，这种分解是唯一的。与LU分解法相比，其计算量降为O（n2)

●6.5向量和矩阵的范数

为了对求解线性代数方程组直接法和迭代法的算法进行定量的理论分析，需要对Rn(n维向量空间)中向量或者Rnn中矩阵的“大小”引进某种度量，范数就是一种度量的方式。 由此，赋予了范数的向量空间和矩阵空间都纳入了赋范线性空间这一大家族。

●6.6矩阵的条件数

系数矩阵A的条件数是反映该方程组是病态还是良态的重要概念，其刻画了输出数据（此处是解）对输入数据（系数矩阵和右端项）变化的灵敏度。条件数抓住了改善方程组求解精度的关键所在。

第七章线性方程组的求解： 迭代法

上一章学习的直接法主要适用于求解系数矩阵为低阶稠密矩阵的线性代数方程组。而对于由工程应用中产生的大型稀疏矩阵方程组，直接法则并不适用。本章从算法设计和理论分析两个方面系统介绍近似求解线性代数方程组的迭代法。
本章主要讲授迭代法的构造思想、雅可比与高斯塞德尔迭代法、迭代法的收敛性以及超松弛迭代法 。通过本章学习，力图使学生掌握求解线性代数方程组迭代法的设计思想、实现技巧及分析迭代法的收敛性。

●7.1迭代法简介

本节首先通过一个简单的例子构造一种迭代求解算法，并通过具体计算展示迭代法求解线性代数方程组的详细过程。然后讨论对一般线性代数方程组如何利用矩阵分裂去构造迭代求解算法，并引入迭代法收敛的概念。

●7.2Jacobi迭代法、Gauss-Seidel迭代

本节讲授两类重要的迭代方法：雅可比和高斯塞德尔迭代法。首先介绍如何利用矩阵分裂的思想构造雅可比迭代法，并通过观察雅可比迭代格式提出它的“改进版”：高斯塞德尔迭代法。接下来详细讨论了两种迭代法的收敛性。

●7.3迭代法收敛性

本节在一般意义下讨论迭代法的收敛性，并证明若干理论结果。首先利用矩阵的Jordan标准型证明迭代法收敛基本定理。由于迭代法基本定理要求计算矩阵特征值，使用起来有不便之处，为此又引出若干使用更加便捷的判断迭代法收敛的充分条件。

●7.4超松弛迭代法

本节介绍从高斯塞德尔迭代法修正而来的超松弛迭代法。首先介绍超松弛迭代格式的构造过程，并给出一些实际算例。然后讨论了超松弛迭代法的收敛性以及松弛因子的选取。