西安交通大学计算方法B完整版.doc

1、第一章 绪论1.1数值计算现代科学的发展，已导致科学与技术的研究从定性前进到定量，尤其是现代数字计算机的出现及迅速发展，为复杂数学问题的定量研究与解决，提供了强有力的基础。通常我们面对的理论与技术问题，绝大多数都可以从其物理模型中抽象出数学模型，因此，求解这些数学模型已成为我们面临的重要任务。一、 本课程的任务：寻求解决各种数学问题的数值方法如何将高等数学的问题回归到初等数学（算术）的方法求解了解计算的基础方法，基本结构（否则只须知道数值软件）并研究其性质。立足点：面向数学解决数学问题面向计算机利用计算机作为工具充分发挥计算机的功能，设计算法，解决数学问题 例如：迭代法、并行算法二、 问题的类

2、型1、离散问题：例如，求解线性方程组 从离散数据：矩阵A和向量b，求解离散数据x；2、连续问题的离散化处理：例如，数值积分、数值微分、微分方程数值解；3、离散问题的连续化处理：例如，数据近似，统计分析计算；1.2数值方法的分析在本章中我们不具体讨论算法，首先讨论算法分析的基础误差。一般来讲，误差主要有两类、三种（对科学计算）：1）公式误差“截断误差”，数学计算，算法形成主观（人为）：数学问题-数值方法的转换，用离散公式近似连续的数学函数进行计算时，一般都会发生误差，通常称之为“截断误差”； 以后讨论2）舍入误差及输出入误差计算机，算法执行客观（机器）：由于计算机的存储器、运算器的字长有限，在运

3、算和存储中必然会发生最末若干位数字的舍入，形成舍入误差；在人机数据交换过程中，十进制数和二进制数的转换也会导致误差发生，这就是输入误差。这两种误差主要是由于计算机的字长有限，采用浮点数系所致。首先介绍浮点数系 一、计算机上的运算浮点运算 面向计算机设计的算法，则先要讨论在计算机上数的表示。科学记数法浮点数：约定尾数中小数点之前的数全为零，小数点后第一个数不能为零。 目前，一般计算机都采用浮点数系，一个存储单元分成首数和尾数： 首数 尾数(位)其中首数存放数的指数（或“阶”）部分，尾数存放有效数字。对于b进制，尾数字长为t位的浮点数系中的（浮点）数，可以用以下形式表示：此处，指数（称为阶）限制在

4、范围内。以下记实数系中的实数为，它在浮点数系中对应的浮点数记为进制，尾数位数，阶的范围。几乎所有近代计算机都采用“二进制”（即）：位、字节和字分别是指位数不同的二进制数。例如十进制转换二进制10000 000120000 001040000 010080000 100090000 1001100000 101027位是一个二进制数（即0或1）；字节是8个二进制数字；上表的最后一列是字节。单精度浮点数（single precision）按32位存储，双精度浮点数（double precision）按64位存储。精度用于指明每个浮点数保留多少位以及尾数和阶数各分配多少位。单精度浮点数的尾数为23位

5、、阶数为8位；双精度浮点数的尾数为53位（包含符号位）、阶数为11位（包含符号位）。双精度浮点数的等价二进制数如下所示： 浮点数的特点：1、 实数转换到浮点数浮点化，缺点：总会产生误差（除极个别的情况：）按 四舍五入，绝对误差：（举例），优点：浮点化产生的相对误差有界（与数字本身的数量级无关） 注：设实数，则按进制可表达为：按四舍五入的原则，当它进入浮点数系时，若，则 若，则 对第一种情况：对第二种情况：就是说总有： 另一方面，由浮点数要求的 ， 有，将此两者相除，便得2、 每一个浮点数系的数字有限： 3、 浮点数系中的运算非自封闭,（因为数字有限等）例：在中，运算和,的结果显然已不在此浮点数

