《经济数学基础》课程教学资源：实验5 线性代数方程组的数值解法

为什么县学习能性才覆 大学数学实验 的教值解法 Experiments in Mathematics 许多实际问题归结为线性(代数)方程组 机械设备、土建结构的受力分析 经济计划 实验5线性代数方程组的数值解法 输电网络、管道系统的参数计算企业管理 大型的方程组需要有效的数值解法 半大歇教科系 教值解法的稳定性和收敛性问题需要注意 实验5的走內内率 线性方程组的一般形式、两类解法 anx1+a2x2+…+ax=b 1.两类数值解法: a2x+a2x2+…+a2x,=b2 或AX=b 直接方法;选代方法 ax.+ax.+…+ax=b 2.超定线性方程组的最小二乘解 经过有限次算术迳算求出精确解(实际上 3.线性方程组数值解法的 MATLAB实现 由于有舍入误差只能得到近似解) 高 (GBu8)消元法及与它密切相关的矩阵UU分解 4.实际问题中方程组的数值解 选代法从初始解出发,根据设计好的步骤用次 求出的近似解逼近精确解 雅可比(J8cobi 选代法和高斯一塞德尔( Gauss-Seide1)选代法 (学静学实鉴 学学实纷 直接法一高斯消元法 直接法-列主元素消元法 a1x1+a1x,+…+anx 高斯消元法条件 a2x2+…+a2xn=2 ak(绝对值)很小时, +ax,= 过 用它作除数会导致舍入误 ami. 差的很大增加 qx1+ax2+……+amxn=b +……+ak)x=kk) 解￥ amx,t++. 办法 条件 过 最大的一个(列主元) 程 将列主元所在行与第k行交换后,再按上面的高斯消元 (k=1,2,…,n) 进行下去,称为列主元素消元法

1 大学数学实验 Experiments in Mathematics 实验5 线性代数方程组的数值解法 清华大学数学科学系 • 许多实际问题归结为线性（代数）方程组 • 大型的方程组需要有效的数值解法 • 数值解法的稳定性和收敛性问题需要注意 为什么要学习线性方程组 的数值解法 机械设备、土建结构的受力分析 输电网络、管道系统的参数计算 经济计划 企业管理 3. 线性方程组数值解法的MATLAB实现 4. 实际问题中方程组的数值解。 1. 两类数值解法: 直接方法；迭代方法 实验5的主要内容 2. 超定线性方程组的最小二乘解 线性方程组的一般形式、两类解法 直接法 经过有限次算术运算求出精确解（实际上 由 于 有 舍 入 误 差 只 能 得 到 近 似 解 ） ---- 高 斯 （Gauss）消元法及与它密切相关的矩阵LU分解 迭代法 从初始解出发，根据设计好的步骤用逐次 求出的近似解逼近精确解 ---- 雅可比（Jacobi） 迭代法和高斯—塞德尔（Gauss—Seidel）迭代法 n n nn n n n n n n a x a x a x b a x a x a x b a x a x a x b + + + = + + + = + + + = L LL L L 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 或 AX=b 直接法---高斯消元法 (2) (2) 2 (2) 2 (2) 2 (2) 2 2 (2) 22 (1) 1 (1) 2 1 (1) 1 12 (1) 11 n nn n n n n n n a x a x b a x a x b a x a x a x b + + = + + = + + + = L LL L L ( ) ( ) ( 1) 1 ( 1) 1 1, ( 1) 1, 1 (2) 2 (2) 2 2 (2) 22 (1) 1 (1) 2 1 (1) 1 12 (1) 11 n n n n nn n n n n n n n n n n n n n n a x b a x a x b a x a x b a x a x a x b = + = + + = + + + = − − − − − − − − LL LL LL 消 元 过 程 回 代 过 程 ( 1,2, , ) 0 ( ) k n a k kk = L ≠ 条件 直接法-列主元素消元法 0( 1,2, , ) ( ) a k n k 高斯消元法条件 kk ≠ = L 解决 办法 ( , ) ( ) a i k n k 选 ik = L 最大的一个（列主元） 将列主元所在行与第k行交换后, 再按上面的高斯消元 法进行下去，称为列主元素消元法。 (绝对值 )很小时， 用它作除数会导致舍入误 差的很大增加 (k) kk a ( ) ( ) ( ) ( ) ( ) ( ) k n n k k nn k nk k n k k k kn k kk a x a x b a x a x b + + = + + = LL LL LL

