数值分析第六章

1、第六章第六章 曲线拟合曲线拟合6.1.2 曲线拟合问题仍然是已知仍然是已知 x1 xm ; y1 ym, 求一个简单易求一个简单易算的近似函数算的近似函数 f(x) 来拟合这些数据来拟合这些数据。但是但是 m 很大；很大； yi 本身是测量值，不准确，即本身是测量值，不准确，即 yi f (xi)这时没必要取这时没必要取 f(xi) = yi , 而要使而要使 i=f(xi) yi 总体上总体上尽可能地小。尽可能地小。这种构造近似函数这种构造近似函数 的方法称为的方法称为曲线拟合，f(x) 称为称为拟合函数拟合函数称为称为“残差残差”常见做法：常见做法：u使使 最小最小|)(|max1iimi

2、yxP 较复杂，较复杂，P284u使使 最小最小 miiiyxP1|)(|不可导，求解困难，不可导，求解困难，P283u使使 最小最小 miiiyxP12|)(|“使使 i=P(xi) yi 尽可能地小尽可能地小”有不同的准有不同的准则则6.2 线性拟合问题6.2.1 |.|2 意义下的线性拟合（线性最小二乘问题）确定拟合函数确定拟合函数 ，对于一组数据，对于一组数据(xi, yi) (i = 1, 2, , m) 使得使得 达到达到极小极小，这里，这里 n n), 称线性方程组Ax=b (1)(1) 为超定方程组超定方程组; 这里xRn,bRm. 如果A的秩r(A)=n, 称A为列满秩矩阵列

3、满秩矩阵. . 记残向量r=b-Ax，考虑确定一个向量x， 使r2 2b-Ax2 2, 达到最小的问题称为线性最小二乘问题线性最小二乘问题， 这样的x称为方程组(1)的最小二乘解最小二乘解. .6.3.4 最小二乘解的存在惟一性 结论1 ：设A是mn阶矩阵，xRn, bRm. 由线性方程组理论可知，线性方程组 Ax=b (24) 有解的充分必要条件是 r (A)= r (A|b). (25) 定理定理6.3.7假设方程组假设方程组(24)有解，令有解，令x是其一个是其一个解解. 那么，方程组那么，方程组(24)的所有解的集合为的所有解的集合为x+N(A). 方程组方程组(24)有有 惟一解的充

4、分必要条惟一解的充分必要条件是件是null(A)=0. 这里，这里， null (A)表示表示A的核子空的核子空间的维数间的维数. 证明: 首先首先证明任意的向量yx+N(A)都是方程组(24)的解. 事实上，将y记为y=x+z, 其中zN(A)， 即Az=0，xx. 因此， Ay=Ax+Az=b,即y满足方程组(24). 反过来， 若y满足方程组(24)， 有 Ay-Ax =A(y-x)= 0， 即y-xN(A). 记y=x+(y-x)，从而有yx+N(A). 惟一性惟一性. 因为齐次方程组Ax=0有惟一零解的充 分必要条件是A为满秩矩阵，即null (A)=0. 定理定理6.3.8当当mn

