2011工程硕士讲课讲义

算法的数值稳定性 xn

dx,n?0,1,?,8. 计算积分En??0x?101

1xn?10xn?11dx??xn?1dx?, 解：由：En?10En?1??00x?10n1

可得两个递推算法.

111?10En?1,n?1,2,?,8； 算法2：En?1?(?En),n?8,7,?,1. n10n

11**当仅考虑初始值有误差时，对于算法1，由：En??10En?1,En??10En?1， nn算法1：En?

*可知误差?n?En?En满足：?n??10?n?1?(?10)n?0,n?1,2,?，

因此算法1是不稳定的.

对于算法2，同理可知误差?i?Ei*?Ei满足：?i?1??1?i,i?n,n?1,?1， 10

1?所以?0??????n，因此算法2是稳定的. ?10?

高斯消去法——示例

考虑如下线性方程组：

x1?x2?x3?1?1?11??x1??1??1?11??x1??1?????????????????2x1?2.001x2?2.01x3??5???22.001?2.01??x2????5??00.001?0.01??x2????3?

??????0????x1?9x2?2x3?30601?92?0101???1??x3??30601????x3??60600?n从上述方程组的第三个方程依此求解，得

?x1?x2?x3?1?2401???3?0.01x3??3000 ?x2?1000

?x?600?3

高斯消去法的不足及其改进——高斯（全、列）主元素消去法

在上例中，由于建模、计算等原因，系数2.001而产生0.0005的误差，实际求解的方程组为

?11??x1??1?.2?1?x1?2565??????22.0005?2.01?x??5??x?3014.9 ??2???2???????x?450.70?92??1??x3??30601??3

高斯消去法的消元过程，从代数运算的角度看就是用一个下三角矩阵L左乘方程组的系数矩阵Ａ，且乘积的结果为上三角矩阵U，即

?L?1A?U?Ly?b?Ax?LUx?b??， ?Ux?y??A?LU

用于度量“量”的大小的概念

例１．３ Rn?Cn?上常用的向量范数：

?x??x1，x2，?，xn??Rn?Cn?， T

１、１—范数：x1??xk；２、２—范数：x

k?1n2?xTx；

３、?—范数：x??maxx1，x2，?，xn； 1?k?n??

例１．５ 常用的矩阵范数： ?n?T１、１范数（列范数）：A1?max??aijj?1，2，?，n?；２、２范数（谱范数）： A2??maxAA； 1?j?n?i?1?

３、?—范数（行范数）：A??n??max??aij，i?1，2，?，n?； 1?i?n?i?1?

迭代法求解线性方程组的基本思想是

１） 不追求“一下子”得到方程组的解，而是在逐步逼近方程组的精确解的迭代过程中获得满足

精度要求的近似解，这一点与直接法不同；

２） 通过对问题的转化，避免（困难的）矩阵求逆运算。

例1 解下面方程组（精确解为x*?(1,1,1)T）.

?10x1?3x2?x3?14,??2x1?10x2?3x3??5,

?x?3x?10x?14.23?1

解 1） 改写成等价形式，（2）构造迭代公式，即为雅可比迭代公式

?(k?1)1(k)(k)?(14?3x2?x3),?x110??(k?1)1(k)(k) ?x2?(5?2x1?3x2),10??(k?1)1(k)(k)x?(14?x?3x12),k?0,1,2,?.?310?

(0)(0)(0)3） 取初始向量x(0)?(0,0,0)T，即x1?x2?x3?0,代入上式，求出

x1(1)?1414(1)5(1)?1.4,x2?0.5,x3??1.4. 101010

再代回公式中，求出

1(14?3?0.5?1.4)?1.11， 10

1(2)x2?(5?2?1.4?3?0.5)?1.2， 10

1(2)x3?(14?1.11?3?1.2)?1.11. 10x1(2)?

１、Jacobian 迭代法:

?a11?aA??21

????an1

a12a22?an2

?a1n??a11

?0?a2n????

?????

??

?ann??00??0?

??aa22??????210

??0?????

??

?0ann???an1??ann?1

?

0??0?a12??0?????????0??0?a1n???????an?1n?2、

?

?0??

?D?L?U

Gauss-Seidel 迭代法:

Ax?b??1?1

?xn?1??D?L?Uxn??D?L?b?

?A?D?L?U

（9） ?1

?M??D?L?U???1

?f??D?L?b

根据GS迭代法（9），可进一步得到

xn?1??D?L?Uxn??D?L?b??D?L?xn?1?Uxn?b?xn?1?D?1(Lxn?1?Uxn)?D?1b

?1

?1

即

??00??x1??1

?n???2

?a210?xn??1???1

????D??????????xN???n?1????an1??ann?1

0??x1??0?a12

n?1????2

0??xn?1??00

?

???????

????N??0??xn?1??00

????a1n??x1

n????2

????xn??

?b?

??an?1n?????

???N???0??xn???

（11）

k

