西安交通大学计算方法(C)讲义

计算方法（C）

目 录

第1章 绪论

1.1 数值计算 1.2 数值方法的分析

1.2.1 计算机上数的运算 1.2.2 算法分析 第2章 线性代数方程组 2.1 Gauss消去法

2.1.1 消去法 2.1.2 主元消去法 2.2 矩阵分解

2.2.1 Gauss消去法的矩阵意义 2.2.2 矩阵的LU分解及其应用 2.2.3 其他类型矩阵的分解 2.2.4 解三对角矩阵的追赶法 2.3

线性方程组解的可靠性 2.3.1 向量和矩阵范数

2.3.2 残向量与误差的代数表征 2.4

解线性方程组解的迭代法 2.4.1 基本迭代法 2.4.2 迭代法的矩阵表示 2.4.3 收敛性

第3章 数据近似

3.1 多项式插值 3.1.1 插值多项式

3.1.2 Lagrange插值多项式 3.1.3 Newton插值多项式 3.1.4 带导数条件的插值多项式 3.1.5 插值公式的余项 3. 2 最小二乘近似

3.2.1 最小二乘问题的法方程 3.2.2 正交化算法 第4章 数值微积分

1

4.1 内插求积，Newton-Cotes公式 4.1.1 Newton-Cotes公式 4.1.2 复化求积公式 4.1.3 步长的选取 4.1.4 Romberg方法 4.1.5 待定系数法 4.2

数值微分

4.2.1 插值公式方法

4.2.2 Taylor公式方法 (待定系数法) 4.2.3 外推法

第5章 非线性方程求解

5.1 解一元方程的迭代法 5.1.1 简单迭代法 5.1.2 Newton法 5.1.3 割线法 5.1.4 区间方法 5.2 收敛性问题

5.2.1 简单迭代——不动点 5.2.2 收敛性的改善 5.2.3 Newton法的收敛性 5.2.4 收敛速度

2

第1章 绪论

1.1数值计算

现代科学的发展，已导致科学与技术的研究从定性前进到定量，尤其是现代数字计算机的出现及迅速发展，为复杂数学问题的定量研究与解决，提供了强有力的基础。

通常我们面对的理论与技术问题，绝大多数都可以从其物理模型中抽象出数学模型，因此，求解这些数学模型已成为我们面临的重要任务。

一、 本课程的任务：

寻求解决各种数学问题的数值方法——如何将高等数学的问题回归到初等数学（算术）的方法求解——了解计算的基础方法，基本结构（否则只须知道数值软件）——并研究其性质。

立足点：

面向数学——解决数学问题 面向计算机——利用计算机作为工具

充分发挥计算机的功能，设计算法，解决数学问题 例如：迭代法、并行算法 二、 问题的类型

1、离散问题：例如，求解线性方程组 Ax?b ——从离散数据：矩阵A和向量b，求解离散数据x；

2、连续问题的离散化处理：例如，数值积分、数值微分、微分方程数值解； 3、离散问题的连续化处理：例如，数据近似，统计分析计算；

1.2数值方法的分析

在本章中我们不具体讨论算法，首先讨论算法分析的基础——误差。 一般来讲，误差主要有两类、三种（对科学计算）：

1）公式误差——“截断误差”，数学?计算，算法形成——主观（人为）：数学问题-数值方法的转换，用离散公式近似连续的数学函数进行计算时，一般都会发生误差，通常称之为“截断误差”； ——以后讨论

2）舍入误差及输出入误差——计算机，算法执行——客观（机器）：由于计算机的存储器、运算器的字长有限，在运算和存储中必然会发生最末若干位数字的舍入，形成舍入误差；在人机数据交换过程中，十进制数和二进制数的转换也会导致误差发生，这就是输入误差。这两种误差主要是由于计算机的字长有限，采用浮点数系所致。

首先介绍浮点数系

3

1.2.1 计算机上的运算——浮点运算