6、系内，而或也不在此浮点数系内，需结果才在此浮点数系内。浮点运算应注意：1） 避免产生大结果的运算，尤其是避免小数作为除数参加运算；2） 避免“大”“小”数相加减；3） 避免相近数相减，防止大量有效数字损失；4）尽可能简化运算步骤，减少运算次数。原因：记，由，可得： （“。”表示任意一种四则运算）此处 是由机器字长（实质上是尾数字长的大小）确定的常数（它反映了实际运算的精度）。显然，若要求运算的舍入误差小，应使运算结果（如：）较小。尤其是小分母运算：，小大误差。其次，当浮点数系中两个数量级相差较大的数相加（或减），注意到由于浮点数系中数字字长的有限性，可能导致“大数吃小数”。例如，中，则似乎没有

7、参加运算。 第三，同样，由于浮点数系中数字字长的有限性，当两个相近数相减时：例如，在中，两数相减：，计算结果仅剩2位有效数字，而原来参加运算的数字有8位有效数字，这将严重影响最终计算结果的精度。二、 算法分析作为一个可用的算法，必须考虑其效率和可靠性，定义：计算机完成一个乘法和一个加法，称为一个浮点运算（记为flop）；注：由于计算机在运算时，加（减）法所耗时间远少于乘（除）法，所以通常只须计算乘法的次数，因此也有“一个算法需要多少个乘法”这一提法。1、计算效率可计算性（计算复杂性空间、时间）例：解线性方程组的Grammar 方法：，其中是方程组系数矩阵对应的行列式，而则是以右端向量替代的第列

8、所得矩阵对应的行列式。由线性代数知识可知，若，则，其中是由变换到所需的置换次数。可见每计算一个行列式，需要个浮点运算；因此，按Grammar方法解方程组约需 个浮点运算。当时，用一个运算速度为的计算机进行求解，约需年（日前报道我国计算机已达到秒，这仍需近10年）。而n=20的方程组应该说是一个小型的方程组。因此Grammar方法是一个不能接受的算法，它缺乏可计算性。第二章将介绍的Gauss消去法和迭代法就有较高的效率，具有很好的可计算性。2、计算可靠性作为算法，除了考虑其效率外，必须重视可靠性，它包括两方面：问题的性态 和 方法的稳定性l 问题的性态所计算的问题当原始数据发生小扰动时，问题的解

9、一般也发生扰动。问题的性态问题的解对原始数据发生变化的敏感性。原始数据小扰动问题解 例：线性方程组： 的解是：若将方程组的系数改写成具有2位有效数字的小数： 的解则变成：；这是一个典型的病态方程组。一般：由原始数据 计算结果， 扰动后的数据 计算结果，若对问题存在常数m，满足关系式： 或 则称（相对误差之比的上界）m为该问题的条件数，记作 ；由微积分中值定理知识容易计算出，当时， 。稍后我们在第二章将对线性方程组的性态作进一步的分析。l 算法的数值稳定性：例：计算；解：由微积分知识，可得计算公式， ，我们将准确值与计算结果列表如下：方法准确值.6321.3679.2642.2073.1709.

10、1455.1268.1124.1010.6321.3679.2642.2074.1704.1480.1120.2160-.7280.6320.3680.2643.2073.1709.1455.1268.1124.1010由上表可见，方法中，原始步的误差，随着计算步数的增加被严重地放大，特别是竟变成负数（注意：被积函数是非负函数），而方法则相反；这是因为方法中，若前步有误差：，则，说明的误差，经一步计算后被扩大了倍，随着的增大，误差将被大大地扩大；而通过同样的分析可知：方法中的误差则被缩小倍。算法的数值稳定性：算法对初始误差导致的最终误差的可控性，如果最终误差被有效地控制，则称算法是稳定的，否则

11、就是不稳定的。第二章 线性方程组求解线性方程组：其中2.1 消去法 2.1.1 消去法 设计方法原则：面向计算机（事先未知元素，编制程序），例： 基本思想：降维N维问题转化为N-1维问题逐次降维，依次进行消去过程对方程组（2.1）由上而下逐步消去对角元 以下的 ，使之转化为如下等价形式，达到目标： 从而，可进入回代过程，再由下而上，逐步解得 ：这儿的主元对问题（2.1）设，目标：将第2n方程的的系数转化为0；方法：“第个方程”-“第1个方程”（，得到现在只须关心由第2n方程形成的n-1维方程组，以后可仿此进行。消去：第步：设，以第行为基准，消去以下各行中列以下的，令 施行：第行第行新的第行，元