直接法一高斯消元法的矩阵表示 直接法一高斯消元法的矩阵表示 高斯消元法的第一次消元 第二次消元相当于再左乘单位下三角阵M a11+a12x2+……+a1nx ax+ax2+…+amxn= M4x=Mb口M2MAx=M2Mb a,x,+anx+-+a, x=b a2x2+…+a23xn=b2 最终消元形式M。…M2M1Ax=Mn…MMb 记Mn1…M2M1 an1x1+a2x2+…+amxn=b anx2+…+axn=b M为单位下三角阵 相当于方程 -a/a1 Ux= Mb AX=b两边 左乘单位下 M, Ax= M, b U为上三角阵,且 ap-L- r+ap=, =b el 三角阵M1 对角元素a()≠0 x=U-Mb 直油-矩I分解 直油-矩陈分解 若A可逆,但顺序主子式D≠0不成立 0已A的顺序主子式D (k=1,2,…,n) 消元中会遇到某个an=0,但必存在aA)≠0=k+1…n) 高斯消元法通过左乘M使MA=U记L=M,L为 第行与第A行交换日乘以初等交换阵 M单位下三角阵,U上三角阵 单位下三角阵 若A可逆且顺序主子式不为零,则A可分解为一个 P~交换阵(单位阵经若干次行交换) 单位下三角阵和一个上三角阵U的积A=LU 若A可逆,则存在交换阵P使PA=LU 这种分解是唯一的,称矩阵LU分解。 L为单位下三角阵,U为上三角阵 学学实 (大学数学实验) 直接法一对称正定矩阵的分解 直接法一三对角矩阵的L解 正定对称矩阵A可分解成对角元素为正的 在三次样条插值和其它一些计算中,会遇到求解系数矩阵A具有 下三角阵L与它的转置矩阵之积,即 对角形式的线性方程组,这时A的LU分解(假定分解存在) 可表为: 或A=LDL 4,h c 其中L是单位下三角阵,D是元素为正的对角阵 这种分解称三角分解或 Cholesky分解 L和U的计 算公式为 =b-l-1t=2,3…n

