数值分析第六章.ppt

第六章 曲线拟合6.1.2 曲线拟合问题仍然是已知 x1 … xm ; y1 … ym, 求一个简单易 算的近似函数 f(x) 来拟合这些数据但是① m 很大；② yi 本身是测量值，不准确，即 yi  f (xi)这时没必要取 f(xi) = yi , 而要使 i=f(xi)  yi 总体上尽可能地小 这种构造近似函数 的方法称为曲线拟合，f(x) 称为拟合函数称为“残差”常见做法：u使 最小较复杂， P284u使 最小不可导，求解困难，P283u使 最小“使 i=P(xi)  yi 尽可能地小”有不同的准则6.2 线性拟合问题 6.2.1 ||.||2 意义下的线性拟合（线性最小二 乘问题）确定拟合函数 ，对于一组数据(xi, yi) (i = 1, 2, …, m) 使得 达到极小，这里 n n), 称线性方程组￿ Ax=b (1)￿为超定方程组; 这里x∈Rn,b∈Rm. 如果A的秩r(A)=n, 称A为列满秩矩阵.￿记残向量r=b-Ax，考虑确定一个向量x，使‖r‖2 2＝‖b-Ax‖2 2, 达到最小的问题称 为线性最小二乘问题， 这样的x称为方程组 (1)的最小二乘解.￿6.3.4 最小二乘解的存在惟一性 结论1 ：设A是m×n阶矩阵，x∈Rn, b∈Rm. 由线性方程组理论可知，线性方程组￿Ax=b (24)￿有解的充分必要条件是￿ ￿ r (A)= r (A|b). (25)定理6.3.7￿￿ 假设方程组(24)有解，令x是其一 个解. 那么，方程组(24)的所有解的集合为 {x}+N(A). 方程组(24)有 惟一解的充分必要条 件是null(A)=0. 这里， null (A)表示A的核子 空间的维数.证明: 首先证明任意的向量y∈{x}+N(A)都是方程 组(24)的解.￿ 事实上，将y记为y=x+z,￿其中z∈N(A)， 即Az=0，x∈{x}. 因此， Ay=Ax+Az=b,￿ 即y满足方程组(24).￿反过来， 若y满足方程组(24)， 有Ay-Ax =A(y-x)= 0，￿即y-x∈N(A).￿记y=x+(y-x)，从而有y∈｛x｝+N(A).￿惟一性. 因为齐次方程组Ax=0有惟一零解的 充 分必要条件是A为满秩矩阵，即null (A)=0. 定理6.3.8￿￿ 当m>n时， 超定方程组 (1)的最小二乘解总是存在的. 最小 二乘解惟一的充分必要条件是 ￿￿ null (A)=0.￿• 证: 记b=b１＋b２， 其中b1∈R(A)，b2∈N(AＴ）.￿对任意x∈Rn, Ax∈R(A), b1-Ax∈R(A). 因此， ‖r‖22＝‖b-Ax‖22＝‖(b１-Ax)+b２‖22.￿由定理6.3.3的推论1和定理6.3.2，￿‖r‖22＝‖b１-Ax‖22+‖b２‖22．￿要使‖r‖22达到最小等价于确定x，使‖b１-Ax‖22 为0， 即求方程组Ax=b１的解x.￿因为b１,Ax, b１－Ax都是R(A)中的向量，因此 ，可以 把b１看成由A的列向量线性表示， 即b１＝ Ax.￿换句话说，方程组Ax=b１的解总是存在的，从 而方程 组(1)的最小二乘解也总是存在的.￿惟一性的证明可直接由定理6.3.7得到. 6.3.1 正交性的有关性质性代数欧氏空间理论中， 将R3中两个向 量x,y之间的夹角φ满足的关系式￿xTy=‖x‖2‖y‖2cosφ (2)￿推广到Rn. 设x,y∈Rn， 由Cauchy不等式 ￿-1≤ ≤1￿从而得到Rn中两个向量之间的夹角为φ=￿ arccos (3)￿定理6.3.1 设x, y是Rn中的向量， x与y正交 的充分必要条件为xＴy=0.￿证：必要性. 当x与y正交，它们的夹角φ=π/2 ， 由(2)式， 有xＴy=0.￿充分性. 当xＴy=0, 由(3)式，φ=π/2, 即x与y正交.￿￿注： 如果x与y正交， 记为x⊥y定理6.3.2：设x， y∈Rn， 且x⊥y，那 么：‖x+y‖22＝‖x‖22＋‖y‖22．￿证：由‖x+y‖22=(x+y)Ｔ (x+y)= xＴx+2yＴx+yＴy￿而xＴy=yＴx=0, 因此￿‖x+y‖22＝‖x‖22+‖y‖22￿ 注：推广到Rn中的向量组α１，α２，…，αk， 如果αiＴαj=0 (i≠j), 称α1，α2，…，αk是正交向量组. • 特别地: 如果‖αi‖2=1(i=1,2,…，k)， 即αiTαj=δij，称α1，α2，…，αk为标准正交向量组. • 设U是Rn中的子空间， x∈Rn. 如果x与U中 任意向量正交， 称向量x与子空间U正交 ， 记为x⊥U. • 设U，V是Rn中两个子空间， 如果任意 x∈U和任意y∈V是正交的， 称子空间U 与子空间V正交， 记为U⊥V. • 设U，V是Rn中互补的子空间. 如果U⊥V ， 那么称U，V互为正交补子空间， 记 U=V⊥或V=U⊥. 可以证明， 一个子空间的 正交补子空间是惟一的.￿定理6.3.3 设A是n×k阶矩阵，x∈R￿ n, 那么下列三种情况是等价的：￿①x⊥R(A);￿②AＴx=0;￿③x∈N(AＴ).￿这里，N(AＴ)={AＴx=0￿￿ , x∈Rn}称为AＴ的核子空间.￿ 证：由N(AＴ)的定义， ②与③显然等价.￿下面证明①与②等价.￿记A=(α1,α2,…，αk)， 那么，αi∈R(A) (i=1,2,…,k).￿假设x⊥R(A), 即αiＴx=0 (i=1,2,…，k). 从而AＴx=0￿ .￿另一方面，如果AＴx=0, 那么有z∈Rk， 使Az=y∈R(A). 这时，yＴx=zＴAＴx=0,￿ 即x⊥y. 由z的任意性， 得Az是任意的， 因此x⊥R(A). • 由这个定理， 容易得到：￿￿推论1￿ 设A是n×k阶矩阵， 那么R(A)有惟一的正交补子空间N(AＴ). 6.3 线性最小二乘问题设A是m×n阶矩阵(m>n), 称线性方程组￿ Ax=b (1)￿为超定方程组; 这里x∈Rn, b∈Rm. 如果A的秩￿ r (A) =n, 称A为列满秩矩阵.￿记残向量r=b-Ax， 考虑确定一个向量x， 使‖r‖2 2＝‖b-Ax‖2 2, 达到最小的问题称为线性 最小二乘问题， 这样的x称为方程组(1)的最 小二乘解.￿6.3.1 正交性的有关性质性代数欧氏空间理论中， 将R3中两个向 量x,y之间的夹角φ满足的关系式￿xTy=‖x‖2‖y‖2cosφ (2)￿推广到Rn. 设x,y∈Rn， 由Cauchy不等式 ￿-1≤ ≤1￿从而得到Rn中两个向量之间的夹角为 ￿φ=￿ arccos (3)￿定理6.3.1 设x, y是Rn中的向量， x与y正交 的充分必要条件为xＴy=0.￿证：必要性. 当x与y正交，它们的夹角φ= π/2， 由(2)式， 有xＴy=0.￿充分性. 当xＴy=0, 由(3)式，φ=π/2, 即x与y正交.￿￿注： 如果x与y正交， 记为x⊥y定理6.3.2：设x， y∈Rn， 且x⊥y，那 么：‖x+y‖22＝‖x‖22＋‖y‖22．￿证：由‖x+y‖22=(x+y)Ｔ (x+y)= xＴx+2yＴx+yＴy￿而xＴy=yＴx=0, 因此￿‖x+y‖22＝‖x‖22+‖y‖22￿• 注：推广到Rn中的向量组α１，α２，…，αk， 如果αiＴαj=0 (i≠j), 称α1，α2，…，αk是正交向量组. • 特别地: 如果‖αi‖2=1(i=1,2,…，k)， 即αiTαj=δij，称α1，α2，…，αk为标准正交向量组. • 设U是Rn中的子空间， x∈Rn. 如果x与U中 任意向量正交， 称向量x与子空间U正交 ， 记为x⊥U. • 设U，V是Rn中两个子空间， 如果任意 x∈U和任意y∈V是正交的， 称子空间U 与子空间V正交， 记为U⊥V. • 设U，V是Rn中互补的子空间. 如果U⊥V ， 那么称U，V互为正交补子空间， 记 U=V⊥或V=U⊥. 可以证明， 一个子空间的 正交补子空间是惟一的.￿定理6.3.3 设A是n×k阶矩阵，x∈R￿ n, 那么下列三种情况是等价的：￿①x⊥R(A);￿②AＴx=0;￿③x∈N(AＴ).￿这里，N(AＴ)={AＴx=0￿￿ , x∈Rn}称为AＴ的核子空间.￿ 证：由N(AＴ)的定义， ②与③显然等价.￿下面证明①与②等价.￿记A=(α1,α2,…，αk)， 那么，αi∈R(A) (i=1,2,…,k).￿假设x⊥R(A), 即αiＴx=0 (i=1,2,…，k). 从而AＴx=0￿ .￿另一方面，如果AＴx=0, 那么有z∈Rk， 使Az=y∈R(A). 这时，yＴx=zＴAＴx=0,￿ 即x⊥y. 由z的任意性， 得Az是任意的， 因此x⊥R(A). 由这个定理， 容易得到：￿￿推论1￿ 设A是n×k阶矩阵， 那么R(A)有惟一的正交补子空间N(AＴ). 6.3.2 矩阵的QR分解定理6.3.4 设A=(α1,α2,…，αn)是列满秩矩阵，αi∈Rm (i=1,2,…，n)且m≥n. 那么， A有惟一的QR分解，记为￿ A=QR， (4)￿ 这里，Q是有n个标准正交列的m×n阶矩阵，R是有正对角 元的n阶上三角矩阵.￿ 证：由A是列满秩矩阵可知， AＴA是n阶正定矩阵， 因此 有 惟一的￿ Cholesky￿ 分解：￿AＴA=RＴR, (5)￿这里R是有正对角元的上三角矩阵， R－１存在.令￿ Q=AR－１, (6)￿那么， QＴQ=R－ＴAＴAR－１＝In,￿ 即Q是有标准正交列的m×n阶矩阵.￿ 由(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=I (对合性).￿ 证：直接验证， 性质①成立.￿由H=I-2wwＴ, wＴw=1和性质①，￿H2＝HＴH=(I-2wwＴ)Ｔ (I-2wwＴ)=I-4wwＴwwＴ￿ +4wwＴ=I,￿即HＴ=H-1，性质②和③成立. 定理6.3.6￿ 设Rn中有非零向量x≠y且‖x‖2=‖y‖2，那么，存在 Householder矩阵H，使Hx=y 证：不妨令w=(x-y)/ ‖x-y‖2 ,有wTw=1.设H=I- 2wwT ,那么 Hx=(I-2wwT)由已知， xＴx=yＴy. 所以 (x-y)Ｔ(x-y)=xＴx- 2yＴx+yＴy=2(xＴx-yＴx).￿从而， Hx=x-(x-y)=y. 证明中如果令u=x-y， 那么Householder矩阵形为(。