12、素变化：（），经过步消去（注意：以下无元可消），得到式。注意：每计算1个仅需1个浮点运算回代：第一步 ， 第二步 ，第步 运算量：消元：n元方程组：第1步消元：对第行，共n-1行；每1行：计算，1个乘除法（或“浮点运算”），计算新的共 个乘除法（或“浮点运算”），第1次元共个乘除法，因此，消元的运算量； 回代：第1步，求需要1个乘除法（或“浮点运算”），即：第2步求用2个乘除法（或“浮点运算”），一般，第步求用个浮点运算，因此，回代的运算量 ；消去法 的 总运算量： 。 例2-1：解线性方程组 解：利用增广矩阵（因为线性方程组的解仅与系数与右端常数项相关）例： ；解 ；解：；解 ；解；解；2.

13、1.3 （列）主元消去法算法中，若第步： 或 则按照原来的简单消去法算法可能无法执行，也可能出现大误差：例：在浮点数系中计算；方程组 准确解：解：按消去法解： 误差大，原因：若有误差 则，则演变为；这说明前步各元素的误差均被放大倍。克服方法，将按绝对值最大的元素交换到主元位置，使，使前步的误差不再被放大。 消元过程中，第步消元以第行为基准，消去其后的个方程的（系数矩阵第列以下的元素），消去法要求主元。为避免出现作为主元，并使前步的误差不被放大，应使，为此应使：，通常采用按列选主元的列主元消去法：若，便将第行与第行交换，使与交换位置，使新的第行执行在原始消去法中的角色，保证将作为除数的主元，从而

14、，重复前述的消去过程。列主元消去法的效果：1. 算法稳定，即计算误差能被有效控制；2. 当矩阵的行列式时，算法总可以执行完成；注：若矩阵是对称正定或严格对角占优，则不选主元，消去法也是稳定的；矩阵严格对角占优的定义：对角元的绝对值大于该行其他元的绝对值之和，即；问题：为什么系数矩阵严格对角占优，则不选主元的消去法也是稳定的？为保证消去法是稳定的，算法应如何进行？注意：第一步消元 ，由于占优：，它的效果与主元消去法的一样，误差不会被放大。但因此算法也应适当改变，应先对第一行计算此值，然后从第2列起逐列从上到下计算。且第一步消元后生成的右下方阶矩阵仍是严格对角占优，以第二列为例：又 即新的第二行的

15、对角元绝对占优，其他也可同样证明。例2-2：列主元消去法求解例2-1同样得到原方程组的解 ；2.2 矩阵分解2.2.1 Gauss消去法的矩阵意义矩阵的三角分解若将消去法解方程过程中产生的作为一个单位下三角矩阵其对角元为1，对角线上的元素均为0的对应元素；将消去法消元过程最后得到的上三角矩阵对角线以下元素均为0记作或（仅考虑方程的系数矩阵部分）；如例2.1，再将与或相乘：或 显然相乘得到的正是原始所求解的方程的增广矩阵，而相乘得到的正是原始所求解的方程的系数矩阵。反过来，一个矩阵也可以通过求解的过程获得这样的“分解”，其中为单位下三角矩阵，为上三角矩阵。这样将一个矩阵分解成一个下三角矩阵和一个

16、上三角矩阵的乘积形式，称为矩阵的三角（Doolittle）分解。1） 消去法的矩阵意义： 以例2-1说明与以下矩阵乘法是一样的：可见，一般的第一步消元是：若记第步消元后形成的矩阵为，特别：则第步消元是将以下初等矩阵左乘矩阵形成因此，Gauss消去过程从矩阵运算的角度来看，是其中 为上三角矩阵，为向量： 2.2.2 矩阵分解注意到初等矩阵具有性质：及因此，我们有 根据矩阵乘积的性质，有 这就是基本的矩阵三角分解Doolittle分解将矩阵分解为单位下三角矩阵与上三角矩阵的乘积。从矩阵乘法与行列式的关系可知，若矩阵A三角分解得到A=LU，则有：det A = det L * det U ，由于下三