2 直接法 - 高斯消元法的矩阵表示 相当于方程 AX=b 两 边 左乘单位下 三角阵M1 ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − = / 1 / 1 1 (1) 11 (1) 1 (1) 11 (1) 21 1 a a a a M n LL O n n nn n n n n n n a x a x a x b a x a x a x b a x a x a x b + + + = + + + = + + + = L LL L L 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 高斯消元法的第一次消元 (2) (2) 2 (2) 2 (2) 2 (2) 2 2 (2) 22 (1) 1 (1) 2 1 (1) 1 12 (1) 11 n nn n n n n n n a x a x b a x a x b a x a x a x b + + = + + = + + + = L LL L L M1Ax = M1b 最终消元形式 M n−1LM 2M1Ax = M M M b n−1L 2 1 直接法 - 高斯消元法的矩阵表示 第二次消元相当于再左乘单位下三角阵M2 M1Ax = M1b M2M1Ax = M2M1b 1 21 , Mn MM M M 记 − L = 为单位下三角阵 记 MA =U Ux = Mb 0 , ( ) ≠ k kk a U 对角元素 为上三角阵 且 ( ) ( ) ( 1) 1 ( 1) 1 1, ( 1) 1, 1 (2) 2 (2) 2 2 (2) 22 (1) 1 (1) 2 1 (1) 1 12 (1) 11 n n n n nn n n n n n n n n n n n n n n a x b a x a x b a x a x b a x a x a x b = + = + + = + + + = − − − − − − − − LL LL LL x U Mb −1 = 直 接 法 - 矩 阵 LU 分 解 高斯消元法通过左乘M,使MA=U M单位下三角阵，U上三角阵 记 L=M-1，L为 单位下三角阵 若A可逆且顺序主子式不为零，则A可分解为一个 单位下三角阵L和一个上三角阵U的积 A=LU。 这种分解是唯一的，称 矩阵LU分解。 ( 1,2, , ) 0 ( ) k n a k kk = L ≠ 0, ( 1, ) 1 11 1 k n a a a a A D k kk k L L M M L 的顺序主子式 = ≠ = 若A可逆，则存在交换阵 P 使 PA=LU L为单位下三角阵，U为上三角阵。 第i行与第k行交换 0 0( 1, ) ( ) ( ) a a i k n k ik k 消元中会遇到某个 kk = ，但必存在 ≠ = + L 直 接 法 - 矩 阵 LU 分 解 若A可逆，但顺序主子式 D ≠ 0不成立 乘以初等交换阵 MA =U ⇒ MPA =U P~交换阵（单位阵经若干次行交换） 直接法 - 对称正定矩阵的分解 正定对称矩阵 A 可分解成对角元素为正的 下三角阵 L 与它的转置矩阵之积，即 T A = LL T 或 A = LDL 其中 L 是单位下三角阵，D 是元素为正的对角阵。 这种分解称三角分解或 Cholesky 分解。 直接法 - 三对角矩阵的LU分解 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = − − − − − n n n n n n n n n u u c u c u c l l l a b a b c a b c b c A 1 1 2 2 1 1 3 2 1 1 1 2 2 2 1 1 1 1 1 1 O O O O O O O 1 1 1 1 2,3, , 2,3, , i i i i i ii u b a l in u u b lc i n − − ⎧ = ⎪ ⎪ ⎨ = = ⎪ ⎪⎩ =− = L L 在三次样条插值和其它一些计算中，会遇到求解系数矩阵A具有 三对角形式的线性方程组，这时A的LU分解（假定分解存在） 可表为: L和U的计 算公式为

A x=b 大学静学实扮 直接法一三对角矩阵的L解 真染-误基分「1「x 线性方程组Ax=通过等价的两个三角形 X+x2=2 11.01x2 方程组Ly=/和Ux=y求解如下 x1+10lx=2 y=f x+1.01x2=2.01 y=f-y,i=2…n x对b的扰动 jx x=(y-cx)l4,i=n-1-…1 Ax=b,如果解x对b或A的扰动敏感,就称方程组是 求解三对角形方程組的追赶法 病态的,也称系数矩阵A是病态的 向量和矩阵的救底量向量、绳阵大小的量指 条件敷与误差分析Ax=bA|s4| 向量范数设x=(x,…xn),范数记作| A(x+x)=b+荡口Aox=b 最常用的向量范数是2-范数2=(x+ 日科H网 1-范数风=x+…+∞-范数|L=max(…|x |4叫|≥|4 矩阵范款设A=(an)nn,范数记作|4 ‖北l= YmaNA)2-范数max表示最大特征根 1Ah=maxa(-范数)AL2=maxl(∞-范数 定义的条件数为Cond(4)=|4-1|4 A的条件数越大,(由的扰动引起的)x的误差可能越大 量和细降花的幅亭|4≤|4 (学静学实鉴 (大学数学实验) 条件敷与误差分析 选代法一一个例子 2)设A有扰动6A,分析x的误差8x x1=-0.3x2-0.x3+1.4 (A+SA(x+ Sx)=b 0.lx1-0.3x+14 cond(a) k=0,1,2 A的条件数越大,(由A的扰动引起的)x的误差越大 x3(k+)=-01x)-03x2()+14 x的(相对)误差不超过b的(相对)误差的ConA)倍, x0)=x0)=0x=1.4,x2=0.5,x 也大致上是A的(相对误差的Con4)倍 x1)=0.9906x=09645x4=0 条件教大的矩阵是病态矩阵 精确解x1=x2=x3=1