面向计算机设计的算法，则先要讨论在计算机上数的表示。科学记数法——浮点数：约定尾数中小数点之前的数全为零，小数点后第一个数不能为零。 目前，一般计算机都采用浮点数系，一个存储单元分成首数和尾数： × × ┅┅┅┅ ? × × × ┅┅┅┅┅┅┅┅ × × 首数l 尾数(t位)

其中首数存放数的指数（或“阶”）部分，尾数存放有效数字。对于?进制，尾数字长为t位的浮点数系F(?,t,L,U)中的（浮点）数，可以用以下形式表示：

ddd12fl(x)??(???t)??l??2?t1?d??10?d??,jj?2,3,?,t

此处，指数l（称为阶）限制在L?l?U范围内。

以下记实数系中的实数为x?R，它在浮点数系F(?,t,L,U)中对应的浮点数记为fl(x)?F(?,t,L,U)——?进制，t尾数位数，L,U阶的范围。

几乎所有近代计算机都采用“二进制”（即??2）：位、字节和字分别是指位数不同的二进制数。例如

十进制 转换 二进制 1 2 4 8 9 10 27 1?20 0000 0001 0000 0010 0000 0100 0000 1000 0000 1001 0000 1010 00011011????? 1字节2?21 4?22 8?23 9?23?20 10?23?21 27?16?8?2?1?24?23?21?20 位是一个二进制数（即0或1）；字节是8个二进制数字；上表的最后一列是字节。

单精度浮点数（single precision）按32位存储，双精度浮点数（double precision）按64位存储。精度用于指明每个浮点数保留多少位以及尾数和阶数各分配多少位。单精度浮点数的尾数为23位、阶数为8位；双精度浮点数的尾数为53位（包含符号位）、阶数为11位（包含符号位）。双精度浮点数的等价二进制数如下所示：

4

11位指数（含符号位）符号位64位???????????????bbbb?bbfddd?ddddd???????????? ?52位尾数 浮点数的特点：

1、 实数转换到浮点数——浮点化，〈缺点：〉总会产生误差（除极个别的情

况：x?2l,l?0,?1,?2,?）

1按 四舍五入，绝对误差：x?fl(x)??l?t（举例），

2〈优点：〉浮点化产生的相对误差有界（与数字本身的数量级无关）

?(x)?x?fl(x)1??1?t x2 注：设实数x?R，则按?进制可表达为：

1?d??ddddl1tt?112x??(???????)??0?d??,j?2,3,?,t,t?1???2j?t?t?1按四舍五入的原则，当它进入浮点数系F(?,t,L,U)时，若dt?1?1?，则 2ddd12 fl(x)??(????t)??l??2?t若dt?1

d?1dd112??，则 fl(x)??(????t)??l2??2?tdt?1111l?tl()????

2?t2

对第一种情况：

x?fl(x)?(对第二种情况：

?t?1??)??l?x?fl(x)???dt?1111l?tll?????()????

2?t?1?t2就是说总有： x?fl(x)?1l?t? 21l另一方面，由浮点数要求的 1?d1??， 有x??，将此两者相除，便得

?x?fl(x)1??1?t

x22、每一个浮点数系的数字有限： 2(??1)?t?1(U?L?1)?1

3、浮点数系中的运算非自封闭,（因为数字有限、尾数字长有限、指数数字有限等）

例：在F(10,4,?5,5)中，x?.5420?10?2,y?.2001?103，运算x?y和x/y,

5

?12210?l?2?1210??1?21????233????213????2?2l32?1???1?302?l31??1?2??112??????11120??3??1??2??1???x???1? ?1????19??2?112??4???例： ??65?33? ；解x??9?

?2??4?054???3??????2???4 ?2???2?2??132??1????210???????41?10??2121?7?4??1???x??；解?1?：??52?22?13???131?121?????????1??????1245??10?21??55???10314??1??201????1725??213?1???64?9??1?11??4???????51860???3211??34???1????117??5?x?；解 ???240????2?510????3?20??43?2?3??66?42??1?123??12342???1?????????14916101126128???????1?? ?；解x???

18276444??131??62418??1?????????11681256190??1761???1?2424??????????1??2?3??4?23430??13430???12?1????????34540??21?1?2?3?20????2??；解x???