17、角矩阵或上三角矩阵的行列式是全部对角元的乘积，因此可利用三角分解求矩阵对应的行列式的值。例如：上述例2.1方程组系数矩阵对应的行列式的值是-1，下例2.3 对称正定矩阵对应的行列式的值为144。当系数矩阵为的方程组可以顺利求解（不必选主元）时，解的过程显然是唯一的，因此它的Doolittle分解必然也是唯一的，从而可以通过待定系数的方法获得该矩阵的Doolittle分解（通常称为“直接分解”或“紧凑格式”）。2.2.3 其他三角分解除了上述的单位下三角矩阵与上三角矩阵的乘积形式以外，还有其他类型的分解，例如下三角矩阵和单位上三角矩阵的乘积，单位下三角矩阵与对角矩阵、单位上三角矩阵的乘积。对于对

18、称矩阵，可以分解成矩阵分解的形式，特别是对称正定矩阵，可以分解成形式（称为Cholesky分解），其中为下三角矩阵由Doolittle分解的唯一性可知这些形式的分解也是唯一的。这些不同的分解都可以通过矩阵乘积的方法取得。下面例2.3以对称正定矩阵为例，说明通过矩阵乘积的方法取得矩阵分解的不同形式。当然，当矩阵的Doolittle分解存在唯一时，这些不同的分解分别时唯一的，因此可以通过待定系数的方法取得，也即通过直接分解的方法取得这些分解。例2-3： 由此可知：进一步可以考察矩阵左上方各阶顺序主子式与三角分解所得矩阵的左上方的各阶顺序主子式的关系：若记矩阵A的各阶顺序主子矩阵为，同样的记号也适用

19、于矩阵，则有，从而矩阵的各阶顺序主子式的值等于的相应的顺序主子式的值：，（因为）。以例2-3矩阵分解为例，容易得到：由此，也很容易看到，一个对称矩阵通过消去过程得到的分解（其中为单位下三角，为上三角矩阵），当的对角元全部为正数时，该对称矩阵必为对称正定矩阵。 由消去的过程可知各次主元是（矩阵的对角元），可知当矩阵的各阶顺序主子式均非零时，（原始的）消去法可以顺利完成，这是因为当各阶顺序主子式均非零时，均非零，即消去法可以顺利完成。进一步，当矩阵非奇时，列主元消去法必可顺利完成：因为当矩阵非奇时，的第一列必不全为零，故通过选主元，可进行第一步消元，即算法可执行，得到，且其下方全为零，因为所以的代

20、数余子式也非零，（），即矩阵非奇，因此下一步列主元消去可进行，由此，可完成全部消元过程。 2.2.5 带状矩阵的分解定理2.5 若分解), 则(下)带宽,(上)带宽.证明: 对二和三阶矩阵显然.(确定),对矩阵的阶作归纳证明:设对阶矩阵结论成立.令,可验证(介绍分块运算): 由归纳假设, 因此 最后的矩阵乘法：前者是初等矩阵左乘实际上是Gauss变换矩阵相乘，后者按分块运算容易得到。特殊情况,三对角矩阵：， 由前述的方法，很容易将它分解成两个特殊的下、上三角矩阵的乘积： ，其中因为未讲矩阵的直接分解，此处可由确定分解形式、待定系数方式取得： 从而，在解方程组，其中时，可以将该方程组转化为求解两