3 1 1 1 1 , 2, , / ( )/ , 1, ,1 i i ii n nn i i ii i y f y f ly i n x yu x y cx u i n − + ⎧ = ⎨ ⎩ =− = ⎧ = ⎨ ⎩ = − =− L L 线性方程组Ax=f可通过等价的两个三角形 方程组Ly=f和Ux=y求解如下 : 直接法 - 三对角矩阵的LU分解 求解三对角形方程组的追赶法 直接法-误差分析 （1,1） 1.01 2.01 1 2 x + x = x2 2 x 0 2 1 1.01 2 2 1 2 1 2 + = + = x x x x Ax = b，如果解 x 对 b 或 A 的扰动敏感，就称方程组是 病态的，也称系数矩阵 A 是病态的。 A x = b ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = 0 2 x ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = 1 1 x ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = 2.01 2 b ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ =⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ 2 2 1 1.01 1 1 2 1 x x x对b的扰动 敏感 (2,0) 向量和矩阵的范数 度量向量、矩阵大小的数量指标 向量范数 最常用的向量范数是 2-范数 2 2 1/ 2 2 1 ( ) n x = x +L+ x x x x x T 设 = ( 1 ,L n ) ，范数记作 n − x = x +L+ x 1 1 1 范数 矩阵范数 设 A = (aij ) n×n，范数记作 A ||A||2= max(A A) 2 −范数 T λ λmax 表示最大特征根 = ∑ −范数） = || || max (1 1 1 n i ij j A |a | = ∑ ∞ −范数） = || ||∞ max ( 1 n j ij i A |a | max( , ) 1 n ∞ − x = x L x 范数 ∞ 向量和矩阵范数的相容性条件 Ax ≤ A ⋅ x A(x + δx) = b + δb Aδx = δb b ≤ A ⋅ x b b A A x δx δ ≤ ⋅ ⋅ −1 1）设b有扰动 δb，分析x的误差 δx A的条件数越大,(由b的扰动引起的)x的误差可能越大 条件数与误差分析 Ax = b Ax ≤ A ⋅ x δx A δb −1 = δx ≤ A ⋅ δb −1 x ≥ b / A 1 A Cond A A A ( ) − 定义 的条件数为 = ⋅ b b cond A δ = ( ) ( A + δA)( x + δx) = b x的(相对)误差不超过b的(相对)误差的Cond(A)倍, 也大致上是A的(相对)误差的Cond(A)倍。 条件数与误差分析 2）设A有扰动 δA，分析x的误差 δx Ax = b A的条件数越大,(由A的扰动引起的)x的误差越大 A A cond A A A A A x δx δ δ ( ) 1 ≅ ⋅ ⋅ = − 条件数大的矩阵是病态矩阵 迭代法 --- 一 个 例 子 1 23 1 23 12 3 10 3 14 2 10 3 5 3 10 14 x xx x xx xx x + + = − + =− ++ = 0.1 0.3 1.4 0.2 0.3 0.5 0.3 0.1 1.4 ( ) 2 ( ) 1 ( 1) 3 ( ) 3 ( ) 1 ( 1) 2 ( ) 3 ( ) 2 ( 1) 1 = − − + = + + = − − + + + + k k k k k k k k k x x x x x x x x x 0 (0) 3 (0) 2 (0) 1 x = x = x = k = 0,1,2,L 0.9906, 0.9645, 0.9906 (4) 3 (4) 2 (4) x1 = x = x = 0.1 0.3 1.4 0.2 0.3 0.5 0.3 0.1 1.4 3 1 2 2 1 3 1 2 3 = − − + = + + = − − + x x x x x x x x x 1.4, 0.5, 1.4 (1) 3 (1) 2 (1) x1 = x = x = 精确解 x1 = x2 = x3 = 1

逸代浩-雅可比( Jacobi)迭代 地代-高斯-塞德尔( Gauss- Seder1)迭代 将A分解为A=D-L-U,其中D=diag(a1 cobi选代公式D(+=Lx(k)+Ux()+b 0 0 )+03x4+05 uA1203“+1进x=02x+40x”+05 设对角阵D非奇异(即a≠0,i=1…n)Ax=b Gauss-Seideily选代公式Dx4+)=Lxk+)+Ux)+b 4 Dx-(L+U)x=b x=D(L+U)x+D-b 在D非奇异的假设下(D-L)可逆,于是得到 记B1=D(L+U B2=(D-L)U, f2=(D-L)b 迭代格式 x(+=B2x()+/2(k=0,2…) f=Dbx+=Bx+f(k=012…) 代沽的收笕 B=D-(L+L 选代法的收做性 Jacobi选代x=Bx)+f1f=Db 序列收敛x*)→x'(k→∞)的充分条件 Gauss-Seideili选代x=B2x1)+f2B=(D-0 1)若A是严格对角占优的,即>∑内(=1…m) 一般选代形式x=Bx4+f f2=(D-L)-b 则雅可比和高斯一赛德尔迭代均收敛 星组的解x满足:x=Bx+f 代k次得到x“-x=B(x-x) 2)若A对称正定,则高斯一塞德尔迭代收敛 序列收敛x→x(k→∞)的充要条件 3)若B=q<L,则迭代公式x“=Bx“)+∫收敛 B→0(k→∞)⊙B的所有特征根(取模)小于1 且p-x14k--x越小收敛越快 B的谱半径p(B)=ma B 谱半径性质:P(B)圳B‖其中是任何一种矩阵范数 A(i=1…m)是B的特征根 (学静学实鉴 (大学数学实验) 「选代法一超松弛SOR遗代 迭代法一超松弛SOR选代 auss- Seidel选代公式 D(Lx++U)+ box (k+)=Bx(k) x4和x加权o作平均改进 B,=(D-OL)oU+(1-O)D O(D-OL b C)x(4) 若A对称正 收敛充要条件 >1 <1 超松弛迭代 低松弛迭代 Gaus- Seidel1遗代 SOR选代—解大型稀疏矩阵方程組

4 迭代法 - 雅可比（Jacobi）迭代 将 A 分解为 A = D − L − U ，其中 ( , , ) D = diag a11 a22 Lann ， ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = − ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = − − − 0 0 0 , 0 0 0 1,1 12 1 1 2 , 1 21 n n n n n n a a a U a a a a L O O M L L M O O 设对角阵D非奇异（即a 0, i 1, n) ii ≠ = L f D b B D L U 1 1 1 1 ( ) − − = 记 = + ( 0,1,2 ) 1 ( ) 1 x (k+1) =Bx k + f k = L 迭代格式 Ax = b Dx − (L +U )x = b x D L U x D b 1 1 ( ) − − = + + 迭代法 - 高斯-塞德尔(Gauss-Sedeil)迭代 在D非奇异的假设下(D − L)可逆，于是得到 B D L U f D L b 1 2 1 2 ( ) , ( ) − − = − = − ( 0,1,2 ) 2 ( ) 2 x(k+1) = B x k + f k = L Jacobi迭代公式 Dx Lx Ux b k k k = + + ( +1) ( ) ( ) Dx Lx Ux b k k k = + + Gauss-Seideil迭代公式 ( +1) ( +1) ( ) 0.1 0.3 1.4 0.2 0.3 0.5 0.3 0.1 1.4 ( ) 2 ( ) 1 ( 1) 3 ( ) 3 ( ) 1 ( 1) 2 ( ) 3 ( ) 2 ( 1) 1 =− − + = + + =− − + + + + k k k k k k k k k x x x x x x x x x 改进 0.1 0.3 1.4 0.2 0.3 0.5 0.3 0.1 1.4 ( 1) 2 ( 1) 1 ( 1) 3 ( ) 3 ( 1) 1 ( 1) 2 ( ) 3 ( ) 2 ( 1) 1 = − − + = + + = − − + + + + + + + k k k k k k k k k x x x x x x x x x 迭代法的收敛性 原方程组的解 *x 满足： x = Bx + f * * 1 ( ) 1 ( 1) x B x f k k = + + Jacobi迭代 2 ( ) 2 ( 1) x B x f k k = + + Gauss-Seideil迭代 f D b B D L U 1 1 1 1 ( ) − − = = + f D L b B D L U 1 2 1 2 ( ) ( ) − − = − = − x Bx f k k = + ( +1) ( ) 一般迭代形式 ( ) ( ) * (0) * k x x B x x k k 迭代 次得到 − = − () * ( ) k 序列收敛 的 x xk → →∞ 充要条件 B → 0(k → ∞) k ⇔B的所有特征根（取模）小于1 （ 是 的特征根 的谱半径 i n B B B i i i n 1, ) ( ) max 1 = L = ≤ ≤ λ ρ λ ρ(B) <1 2）若 A 对称正定，则高斯—塞德尔迭代收敛; 迭代法的收敛性 谱半径性质：ρ(B) ≤|| B || 其中||B||是任何一种矩阵范数 () * ( ) k 序列收敛 的 x xk → →∞ 充分条件 则雅可比和高斯 赛德尔迭代均收敛； 若 是严格对角占优的，即 − > ∑ = ≠ 1) A b b (i 1, n), j i ii ij L 3) 若 B = q < 1，则迭代公式 x(k+1) = Bx(k ) + f 收敛 且 x x ，q越小收敛越快 q q x x (k 1) * (k 1) (k ) 1 − − − ≤ + + 迭代法 -超松弛 SOR 迭代 Gauss-Seideil迭代公式 ( 1) 1 ( 1) ( ) 1 ( 1) ( ) k kk k x D Lx Ux D b x +−+ − + = ++ ￾ % ( 1) ( 1) ( ) (1 ) k ~ k k x = ωx + −ω x + + 改进 ( 1) k x ω + % 和x 加权 作平均 k ω > 1 ω < 1 ω = 1 超松弛迭代 低松弛迭代 Gauss-Seideil迭代 ( 1) ( ) 1 1 , ( ) [ (1 ) ], ( ) k k x Bx f B DL U D f D Lb ω ω ω ω ωω ω ω ω + − − = + = − +− = − 迭代法 -超松弛 SOR 迭代 若A对称正定 收敛充要条件 0 2 < ω < SOR 迭代------解大型稀疏矩阵方程组