44543??321???1?1?7?3???????????4?55757?14???4311?????7??1????1?3??2?x?；??1? 52??????1?11???02?207??1?1??12?2?????1?10???11?12??1?34????0?27??7?4??0213??????1???2?11?142????10?31??

2.1.2 （列）主元消去法

算法中，若第k步：i)?kk?0

或 ii)?kk???iki?k?1,?,n

则按照原来的简单Gauss消去法算法可能无法执行，也可能出现大误差：

例：在浮点数系F(10,5,?10,10)中计算；方程组

11

?10?5??2?2??x1??1??0.250001875????????x? 准确解： ???????3??x2??2??0.499998749?.20000?101.10000?101?l21?020000?106??????? 11?.30000?10.20000?10?.20000?101?.40000?106.10000?101?? 6??.20000?10?解：按Gauss消去法解：

?.10000?10?4??.20000?101??.10000?10?4 ???~x?(.00000?100.50000?100)T

误差大，原因：若有误差 ?kj??kj??,?k??k?? 则

~~???l?,??ijijikkji??i?lik?k，则演变为

~?l?,?ij??ij?lik(?kj??)???ijik????l(???)???l?； ?iiikkiik~这说明前步各元素的误差均被放大lik倍。克服方法，将按绝对值最大的元素交换到主元位置，使lik?1，使前步的误差不再被放大。

?.10000?10?4??.20000?101?.20000?101.10000?101?1行?2行?????11?.30000?10.20000?10?.30000?101.20000?101?l21?.50000?10?5??????? 11?.20000?10.10000?10?

?.20000?101??.10000?10?4??.20000?101.30000?101.20000?101???11??.20000?10.10000?10??x?(.25000?100 ~.50000?100)T

消元过程中，第k步消元(k?1,2,?,n?1)以第k行为基准，消去其后的，Gauss消去法要求主元n?k个方程的?ik（系数矩阵第k列?kk以下的元素）

?kk?0。为避免出现?kk?0作为主元，并使前步的误差不被放大，应使lik?1，为此应使：?kk?Max{?kk,?k?1,k,??nk}，通常采用按列选主元的列主元消去法：若?mk?Max{?kk,?k?1k,??nk}，便将第k行与第m行交换，使?mk与?kk交换位置，使新的第k行执行在原始Gauss消去法中的角色，保证将作为除数的主元?kk??iki?k?1,?,n，从而lik?1，重复前述的Gauss消去过程。

列主元消去法的效果：

1. 算法稳定，即计算误差能被有效控制；

2. 当矩阵A的行列式A?0时，算法总可以执行完成；

注：若矩阵A是对称正定或严格对角占优，则不选主元，消去法也是稳定的；

12

矩阵严格对角占优的定义：对角元的绝对值大于该行其他元的绝对值之和，即?ii???ij；

j?1j?in问题：为什么系数矩阵A严格对角占优时，不选主元的消去法也是稳定的？ 为保证消去法是稳定的，计算应如何进行？ ?1j?1j?i1~~~?1，?1j??ij??i1注意：第一步消元 ?ij??ij?，由于占优： ?11?11?11它的效果与主元消去法的li1?1一样，误差不会被放大。但因此算法也应适当改变，应先对第一行计算此值，然后从第2列起逐列从上到下计算。且第一步消元后生成的右下方(n?1)?(n?1)阶矩阵仍是严格对角占优，以第二列为例： ~?????1j??~?????1j ??2j2j212j2j21?11?11??j?3n~?2j???2jj?3nn??1j????21?11j?3??n?n1????2j??21?11??j?3n??j?3nn1j??1???2j??21?j?3???11???12???1jj?3????12?12???????????212j2121??11j?311?????12?? ?21?11? n?12?12?~??22??21???21???2j又 ?22??22??21?11?11?j?3~?~ 即新的第二行的对角元绝对占优，其他也可同样证明。 ????222jj?3n例2-2：列主元消去法求解例2-1