21、个简单方程组： 通常被称为“追赶法”： 。这只是Gauss消去法的一个具体应用，在计算机上的应用可以节约存储空间，减少运算量。若手工计算，实际只需应用Gauss消去法即可。例2.3 线性方程组解的可靠性向量与矩阵范数，误差的代数表征 3.1向量与矩阵范数向量范数由二维或三维向量的长度概念推广而来工具。1、向量范数 向量，与之相应的一个非负实数，记作，如果它满足条件：1） 非负性 ，2） 正齐性 ，3） 三角不等式 ；常用的范数1-范数 ，2-范数 ，-范数 ， 注：一般若不指某特定的范数，则范数符号不作下标，记为；2、矩阵范数 矩阵 ，与之相应的一个非负实数，记作，如果它满足条件：1） 非负性

22、 ，2） 正齐性 ，3） 三角不等式 ，4） ，因为矩阵与向量相乘仍是向量，因此：特别要求一种矩阵范数与一种向量范数：5）矩阵与范数的相容性；与前述三种向量范数分别相容的常用的三种矩阵范数：1-范数 ，（最大列和）2-范数 ，-范数 ，（最大行和）；注：作为矩阵的特例向量，这些范数定义无矛盾。例：第2章 Ex-14（79页）-范数，-范数，-矩阵范数，其中-非奇矩阵3、范数的等价性：4、矩阵谱半径： ；有(对任何一种范数) , 2.3.2 残向量与误差误差的代数表征（矩阵的条件数）：若记方程组(2.1)的准确解，近似解；则有近似解的误差：，近似解的残向量：。小小？例： 比较：方程组 与 ，从前

23、者到后者仅是右端产生误差，而对应的解则由变为，即也产生误差；它们之间有关系： ； 注意以上公式：由，以及 得到。此处，从本质上反映了方程组右端的相对误差导致解的相对误差的数值关系，反映了方程组原始数据发生扰动时，方程组解发生变化的大小。比较前已提到的“问题的性态”，数反映了方程组的性态。因此称此数为方程组或矩阵的“条件数”，记作 ；由于总有（实际上，除了外，几乎总有），而从推导可知，（此处“”表示“相当于”），因此一般总有； 上例中：对于更一般的矩阵和右端向量均发生扰动和的情况，有 证明： 存在，且 反证：若 奇异，即，则 有非 解 又矛盾，所以 非奇， 存在，由 （至少对常用的三种范数）：由

24、此得 .若: 2.4 线性方程组的迭代解法迭代法：将方程组 （2.1）转化为等价的形式从而，将向量代入(2.4)的右边，可计算得到一个新的值： 如此反复地进行，便得到向量序列；问题 I）如何将方程组（2.1）的形式转化为(2.3)？ II）给定初始向量，迭代产生的向量序列是否收敛？ III）向量序列的收敛性与初始向量的选取是否相关？ IV）如果收敛，如何估计误差？2.4.1 Jacobi迭代与 Gauss-Seidel迭代首先我们回答问题 I）:由方程组（2.1）：，使等式左端仅保留向量，其他一概放到右端，即：将方程组的第个方程（设，） 改成：，便可将原方程组改写成如下等价形式：Jacobi迭

25、代：将代入上式右端，便可（按顺序逐行）进行计算得到 ，这便是迭代：Gauss-Seidel迭代：按通常的串行计算方式，迭代（2.5）中先计算第一式得到,此数完全可以参与第二式的右端的计算,依次类推，便得到： 这就是迭代。迭代法的矩阵表示将方程组（2.1）的系数矩阵A分裂成三部分：，其中原始方程组形成，即左侧仅有若，分别对第方程除以，并记左侧上标为k+1，右侧上标为k，则有Jacobi迭代：若由“最新信息优先”，即将已生成的立即用于计算，便是Gauss-Seidel迭代：矩阵分裂：Jacobi迭代：Gauss-Seidel迭代：显然，不同的迭代方法是对矩阵A做不同的分裂得到的：Jacobi迭代：