式（11）表明：Gauss-Seidel 迭代法在计算第k个迭代值xn?1时，及时地利用了在此步迭代中得到i

n?1步的迭代值通常比第n步的迭代值更接近方程组的新的迭代值：xn?1，i?1,2,?,k?1，由于第

的精确解，所以，在Jacobian迭代法和Gauss-Seidel迭代法都收敛的情况下，Gauss-Seidel迭代

法的收敛速度比Jacobian迭代法的收敛速度快。

例2 解下面方程组（与例1相同，精确解为x*?(1,1,1)T）.

?10x1?3x2?x3?14,?

?2x1?10x2?3x3??5, ?x?3x?10x?14.

23?1

解 1） 原方程组改为等价方程组

?(k?1)1(k)(k)

?(14?3x2?x3),?x1

10

?

?(k?1)1(k)

?(5?2x1(k?1)?3x2),2） 构造迭代公式，即为高斯-赛德尔迭代公式?x2. 10?

?(k?1)1(k?1)(k?1)

?3x2),k?0,1,2,?.?x3?10(14?x1

?

(0)(0)(0)

3） 取初始向量x(0)?(0,0,0)T，即x1?x2?x3?0,代入上式，求出

x1(1)?

1

(14?3?0?0)?1.4， 10

(1)x2?

(1)x31(5?2?1.4?3?0)?0.78， 101?(14?1.4?3?0.78)?1.026. 10

拉格郎日插值法

一、线性插值(Linear Interpolation)

当n?1时，插值问题的几何意义为：过两个已知点(xi,yi),i?0,1，求直线方程（即一次多项式）. 点斜式直线方程：L1(x)?y0?y1?y0(x?x0). x1?x0

x?x1x?x0y0?y1. x0?x1x1?x0两点对称式直线方程：L1(x)?

由两点式可知，L1(x)是由两个线性函数

l0(x)?x?x1x?x0 ,l1(x)?x0?x1x1?x0

的线性组合得到.这两个线性函数称为插值基函数，其性质为：

?1,k?ilk(xi)??ki??,k,i?0,1. ?0,k?i

二、抛物插值(Quadratic Interpolation)

当n?2时，插值问题的几何意义为：过已知的三个点(xi,yi),i?0,1,2,求抛物线（即二次多项式）.为了求出L2(x)的表达式，可采用基函数方法，此时基函数l0(x)、l1(x)及l2(x)是二次函数，且在节点上满足条件：

?1,k?ilk(xi)??ki??,k,i?0,1,2. （5.5） ?0,k?i

满足条件（5.5）的插值基函数很容易求出，例如求l0(x)，因为它有两个零点x1及x2，故可表示为l0(x)?A(x?x1)(x?x2)，其中A待定，可由条件l0(x0)?1确定. 于是，l0(x)?(x?x1)(x?x2).同理可求得l1(x)及l2(x).因此，得抛物插值 (x0?x1)(x0?x2)

L2(x)?l0(x)y0?l1(x)y1?l2(x)y2

?(x?x1)(x?x2)(x?x0)(x?x2)(x?x0)(x?x1)y0?y1?y2. (x0?x1)(x0?x2)(x1?x0)(x1?x2)(x2?x0)(x2?x1)

5.2.2 n次拉格朗日插值

用插值基函数表示的一次与二次插值很容易推广到一般情形.下面讨论如何构造通过n?1个节点(xi,yi),i?0,1,?,n的n次插值多项式.设所求多项式为

Ln(x)??lk(x)yk，

k?0n

其中lk(x),k?0,1?,n是次数不超过n的待定多项式（插值基函数）.

要Ln(x)满足插值条件，即Ln(xi)??l(x)yki

k?0nk?yi,从而插值基函数满足条件：

?1,k?ilk(xi)??ki??,k,i?0,1,?,n. （5.6） 0,k?i?

满足条件（5.6）的插值基函数很容易求出，例如求lk(x).因为x0,x1,?,xk?1,xk?1,?,xn是n次多项式lk(x)的n个零点，可设

lk(x)?A(x?x0)(x?x1)?(x?xk?1)(x?xk?1)?(x?xn)，

又由lk(xk)?1，得到

A?1， (xk?x0)(xk?x1)?(xk?xk?1)(xk?xk?1)?(xk?xn)

因此，当k?0,1,?,n时,lk(x)??(

i?0i?knx?xi).n次Lagrange插值多项式为 xk?xi

Ln(x)??lk(x)yk??[?(

k?0k?0i?0i?knnnx?xi)]yk. （5.7） xk?xi

例1 已知y?sinx的函数值y0?sin?

6?1?2?3,sin??y1,sin??y2,见表5-2，求24232

sin5?24的近似值.

解 1） 用线性插值计算，因为5?24在?6~?4之间，故取两点x0??6，x1??4，则有线性插值

L1(x)?

5?5??L1()?0.603553. 2424

2） 用过三点的抛物插值计算，有 ?2， ?1?22??6446x??x??所以sin