210??1??233??2??1?302?????????1行?2行???21223310?1?302??????l21?1?2??????l??1?2??31???221?23?1323?37222???????????2行?3行?????2?2233?2??7????23?222?l32??12????31??1???22???3337221144????? ?????同样得到原方程组的解 x??1?11?T；

2.2 矩阵分解

2.2.1 Gauss消去法的矩阵意义——矩阵的三角分解

13

若将Gauss消去法解方程过程中产生的lij(i?j)作为一个单位下三角矩阵——其对角元为1，对角线上的元素均为0——L的对应元素；将Gauss消去法消元过程最后得到的上三角矩阵——对角线以下元素均为0——记作U或U（仅考虑方程的系数矩阵部分）；如例2.1，再将L与U或U相乘：

?1??12?????LU??21?2?????111??2????1????LU??21????111??2?11120?1210??????3??2233? 1????1?302???2?或

?12?12?1???1?????2?212 3?????1?????1?3?0?2?显然LU相乘得到的正是原始所求解的方程的增广矩阵，而LU相乘得到的正是原始所求解的方程的系数矩阵。反过来，一个矩阵也可以通过Gauss求解的过程获得这样的“LU分解”，其中L为单位下三角矩阵，U为上三角矩阵。

这样将一个矩阵分解成一个下三角矩阵和一个上三角矩阵的乘积形式，称为矩阵的三角（Doolittle）分解。

1） 消去法的矩阵意义： 以例2-1说明

210??1?1210?????2233???????213??l21?2,l31???1?? ??1?302???112?????与以下矩阵乘法是一样的：

210??1210??1??1??????233????213? ??21??2?1???1??112?????1?302???可见，一般的第一步消元是：

?1???li1L1?A,b???????l?n1???11?11??11??1???11?11??11?????????1????11?11??11?1???1???11?11??11?~~?0?11??11?????????~~??1???0?11??11?1?~??1? ??~??1??则第i步消元是将以下初等矩阵左乘矩阵?A(i?1),b(i?1)?形成?A(i),b(i)?

若记第k步消元后形成的矩阵为?A(k),b(k)?，《特别：L1(A,b)?(A(1),b(1))》

14

?1????1Lk???li?1,k??????lnk??????

1????1??因此，Gauss消去过程从矩阵运算的角度来看，是

Ln?1Ln?2?L2L1(A,b)?(U,y)

其中 U为上三角矩阵，y为向量：

??11?? U??????112??1n???22??2n??,????nn???y1????y2?y???

????y??n?2.2.2 矩阵分解A?LU

注意到初等矩阵Lk具有性质： ?1????1?????l21??1?1?1?11????及LL?L?L?L??12n?1k?li?1,i1???ln?1,1??????l??n,1?lni1???根据矩阵乘积的性质，有 A?LU

这就是基本的矩阵三角分解——Doolittle分解——将矩阵分解为单位下三角矩阵L与上三角矩阵U的乘积。

从矩阵乘法与行列式的关系可知，若矩阵A三角分解得到A=LU，则有： det A = det L * det U ，由于下三角矩阵或上三角矩阵的行列式是全部对角元的乘积，因此可利用三角分解求矩阵对应的行列式的值。例如：上述例2.1方程组系数矩阵对应的行列式的值是-1，下例2.3 对称正定矩阵对应的行列式的值为144。

当系数矩阵为A的方程组可以顺利求解（不必选主元）时，解的过程显然是唯一的，因此它的Doolittle分解必然也是唯一的，从而可以通过待定系数的方法获得该矩阵的Doolittle分解（通常称为“直接分解”或“紧凑格式”）。

2.2.3 其他三角分解

除了上述的单位下三角矩阵与上三角矩阵的乘积形式以外，还有其他类型的分解，例如下三角矩阵和单位上三角矩阵的乘积，单位下三角矩阵与对角矩阵、

15

1?ln,2?1?ln,n?1ln?1,2????? ??1??1?1?1L?L因此，我们有 ?A,b??L?12n?1(U,y)?L(U,y)

本文来源：https://www.bwwdw.com/article/l0r2.html