26、 Gauss-Seidel迭代： 逐次超松弛（SOR : Succesive Over-relaxation）：由，改G-S迭代：将由的改变量，作松弛，取松弛因子，有 或 计算式，由： 矩阵分裂：逐次超松弛（SOR）收敛条件： 必要条件： A严格对角占优： 逐次超松弛（SOR）收敛 A对称正定： 逐次超松弛（SOR）收敛2.4.3 收敛性以下我们回答问题II）和III）：记方程组的解为，若当时向量序列收敛于方程的解， 即，有等价关系（注意到范数的等价性）：由于满足关系式 ，将它与一般迭代：，两者相减，可得 ，遍取向量范数，并由矩阵范数与向量范数的相容性，可得：从而，由此可见，当时，无论如何取，

27、总有，即：；即定理2.6：迭代 取任意初值生成的向量序列当时收敛于方程的解的充分条件是.具体化考察对原始问题（2.1）进行迭代或迭代时，迭代收敛对矩阵的要求。由式可知，迭代的迭代矩阵为，迭代的迭代矩阵为 ；由于的第行是：（）；因此，显而易见当为严格对角占优时该行各元素的绝对值之和小于1，所以：；结论是：推论2.7： 若方程组（2.1）的系数矩阵严格对角占优,则任取初值的迭代收敛.其他结论：定理2.8： 若方程组（2.1）的系数矩阵严格对角占优,则任取初值的迭代收敛.证：记 严格对角占优 ，由的有限性，记 由 及 相减 即 设 则所以 由 ，得 证完定理2.9： 若方程组（2.1）的系数矩阵对称

28、正定,则任取初值的迭代收敛；当正定时，迭代收敛，否则就不收敛。最后，有：定理2.10：迭代收敛的充分必要条件是矩阵的谱半径.例：关于充分性：Jocabi：令则因此，总有 ，但并不满足定理的充分条件。例：又， 等价于解： ； 结论：Jacobi 迭代收敛，Gauss-Seidel迭代不收敛。例：结论：Jacobi 迭代不收敛，Gauss-Seidel迭代收敛。例： 正定，不正定， Seidel收敛，Jacobi不收敛。例：例：证明：时Seidel迭代收敛，仅当 时Jacobi 迭代收敛。证：i. 时正定：，综上，时正定，所以Gauss-Seidel迭代收敛；ii. 所以，（当且）仅当 时Jaco

29、bi 迭代收敛。 正定： 正定；综合正定条件，得结论。但这是在正定的前提下的结论，如果不正定，条件是否仍如此？例：，以表示解的Jacobi、Gauss-Seidel迭代收敛的充分必要条件；I：Jacobi 迭代： Jacobi 迭代收敛； II：Gauss-Seidel迭代：等价于解： Gauss-Seidel迭代收敛。2.4.4 迭代终止的判据定理2.11: 迭代,若,则任意取初值生成的向量序列当时收敛于方程的解,且有误差估计: 或 ；证：利用 及 令，便得结论。注1：前者称为“先验估计”，后者称为“事后估计”；迭代法通常要求计算获得的解满足给定的误差界： ：l 先验估计：对要求的误差界，由

30、估计式 可计算得 ，从而，可将由此所得的作为迭代步数的最大控制数，取；l 事后估计：对要求的误差界，由估计式 可知，在迭代计算过程中，应验证不等式 是否满足，如果满足，迭代就可终止，取。在实际计算中，通常将上述两种终止判据同时使用。注2：对于系数矩阵严格对角占优的迭代，可用定理2.8定义的作为收敛因子（即取），当然此时应取-范数；注3：若已肯定迭代收敛，但收敛因子q难以获得，可根据： 对适当大的确定q的估计值。Hilbert Matrix nn374859610第三章 数据近似已知函数关系的数据点：，求一个适当的函数，它是已知函数族称为基函数的线性组合，即：寻求系数，使，与按某种标准相近似；通

31、常按下述标准之一，使之取得极小：若取向量形式： ,则上述三数分别为：；3.1 多项式插值一般，若有个数据点，上述近似标准要求即：，则称近似函数为满足插值条件(3.2)的插值函数，而点称为插值节点。若满足插值条件(3.2)的函数的基函数取 ，则是多项式称满足插值条件(3.2) 的多项式为插值多项式。代数学基本定理：n次多项式有且仅有n个根（包括重根）3.1.1 插值多项式根据插值条件(3.2)，可形成有个未知量的个方程： ，这个方程组的系数矩阵称为Verdermonde矩阵，由其性质可知，当 时，该方程组的解存在且唯一。因此有定理3.1：对数据点，存在满足条件(3.3)的唯一的插值多项式；强调：