大学静学实扮 鬼定觉代歙方翟组的录小二最 曲线拟合 使点(xy)与曲线y=/x) 的距高8尽量小户1,n 实验1§2.1汽车刹车距高建立了刹车距离d与车速v f(r) 的关系 d,=k1v,+k2y2,i=1,2,…,n 方程个数超过了未知数个数,称为超定方程组 最小二乘准则 已知一组数据,即平面上n个点x),p=1n寻求一个函数 (曲线)y=fx).使(x)在某种准则下与所有数据点最为接近 使f(x1)与y1(i=1,2…,n)之差的平方和 即曲线拟合得最好 (即图中δ的平方和)最小 曲线拟合-黛恤量小二晁油的基本思路 线性最小二乘法的求解 先选定一组函数rA(x),r2(x),,rm(x),m<n,令 J(a1,a2…an)=∑心∑a(x,)-2(2) f(, r(ray)+.tamr(x) (1) 其中a1a2…am为待定系数 ∑n(x,∑a4r1(x,)-y,=0 0 记J(a,a2…am)=∑82=∑[f(x,)-y )(忘(xn()-小0 =∑∑a(x)-yF r1(x1)…rn(x1) 按照最小二乘准则,问题归结为:求a1a2…am使 r1(xn)…Fn(xn) J(a1a2y…an)最小 (3)→(RRa=Ry(4) 学学实 线性最小二乘法的求解 5问题 2.为什么要规定m<n?若m=n或m>n,会如何? r1(x1)…m(x1) 当RR可逆时(4)有唯一解R 分强令f(x)=a(x)+…+ am(F(G=1,n a=(RR r1(xn)…r(xn) r1(x1)…rn( a={a1,…an Ra=y y1,…ynj 同题 1.怎样选择Gr(x,…rn(o),以保证系数 {apa)有唯一解? 若m>m,a有无穷多解若m=,R可逆时a有唯一解 {a1,a有唯一解←RR可逆←Rank(RR)=m 若m<n,超定方程组,a无解;求最小二乘解 ←Rank(R)=m←R列满秩 问题3.线性最小二乘中的“线性”指的是什么 ←{r(x),…,rm(x)}在x点线性无关(产=1,…n) f(x)对a线性,于是求解线性方程组(RR=Ry

5 超定线性代数方程组的最小二乘解 实验1§2.1汽车刹车距离建立了刹车距离d与车速v 的关系： 2 1 2 d = k v + k v 方程个数超过了未知数个数，称为超定方程组 d k v k v i n i i i , 1,2, , 2 = 1 + 2 = L 数据拟合 已知一组数据，即平面上 n个点(xi ,yi ), i=1,…n, 寻求一个函数 （曲线）y=f(x), 使f(x)在某种准则下与所有数据点最为接近， 即曲线拟合得最好。 数据拟合问题的提法 (#) + + + + + + + + + x y y=f(x) (xi ,yi ) δi 使点(xi ,yi ) 与曲线 y=f(x) 的距离δi尽量小,i=1,…n 曲线拟合 最小二乘准则 δ i i L i 使 f(x )与 y (i=1,2, ,n)之差的平方和 (即图中 的平方和)最小 先选定一组函数 r1(x), r2(x), …rm(x), m<n, 令 f(x)=a1r1(x)+a2r2(x)+ …+amrm(x) （1） 其中 a1,a2, …am 为待定系数。 曲线拟合--线性最小二乘法的基本思路 记 2 2 1 2 1 1 2 1 1 (, , ) [() ] [ ( ) ] (2) n n m i ii i i n m kk i i i k Ja a a f x y ar x y δ = = = = == − = − ∑ ∑ ∑ ∑ L 按照最小二乘准则, 问题归结为：求 a1,a2, …am 使 J(a1,a2, …am) 最小。 线性最小二乘法的求解 ( 1, ) 0 k m a J k = L = ∂ ∂ ( 3 ) ( )[ ( ) ] 0 ( )[ ( ) ] 0 1 1 1 1 1 ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ − = − = ⇒ ∑ ∑ ∑ ∑ = = = = n i m k m i k k i i n i m k i k k i i r x a r x y r x a r x y L L ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = n m n m n m y y y a a a r x r x r x r x R M M L LL L 1 1 1 1 1 1 , , ( ) ( ) ( ) ( ) 记 (3) (R R)a R y (4) T T ⇒ = ( , , ) [ ( ) ] (2) 2 1 1 1 2 k i i n i m k m k J a a a = ∑ ∑ a r x − y = = L (R R)a R y (4) T T = 当 RTR 可逆时(4)有唯一解 ( ) (5) 1 a R R R y T − T = 线性最小二乘法的求解 n m n n m m r x r x r x r x R × ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = ( ) ( ) ( ) ( ) 1 1 1 1 L LL L 问题 1.怎样选择 {r1(x), …rm(x)}，以保证系数 {a1,…am}有唯一解？ {a1,…am}有唯一解 ← RTR可逆 ←Rank(RTR)=m ← Rank(R)=m ← R列满秩 ← {r1(x), …rm(x)}在xi 点线性无关 (i=1,…n) 分 析 2.为什么要规定m<n?若m=n或m>n,会如何? 若m>n，a有无穷多解 若m<n，超定方程组, a无解；求最小二乘解 若m=n，R可逆时a有唯一解 强令f(xi)= a1r1(xi )+ …+amrm(xi )= yi (i=1, …n) (即曲线 f(x)过全部数据点，此时J=0) 得 n m n n m m r x r x r x r x R × ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = ( ) ( ) ( ) ( ) 1 1 1 1 L L L L Ra= y, T n T m y y y a a a [ , ] [ , ] 1 1 L L = = 问题 分 析 问题 3. 线性最小二乘中的“线性”指的是什么 f(x)对a线性，于是求解线性方程组 R R a R y T T ( ) =