5、时，时， 超定方程组超定方程组(1)的最小二乘解总是存在的的最小二乘解总是存在的. 最小最小二乘解惟一的充分必要条件是二乘解惟一的充分必要条件是null (A)=0. 证: 记b=bb， 其中b1R(A)，b2N(A）. 对任意xRn, AxR(A), b1-AxR(A). 因此， r22b-Ax22(b-Ax)+b22. 由定理6.3.3的推论1和定理6.3.2， r22b-Ax22+b22 要使r22达到最小等价于确定x，使b-Ax22 为0， 即求方程组Ax=b的解x. 因为b,Ax, bAx都是R(A)中的向量，因此，可以 把b看成由A的列向量线性表示， 即bAx. 换句话说，方程组A

6、x=b的解总是存在的，从而方程 组(1)的最小二乘解也总是存在的. 惟一性的证明可直接由定理6.3.7得到. 6.3.1 正交性的有关性质 在线性代数欧氏空间理论中， 将R3中两个向量x,y之间的夹角满足的关系式 xTy=x2y2cos (2) 推广到Rn. 设x,yRn， 由Cauchy不等式 -1 1 从而得到Rn中两个向量之间的夹角为 =arccos (3)22Tx yxy22Tx yxy 定理定理6.3.1 设x, y是Rn中的向量， x与y正交 的充分必要条件为xy=0. 证：必要性. 当x与y正交，它们的夹角=/2， 由(2)式， 有xy=0. 充分性. 当xy=0, 由(3)式，

7、=/2, 即x与y正交. 注： 如果x与y正交， 记为xy定理6.3.2：设x， yRn， 且xy，那 么： x+y22x22y22 证：由x+y22=(x+y) (x+y) = xx+2yx+yy 而xy=yx=0, 因此 x+y22x22+y22注：注：推广到Rn中的向量组，k， 如果ij=0 (ij), 称1，2，k是 正交向量组正交向量组. 特别地特别地: 如果i2=1(i=1,2,，k)， 即 iTj=ij，称1，2，k 为标准正交向量组. 设U是Rn中的子空间， xRn. 如果x与U中任意向量正交， 称向量向量x与子空间与子空间U正交正交， 记为xU. 设U，V是Rn中两个子空间，

8、 如果任意xU和任意yV是正交的， 称子空间子空间U与子空与子空间间V正交正交， 记为UV. 设U，V是Rn中互补的子空间. 如果UV， 那么称U，V互为正交补子空间正交补子空间， 记U=V或V=U. 可以证明， 一个子空间的正交补子空间是惟一的.定理定理6.3.3 设A是nk阶矩阵，xRn, 那么下列三种情况是 等价的： xR(A); Ax=0; xN(A). 这里，N(A)=Ax=0, xRn称为称为A的核子空间的核子空间.证：由N(A)的定义， 与显然等价. 下面证明与等价. 记A=(1,2,，k)， 那么，iR(A) (i=1,2,k). 假设xR(A), 即ix=0 (i=1,2,，

9、k). 从而Ax=0. 另一方面，如果Ax=0, 那么有zRk， 使Az=yR(A). 这时，yx=zAx=0,即xy. 由z的任意性， 得Az是任意的， 因此xR(A). 由这个定理，由这个定理， 容易得到：容易得到： 推论推论1设A是nk阶矩阵， 那么R(A)有惟一的正交补子 空间N(A). 6.3 线性最小二乘问题设A是mn阶矩阵(mn), 称线性方程组Ax=b (1) 为超定方程组超定方程组; 这里xRn, bRm. 如果A的秩r (A) =n, 称A为列满秩矩阵列满秩矩阵. 记残向量r=b-Ax， 考虑确定一个向量x， 使r2 2b-Ax2 2, 达到最小的问题称为线性线性最小二乘问

10、题最小二乘问题， 这样的x称为方程组(1)的最最小二乘解小二乘解.6.3.1 正交性的有关性质 在线性代数欧氏空间理论中， 将R3中两个向量x,y之间的夹角满足的关系式 xTy=x2y2cos (2) 推广到Rn. 设x,yRn， 由Cauchy不等式 -1 1 从而得到Rn中两个向量之间的夹角为 =arccos (3)22Tx yxy22Tx yxy 定理定理6.3.1 设x, y是Rn中的向量， x与y正交 的充分必要条件为xy=0. 证：必要性. 当x与y正交，它们的夹角= /2， 由(2)式， 有xy=0. 充分性. 当xy=0, 由(3)式，=/2, 即x与y正交. 注： 如果x与y

11、正交， 记为xy定理6.3.2：设x， yRn， 且xy，那 么： x+y22x22y22 证：由x+y22=(x+y) (x+y) = xx+2yx+yy 而xy=yx=0, 因此 x+y22x22+y22 注：注：推广到Rn中的向量组，k， 如果ij=0 (ij), 称1，2，k是 正交向量组正交向量组. 特别地特别地: 如果i2=1(i=1,2,，k)， 即 iTj=ij，称1，2，k 为标准正交向量组. 设U是Rn中的子空间， xRn. 如果x与U中任意向量正交， 称向量向量x与子空间与子空间U正交正交， 记为xU. 设U，V是Rn中两个子空间， 如果任意xU和任意yV是正交的， 称子

12、空间子空间U与子空与子空间间V正交正交， 记为UV. 设U，V是Rn中互补的子空间. 如果UV， 那么称U，V互为正交补子空间正交补子空间， 记U=V或V=U. 可以证明， 一个子空间的正交补子空间是惟一的.定理定理6.3.3 设A是nk阶矩阵，xRn, 那么下列三种情况是 等价的： xR(A); Ax=0; xN(A). 这里，N(A)=Ax=0, xRn称为称为A的核子空间的核子空间.证：由N(A)的定义， 与显然等价. 下面证明与等价. 记A=(1,2,，k)， 那么，iR(A) (i=1,2,k). 假设xR(A), 即ix=0 (i=1,2,，k). 从而Ax=0. 另一方面，如果A

13、x=0, 那么有zRk， 使Az=yR(A). 这时，yx=zAx=0,即xy. 由z的任意性， 得Az是任意的， 因此xR(A). 由这个定理，由这个定理， 容易得到：容易得到： 推论推论1设A是nk阶矩阵， 那么R(A)有惟一的正交补子 空间N(A). 6.3.2 矩阵的QR分解定理定理6.3.4 设A=(1,2,，n)是列满秩矩阵，iRm (i=1,2,，n)且mn. 那么， A有惟一的QR分解，记为 A=QR， (4)这里，Q是有n个标准正交列的mn阶矩阵，R是有正对角元的n阶上三角矩阵.证：证：由A是列满秩矩阵可知， AA是n阶正定矩阵， 因此有 惟一的Cholesky分解： AA=

14、RR, (5) 这里R是有正对角元的上三角矩阵， R存在. 令Q=AR, (6) 那么， QQ=RAARIn,即Q是有标准正交列的mn阶矩阵.由(6)式， (4)式成立， 且由(5)式的惟一性， 分解式(4)也是惟一的. 6.3.3 Householder矩阵与矩阵的正交三角化 定义定义1设w是欧氏空间Rn中的单位向量， 形如H=I-2ww (10) 的n阶矩阵称为Householder矩阵， 也称 为反射(镜像)矩阵或称为Householder变 换(反射变换、镜像变换). 定理6.3.5 设H是Rn中的Householder 矩阵， 那么， H=H (对称性)； H=H (正交性)； H2

15、=I (对合性).证：直接验证， 性质成立. 由H=I-2ww, ww=1和性质， H2HH=(I-2ww) (I-2ww) =I-4wwww+4ww=I, 即H=H-1，性质和成立. 定理定理6.3.6设Rn中有非零向量xy 且x2=y2，那么，存在 Householder矩阵H，使Hx=y 证：不妨令w=(x-y)/ x-y2 ,有wTw=1.设H=I- 2wwT ,那么 Hx=(I-2wwT) 由已知， xx=yy. 所以 (x-y)(x-y)=xx- 2yx+yy=2(xx-yx). 从而， Hx=x-(x-y)=y. 证明中如果令u=x-y， 那么Householder矩阵形为(11

16、)式，即H=I-uu,=uu. 同样可验证Hx=y成立. ()()()()22()()()()TTTTTTx y x y xx y xx yx xxxx y x yx y x y 例例1 设设R3中向量中向量x=(0,4,3)和向量和向量e1，其中其中2=x，即即= =5. 按按(11)式构造一个式构造一个3阶阶Householder矩阵矩阵H，使使Hx=e1. 解解:令令u=x-e1.设设=-5, 于是于是 u=(-5, 4, 3) 又由又由uu=25+16+9=50, 所以所以=25. 由由H=I-uu, 得得 2243100510104(5, 4, 3)2500130201512091225151216H 容易验证容易验证Hx=e1. 在