32、插值多项式唯一 形式可以不同3.1.2 Lagrange(形式)插值多项式 由两点直线方程谈起，；若有不超过次的多项式： ，可形成如下表：1000000001000000001000000001称为Lagrange基本插值多项式，显然它有个根：；由于次多项式有且仅有个根，因此注意到 ，可知：；若记 便有 不难证明 为所求的插值多项式，它被称为Lagrange（形式）插值多项式。缺点：增加插值节点后，Lagrange插值多项式发生大变化。举例， 3.1.3 Newton(形式)插值多项式 定义：差商一阶差商： ；二阶差商： ；n阶差商： ；考虑逐次增加插值节点后，插值多项式的变化：记满足插值条件

33、的（不超过）次插值多项式为，并记，即，注意：是次多项式；由 故有 ；由于次多项式有且仅有个根，因此；确定系数：同样的方法可得：由此形成的插值多项式称作Newton插值多项式，记作：差商-性质1、对称性：对的任意排列，有 证明：前方法的Newton插值多项式的导出过程是：从仅满足一个插值条件的插值多项式开始，逐步增加插值条件，直到最后的，形成的，它的次项的系数就是；同样，若从仅满足一个插值条件的插值多项式开始，逐步增加插值条件，直到最后的，形成的的最高次（次）项的系数就必定是。由插值多项式的唯一性可知，这两个插值多项式是同一的，从而它们的次项的系数也是同一的，由此便得结论。差商-性质2、设有直到

34、n阶导数，则 证明：设为插值节点，则对应的Newton插值多项式，令，显然，它有个零点：；由定理可知有n个零点，同理可知有n-1个零点，依此不难推出在中至少有一个零点，记为，即：，而，由此得结论。例：多项式，且与点的选择无关； 例：设3.1.4 带导数的插值多项式若在点可导，利用差商和导数的定义，有，类似，可得到 ；上述结论也可以从差商性质2推出；例如，当时可获得上述第一个结论，当 时 可得到后一个结论。说明：由此可知，Newton插值多项式是Taylor展开式的推广例：求满足下述插值条件的插值多项式，解：建立差商表：由此可写出插值多项式 ；注：利用Newton插值多项式，重节点差商公式，以及

35、差商性质2，容易看到：Taylor展开式实质上是当时的Newton插值多项式。 3.1.5 插值公式的余项若将以为插值节点插值多项式，再增加一个插值节点，得插值多项式，由插值性质，有，据此，并由所取 的任意性，可将改作，便得插值公式的余项公式：利用差商性质2，及符号，又可以有余项的另一种表达形式 l Runge现象：问题：答1：若有界，有界， 则可。例：，显然 ，取区间，插值点等距分布：等分区间，步长 ，节点 逐步向外扩充，比较：使 最小：是区间中点，等分区间等分，则 而当或，则 所以， 从而 若插值点非等距分布，例如可证明：，因此当 时，另一方面，即使 有界，当 无界时，仍可能无界。例：，显

36、然，当经典的例子：函数，区间等分份，节点；（参考后图）注意：通常插值公式用到.附表：的函数插值多项式值0.840.860.880.900.920.950.962.67444.06913.94510.0471-10.3345-39.9524-50.86440.970.9730.9740.9750.9760.978-58.5447-59.5704-59.7279-59.7819-59.7254-58.2381解决方案：1) 分段多项式插值减小，低阶导数可估计、有界；同时保持小区间。2) 其他插值方法，例如用其他基函数插值等；3) 最小二乘近似逼近点多，近似函数低阶（放弃插值）；4) 其他逼近方法。

37、 Runge 函数及插值的图形 3.2 分段插值分段三次多项式插值样条插值区间 上的节点：要求：分段三次多项式 ，在节点处插值：，在内节点处连续：思路：由 连续 预设, 为一次多项式：故积分2次积分常数（2个） 由插值条件 确定 积分常数 得（含预设的） 利用连续： 确定的个方程 + 2边界条件 确定加入的表达式，形成 1、 区间 中，设 2、求表达式：对 积分2次： 其中：由插值条件得3、求导，要求导数连续： 有 根据导数连续： ，则由 并记 可得共个方程： 4、完成 需 共个，确定之应有个方程，尚缺2个方程；需 边界条件：a) 自然样条（简支）：，即 b) 给定(刚支）：令,由表达式： 形

38、成2个新的分别关于和的方程：c) 无其他导数条件：由确定（三次）插值多项式由确定（三次）插值多项式的的系数：，的的系数是，令： 又由原始设定：可知：形成方程： 综上，形成如下形式的元方程组：d) 周期样条： 是周期函数，此时 对方程：及 对下标做适当调整：，形成：其中：；注：第1）2）4）三种情况线性方程组均为严格对角占优矩阵，而3）产生了“不可约对角占优矩阵”（我们在此不再对此进一步讨论），它与严格对角占优矩阵有几乎相同的性质。计算步骤：1、 计算：2、 解方程组，取得，形成3、 对 ，计算；定理3.5 设 ，则以 为节点的三次样条满足 ，其中 。证明：记先在区间中考虑，记，取 ，令 ，则

39、； 由定理，存在 使。注意：，因此，由 可知： 又：，所以。由于 所以 进一步有 又由 可得 所以 最后，由的任意性，有 证完注意:此处用到 隐含是内点标号! 若（ 情况是相同的）：对于边界条件a）此情况不存在，边界条件b）此时， 与前证明完全一样；边界条件d）此时 扮演相同的角色，也都是内点，不存在问题；关于边界条件c）问题较难讨论。3.3 最小二乘法3.3.1 （线性）最小二乘问题的法方程已知数据点： ，求近似式：，使函数与按以下标准取得极小： ；当时，该问题称为最小二乘问题，问题的解称为最小二乘解。通过对以为参数，以为极小化目标函数的计算，可以证明该最小二乘问题的解就是方程组的解，此方程

40、组称为最小二乘问题的法方程组，其中 ；对此也可以从另一个角度作一简单的解释。作向量差 ；由方程组理论可知，当方程组的方程个数大于未知量个数时（通常称为超定方程组），方程组一般无解，因此当 时，方程组 一般无解。但若将此方程组左乘，则方程组变成通常的阶方程组，从而可以求解，这个阶方程组就是法方程组。严格证明: 注意到 关于的极小与 对应极小是完全一样的.因此最小二乘问题的解应满足方程:为解释方便,将记为 ,注意到 , 有交换求和顺序，便形成方程组： 比较法方程 的具体表达式： 可知：法方程 的解 最小二乘问题的解。 3.3.2 正交化算法通常法方程组是病态的（），因此求解法方程组最好采用正交化方

41、法，这是一个解线性方程组的稳定性非常好的方法。定义：若矩阵满足条件，即矩阵的逆矩阵是它的转置矩阵，则称此矩阵为正交矩阵。注意，从矩阵乘法规则容易看到，正交矩阵的列是互相正交的，而且它的列的2-范数长度为1。这也是它被称为正交矩阵的原因。正交矩阵性质1：正交矩阵的乘积仍是正交矩阵。设是正交矩阵，则；正交矩阵性质2： （正交变换在二、三维空间中旋转变换坐标轴夹角总是直角不改变向量长度）；引理3.6：对任意非零向量，总存在正交矩阵，使，其中；证明：首先，对任意向量，若，容易验证矩阵为正交矩阵。其次，令 即 ；注意，向量是由其方向和长度唯一确定的，此向量 的方向是 ，而其长度则为：，因此取 。验证：，而注意到因此， ，这就说明了： ，即，对于给定的向量，取适当的向量，形成正交矩阵