第三讲 基本迭代方法 定常迭代法 收敛性分析 正则分裂 交替方向迭代法 加速技巧

Size: px
Start display at page:

Download "第三讲 基本迭代方法 定常迭代法 收敛性分析 正则分裂 交替方向迭代法 加速技巧"

Transcription

1 第三讲 基本迭代方法 定常迭代法 收敛性分析 正则分裂 交替方向迭代法 加速技巧

2 2/98 迭代方法 求解线性方程组的一般方法 : 直接法和迭代法. 迭代法 : 定常迭代法和子空间迭代法. 快速算法 : 特殊问题的特殊结构, FFT, 多重网格, 快速多极子, 等等. 快速算法通常是与问题本身结构密切相关, 一般只适用于某些特定问题的求解. 注记 在实际应用中, 这些方法往往结合使用, 如混合方法, 预处理方法等. 本讲主要内容 : 定常迭代法 ( 基本迭代法, 矩阵分裂迭代法 ), 收敛性方向, 加速技巧. 在本讲中, 如果没有特别指出, 一般假定 A 是非奇异的实矩阵.

3 3/98 1 定常迭代法 1.1 矩阵分裂与定常迭代 1.2 Jacobi 迭代 1.3 Gauss-Seidel 迭代 1.4 SOR 迭代 1.5 SSOR 迭代 1.6 AOR 与 SAOR 迭代 1.7 Richardson 迭代 1.8 块迭代方法 定常迭代法有时也称为经典迭代法, 基本迭代法或不动点迭代法.

4 4/98 迭代法基本想法 当直接求解 Ax = b 比较困难时, 我们可以求解一个近似等价方程组 Mx = b, 其中 M 是对 A 的某种意义下的近似. 设 Mx = b 的解为 x (1). 则它与原方程的解 x = A 1 b 之间的差满足 A ( x x (1)) = b Ax (1) 如果 x (1) 已经满足精度要求, 则可以停止计算, 否则需要进行修正.

5 5/98 设修正量为 x, 则 x 满足方程 A x = b Ax (1) 直接求解该方程比较困难, 因此我们还是求解近似方程 M x = b Ax (1). 得到一个近似的修正量 x. 于是修正后的近似解为 x (2) = x (1) + x = x (1) + M 1 (b Ax (1) ) 如果 x (2) 满足精度要求, 则停止计算, 否则继续按以上方式进行修正.

6 6/98 不断重复以上过程, 于是我们就得到一个序列 满足以下递推关系 x (1), x (2),...,, x (k),.... 这就构成了一个迭代方法. x (k+1) = x (k) + M 1 (b Ax (k) ) 由于每次迭代的格式是一样的, 因此称为定常迭代. 如何构造好的定常迭代方法 (1) 以 M 为系数矩阵的线性方程组比原线性方程组更容易求解 (2) M 应该是 A 的一个很好的近似, 且迭代序列 {x k } 收敛

7 7/98 常见的定常迭代方法 Jacobi 迭代 Gauss-Seidel (G-S) 迭代 超松弛 (SOR, Successive Over-Relaxation) 迭代 对称超松弛 (SSOR, Symmetric SOR) 迭代 加速超松弛 (AOR, Accelerated Over-Relaxation) 迭代 交替方向 (ADI) 迭代和对称与斜对称 (HSS) 迭代 关键技术 矩阵分裂

8 8/ 矩阵分裂与定常迭代 定义 1 ( 矩阵分裂, Matrix Splitting) 设 A R n n 非奇异, 称 A = M N (3.1) 为 A 的一个矩阵分裂, 其中 M 非奇异.

9 9/98 给定一个矩阵分裂 (3.1), 则原方程组 Ax = b 就等价于 Mx = Nx + b. 于是我们就可以构造出以下的迭代格式 或 Mx (k+1) = Nx (k) + b, k = 0, 1,..., x (k+1) = M 1 Nx (k) + M 1 b Gx (k) + g, k = 0, 1,..., 其中 G M 1 N 称为迭代矩阵. (3.2) 这就是基于矩阵分裂 A = M N 的迭代方法. 选取不同的 M, 就可以构造出不同的迭代方法.

10 10/ Jacobi 迭代 记 A = D L U, 其中 D 为 A 的对角部分, L 和 U 为 A 的严格下三角和严格上三角部分. 取 M = D, N = L + U, 则可得 Jacobi 迭代方法 : x (k+1) = D 1 (L + U)x (k) + D 1 b, k = 0, 1, 2,.... (3.3) 对应的迭代矩阵为 G J = D 1 (L + U) 分量形式 : ( x (k+1) i = 1 b i a ii n j=1,j i a ij x (k) j ), i = 1, 2,..., n.

11 算法 1.1 Jacobi 迭代方法 1: Given an initial guess x (0) 2: while not converge do 3: for i = 1 to n do ( 4: x (k+1) i = 1 b i i 1 5: end for 6: end while a ii j=1 a ij x (k) j n j=i+1 a ij x (k) j ) Jacobi 迭代中 x (k+1) i 的更新顺序与 i 无关, 因此非常适合并行计算 Jacobi 迭代格式也可以写为 x (k+1) = x (k) + D 1 (b Ax (k) ), k = 0, 1, 2,..., 即 x (k+1) 是 x (k) 的一个修正. 11/98

12 1.3 Gauss-Seidel 迭代取 M = D L, N = U, 即可得 Gauss-Seidel (G-S) 迭代方法 : x (k+1) = (D L) 1 Ux (k) + (D L) 1 b (3.4) 对应的迭代矩阵为 G GS = (D L) 1 U 将 G-S 迭代改写为 Dx (k+1) = Lx (k+1) + Ux (k) + b, 即可得分量形式 x (k+1) i = 1 a ii ( i 1 b i j=1 a ij x (k+1) j n j=i+1 a ij x (k) j ) 12/98

13 13/98 算法 1.2 Gauss-Seidel 迭代方法 1: Given an initial guess x (0) 2: while not converge do 3: for i = 1 to n do ( 4: x (k+1) i = 1 b i i 1 5: end for 6: end while a ii j=1 a ij x (k+1) j n j=i+1 a ij x (k) j ) 注记 G-S 迭代的主要优点是充分利用了已经获得的最新数据. 在 G-S 迭代中, 未知量的更新必须按自然顺序进行, 不适合并行.

14 14/ SOR 迭代 在 G-S 迭代中, 如果对修正量进行适当调整, 可能会加快收敛速度, 即 ) x (k+1) i = x (k) i + ω i 1 n (b i a ij x (k+1) j a ij x (k) j a ii j=1 这就是 SOR (Successive Overrelaxation) 迭代方法. 其中 ω 为松弛参数 : 当 ω = 1 时, SOR 即为 G-S 迭代, j=i 当 ω < 1 时, 称为低松弛 (under relaxation) 迭代, 当 ω > 1 时, 称为超松弛 (over relaxation) 迭代.

15 15/98 SOR 迭代方法 (cont.) 事实上, 也可以将 SOR 看成是将 G-S 迭代中的第 k + 1 步近似解与第 k 步近似解做加权平均所得到, 即 x (k+1) = (1 ω)x (k) + ω ( D 1 (Lx (k+1) + Ux (k) ) + D 1 b ). (3.5) 整理后即为 x (k+1) = (D ωl) 1 ((1 ω)d + ωu) x (k) + ω(d ωl) 1 b, (3.6) 注意向量加权与分量加权的区别. SOR 迭代曾经在很长一段时间内是求解线性方程组的首选方法

16 16/98 SOR 迭代方法 (cont.) SOR 的迭代矩阵为 G SOR = (D ωl) 1( (1 ω)d + ωu ) 对应的矩阵分裂为 M = 1 ω D L, N = 1 ω ω D + U

17 17/98 算法 1.3 求解线性方程组的 SOR 迭代方法 1: Given an initial guess x (0) and parameter ω 2: while not converge do 3: for i = 1 to n do 4: x (k+1) i 5: end for 6: end while = x (k) i + ω a ii ( b i i 1 j=1 a ij x (k+1) j n j=i a ij x (k) j ) 注记 SOR 迭代最大的优点是引入了松弛参数 ω: 通过选取适当的 ω 就可以大大提高方法的收敛速度. 但是 SOR 迭代最大的难点就是如何选取最优的参数.

18 1.5 SSOR 迭代将 SOR 迭代中的 L 和 U 相互交换位置, 则可得迭代格式 x (k+1) = (D ωu) 1 ((1 ω)d + ωl) x (k) + ω(d ωu) 1 b. 将这个迭代格式与 SOR 相结合, 就可以得到下面的两步迭代方法 x (k+ 1 2 ) = (D ωl) 1[ (1 ω)d + ωu ] x (k) + ω(d ωl) 1 b, x (k+1) = (D ωu) 1[ (1 ω)d + ωl ] x (k+ 1 2 ) + ω(d ωu) 1 b. 这就是对称超松弛 (SSOR ) 迭代方法. 消去中间迭代向量 x (k+ 1 2 ), 可得 x (k+1) = G SSOR x (k) + g, 其中迭代矩阵 G SSOR = (D ωu) 1[ (1 ω)d + ωl ] (D ωl) 1[ (1 ω)d + ωu ]. 18/98

19 19/98 对应的矩阵分裂为 1 [ M = D ω(l + U) + ω 2 LD 1 U ] ω(2 ω) 1 = ω(2 ω) (D ωl)d 1 (D ωu), 1 [ ] N = [ (1 ω)d + ωl D 1 (1 ω)d + ωu ]. ω(2 ω) 注记 对于某些特殊问题, SOR 迭代不收敛, 但仍然可能构造出收敛的 SSOR 迭代. 注记 一般来说, SOR 迭代的渐进收敛速度对参数 ω 比较敏感, 但 SSOR 的收敛速度对参数 ω 不太敏感.

20 20/98 算法 1.4 SSOR 方法 1: Given an initial guess v (0) and parameter ω 2: while not converge do 3: for i = 1 to n do 4: x (k+ 1 2 ) i 5: end for = x (k) i + ω a ii ( b i i 1 j=1 6: for i = n to 1 do ( 7: x (k+1) i = x (k+ 1 2 ) i + ω b i i 1 a ii 8: end for 9: end while a ij x (k+ 1 2 ) j j=1 a ij x (k+1) j n j=i n a ij x (k) j j=i ) a ij x (k+ 1 2 ) j )

21 21/ AOR 与 SAOR 迭代加速超松弛 (AOR, Accelerated Over-Relaxation ) 迭代方法 : x (k+1) = (D γl) 1 ((1 ω)d + (ω γ)l + ωu) x (k) +ω(d γl) 1 b, 其中 γ 和 ω 为松弛参数. 对应的矩阵分解为 M = 1 (D γl), ω N = 1 [(1 ω)d + (ω γ)l + ωu] ω 迭代矩阵为 G AOR = (D γl) 1[ (1 ω)d + (ω γ)l + ωu ]

22 22/98 AOR 迭代方法 (cont.) (1) 当 γ = ω 时, AOR 迭代即为 SOR 迭代 ; (2) 当 γ = ω = 1 时, AOR 迭代即为 G-S 迭代 ; (3) 当 γ = 0, ω = 1 时, AOR 迭代即为 Jacobi 迭代. 注记 AOR 迭代中含有两个参数. 因此在理论上, 通过选取合适的参数, AOR 迭代会收敛得更快. 但也是因为含有两个参数, 使得参数的选取变得更加困难, 因此较少使用. 注记 与 SSOR 类似, 我们也可以定义 SAOR 迭代.

23 23/ Richardson 迭代 Richardson 迭代是一类形式非常简单的方法, 其迭代格式为 x (k+1) = x (k) + ω(b Ax (k) ), k = 0, 1, 2,.... 它可以看作是基于以下矩阵分裂的迭代方法 : M = 1 ω I, N = 1 ω I A. 对应的迭代矩阵为 G R = I ωa.

24 24/98 定理 1 设 A R n n 是对称正定矩阵, λ 1 和 λ n 分别是 A 的最大和最小特征值, 则 Richardson 迭代方法收敛当且仅当 0 < ω < 1 λ 1. 另外, Richardson 迭代的最优参数为 ω = arg min ω ρ(g R ) = 2 λ 1 + λ n, 即当 ω = ω 时, 迭代矩阵的谱半径达到最小, 且有 1 ωλ n if ω ω λ 1 λ n ρ(g R ) = = κ(a) 1 if ω = ω λ 1 + λ n κ(a) + 1 ωλ 1 1 if ω ω.

25 25/98 注记 如果在每次迭代时取不同的参数, 即 x (k+1) = x (k) + ω k (b Ax (k) ), k = 0, 1, 2,..., 则每次迭代的格式就不一样了, 因此不再是定常迭代, 而是非定常 (Nonstationary ) 迭代. 此时称为非定常 Richardson 迭代.

26 26/ 块迭代方法将 A 写成分块形式 : A 11 A 12 A 1p A A = 21 A 22 A 2p......, A p1 A p2 A pp

27 27/98 块 Jacobi 迭代 : A ii x (k+1) i 块 Gauss-seidel 迭代 : A ii x (k+1) i 块 SOR 迭代 : x (k+1) i = b i i 1 = b i j=1 = (1 ω)x (k) i i = 1, 2,..., p. p j=1,j i A ij x (k+1) j + ωa 1 ii A ij x (k) j, i = 1, 2,..., p. p j=i+1 ( i 1 b i j=1 A ij x (k) j, i = 1, 2,..., p. A ij x (k+1) j p j=i+1 A ij x (k) j ),

28 28/98 2 收敛性分析 2.1 迭代法的收敛性 2.2 不可约对角占优矩阵 2.3 对称正定矩阵 2.4 相容次序

29 29/ 迭代法的收敛性 定义 2 ( 迭代法的收敛性 ) 对于迭代方法 x (k+1) = Gx (k) + g, 如果存在 x, 使得对任意的初始向量 x (0), 都有 lim k x(k) = x, 则称迭代格式 (3.2) 是收敛的, 否则就称为发散的. 注记 基于矩阵分裂的迭代方法, 其收敛性取决于迭代矩阵的谱半径.

30 30/98 矩阵谱半径 设 A R n n, 则称 ρ(a) max λ λ σ(a) 为 A 的谱半径, 其中 σ(a) 表示 A 的所有特征值组成的集合. 谱半径与矩阵范数之间有如下的关系. 引理 2 ( 谱半径与范数的关系 ) 设 G R n n, 则 (1) 对任意算子范数, 有 ρ(g) G ; (2) 反之, 对任意 ε > 0, 都存在一个算子范数 ε, 使得 G ε ρ(g) + ε, 其中范数 ε 依赖于 G 和 ε. 所以, 若 ρ(g) < 1, 则存在算子范数 ε, 使得 G ε < 1;

31 31/98 谱半径性质 由上述引理可以得到下面的结论. 定理 3 设矩阵 G R n n, 则 lim k G k = 0 当且仅当 ρ(g) < 1. ( 板书 ) 谱半径与算子范数之间的一个非常重要的性质 : 引理 4 设 G R n n, 则对任意算子范数, 有 ρ(g) = lim k G k 1 k. ( 板书 )

32 32/98 迭代法收敛性判断 首先给出一个迭代方法收敛的充分条件. 引理 5 若存在算子范数, 使得 G < 1, 则迭代方法 3.2 收敛. ( 板书 ) 我们记 e (k) x (k) x 为第 k 步迭代解 x (k) 的误差向量. 定理 6 ( 收敛性定理 ) 对任意迭代初始向量 x (0), 迭代方法 3.2 收敛的充要条件是 ρ(g) < 1. ( 板书 )

33 33/98 收敛速度 经过 k 次迭代后, 误差满足 e (k) = G k e (0). 因此, 有 e (k) e (0) Gk, 即误差总体大约下降了 G k, 平均每次迭代的下降量为 G k 1 k. 定义 3 ( 收敛速度 ) 设 G 是迭代矩阵, 则迭代方法 3.2 的平均收敛速度定义为 R k (G) ln G k 1 k, 渐进收敛速度定义为 R(G) lim k R k (G) = ln ρ(g). 平均收敛速度与迭代步数和范数有关, 渐进收敛速度只依赖谱半径

34 34/98 定理 7 ( 误差估计 ) 若存在某算子范数 使得 G = q < 1, 则 : (1) x (k) x q k x (0) x ; (2) x (k) x q 1 q x(k) x (k 1) ; (3) x (k) x qk 1 q x(1) x (0). 注记 一般来说, 一个好的迭代方法要具备 : (1) ρ(g) 越小越好 ; (2) 以 M 为系数矩阵的线性方程组越容易求解越好.

35 35/ 不可约对角占优矩阵 两种情形 : 严格对角占优, 不可约弱对角占优 定理 8 设 A R n n, 若 A 严格对角占优, 则 Jacobi 迭代和 G-S 迭代都收敛, 且 G GS G J < 1. ( 板书 ) 定理 9 设 A R n n, 若 A 是弱对角占优且不可约, 则 Jacobi 迭代和 G-S 迭代都收敛. 进一步, 若 A 是非负矩阵, 则 ρ(g GS ) < ρ(g J ) < 1. ( 证明参见 Varga 2000) 定理中的结论对一般矩阵并不成立 : 对某些矩阵, Jacobi 收敛, 但 G-S 却不一定收敛.

36 36/98 对于非负矩阵, 我们有下面的结论 : 定理 10 若 G J 0, 则下面四个结论有且仅有一个成立 : (1) ρ(g GS ) = ρ(g J ) = 0, (2) 0 < ρ(g GS ) < ρ(g J ) < 1, (3) ρ(g GS ) = ρ(g J ) = 1, (4) ρ(g GS ) > ρ(g J ) > 1. 这表明, Jacobi 迭代和 G-S 迭代此时具有相同的收敛性.

37 37/98 SOR 的收敛性 定理 11 若 A 严格对角占优且 0 < ω 1, 则 SOR 收敛. ( 板书 ) 定理 12 若 A 是弱对角占优且不可约, 且 0 < ω 1, 则 SOR 收敛. ( 练习 )

38 38/ 对称正定矩阵 在给出收敛性结论之前, 也介绍两个需要用到的引理. 引理 13 设 A C n n Hermite 对称, 且 A = M N 是 A 的一个矩阵分裂, 则 M + N 也是 Hermite 对称, 且对任意 x C n 有 x Ax x A x = u (M + N)u, 其中 x = M 1 Nx, u = x x. ( 板书 ) 引理 14 设 A R n n 对称, 且 A = M N 是 A 的一个矩阵分裂. (1) 若 A 和 M +N 都是正定矩阵, 则 M 非奇异且 ρ(m 1 N) < 1; (2) 如果 ρ(m 1 N) < 1 且 M + N 正定, 则 A 正定. ( 板书 )

39 39/98 SOR 收敛的一个必要条件 定理 15 对于 SOR 迭代, 有 ρ(g SOR ) 1 ω, 故 SOR 迭代收敛的必要条件是 0 < ω < 2. ( 板书 )

40 40/98 定理 16 设 A R n n 对称正定. (1) 若 2D A 正定, 则 Jacobi 迭代收敛. (2) 若 0 < ω < 2, 则 SOR 和 SSOR 收敛. (3) G-S 迭代收敛. ( 练习 ) 注记 由定理 16 可知, 若系数矩阵对称正定, 则 SOR 迭代收敛的充要条件是 0 < ω < 2. 这就是著名的 Ostrowski Reich 定理.

41 41/98 定理 17 设 A R n n 对称. (1) 若 2D A 正定且 Jacobi 迭代收敛, 则 A 正定 ; (2) 若 D 正定, 且存在 ω (0, 2) 使得 SOR ( 或 SSOR) 收敛, 则 A 正定 ; (3) 若 D 正定, 且 G-S 迭代收敛, 则 A 正定. ( 练习 )

42 42/ 相容次序 针对一类特殊的矩阵, 这三种迭代法的特征值之间存在一种特殊关系, 特别是 Jacobi 迭代和 SOR 迭代. 定义 4 设 A R n n, 如果存在一个置换矩阵 P, 使得 [ ] P AP D 1 F =, (3.7) E D 2 其中 D 1, D 2 为对角矩阵, 则称 A 具有性质 A.

43 43/98 引理 18 设 B R n n 具有下面的结构 [ ] 0 B 12 B =, B 21 0 令 B L 和 B U 分别表示 B 的下三角和上三角部分, 则 (1) 若 µ 是 B 的特征值, 则 µ 也是 B 的特征值 ; (2) B(α) 的特征值与 α 无关, 其中 B(α) = αb L + 1 α B U, α 0.

44 44/98 设 A R n n 的对角线元素全不为零, 记 L = D 1 L, Ũ = D 1 U. 定义 5 设 A R n n 的对角线元素均非零, α R 非零. 若矩阵 G(α) = α L + 1 αũ 的特征值与 α 无关, 则称 A 具有相容次序. 注记 设 A 的对角线元素均非零, 若 A 具有性质 A, 则存在置换矩阵 P, 使得 P AP 具有相容次序. 注记 该结论可以推广到块三对角形式.

45 45/98 例 1 设 D i 是非奇异的对角矩阵, 则任意块三对角矩阵 D 1 A 1. B AN 1 B N 1 D N 都有相容次序. ( 练习 )

46 46/98 定理 19 设 A 具有相容次序且对角线均非零, ω 0, 则下列命题成立 (1) Jacobi 迭代矩阵 G J 的特征值正负成对出现 ; (2) 若 µ 是 G J 的一个特征值且 λ 满足 则 λ 是 SOR 迭代矩阵 G SOR 的特征值 ; (λ + ω 1) 2 = λω 2 µ 2, (3.8) (3) 反之, 若 λ 0 是 G SOR 的一个特征值且 µ 满足 (3.8), 则 µ 是 G J 的特征值. ( 板书 )

47 47/98 推论 20 设 A 具有相容次序且对角线均非零. 若 G J 的特征值全部为实数, 则 SOR 迭代收敛的充要条件是 0 < ω < 2 且 ρ(g J ) < 1. 推论 21 若 A 具有相容次序且对角线均非零, 则 ρ(g GS ) = ρ(g J ) 2, 即当 Jacobi 迭代收敛时, G-S 迭代比 Jacobi 迭代快一倍.

48 48/98 SOR 的最优参数 定理 22 设 A 具有相容次序且对角线均非零. 若 G J 的特征值全部为实数, 且 ρ J ρ(g J ) < 1, 则 SOR 迭代的最优参数为 ω opt = ρ 2 J, 此时 ρ(g SOR ) = ω opt 1 = ( 1 + ρ 2 J 1 ρ 2 J ) 2.

49 49/98 进一步, 有 ω 1, ω opt ω 2 ρ(g SOR ) = 1 ω ω2 ρ 2 J + ωρ J 1 ω ω2 ρ 2 J, 0 < ω ω opt 证明. 直接求解等式 (3.8), 分情况讨论即可.

50 50/98 3 正则分裂 3.1 正则分裂, 弱正则分裂和非负分裂 3.2 正则分裂与迭代收敛 3.3 P - 正则分裂 除了 Jacobi, G-S, SOR 分裂外, 这里介绍另外几类常见的矩阵分裂.

51 51/ 正则分裂, 弱正则分裂和非负分裂 定义 6 设 A R n n, 矩阵分裂 A = M N. (1) 正则分裂 : M 1 0, N 0 (2) 弱正则分裂 : M 1 0, M 1 N 0 (3) 非负分裂 : M 1 N 0 注记 显然, 正则分裂一定是弱正则分裂, 弱正则分裂一定是非负分裂.

52 52/98 设 A 和 M 都非奇异, 则 由此可得下面的结论 : M 1 N = (A + N) 1 N = (I + A 1 N) 1 A 1 N. 引理 23 设 A = M N, 其中 A R n n 和 M R n n 都非奇异. 则 τ 是 A 1 N 的特征值当且仅当 µ = τ/(1 + τ) 是 M 1 N 的特征值. 并且, A 1 N 和 M 1 N 具有相同的特征向量. ( 板书 )

53 53/98 下面给出正则分裂所对应迭代矩阵 M 1 N 的性质 : 定理 24 设 A = M N 是 A R n n 的一个正则分裂, 则 A 非奇异且 A 1 0 当且仅当 ρ(m 1 N) = ρ(a 1 N) 1 + ρ(a 1 N) < 1. ( 板书 ) 推论 25 设 A R n n 是 M 矩阵, 且 A = M N 是一个正则分裂. 则 ρ(m 1 N) < 1.

54 54/98 设 A 是 M- 矩阵, 下面的结论给出了构造 A 的正则分裂的一种方法. 推论 26 设 A R n n 是 M 矩阵. 现将 A 的某些非对角元素设置为 0, 得到的新矩阵记为 M. 则 A = M N 是正则分裂, 故 ρ(m 1 N) < 1.

55 55/98 如果 A 还是对称正定的, 则我们有下面的结论. 推论 27 设 A R n n 是 M 矩阵, A = M N 是正则分裂. 若 A 对称正定且 N 对称, 则 ρ(m 1 N) ρ(a 1 )ρ(n) 1 + ρ(a 1 )ρ(n) < 1. ( 板书 )

56 56/98 两个不同正则分裂谱半径比较 定理 28 ( 比较定理 ) 设 A = M 1 N 1 = M 2 N 2 是 A R n n 的两个正则分裂. (1) 若 A 1 0 且 N 2 N 1 0, 则 0 ρ(m 1 1 N 1 ) ρ(m 1 2 N 2 ) < 1. (3.9) (2) 若 A 1 > 0 且 N 2 N 1 0, 则 0 < ρ(m 1 1 N 1 ) < ρ(m 1 2 N 2 ) < 1. (3.10) ( 板书 )

57 57/98 如果 A 是不可约 M- 矩阵, 则我们有下面的结论. 推论 29 设 A R n n 是不可约 M 矩阵, M 1 和 M 2 分别是将 A 的某些非对角元素设置为 0 后得到的. 若矩阵分裂 A = M 1 N 1 = M 2 N 2 满足 N 2 N 1 0, 则 0 < ρ(m 1 1 N 1 ) < ρ(m 1 2 N 2 ) < 1. 引理 30 设 A = M 1 N 1 = M 2 N 2 是矩阵 A R n n 的两个正则分裂, 且 A 1 0. (1) 若 N 2 N 1, 则 M 1 1 M 1 2 ; (2) 若 M 1 1 M 1 2, 则 A 1 N 2 A 1 A 1 N 1 A 1 ; (3) 若 A 1 N 2 A 1 A 1 N 1 A 1, 则 (A 1 N 2 ) k A 1 (A 1 N 1 ) k A 1

58 58/98 下面的比较定理是由 Csordas 和 Varga 给出的. 定理 31 设 A = M 1 N 1 = M 2 N 2 是 A R n n 的两个正则分裂. (1) 若 A 1 0, 且存在一个正整数 k 使得 (A 1 N 2 ) k A 1 (A 1 N 1 ) k A 1, 则 0 ρ(m 1 1 N 1 ) ρ(m 1 2 N 2 ) < 1. (2) 若 A 1 > 0, 且存在一个正整数 k 使得 (A 1 N 2 ) k A 1 > (A 1 N 1 ) k A 1, 则 0 < ρ(m 1 1 N 1 ) < ρ(m 1 2 N 2 ) < 1.

59 59/98 根据引理 30 和定理 31, 我们立即可以得到下面的结论 : 定理 32 设 A = M 1 N 1 = M 2 N 2 是 A R n n 的两个正则分裂. (1) 若 A 1 0 且 M 1 1 M 1 2, 则 0 ρ(m 1 1 N 1 ) ρ(m 1 2 N 2 ) < 1. (2) 若 A 1 > 0 且 M 1 1 > M 1 2, 则 0 < ρ(m 1 1 N 1 ) < ρ(m 1 2 N 2 ) < 1. 注记 需要指出的是, 条件 M 1 1 M 1 2 比 N 2 N 1 0 要更弱一些.

60 60/98 关于弱正则分裂, 我们有下面的结论 : 定理 33 设 A = M N 是 A R n n 的一个弱正则分裂, 则 A 非奇异且 A 1 0 当且仅当 ρ(m 1 N) < 1. 注记 由该定理可知, 将 正则分裂 替换成 弱正则分裂, 推论 27 中的结论仍然成立. 但定理 32 对弱正则分裂不成立.

61 61/98 [ ] 1 1 例 2 设 A = 的两个分裂 1/2 1 A = M 1 N 1 = M 2 N 2, 其中 [ ] [ ] 1 (1 + α) 0 α M 1 =, N 1 =, 0 < α < 1/3, 1/2 (1 α) 0 α 则 M 2 = A, N 2 = 0. M 1 1 = [ 2 1 3α 1 α 1 + α 1/2 1 ], M 1 2 = A 1 = 2 ] 1 1 1/2 1 [. 所以 M 1 1 > M 1 2, 但 ρ(m 1 1 N 1 ) = 3α 2 > ρ(m 1 2 N 2 ) = 0.

62 62/98 定理 34 设 A = M N 是 A R n n 的一个非负分裂, 则下面的结论是等价的 : (1) ρ(m 1 N) < 1; (2) I M 1 N 是单调的 ; (3) A 非奇异且 A 1 N 0; (4) A 非奇异且 ρ(m 1 N) = ρ(a 1 N) 1 + ρ(a 1 N).

63 63/ 正则分裂与迭代收敛 如果 A 是 M- 矩阵, 则有 A 1 0, 因此, 由定理 24 立即可得下面结论 : 定理 35 设 A 是 M- 矩阵. 如果 A = M N 是正则分裂, 则对应的矩阵分裂迭代法 (3.2) 收敛.

64 64/98 Jacobi 迭代的收敛性 设 A 是 M- 矩阵, 则所有对角线元素都为正, 且 L + U 0. 所以当 M = D, N = L + U 时, A = M N 是正则分裂, 因此 定理 36 设 A 是 M- 矩阵, 则 Jacobi 迭代收敛. 若 A R n n 是 H- 矩阵, 则比较矩阵 D L U 是 M- 矩阵, 且 ρ(g J ) = ρ(d 1 (L+U)) ρ( D 1 (L+U) ) = ρ( D 1 ( L + U )) < 1. 定理 37 设 A R n n 是 H- 矩阵, 则 Jacobi 迭代收敛.

65 65/98 事实上, 我们有下面更强的结论. 定理 38 设 A R n n 的对角线元素均非零, 则 A 是 H- 矩阵的充要条件是 ρ( G J ) < 1. ( 证明参见 [Xu 95])

66 66/98 G-S 迭代的收敛性 若 A 是 M- 矩阵, 则 (D L) 1 0. 故 G-S 对应的矩阵分裂也是正则分裂. 定理 39 设 A 是 M- 矩阵, 则 G-S 迭代方法收敛. 记 L D 1 L. 则 L 是严格下三角矩阵, 因此 ρ( L) = 0 < 1, 且当 k n 时有 Lk = 0. 所以 (D L) 1 = (I L)D 1 = (I + L + L L n 1 )D 1.

67 67/98 所以 (D L) 1 U (D L) 1 U n 1 = L k D 1 U k=0 n 1 L k D 1 U k=0 = ( D L ) 1 U. 于是我们有下面的结论 : 定理 40 设 A R n n 是 H- 矩阵, 则 G-S 迭代方法收敛.

68 68/98 AOR 迭代的收敛性 设 A = [a ij ] R n n, 定义 A 的等模矩阵集合 : Ω(A) { B = [b ij ] C n n : b ij = a ij, 1 i, j n }. 下面的定理给出了 AOR 和 SAOR 的收敛性. 定理 41 设 A R n n 是 H 矩阵, 且对角线元素均非零, 参数 ω 和 γ 2 满足 0 γ ω. 则对任意 B Ω(A) 和任意 0 < ω < ρ( G J ) + 1, 都有 ρ(g AOR (B)) < 1 和 ρ(g AOR (B)) < 1, 即求解线性方程组 Bx = f 的 AOR 迭代和 SAOR 迭代都收敛. 这里 G AOR (B) 和 G AOR (B) 分别表示 AOR 和 SAOR 所对应的迭代矩阵. ( 证明参见 [Xu 95])

69 69/ P - 正则分裂 定义 7 (P - 正则分裂 ) 设 A C n n, 如果 M + N 是正定的, 则称 A = M N 是 A 的一个 P - 正则分裂. 注记 M + N 正定当且仅当 M + N 正定. 因此, 若 A 是 Hermite 的, 则 A = M N 是 P - 正则分裂当且仅当 M + M A 是 Hermite 正定

70 70/98 定理 42 (Stein Theorem) 设 G C n n. 则 ρ(g) < 1 的充要条件是存在一个 Hermite 正定矩阵 A C n n 使得 A G AG 也 Hermite 正定. 下面的定理称为 Householder-John 定理. 定理 43 设 A C n n 是非奇异的 Hermite 矩阵. 如果 A = M N 是一个 P - 正则分裂, 则 ρ(m 1 N) < 1 当且仅当 A 正定. 定理 43 可用来证明 Ostrowski-Reich 定理, 即 : 如果 A C n n 是 Hermite 正定, 则 SOR 对所有 ω (0, 2) 都收敛. 下面我们给出一个更一般的结论.

71 71/98 定理 44 (Ostrowski) 设 A = D E E C n n, 其中 D 是 Hermite 正定的, 且对于所有 ω (0, 2), 矩阵 D ωe 都非奇异, 则 ρ(g ω ) < 1 的充要条件是 A 正定且 0 < ω < 2, 其中 G ω (D ωe) 1 [(1 ω)d + ωe ]. 需要指出的是, 定理 44 中的矩阵 E 不需要是严格下三角或严格上三角. 作为特例, 当 ω = 1 时, 下面的结论由 Reich 给出. 推论 45 设 A = D E E C n n, 其中 D 是 Hermite 正定的, 且 D E 非奇异, 则 G-S 迭代收敛的充要条件是 A 正定. 由定理 43 可知, Hermite 正定矩阵的 P - 正则分裂是收敛的. 但反之结论不一定成立, 即 Hermite 正定矩阵的收敛分裂不一定是 P - 正则的.

72 72/98 例 3 Let A = M N, where [ ] 1 m A =, M = ε ε 2, N = ε ε Then M 1 = [ ] ε m 0 ε m ε 2 1 ε 1 [ ] and M 1 1 ε m N =. 0 1 ε Hence, ρ(m 1 N) = 1 ε < 1. On the other hand, we have 2 M + M A = ε 1 m ε 2, m 2 ε 2 ε 1, 0 < ε < 1. which is not positive definite if m > ε(2 ε). Therefore, A = M N is not a P -regular splitting for m > ε(2 ε).

73 73/98 下面结论给出了 Hermite 正定矩阵的分裂是 P - 正则分裂的充要条件. 定理 46 设 A C n n 是 Hermite 正定的, 则 A = M N 是 P - 正则分裂的充要条件是 M 1 N A 1 2 < 1. 定理 47 设 A C n n 是非奇异 Hermite 矩阵, 分裂 A = M N. 如果 M C n n 是 Hermite 的, 且 ρ(m 1 N) < 1, 则 A 是正定的, 且 A = M N 是 P - 正则分裂.

74 74/98 4 交替方向迭代法 4.1 多步迭代法 4.2 交替方向法 4.3 HSS 迭代 4.4 HSS 迭代的推广

75 75/ 多步迭代法 设 A = M 1 N 1 = M 2 N 2 是 A 的两个矩阵分裂, 则可以构造迭代格式 M 1 x (k+ 1 2 ) = N 1 x (k) + b, k = 0, 1, 2,.... (3.11) M 2 x (k+1) = N 2 x (k+ 1 2 ) + b, 这就是两步迭代方法, 对应的分裂称为二重分裂. 易知, 两步迭代格式 (3.11) 的迭代矩阵为 G = M 1 2 N 2 M 1 1 N 1. 因此, 其收敛的充要条件是 ρ(m 1 2 N 2 M 1 1 N 1 ) < 1.

76 76/98 类似地, 我们可以推广到多步迭代方法. 设 l 是一个正整数, 则 A 的 l 重分裂为 A = M 1 N 1 = M 2 N 2 = = M l N l, 相应的多步迭代方法为 M 1 x (k+ 1 l ) = N 1 x (k) + b, M 2 x (k+ 2 l ) = N 2 x (k+ 1 l ) + b, M l x (k+1) = N l x (k+ l 1 l ) + b, k = 0, 1, 2,....

77 77/ 交替方向法 交替方向法 (alternating direction implicit, ADI ) 是由 Peaceman 和 Rachford 于 1955 年提出, 用于计算偏微分方程的数值解, 因而有时也称为 PR 迭代. 其本质上也是一个两步迭代方法. 设 A = A 1 + A 2, 则 ADI 迭代格式为 (αi + A 1 )x (k+ 1 2 ) = (αi A 2 )x (k) + b, (αi + A 2 )x (k+1) = (αi A 1 )x (k+ 1 2 ) + b, k = 0, 1, 2,..., (3.12) 其中 α R 是迭代参数. 易知 ADI 迭代的迭代矩阵为 G ADI (α) = (αi + A 2 ) 1 (αi A 1 )(αi + A 1 ) 1 (αi A 2 )

78 78/98 它相似于 G ADI (αi A 1 )(αi + A 1 ) 1 (αi A 2 )(αi + A 2 ) 1 所以 ADI 迭代 (3.12) 收敛的充要条件是 ρ( G ADI ) < 1. 定理 48 设 A R n n 对称正定, A = A 1 + A 2, 其中 A 1 对称正定, A 2 对称半正定, 则对任意参数 α > 0, 有 ρ( G ADI ) < 1, 即 ADI 迭代法 (3.12) 收敛. ( 板书 )

79 79/ HSS 迭代 HSS 迭代全称为 Hermitian and Skew-Hermitian Splitting method. 任何一个矩阵都可以分裂成对称与斜对称部分之和, 即 A = H + S 其中 H 和 S 分别是 A 的对称与斜对称 (Skew-Hermitian) 部分, 即 H = A + A, S = A A 2 2 这个分裂就称为 HS 分裂, 简称 HSS.

80 80/98 类似于 ADI 迭代, 我们可得下面的 HSS 迭代 (αi + H)x (k+ 1 2 ) = (αi S)x (k) + b, (αi + S)x (k+1) = (αi H)x (k+ 1 2 ) + b, k = 0, 1, 2,.... (3.13) 迭代矩阵 G HSS (α) = (αi + S) 1 (αi H)(αI + H) 1 (αi S) (αi H)(αI + H) 1 (αi S)(αI + S) 1 G HSS 容易验证, (αi S)(αI + S) 1 是一个酉矩阵. 又 H 是对称矩阵, 因此 (αi H)(αI + H) 1 2 = max α λ λ σ(h) α + λ. 定理 49 设 A 正定, 则对任意参数 α > 0, HSS 迭代方法收敛.

81 81/98 参数 α 的选取 为达到最快收敛效果, 我们希望迭代矩阵的谱半径越小越好. 但是在一般情况下, 谱半径很难计算或估计. 因此要极小化谱半径是非常困难的, 或者说是不可能的. 此时, 我们能做的往往是极小化它的一个上界. 由前面的分析可知 ρ(g HSS ) = ρ( G HSS ) max λ σ(h) α λ α + λ σ(α). (3.14) 因此, 我们可以通过极小化 σ(α) 来获取近似最优参数 α.

82 82/98 记 H 的最大和最小特征值分别为 λ max (H) 和 λ min (H). 定理 50 设 A R n n 正定, 则极小极大问题 min max α λ α>0 λ min(h) λ λ max(h) α + λ 的解为 α = λ max (H)λ min (H). 此时 σ(α ) = λmax (H) λ min (H) λmax (H) + λ min (H) = κ(h) 1 κ(h) + 1.

83 83/98 注记 在定理 50 中我们是在区间 [λ min (H), λ max (H)] 内极小化是 (3.14) 中的 σ(h). 事实上, 我们可以证明 max α λ λ σ(h) α + λ = max α λ λ min(h) λ λ max(h) α + λ. α λ α+λ, 而不 需要指出的是, 定理 50 中的最优参数 α 极小化的是上界 σ(α), 而不是谱半径本身. 如果 A 是正规矩阵, 则 HS = SH, 因此可得 ρ(g HSS ) = σ(α). 此时, α 不仅仅极小化 σ(α), 它也极小化 ρ(g HSS ). 由定理 50 可知, 如果 A 正定, 则取近似最优参数 α 的 HSS 迭代的收敛速度与 CG 迭代相当.

84 84/ HSS 迭代的推广 NSS 迭代 与 HS 分裂类似, 我们可以将 A 分裂成正规矩阵与斜对称矩阵之和 : A = N + S, 其中 N 是正规矩阵, S 是斜对称矩阵, 即正规与斜对称分裂 (NSS ). 基于这个分裂, 我们就可以构造下面的正规与斜对称分裂迭代 : (αi + N)x (k+ 1 2 ) = (αi S)x (k) + b, k = 0, 1, 2,..., (αi + S)x (k+1) = (αi N)x (k+ 1 2 ) + b, 其中 α R 是给定的迭代参数. 对应的迭代矩阵为 G NSS (α) = (αi + S) 1 (αi N)(αI + N) 1 (αi S).

85 85/98 PSS 迭代 与 NS 分裂类似, 我们还可以将 A 分裂成正定矩阵与斜对称矩阵之和 : A = P + S, 其中 P 是正定矩阵, S 是斜对称矩阵, 即正定与斜对称分裂 (PSS ). 对应的 PSS 迭代为 (αi + P )x (k+ 1 2 ) = (αi S)x (k) + b, (αi + S)x (k+1) = (αi P )x (k+ 1 2 ) + b, k = 0, 1, 2,..., 其中 α R 是迭代参数, 迭代矩阵为 G PSS (α) = (αi + S) 1 (αi P )(αi + P ) 1 (αi S). 有两个问题需要考虑 : 一是参数 α 的选取, 另一个是 S 的选取.

86 86/98 5 加速技巧 当迭代解 x (0), x (1), x (2),..., x (k) 已经计算出来后, 我们可以对其进行组合, 得到一个更好的近似解, 从而加快收敛速度. 这里介绍两类常用的加速技巧 : 外推加速和 Chebyshev 加速

87 87/98 外推技术 设原迭代格式为 x (k+1) = Gx (k) + b. (3.15) 由 x (k) 和 x (k+1) 加权组合后可得新的近似解 x (k+1) = (1 ω)x (k) + ω(gx (k) + b), (3.16) 其中 ω 是参数. 这种加速方法就称为外推方法. 为了使得迭代格式 (3.16) 尽可能快地收敛, 需要选择 ω 使得其迭代矩阵 G ω (1 ω)i + ωg 的谱半径尽可能地小. 设 G 的特征值都是实数, 且最大和最小特征值分别为 λ 1 和 λ n, 则 ρ(g ω ) = max (1 ω) + ωλ = max{ 1 ω + ωλ 1, 1 ω + ωλ n }. λ σ(g)

88 88/98 定理 51 设 G 的特征值都是实数, 其最大和最小特征值分别为 λ 1 和 λ n, 且 1 / [λ n, λ 1 ], 则 此时 ω = arg min ω ρ(g ω ) = ρ(g ω ) = 1 ω d, 2 2 (λ 1 + λ n ), 其中 d 是 1 到 [λ n, λ 1 ] 的距离, 即当 λ n λ 1 < 1 时, d = 1 λ 1, 当 λ 1 λ n > 1 时, d = λ n 1. 假设原迭代方法收敛, 即 1 < λ n λ 1 < 1. 则当 λ n + λ 1 1 时, ω 1, 此时外推迭代 (3.16) 比原迭代方法收敛更快. 最优参数依赖于原迭代矩阵 G 的特征值, 因此实用性不强. 在实际应用时可以估计特征值所在的区间 [a, b], 然后用 a, b 来代替 λ n 和 λ 1.

89 89/98 JOR 迭代 对 Jacobi 进行外推加速, 则可得 JOR (Jacobi over-relaxation) 迭代 : x (k+1) = (1 ω)x (k) + ω(d 1 (L + U)x (k) + D 1 b) = x (k) + ωd 1 (b Ax (k) ), k = 0, 1, 2,.... 定理 52 设 A 对称正定. 若 则 JOR 迭代收敛. 0 < ω < 2 ρ(d 1 A),

90 90/98 Chebyshev 加速 Chebyshev 加速可以看作是对外推技巧的推广. 假定已经计算出 x (0), x (1),..., x (k), 下面考虑如何将这些近似解进行组合, 以便得到更好的近似解. 记 ε k = x (k) x 为第 k 步迭代解的误差, 则有 ε k = Gε k 1 = G 2 ε k 2 = = G k ε 0. 设 x (k) 为 x (0), x (1),..., x (k) 的一个线性组合, 即 其中 α i 为待定系数, 且满足 x (k) = α 0 x (0) + α 1 x (1) + + α k x (k), (3.17) k α i = 1. 于是 i=0 x (k) x = α 0 ε 0 + α 1 Gε α k G k ε 0 p k (G)ε 0, (3.18)

91 91/98 其中 p k (t) = k α i t i 为 k 次多项式, 且满足 p k (1) = 1. i=0 我们希望通过适当选取参数 α i, 使得 x (k) x 尽可能地小, 即使得 x (k) 收敛到 x 速度远远快于 x (k) 收敛到 x 速度. 这种加速方法就称为多项式加速或半迭代方法 (semi-iterative method). 例 4 设 p n (t) 为 G 的特征多项式, 则 p n (G) = 0, 所以选取 α i 为 p n 的系数, 则 x (n) x = 0. 但这种选取方法不实用, 原因是 : (1) p n (t) 的系数并不知道 ; (2) 我们通常希望收敛所需的迭代步数 n.

92 92/98 下面讨论参数 α i 的较实用的选取方法. 由 (3.18) 可知 x (k) x 2 = p k (G)ε 0 2 p k (G) 2 ε 0 2. 因此我们需要求解下面的极小化问题 min p(g) 2, (3.19) p P k,p(1)=1 其中 P k 表示所有次数不超过 k 的多项式组成的集合. 一般来说, 这个问题是非常困难的. 但在一些特殊情况下, 我们可以给出其最优解. 假设迭代矩阵 G 是对称矩阵, 即 G 存在特征值分解 G = QΛQ, 其中 Λ 是对角矩阵, 且对角线元素都是实的, Q 是正交矩阵. 于是有

93 93/98 min p(g) 2 = min p(λ) 2 p P k,p(1)=1 p P k,p(1)=1 = min { max p(λi ) } p P k,p(1)=1 1 i n min max p P k,p(1)=1 λ [λ n,λ 1] { p(λ) }, (3.20) 其中 λ 1, λ n 分别表示 G 的最大和最小特征值. 这是带归一化条件的多项式最佳一致逼近问题 ( 与零的偏差最小 ). 该问题的解与著名的 Chebyshev 多项式有关. 注记 由于所有算子范数 p k (G) 的下确界是 ρ(p k (G)), 因此, 一种较实用的选取方法是使得 p k (G) 的谱半径尽可能地小.

94 94/98 考虑迭代格式 (3.15), 我们假定 : (1) 迭代矩阵 G 的特征值都是实数 ; (2) 迭代矩阵谱半径 ρ = ρ(g) < 1, 故 λ(g) [ ρ, ρ] ( 1, 1). 于是最小最大问题 (3.20) 就转化为 min max p P k,p(1)=1 λ [ ρ,ρ] { p(λ) }. 由于 1 [ ρ, ρ], 由 Chebyshev 多项式的性质克制, 上述问题的解为 p k (t) = T k(t/ρ) T k (1/ρ). 其中 T k (t) 为 k 阶 Chebyshev 多项式. 在实际计算中, 我们无需通过线性组合 (3.17) 来计算 x (k).

95 95/98 事实上, 我们可以通过 Chebyshev 多项式的三项递推公式 T k (t) = 2t T k 1 (t) T k 2 (t), k = 2, 3,..., 由 x (k 1) 和 x (k 2) 直接计算出 x (k). 这样做的另一个好处是无需存储所有的 x (i). 1 令 µ k = T k (1/ρ), 即 T k (1/ρ) = 1. 由三项递推公式可得 µ k 1 = 2 µ k ρ 1 1. µ k 1 µ k 2

96 96/98 所以 x (k) x = p k (G) ε 0 = µ k T k (G/ρ) ε 0 [ ] 2G = µ k ρ T k 1(G/ρ) T k 2 (G/ρ) ε 0 [ 2G = µ k ρ 1 p k 1 (G/ρ)ε 0 1 ] p k 2 (G/ρ)ε 0 µ k 1 µ k 2 整理后可得 = µ k [ 2G ρ 1 ( x (k 1) x ) 1 ( x (k 2) x ) µ k 1 µ k 2 x (k) = 2µ k G µ k 1 ρ x(k 1) µ k x (k 2) + d k, µ k 2 ].

97 97/98 其中 d k = x 2µ k G µ k 1 ρ x + µ k x µ k 2 = x 2µ k x g µ k 1 ρ + µ k x µ k 2 = µ k ( 1 µ k 2 ρµ k µ k 2 = 2µ kg µ k 1 ρ. ) x + 2µ kg µ k 1 ρ 由此, 我们可以得到迭代格式 (3.15) 的 Chebyshev 加速方法.

98 98/98 算法 5.1 Chebyshev 加速方法 1: Set µ 0 = 1, µ 1 = ρ = ρ(g), x (0) = x (0), k = 1 2: compute x (1) = Gx (0) + g 3: while not converge do 4: k = k ( : µ k = ρ 1 1 ) 1 µ k 1 µ k 2 6: x (k) = 2µ k G µ k 1 ρ x(k 1) µ k x (k 2) + 2µ k µ k 2 µ k 1 ρ g 7: end while 该方法的每步迭代中只有一次矩阵向量乘积, 故整体运算量与原迭代基本相当. 若 λ(g) [α, β], 且 1 < α β < 1, 我们也可以构造出相应的 Chebyshev 加速方法, 留作练习.

目录 三种迭代格式 Jacobi 迭代法 Gauss-Seidel 迭代 超松弛迭代法 Jacobi 与 G-S 迭代的收敛性分析 收敛的充分必要条件 收敛的充分条件及误差估计 收敛速度 平均

目录 三种迭代格式 Jacobi 迭代法 Gauss-Seidel 迭代 超松弛迭代法 Jacobi 与 G-S 迭代的收敛性分析 收敛的充分必要条件 收敛的充分条件及误差估计 收敛速度 平均 线性方程组的古典迭代解法 目录 1 3.1 三种迭代格式 3.1.1 Jacobi 迭代法 3.1.2 Gauss-Seidel 迭代 3.1.3 超松弛迭代法 2 3.2 Jacobi 与 G-S 迭代的收敛性分析 3.2.1 收敛的充分必要条件 3.2.2 收敛的充分条件及误差估计 3 3.3 收敛速度 3.3.1 平均收敛速度和渐近收敛速度 3.3.2 模型问题 3.3.3 Jacobi 和

More information

2/63 1 非负矩阵 1.1 非负矩阵基本性质 1.2 正矩阵 1.3 非负矩阵的更多性质

2/63 1 非负矩阵 1.1 非负矩阵基本性质 1.2 正矩阵 1.3 非负矩阵的更多性质 第二讲 非负矩阵与 M 矩阵 非负矩阵 不可约非负矩阵 M- 矩阵与单调矩阵 对角占优 M- 矩阵 注记 非负矩阵在很多领域都有重要应用, 如数理经济, 运筹, 图像处理等. 同样, 它在矩阵理论与数值代数中也扮演着很重要的角色. 若无特别注明, 本讲内容都是在实数域中讨论. 2/63 1 非负矩阵 1.1 非负矩阵基本性质 1.2 正矩阵 1.3 非负矩阵的更多性质 3/63 非负矩阵, 正矩阵

More information

标题

标题 第 37 卷第 6 期西南大学学报 ( 自然科学版 ) 2015 年 6 月 Vol 37 No 6 JournalofSouthwestUniversity (NaturalScienceEdition) Jun 2015 DOI:10 13718/j cnki xdzk 2015 06 013 求解奇异鞍点问题的 GPHSSGGSOR 1 迭代法的半收敛性 曾闽丽, 林则安, 林智期 莆田学院数学学院,

More information

幻灯片 1

幻灯片 1 线性代数方程组 浙江大学控制系 本章内容 高斯消去法 LU 分解 特殊矩阵和矩阵求逆 误差分析 条件数 迭代方法 205/6/2 数值计算方法 2 误差分析和方程组条件数 利用逆矩阵确定方程组是否病态的方法 缩放系数矩阵 A, 使其每一行的最大元素为 计算缩放后的逆矩阵, 如果 A - 中有元素的值大于 几倍, 则方程组是病态的 将逆矩阵与原矩阵相乘, 检查结果是否接近单位阵 如果不接近单位阵, 则方程组是病态的

More information

6.3 正定二次型

6.3 正定二次型 6.3 正定二次型 一个实二次型, 既可以通过正交变换化为标准形, 也可以通过拉格朗日配方法化为标准形, 显然, 其标准形一般来说是不惟一的, 但标准形中所含有的项数是确定的, 项数等于二次型的秩 当变换为实变换时, 标准形中正系数和负系数的个数均是不变的 定理 ( 惯性定理 ) 设有二次型 f =x T Ax, 它的秩为 r, 如果有两个实的可逆变换 x=c y 及 x=c z 分别使 f =k

More information

第七讲 子空间迭代方法 1 Krylov 子空间 2 GMRES 算法 3 共轭梯度法 (CG) 4 收敛性分析 5 其它 Krylov 子空间迭代算法

第七讲 子空间迭代方法 1 Krylov 子空间 2 GMRES 算法 3 共轭梯度法 (CG) 4 收敛性分析 5 其它 Krylov 子空间迭代算法 第七讲 子空间迭代方法 1 Krylov 子空间 2 GMRES 算法 3 共轭梯度法 (CG) 4 收敛性分析 5 其它 Krylov 子空间迭代算法 2/55 基本思想 在一个维数较低的子空间中寻找解析解的一个最佳近似. 子空间迭代算法的主要过程可以分解为下面三步 : (1) 寻找合适的子空间 ; (2) 在该子空间中求 最佳近似 ; (3) 若这个近似解满足精度要求, 则停止计算 ; 否则,

More information

슬라이드 1

슬라이드 1 08-09 年度第一学期 0050 00503 计算方法 (B) 童伟华管理科研楼 05 室 E-mail: togwh@ustc.edu.c 中国科学技术大学数学科学学院 http://math.ustc.edu.c/ 第七章计算矩阵的特征值与 特征向量 特征值与特征向量 在实际工程计算中, 经常会遇到特征值和特征向量的计算, 如 : 机械 结构或电磁振动中的固有值问题 ; 物理学中的各种临界值等

More information

矩阵函数

矩阵函数 矩阵函数 矩阵分析 - 研究生课程 矩阵的多项式表示与矩阵的极小多项式 定义 1: 已知 和关于变量 的多项 式 那么我们称 为 的矩阵多项式 n x n 1 n 1 1 0 f( x) a x + a x + L + a x+ a n n n 1 n 1 1 0 f( ) a + a + L + a + a I n n n C 设为一个阶矩阵, 为其 Jordan 标准形, 则 n J 于是有 1

More information

AU = U λ c 2 c 3 c n C C n,, n U 2 U2 C U 2 = B = b 22 b 23 b 2n b 33 b 3n b nn U = U ( U 2, U AU = = = ( ( U 2 U 2 U AU ( U2 λ λ d 2 d 3 d n b 22 b 2

AU = U λ c 2 c 3 c n C C n,, n U 2 U2 C U 2 = B = b 22 b 23 b 2n b 33 b 3n b nn U = U ( U 2, U AU = = = ( ( U 2 U 2 U AU ( U2 λ λ d 2 d 3 d n b 22 b 2 Jordan, A m? (264(, A A m, A (, P P AP = D, A m = P D m P, P AP 837, Jacobi (, ( Jacobi,, Schur 24 Cayley-Hamilton 25,, A m Schur Jordan 26 Schur : 3 (Schur ( A C n n, U U AU = B, (3 B A n n =, n, n λ

More information

矩阵论 第三章:矩阵分析

矩阵论 第三章:矩阵分析 矩阵论 第三章 : 矩阵分析 马锦华 数据科学与计算机学院 中山大学 第三章 : 矩阵分析 3.1 矩阵序列 3.2 矩阵级数 3.3 矩阵函数 3.4 矩阵的微分与积分 3.5 矩阵分析应用举例 2 矩阵序列 定义 3.1: 设有中的矩阵序列 其中 若 m n C lim a a i 1, 2,, m; j 1, 2,, n, ij ij, 收敛于 记为 或 a ij mn 不收敛的矩阵序列称为发散.,

More information

Remark:随机变量不只离散和连续两种类型

Remark:随机变量不只离散和连续两种类型 Remar: 随机变量不只离散和连续两种类型 当题目要求证明随机变量的某些共同性质时 很多同学只对连续和离散两种类型进行讨论 这是比较典型的错误 练习 4. () P( = ) = P( = ) = P( = ) = P( ) = = = = = = () 由 E < 且 lm a =+ 不妨设 a > 其中 j = f{ : a a j} ap ( a) = a p ap ap j j j a :

More information

2/115 大规模稀疏线性方程组 Ax = b, A R n n, b R n. Krylov 子空间方法是子空间方法的成功代表 首选方法 Krylov 子空间方法. 基本思想 在一个维数较小的子空间 K R n 中寻找近似解. 这类方法也被看作是一种 投影方法, 即寻找真解在某个子空间中 的投影

2/115 大规模稀疏线性方程组 Ax = b, A R n n, b R n. Krylov 子空间方法是子空间方法的成功代表 首选方法 Krylov 子空间方法. 基本思想 在一个维数较小的子空间 K R n 中寻找近似解. 这类方法也被看作是一种 投影方法, 即寻找真解在某个子空间中 的投影 第四讲 Krylov 子空间方法 投影方法 Krylov 子空间与 Arnoldi 过程 一般线性方程组的 Krylov 子空间方法 对称线性方程的 Krylov 子空间方法 收敛性分析 基于双正交化过程的迭代方法 免转置迭代方法 正规方程的迭代方法 2/115 大规模稀疏线性方程组 Ax = b, A R n n, b R n. Krylov 子空间方法是子空间方法的成功代表 首选方法 Krylov

More information

Microsoft PowerPoint - Eng-math-lecture14.ppt [Compatibility Mode]

Microsoft PowerPoint - Eng-math-lecture14.ppt [Compatibility Mode] -- 第 讲 一 特征值与特征向量的概念定义 设 是 阶矩阵 如果数 和 维非零列向量 x 使关系式 x x 成立 那末 这样的数 称为方阵 的特征值 非零向量 x称为 的对应于特征值 的特征向量 说明 特征向量 x 特征值问题是对方阵而言的 阶方阵 的特征值 就是使齐次线性方程组 ( E x 有非零解的 值 即满足方程 E 的 都是矩阵 的特征值 // // E a a a a a a a a a

More information

<4D F736F F D20B5DACAAED5C220CBABCFDFD0D4BAAFCAFDA3A8BDB2D2E5A3A92E646F63>

<4D F736F F D20B5DACAAED5C220CBABCFDFD0D4BAAFCAFDA3A8BDB2D2E5A3A92E646F63> 高等代数第十章双线性函数 第十章双线性函数 10.1 线性函数 1. 设 V 是数域 F 上的一个线性空间, f 是 V 到 F 的一个映射, 若 f 满足 : (1) f( α + β) = f( α) + f( β); (2) f( kα) = kf( α), 式中 α, β 是 V 中任意元素, k 是 F 中任意数, 则称 f 为 V 上的一个线性函数. 2. 简单性质 : 设 f 是 V

More information

4= 8 4 < 4 ϑ = 4 ϑ ; 4 4= = 8 : 4 < : 4 < Κ : 4 ϑ ; : = 4 4 : ;

4= 8 4 < 4 ϑ = 4 ϑ ; 4 4= = 8 : 4 < : 4 < Κ : 4 ϑ ; : = 4 4 : ; ! #! % & ( ) +!, + +!. / 0 /, 2 ) 3 4 5 6 7 8 8 8 9 : 9 ;< 9 = = = 4 ) > (/?08 4 ; ; 8 Β Χ 2 ΔΔ2 4 4 8 4 8 4 8 Ε Φ Α, 3Γ Η Ι 4 ϑ 8 4 ϑ 8 4 8 4 < 8 4 5 8 4 4

More information

201408

201408 Computer Engineering and Applications 计算机工程与应用 2014,50(8) 11 定常二级迭代法与其外迭代法收敛性的比较 1,2 薛秋芳, 高兴宝 1 1, 刘晓光 XUE Qiufang 1,2, GAO Xingbao 1, LIU Xiaoguang 1 1. 陕西师范大学数学与信息科学学院, 西安 710062 2. 西安理工大学理学院应用数学系, 西安

More information

Ζ # % & ( ) % + & ) / 0 0 1 0 2 3 ( ( # 4 & 5 & 4 2 2 ( 1 ) ). / 6 # ( 2 78 9 % + : ; ( ; < = % > ) / 4 % 1 & % 1 ) 8 (? Α >? Β? Χ Β Δ Ε ;> Φ Β >? = Β Χ? Α Γ Η 0 Γ > 0 0 Γ 0 Β Β Χ 5 Ι ϑ 0 Γ 1 ) & Ε 0 Α

More information

扩充矩阵 给定矩阵 A 和向量 b a 11 a 12 a 13 b 1 A = a 21 a 22 a 23 b = b 2 a 31 a 32 a 33 b 3 定义扩充矩阵 ( A b ) = a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 b 1 b

扩充矩阵 给定矩阵 A 和向量 b a 11 a 12 a 13 b 1 A = a 21 a 22 a 23 b = b 2 a 31 a 32 a 33 b 3 定义扩充矩阵 ( A b ) = a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 b 1 b 数值代数 夏银华 中国科学技术大学 扩充矩阵 给定矩阵 A 和向量 b a 11 a 12 a 13 b 1 A = a 21 a 22 a 23 b = b 2 a 31 a 32 a 33 b 3 定义扩充矩阵 ( A b ) = a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 b 1 b 2 b 3 初等变换矩阵 放缩 (scaling): 第 i 个方程

More information

! /. /. /> /. / Ε Χ /. 2 5 /. /. / /. 5 / Φ0 5 7 Γ Η Ε 9 5 /

! /. /. /> /. / Ε Χ /. 2 5 /. /. / /. 5 / Φ0 5 7 Γ Η Ε 9 5 / ! # %& ( %) & +, + % ) # % % ). / 0 /. /10 2 /3. /!. 4 5 /6. /. 7!8! 9 / 5 : 6 8 : 7 ; < 5 7 9 1. 5 /3 5 7 9 7! 4 5 5 /! 7 = /6 5 / 0 5 /. 7 : 6 8 : 9 5 / >? 0 /.? 0 /1> 30 /!0 7 3 Α 9 / 5 7 9 /. 7 Β Χ9

More information

标题

标题 第 35 卷第 期西南大学学报 ( 自然科学版 ) 3 年 月 Vol.35 No. JouralofSouthwestUiversity (NaturalScieceEditio) Feb. 3 文章编号 :673 9868(3) 69 4 一类积分型 Meyer-KiḡZeler-Bzier 算子的点态逼近 赵晓娣, 孙渭滨 宁夏大学数学计算机学院, 银川 75 摘要 : 应用一阶 DitziaṉTotik

More information

! # % & ( & # ) +& & # ). / 0 ) + 1 0 2 & 4 56 7 8 5 0 9 7 # & : 6/ # ; 4 6 # # ; < 8 / # 7 & & = # < > 6 +? # Α # + + Β # Χ Χ Χ > Δ / < Ε + & 6 ; > > 6 & > < > # < & 6 & + : & = & < > 6+?. = & & ) & >&

More information

2016自然科学版第3期

2016自然科学版第3期 兰州大学学报 : 自然科学版, 016, 5(3) / 6 月 Journal of Lanzhou University:Natural Sciences,016,5(3) / June 几类特殊矩阵及性质 雍龙泉 1, 刘三阳, 史加荣 3, 熊文涛 4 5, 封全喜 1 陕西理工大学数学与计算机科学学院, 陕西汉中 73001 西安电子科技大学数学与统计学院, 西安 710071 3 西安建筑科技大学理学院,

More information

10-03.indd

10-03.indd 1 03 06 12 14 16 18 é 19 21 23 25 28 30 35 40 45 05 22 27 48 49 50 51 2 3 4 é é í 5 é 6 7 8 9 10 11 12 13 14 15 16 17 18 19 é 20 21 22 23 ü ü ü ü ü ü ü ü ü 24 ü 25 26 27 28 29 30 31 32 33 34 35 36 37 38

More information

1 线性空间 基 维数和坐标 3 子空间 4 线性空间的同构 5 线性映射 6 线性映射的像与核 7 线性变换 8 不变子空间 厦门大学数学科学学院网址 :gdjpkc.xmu.edu.c; IP://

1 线性空间 基 维数和坐标 3 子空间 4 线性空间的同构 5 线性映射 6 线性映射的像与核 7 线性变换 8 不变子空间 厦门大学数学科学学院网址 :gdjpkc.xmu.edu.c; IP:// 线性空间与线性映射 知识回顾 1 线性空间 基 维数和坐标 3 子空间 4 线性空间的同构 5 线性映射 6 线性映射的像与核 7 线性变换 8 不变子空间 厦门大学数学科学学院网址 :gdjpkc.xmu.edu.c; IP://11.19.180.133 1 线性空间 厦门大学数学科学学院网址 :gdjpkc.xmu.edu.c; IP://11.19.180.133 定义称 V 是数域 F 上的线性空间,

More information

! # % & # % & ( ) % % %# # %+ %% % & + %, ( % % &, & #!.,/, % &, ) ) ( % %/ ) %# / + & + (! ) &, & % & ( ) % % (% 2 & % ( & 3 % /, 4 ) %+ %( %!

! # % & # % & ( ) % % %# # %+ %% % & + %, ( % % &, & #!.,/, % &, ) ) ( % %/ ) %# / + & + (! ) &, & % & ( ) % % (% 2 & % ( & 3 % /, 4 ) %+ %( %! ! # # % & ( ) ! # % & # % & ( ) % % %# # %+ %% % & + %, ( % % &, & #!.,/, % &, ) ) ( % %/ ) 0 + 1 %# / + & + (! ) &, & % & ( ) % % (% 2 & % ( & 3 % /, 4 ) %+ %( %! # ( & & 5)6 %+ % ( % %/ ) ( % & + %/

More information

! Ν! Ν Ν & ] # Α. 7 Α ) Σ ),, Σ 87 ) Ψ ) +Ε 1)Ε Τ 7 4, <) < Ε : ), > 8 7

! Ν! Ν Ν & ] # Α. 7 Α ) Σ ),, Σ 87 ) Ψ ) +Ε 1)Ε Τ 7 4, <) < Ε : ), > 8 7 !! # & ( ) +,. )/ 0 1, 2 ) 3, 4 5. 6 7 87 + 5 1!! # : ;< = > < < ;?? Α Β Χ Β ;< Α? 6 Δ : Ε6 Χ < Χ Α < Α Α Χ? Φ > Α ;Γ ;Η Α ;?? Φ Ι 6 Ε Β ΕΒ Γ Γ > < ϑ ( = : ;Α < : Χ Κ Χ Γ? Ε Ι Χ Α Ε? Α Χ Α ; Γ ;

More information

1989-2004数学三、四考研试题(线性代数部分3)

1989-2004数学三、四考研试题(线性代数部分3) 989- 数学三 四考研试题 线性代数部分 ) 三 计算证明题. 已知 XXB 其中 求矩阵 X. B - 5 989 年数学三 四 ). 设 ) ) t) ) 问当 t 何值时 向量组 线性无关? ) 问当 t 何值时 向量组 线性相关? ) 当向量组 线性相关时 将 表示为 的线性组合. 设 ) 试求矩阵 的特征值 - - 989 年数学三 ) ) 利用 ) 小题的结果 求矩阵 E 的特征值 其中

More information

试卷

试卷 竞赛试卷 ( 数学专业 参考答案 一 (5 分 在仿射坐标系中 求过点 M ( 与平面 :3x y + z 平行 且与 x y 3 z 直线 l : 相交的直线 l 的方程 4 解法一 : 先求 l 的一个方向向量 X Y Z 因为 l 过点 M 且 l 与 l 相交 所以有 4 X 3 - Y ( Z..4 分 即 X + Y Z...3 分 又因为 l 与 平行 所以有 联立上述两个方程解得 :

More information

08-01.indd

08-01.indd 1 02 04 08 14 20 27 31 35 40 43 51 57 60 07 26 30 39 50 56 65 65 67 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ω ρ ε 23 λ ω < 1 ω < 1 ω > 0 24 25 26 27 28 29 30 31 ρ 1 ρ σ b a x x i +3 x i

More information

ii 纸上得来终觉浅, 绝知此事要躬行 学而不思则罔, 思而不学则殆 知识, 只有当它靠积极的思考得来 而不是凭记忆得来的时候, 才是真正的知识

ii 纸上得来终觉浅, 绝知此事要躬行 学而不思则罔, 思而不学则殆 知识, 只有当它靠积极的思考得来 而不是凭记忆得来的时候, 才是真正的知识 矩阵计算讲义 * 潘建瑜 jypan@math.ecnu.edu.cn 2018 年 3 月 1 日 * 本讲义仅供 矩阵计算 课堂教学使用 ii 纸上得来终觉浅, 绝知此事要躬行 学而不思则罔, 思而不学则殆 知识, 只有当它靠积极的思考得来 而不是凭记忆得来的时候, 才是真正的知识 目录 第零讲 引言 1 0.1 课程主要内容..........................................

More information

Ρ Τ Π Υ 8 ). /0+ 1, 234) ς Ω! Ω! # Ω Ξ %& Π 8 Δ, + 8 ),. Ψ4) (. / 0+ 1, > + 1, / : ( 2 : / < Α : / %& %& Ζ Θ Π Π 4 Π Τ > [ [ Ζ ] ] %& Τ Τ Ζ Ζ Π

Ρ Τ Π Υ 8 ). /0+ 1, 234) ς Ω! Ω! # Ω Ξ %& Π 8 Δ, + 8 ),. Ψ4) (. / 0+ 1, > + 1, / : ( 2 : / < Α : / %& %& Ζ Θ Π Π 4 Π Τ > [ [ Ζ ] ] %& Τ Τ Ζ Ζ Π ! # % & ( ) + (,. /0 +1, 234) % 5 / 0 6/ 7 7 & % 8 9 : / ; 34 : + 3. & < / = : / 0 5 /: = + % >+ ( 4 : 0, 7 : 0,? & % 5. / 0:? : / : 43 : 2 : Α : / 6 3 : ; Β?? : Α 0+ 1,4. Α? + & % ; 4 ( :. Α 6 4 : & %

More information

Microsoft PowerPoint - 概率统计Ch02.ppt [Compatibility Mode]

Microsoft PowerPoint - 概率统计Ch02.ppt [Compatibility Mode] 66 随机变量的函数.5 随机变量的函数的分布 设 是一随机变量, 是 的函数, g(, 则 也是一个随机变量. 本节的任务 : 当 取值 x 时, 取值 y g 67 ( 一 离散型随机变量的函数 设 是离散型随机变量, 其分布律为 或 P { x } p (,, x x, P p p, x p 已知随机变量 的分布, 并且已知 g 要求随机变量 的分布. (, 是 的函数 : g(, 则 也是离散型随机变

More information

标题

标题 第 38 卷第 5 期西南大学学报 ( 自然科学版 ) 2016 年 5 月 Vol.38 No.5 JournalofSouthwestUniversity (NaturalScienceEdition) Maẏ 2016 DOI:10.13718/j.cnki.xdzk.2016.05.019 1 求解一类广义均衡问题的交替方向法 徐洁, 张俊容, 刘佳 西南大学数学与统计学院, 重庆 400715

More information

,!! #! > 1? = 4!! > = 5 4? 2 Α Α!.= = 54? Β. : 2>7 2 1 Χ! # % % ( ) +,. /0, , ) 7. 2

,!! #! > 1? = 4!! > = 5 4? 2 Α Α!.= = 54? Β. : 2>7 2 1 Χ! # % % ( ) +,. /0, , ) 7. 2 ! # %!% # ( % ) + %, ). ) % %(/ / %/!! # %!! 0 1 234 5 6 2 7 8 )9!2: 5; 1? = 4!! > = 5 4? 2 Α 7 72 1 Α!.= = 54?2 72 1 Β. : 2>7 2 1 Χ! # % % ( ) +,.

More information

&! +! # ## % & #( ) % % % () ) ( %

&! +! # ## % & #( ) % % % () ) ( % &! +! # ## % & #( ) % % % () ) ( % &! +! # ## % & #( ) % % % () ) ( % ,. /, / 0 0 1,! # % & ( ) + /, 2 3 4 5 6 7 8 6 6 9 : / ;. ; % % % % %. ) >? > /,,

More information

. () ; () ; (3) ; (4).. () : P.4 3.4; P. A (3). () : P. A (5)(6); B. (3) : P.33 A (9),. (4) : P. B 5, 7(). (5) : P.8 3.3; P ; P.89 A 7. (6) : P.

. () ; () ; (3) ; (4).. () : P.4 3.4; P. A (3). () : P. A (5)(6); B. (3) : P.33 A (9),. (4) : P. B 5, 7(). (5) : P.8 3.3; P ; P.89 A 7. (6) : P. () * 3 6 6 3 9 4 3 5 8 6 : 3. () ; () ; (3) (); (4) ; ; (5) ; ; (6) ; (7) (); (8) (, ); (9) ; () ; * Email: huangzh@whu.edu.cn . () ; () ; (3) ; (4).. () : P.4 3.4; P. A (3). () : P. A (5)(6); B. (3) :

More information

复习 : 线性变换与矩阵 _1 设 V 是数域 K 上 n 维向量空间, ξ1, ξ2... ξ n 是 V 的一组基, 则存在线性空间同构 1 η : V K n a 1 n a 2 α = a iξ i i = 1 a n 线性空间同构保持线性关系, 保持直和分解.

复习 : 线性变换与矩阵 _1 设 V 是数域 K 上 n 维向量空间, ξ1, ξ2... ξ n 是 V 的一组基, 则存在线性空间同构 1 η : V K n a 1 n a 2 α = a iξ i i = 1 a n 线性空间同构保持线性关系, 保持直和分解. 第六章特征值 Eigenvalue 复习 : 线性变换与矩阵 _1 设 V 是数域 K 上 n 维向量空间, ξ1, ξ2... ξ n 是 V 的一组基, 则存在线性空间同构 1 η : V K n a 1 n a 2 α = a iξ i i = 1 a n 线性空间同构保持线性关系, 保持直和分解. 复习 : 线性变换与矩阵 _2 线性变换的表示矩阵设 ϕ 是 V V 的线性变换, 取 V 的一组基

More information

!! )!!! +,./ 0 1 +, 2 3 4, # 8,2 6, 2 6,,2 6, 2 6 3,2 6 5, 2 6 3, 2 6 9!, , 2 6 9, 2 3 9, 2 6 9,

!! )!!! +,./ 0 1 +, 2 3 4, # 8,2 6, 2 6,,2 6, 2 6 3,2 6 5, 2 6 3, 2 6 9!, , 2 6 9, 2 3 9, 2 6 9, ! # !! )!!! +,./ 0 1 +, 2 3 4, 23 3 5 67 # 8,2 6, 2 6,,2 6, 2 6 3,2 6 5, 2 6 3, 2 6 9!, 2 6 65, 2 6 9, 2 3 9, 2 6 9, 2 6 3 5 , 2 6 2, 2 6, 2 6 2, 2 6!!!, 2, 4 # : :, 2 6.! # ; /< = > /?, 2 3! 9 ! #!,!!#.,

More information

2/78 非对称矩阵特征值 / 特征向量的计算 基本约定 1: A R n n 非对称 稠密 基本约定 2: λ 1 λ 2 λ n 0 本讲主要讨论如何计算 A 的全部特征值和 / 或特征向量. 主要介绍以下方法 : 幂迭代方法 反迭代方法 ( 位移策略,Rayleigh 商迭代 ) 正交迭代方法

2/78 非对称矩阵特征值 / 特征向量的计算 基本约定 1: A R n n 非对称 稠密 基本约定 2: λ 1 λ 2 λ n 0 本讲主要讨论如何计算 A 的全部特征值和 / 或特征向量. 主要介绍以下方法 : 幂迭代方法 反迭代方法 ( 位移策略,Rayleigh 商迭代 ) 正交迭代方法 第四讲 非对称特征值问题 1 幂迭代 2 反迭代 3 正交迭代 4 QR 迭代 5 带位移的隐式 QR 迭代 6 特征向量的计算 7 广义特征值问题 8 应用 : 多项式求根 2/78 非对称矩阵特征值 / 特征向量的计算 基本约定 1: A R n n 非对称 稠密 基本约定 2: λ 1 λ 2 λ n 0 本讲主要讨论如何计算 A 的全部特征值和 / 或特征向量. 主要介绍以下方法 : 幂迭代方法

More information

& &((. ) ( & ) 6 0 &6,: & ) ; ; < 7 ; = = ;# > <# > 7 # 0 7#? Α <7 7 < = ; <

& &((. ) ( & ) 6 0 &6,: & ) ; ; < 7 ; = = ;# > <# > 7 # 0 7#? Α <7 7 < = ; < ! # %& ( )! & +, &. / 0 # # 1 1 2 # 3 4!. &5 (& ) 6 0 0 2! +! +( &) 6 0 7 & 6 8. 9 6 &((. ) 6 4. 6 + ( & ) 6 0 &6,: & )6 0 3 7 ; ; < 7 ; = = ;# > 7 # 0 7#? Α

More information

., /,, 0!, + & )!. + + (, &, & 1 & ) ) 2 2 ) 1! 2 2

., /,, 0!, + & )!. + + (, &, & 1 & ) ) 2 2 ) 1! 2 2 ! # &!! ) ( +, ., /,, 0!, + & )!. + + (, &, & 1 & ) ) 2 2 ) 1! 2 2 ! 2 2 & & 1 3! 3, 4 45!, 2! # 1 # ( &, 2 &, # 7 + 4 3 ) 8. 9 9 : ; 4 ), 1!! 4 4 &1 &,, 2! & 1 2 1! 1! 1 & 2, & 2 & < )4 )! /! 4 4 &! &,

More information

/ Ν #, Ο / ( = Π 2Θ Ε2 Ρ Σ Π 2 Θ Ε Θ Ρ Π 2Θ ϑ2 Ρ Π 2 Θ ϑ2 Ρ Π 23 8 Ρ Π 2 Θϑ 2 Ρ Σ Σ Μ Π 2 Θ 3 Θ Ρ Κ2 Σ Π 2 Θ 3 Θ Ρ Κ Η Σ Π 2 ϑ Η 2 Ρ Π Ρ Π 2 ϑ Θ Κ Ρ Π

/ Ν #, Ο / ( = Π 2Θ Ε2 Ρ Σ Π 2 Θ Ε Θ Ρ Π 2Θ ϑ2 Ρ Π 2 Θ ϑ2 Ρ Π 23 8 Ρ Π 2 Θϑ 2 Ρ Σ Σ Μ Π 2 Θ 3 Θ Ρ Κ2 Σ Π 2 Θ 3 Θ Ρ Κ Η Σ Π 2 ϑ Η 2 Ρ Π Ρ Π 2 ϑ Θ Κ Ρ Π ! # #! % & ( ) % # # +, % #. % ( # / ) % 0 1 + ) % 2 3 3 3 4 5 6 # 7 % 0 8 + % 8 + 9 ) 9 # % : ; + % 5! + )+)#. + + < ) ( # )# < # # % 0 < % + % + < + ) = ( 0 ) # + + # % )#!# +), (? ( # +) # + ( +. #!,

More information

# # # #!! % &! # % 6 & () ) &+ & ( & +, () + 0. / & / &1 / &1, & ( ( & +. 4 / &1 5,

# # # #!! % &! # % 6 & () ) &+ & ( & +, () + 0. / & / &1 / &1, & ( ( & +. 4 / &1 5, # # # #!! % &! # % 6 & () ) &+ & ( & +, () + 0. / & / &1 / &1, & ( 0 2 3 ( & +. 4 / &1 5, !! & 6 7! 6! &1 + 51, (,1 ( 5& (5( (5 & &1 8. +5 &1 +,,( ! (! 6 9/: ;/:! % 7 3 &1 + ( & &, ( && ( )

More information

-2 4 - cr 5 - 15 3 5 ph 6.5-8.5 () 450 mg/l 0.3 mg/l 0.1 mg/l 1.0 mg/l 1.0 mg/l () 0.002 mg/l 0.3 mg/l 250 mg/l 250 mg/l 1000 mg/l 1.0 mg/l 0.05 mg/l 0.05 mg/l 0.01 mg/l 0.001 mg/l 0.01 mg/l () 0.05 mg/l

More information

<4F3A5CBED8D5F3C2DB5CB5DA3130BDB220BED8D5F3BAAFCAFDBCB0C6E4CEA2BBFDB7D62E707074>

<4F3A5CBED8D5F3C2DB5CB5DA3130BDB220BED8D5F3BAAFCAFDBCB0C6E4CEA2BBFDB7D62E707074> 矩阵论 主讲教师 : 徐乐 204 年 2 月 0 日星期三 上讲回顾 第 9 讲矩阵函数的求解 矩阵函数的计算 利用 Jordan 标准形求矩阵函数 矩阵论 2 矩阵函数的计算 Hamilton-Cayley 定理 n 阶矩阵 A 是其特征多项式的零点 即令 则有 零化多项式 n ( ) det( I A) c c c n n 对于多项式 f (z), 若 f (A)=0 则称 f (z) 为 A

More information

, ( 6 7 8! 9! (, 4 : : ; 0.<. = (>!? Α% ), Β 0< Χ 0< Χ 2 Δ Ε Φ( 7 Γ Β Δ Η7 (7 Ι + ) ϑ!, 4 0 / / 2 / / < 5 02

, ( 6 7 8! 9! (, 4 : : ; 0.<. = (>!? Α% ), Β 0< Χ 0< Χ 2 Δ Ε Φ( 7 Γ Β Δ Η7 (7 Ι + ) ϑ!, 4 0 / / 2 / / < 5 02 ! # % & ( ) +, ) %,! # % & ( ( ) +,. / / 01 23 01 4, 0/ / 5 0 , ( 6 7 8! 9! (, 4 : : ; 0.!? Α% ), Β 0< Χ 0< Χ 2 Δ Ε Φ( 7 Γ Β Δ 5 3 3 5 3 1 Η7 (7 Ι + ) ϑ!, 4 0 / / 2 / 3 0 0 / < 5 02 Ν!.! %) / 0

More information

8 9 8 Δ 9 = 1 Η Ι4 ϑ< Κ Λ 3ϑ 3 >1Ε Μ Ε 8 > = 8 9 =

8 9 8 Δ 9 = 1 Η Ι4 ϑ< Κ Λ 3ϑ 3 >1Ε Μ Ε 8 > = 8 9 = !! % & ( & ),,., / 0 1. 0 0 3 4 0 5 3 6!! 7 8 9 8!! : ; < = > :? Α 4 8 9 < Β Β : Δ Ε Δ Α = 819 = Γ 8 9 8 Δ 9 = 1 Η Ι4 ϑ< Κ Λ 3ϑ 3 >1Ε 8 9 0 Μ Ε 8 > 9 8 9 = 8 9 = 819 8 9 =

More information

微积分 授课讲义

微积分 授课讲义 2018 10 aiwanjun@sjtu.edu.cn 1201 / 18:00-20:20 213 14:00-17:00 I II Taylor : , n R n : x = (x 1, x 2,..., x n ) R; x, x y ; δ( ) ; ; ; ; ; ( ) ; ( / ) ; ; Ů(P 1,δ) P 1 U(P 0,δ) P 0 Ω P 1: 1.1 ( ). Ω

More information

07-3.indd

07-3.indd 1 2 3 4 5 6 7 08 11 19 26 31 35 38 47 52 59 64 67 73 10 18 29 76 77 78 79 81 84 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

More information

!! # % & ( )!!! # + %!!! &!!, # ( + #. ) % )/ # & /.

!! # % & ( )!!! # + %!!! &!!, # ( + #. ) % )/ # & /. ! # !! # % & ( )!!! # + %!!! &!!, # ( + #. ) % )/ # & /. #! % & & ( ) # (!! /! / + ) & %,/ #! )!! / & # 0 %#,,. /! &! /!! ) 0+(,, # & % ) 1 # & /. / & %! # # #! & & # # #. ).! & #. #,!! 2 34 56 7 86 9

More information

第一章 绪论

第一章  绪论 1-1 1-1 1-5 0.05 1-6 1 60mm 1.5W/(m K) 5-5 m C 1-7 1cm, 0 m 1.04W/(m K) C C 50 50 4.09 10 kj/kg C 1-9 =69 C f =0 w C =14mm d 80mm 8.5W 1-11 10mm 0 C 85 C ( ) 175 W m K 1mm 1-14 T0 0K T = w 50K ε = 0. 7

More information

Β 8 Α ) ; %! #?! > 8 8 Χ Δ Ε ΦΦ Ε Γ Δ Ε Η Η Ι Ε ϑ 8 9 :! 9 9 & ϑ Κ & ϑ Λ &! &!! 4!! Μ Α!! ϑ Β & Ν Λ Κ Λ Ο Λ 8! % & Π Θ Φ & Ρ Θ & Θ & Σ ΠΕ # & Θ Θ Σ Ε

Β 8 Α ) ; %! #?! > 8 8 Χ Δ Ε ΦΦ Ε Γ Δ Ε Η Η Ι Ε ϑ 8 9 :! 9 9 & ϑ Κ & ϑ Λ &! &!! 4!! Μ Α!! ϑ Β & Ν Λ Κ Λ Ο Λ 8! % & Π Θ Φ & Ρ Θ & Θ & Σ ΠΕ # & Θ Θ Σ Ε ! #!! % & ( ) +,. /. 0,(,, 2 4! 6! #!!! 8! &! % # & # &! 9 8 9 # : : : : :!! 9 8 9 # #! %! ; &! % + & + & < = 8 > 9 #!!? Α!#!9 Α 8 8!!! 8!%! 8! 8 Β 8 Α ) ; %! #?! > 8 8 Χ Δ Ε ΦΦ Ε Γ Δ Ε Η Η Ι Ε ϑ 8 9 :!

More information

) Μ <Κ 1 > < # % & ( ) % > Χ < > Δ Χ < > < > / 7 ϑ Ν < Δ 7 ϑ Ν > < 8 ) %2 ): > < Ο Ε 4 Π : 2 Θ >? / Γ Ι) = =? Γ Α Ι Ρ ;2 < 7 Σ6 )> Ι= Η < Λ 2 % & 1 &

) Μ <Κ 1 > < # % & ( ) % > Χ < > Δ Χ < > < > / 7 ϑ Ν < Δ 7 ϑ Ν > < 8 ) %2 ): > < Ο Ε 4 Π : 2 Θ >? / Γ Ι) = =? Γ Α Ι Ρ ;2 < 7 Σ6 )> Ι= Η < Λ 2 % & 1 & ! # % & ( ) % + ),. / & 0 1 + 2. 3 ) +.! 4 5 2 2 & 5 0 67 1) 8 9 6.! :. ;. + 9 < = = = = / >? Α ) /= Β Χ Β Δ Ε Β Ε / Χ ΦΓ Χ Η Ι = = = / = = = Β < ( # % & ( ) % + ),. > (? Φ?? Γ? ) Μ

More information

% %! # % & ( ) % # + # # % # # & & % ( #,. %

% %! # % & ( ) % # + # # % # # & & % ( #,. % !!! # #! # % & % %! # % & ( ) % # + # # % # # & & % ( #,. % , ( /0 ) %, + ( 1 ( 2 ) + %, ( 3, ( 123 % & # %, &% % #, % ( ) + & &% & ( & 4 ( & # 4 % #, #, ( ) + % 4 % & &, & & # / / % %, &% ! # #! # # #

More information

Ⅰ Ⅱ 1 2 Ⅲ Ⅳ

Ⅰ Ⅱ 1 2 Ⅲ Ⅳ Ⅰ Ⅱ 1 2 Ⅲ Ⅳ !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

More information

koji-13.dvi

koji-13.dvi 26 13 1, 2, 3, 4, 5, 6, 7 1 18 1. xy D D = {(x, y) y 2 x 4 y 2,y } x + y2 dxdy D 2 y O 4 x 2. xyz D D = {(x, y, z) x 1, y x 2, z 1, y+ z x} D 3. [, 1] [, 1] (, ) 2 f (1)

More information

幻灯片 1

幻灯片 1 第一类换元法 ( 凑微分法 ) 学习指导 复习 : 凑微分 部分常用的凑微分 : () n d d( (4) d d( ); (5) d d(ln ); n n (6) e d d( e ); () d d( b); ); () d d( ); (7) sin d d (cos ) 常见凑微分公式 ); ( ) ( ) ( b d b f d b f ); ( ) ( ) ( n n n n d f

More information

第一章三角函数 1.3 三角函数的诱导公式 A 组 ( ) 一 选择题 : 共 6 小题 1 ( 易诱导公式 ) 若 A B C 分别为 ABC 的内角, 则下列关系中正确的是 A. sin( A B) sin C C. tan( A B) tan C 2 ( 中诱导公式 ) ( ) B. cos(

第一章三角函数 1.3 三角函数的诱导公式 A 组 ( ) 一 选择题 : 共 6 小题 1 ( 易诱导公式 ) 若 A B C 分别为 ABC 的内角, 则下列关系中正确的是 A. sin( A B) sin C C. tan( A B) tan C 2 ( 中诱导公式 ) ( ) B. cos( 第一章三角函数 1. 三角函数的诱导公式 A 组 一 选择题 : 共 6 小题 1 ( 易诱导公式 ) 若 A B C 分别为 ABC 的内角 则下列关系中正确的是 A. sin( A B) sin C C. tan( A B) tan C ( 中诱导公式 ) B. cos( B C) cos A D. sin( B C) sin A sin60 cos( ) sin( 0 )cos( 70 ) 的值等于

More information

!!! #! )! ( %!! #!%! % + % & & ( )) % & & #! & )! ( %! ),,, )

!!! #! )! ( %!! #!%! % + % & & ( )) % & & #! & )! ( %! ),,, ) ! # % & # % ( ) & + + !!! #! )! ( %!! #!%! % + % & & ( )) % & & #! & )! ( %! ),,, ) 6 # / 0 1 + ) ( + 3 0 ( 1 1( ) ) ( 0 ) 4 ( ) 1 1 0 ( ( ) 1 / ) ( 1 ( 0 ) ) + ( ( 0 ) 0 0 ( / / ) ( ( ) ( 5 ( 0 + 0 +

More information

Introduction to Hamilton-Jacobi Equations and Periodic Homogenization

Introduction to Hamilton-Jacobi Equations  and Periodic Homogenization Introduction to Hamilton-Jacobi Equations and Periodic Yu-Yu Liu NCKU Math August 22, 2012 Yu-Yu Liu (NCKU Math) H-J equation and August 22, 2012 1 / 15 H-J equations H-J equations A Hamilton-Jacobi equation

More information

8 9 < ; ; = < ; : < ;! 8 9 % ; ϑ 8 9 <; < 8 9 <! 89! Ε Χ ϑ! ϑ! ϑ < ϑ 8 9 : ϑ ϑ 89 9 ϑ ϑ! ϑ! < ϑ < = 8 9 Χ ϑ!! <! 8 9 ΧΧ ϑ! < < < < = 8 9 <! = 8 9 <! <

8 9 < ; ; = < ; : < ;! 8 9 % ; ϑ 8 9 <; < 8 9 <! 89! Ε Χ ϑ! ϑ! ϑ < ϑ 8 9 : ϑ ϑ 89 9 ϑ ϑ! ϑ! < ϑ < = 8 9 Χ ϑ!! <! 8 9 ΧΧ ϑ! < < < < = 8 9 <! = 8 9 <! < ! # % ( ) ( +, +. ( / 0 1) ( 2 1 1 + ( 3 4 5 6 7! 89 : ; 8 < ; ; = 9 ; ; 8 < = 9! ; >? 8 = 9 < : ; 8 < ; ; = 9 8 9 = : : ; = 8 9 = < 8 < 9 Α 8 9 =; %Β Β ; ; Χ ; < ; = :; Δ Ε Γ Δ Γ Ι 8 9 < ; ; = < ; :

More information

> # ) Β Χ Χ 7 Δ Ε Φ Γ 5 Η Γ + Ι + ϑ Κ 7 # + 7 Φ 0 Ε Φ # Ε + Φ, Κ + ( Λ # Γ Κ Γ # Κ Μ 0 Ν Ο Κ Ι Π, Ι Π Θ Κ Ι Π ; 4 # Ι Π Η Κ Ι Π. Ο Κ Ι ;. Ο Κ Ι Π 2 Η

> # ) Β Χ Χ 7 Δ Ε Φ Γ 5 Η Γ + Ι + ϑ Κ 7 # + 7 Φ 0 Ε Φ # Ε + Φ, Κ + ( Λ # Γ Κ Γ # Κ Μ 0 Ν Ο Κ Ι Π, Ι Π Θ Κ Ι Π ; 4 # Ι Π Η Κ Ι Π. Ο Κ Ι ;. Ο Κ Ι Π 2 Η 1 )/ 2 & +! # % & ( ) +, + # # %. /& 0 4 # 5 6 7 8 9 6 : : : ; ; < = > < # ) Β Χ Χ 7 Δ Ε Φ Γ 5 Η Γ + Ι + ϑ Κ 7 # + 7 Φ 0 Ε Φ # Ε + Φ, Κ + ( Λ # Γ Κ Γ #

More information

Microsoft PowerPoint - new第八讲.ppt [兼容模式]

Microsoft PowerPoint - new第八讲.ppt [兼容模式] 高等数值算法与应用 ( 八 ) Advanced Numerical Algorithms & Applications 计算机科学与技术系喻文健 内容概要 线性方程组的迭代解法 ( 三 ) 对称矩阵的 Arnoldi 过程 Lanczos 过程 从 Lanczos 过程到共轭梯度法 第三类 Krylov 子空间迭代法基础 Lanczos 双正交化过程 构造预条件矩阵的技术 简单介绍 Wenjian

More information

2 2 Λ ϑ Δ Χ Δ Ι> 5 Λ Λ Χ Δ 5 Β. Δ Ι > Ε!!Χ ϑ : Χ Ε ϑ! ϑ Β Β Β ϑ Χ Β! Β Χ 5 ϑ Λ ϑ % < Μ / 4 Ν < 7 :. /. Ο 9 4 < / = Π 7 4 Η 7 4 =

2 2 Λ ϑ Δ Χ Δ Ι> 5 Λ Λ Χ Δ 5 Β. Δ Ι > Ε!!Χ ϑ : Χ Ε ϑ! ϑ Β Β Β ϑ Χ Β! Β Χ 5 ϑ Λ ϑ % < Μ / 4 Ν < 7 :. /. Ο 9 4 < / = Π 7 4 Η 7 4 = ! # % # & ( ) % # ( +, & % # ) % # (. / ). 1 2 3 4! 5 6 4. 7 8 9 4 : 2 ; 4 < = = 2 >9 3? & 5 5 Α Α 1 Β ΧΔ Ε Α Φ 7 Γ 9Η 8 Δ Ι > Δ / ϑ Κ Α Χ Ε ϑ Λ ϑ 2 2 Λ ϑ Δ Χ Δ Ι> 5 Λ Λ Χ Δ 5 Β. Δ Ι > Ε!!Χ ϑ : Χ Ε ϑ!

More information

4 A C n n, AA = A A, A,,, Hermite, Hermite,, A, A A, A, A 4 (, 4,, A A, ( A C n n, A A n, 4 A = (a ij n n, λ, λ,, λ n A n n ( (Schur λ i n

4 A C n n, AA = A A, A,,, Hermite, Hermite,, A, A A, A, A 4 (, 4,, A A, ( A C n n, A A n, 4 A = (a ij n n, λ, λ,, λ n A n n ( (Schur λ i n ,?,,, A, A ( Gauss m n A B P Q ( Ir B = P AQ r(a = r, A Ax = b P Ax = P b, x = Qy, ( Ir y = P b (4 (4, A A = ( P Ir Q,,, Schur, Cholesky LU, ( QR,, Schur,, (,,, 4 A AA = A A Schur, U U AU = T AA = A A

More information

. /!Ι Γ 3 ϑκ, / Ι Ι Ι Λ, Λ +Ι Λ +Ι

. /!Ι Γ 3 ϑκ, / Ι Ι Ι Λ, Λ +Ι Λ +Ι ! # % & ( ) +,& ( + &. / 0 + 1 0 + 1,0 + 2 3., 0 4 2 /.,+ 5 6 / 78. 9: ; < = : > ; 9? : > Α

More information

目录 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根

目录 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根 线性方程组的直接解法 目录 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 2 2.2 三角形方程组和三角分解 2.2. 三角方程组的解法 2.2.2 Gauss 变换 2.2.3 Doolittle 分解 3 2.3 选主元三角分解 4 2.4 平方根法及改进的平方根法 2.4. 平方根法 2.4.2 改进的平方根法 5 2.5

More information

第五讲 对称特征值问题 1 Jacobi 迭代 2 Rayleigh 商迭代 3 对称 QR 迭代 4 分而治之法 5 对分法和逆迭代 6 奇异值分解 7 扰动分析

第五讲 对称特征值问题 1 Jacobi 迭代 2 Rayleigh 商迭代 3 对称 QR 迭代 4 分而治之法 5 对分法和逆迭代 6 奇异值分解 7 扰动分析 第五讲 对称特征值问题 1 Jacobi 迭代 2 Rayleigh 商迭代 3 对称 QR 迭代 4 分而治之法 5 对分法和逆迭代 6 奇异值分解 7 扰动分析 2/93 关于对称特征值问题的常用算法有 ( 直接法 ): Jacobi 迭代 : 最古老, 收敛速度较慢, 但精度较高, 且很适合并行计算. Rayleigh 商迭代 : 一般具有三次收敛性, 但需要解方程组. 对称 QR 迭代 :

More information

! # %& ( %! & & + %!, ( Α Α Α Α Χ Χ Α Χ Α Α Χ Α Α Α Α

! # %& ( %! & & + %!, ( Α Α Α Α Χ Χ Α Χ Α Α Χ Α Α Α Α Ε! # % & ( )%! & & + %!, (./ 0 1 & & 2. 3 &. 4/. %! / (! %2 % ( 5 4 5 ) 2! 6 2! 2 2. / & 7 2! % &. 3.! & (. 2 & & / 8 2. ( % 2 & 2.! 9. %./ 5 : ; 5. % & %2 2 & % 2!! /. . %! & % &? & 5 6!% 2.

More information

这里考查三个物体偏离平衡位置的位移, 分别记为 y (t), y 2 (t), y 3 (t). 因为物体在平衡状态 所受的重力已经和弹簧伸长的弹力平衡, 所以物体的加速度只和 偏离平衡位置引起的弹簧伸长相关. 根据牛顿第二定律以及胡 克定律 ( 即弹簧的弹力与拉伸长度成正比 ) 可列出如下微分方程

这里考查三个物体偏离平衡位置的位移, 分别记为 y (t), y 2 (t), y 3 (t). 因为物体在平衡状态 所受的重力已经和弹簧伸长的弹力平衡, 所以物体的加速度只和 偏离平衡位置引起的弹簧伸长相关. 根据牛顿第二定律以及胡 克定律 ( 即弹簧的弹力与拉伸长度成正比 ) 可列出如下微分方程 第五章矩阵特征值计算 与线性方程组的求解问题一样, 矩阵特征值与特征向量的计算也是数值线性代数的重要内容. 在理论上, 矩阵的特征值是特征多项式方程的根, 因此特征值的计算可转化为单个多项式方程的求解. 然而对于高阶矩阵, 这种转化并不能使问题得到简化, 而且在实际应用中还会引入严重的数值误差. 因此, 正如第二章指出的, 我们一般将多项式方程求解转化为矩阵特征值计算问题, 而不是反过来. 本章介绍有关矩阵特征值计算问题的基本理论和算法.

More information

9!!!! #!! : ;!! <! #! # & # (! )! & ( # # #+

9!!!! #!! : ;!! <! #! # & # (! )! & ( # # #+ ! #! &!! # () +( +, + ) + (. ) / 0 1 2 1 3 4 1 2 3 4 1 51 0 6. 6 (78 1 & 9!!!! #!! : ;!! ? &! : < < &? < Α!!&! : Χ / #! : Β??. Δ?. ; ;

More information

Fig1 Theforceappliedtothetrainwhenrunning :w = w j +w q (3) :w = w = w 0 +w j (4) w i 121 基本阻力 w r = 600 R ( N/kN) (8) :R : [2] w s [3] w s =0

Fig1 Theforceappliedtothetrainwhenrunning :w = w j +w q (3) :w = w = w 0 +w j (4) w i 121 基本阻力 w r = 600 R ( N/kN) (8) :R : [2] w s [3] w s =0 31 4 2012 8 JournalofLanzhouJiaotongUniversity Vol31No4 Aug2012 :1001-4373(2012)04-0097-07 * 张友兵 张 波 ( 100073) : 分析了列车运行过程中的受力情况 给出了制动过程中减速度的计算方法 并采用正向 反向两种迭代方式计算列车制动曲线 两种方式计算出的制动曲线一致 证明了计算制动曲线的方法是正确的

More information

! Β Β? Β ( >?? >? %? Γ Β? %? % % %? Χ Η Ιϑ Κ 5 8 Λ 9. Μ Ν Ο Χ? Π Β # % Χ Χ Θ Ρ% Ρ% Θ!??? % < & Θ

! Β Β? Β ( >?? >? %? Γ Β? %? % % %? Χ Η Ιϑ Κ 5 8 Λ 9. Μ Ν Ο Χ? Π Β # % Χ Χ Θ Ρ% Ρ% Θ!??? % < & Θ ! # % & ( ) +,. / 0 1 + 2. 3 4. 56. / 7 89 8.,6 2 ; # ( ( ; ( ( ( # ? >? % > 64 5 5Α5. Α 8/ 56 5 9. > Β 8. / Χ 8 9 9 5 Δ Ε 5, 9 8 2 3 8 //5 5! Α 8/ 56/ 9. Φ ( < % < ( > < ( %! # ! Β Β? Β ( >?? >?

More information

untitled

untitled / ux ( [ x ρ + x ρ ] ρ ux ( ρux ( ρ ρ( x ρ + x ρ 3 u ( δ δ x(, ( (, δ δ + ρ δ (, ρ u( v(, / ( δ + δ δ α δ δ x( α, α (( α,( α δ δ ( α + ( α δ δ (, δ δ ( + ( x(, δ δ x(, ( + δ δ ( + ( v( α, α α α δ δ / δ

More information

WL100014ZW.PDF

WL100014ZW.PDF A Z 1 238 H U 1 92 1 2 3 1 1 1 H H H 235 238 92 U 92 U 1.1 2 1 H 3 1 H 3 2 He 4 2 He 6 3 Hi 7 3 Hi 9 4 Be 10 5 B 2 1.113MeV H 1 4 2 He B/ A =7.075MeV 4 He 238 94 Pu U + +5.6MeV 234 92 2 235 U + 200MeV

More information

= Υ Ξ & 9 = ) %. Ο) Δ Υ Ψ &Ο. 05 3; Ι Ι + 4) &Υ ϑ% Ο ) Χ Υ &! 7) &Ξ) Ζ) 9 [ )!! Τ 9 = Δ Υ Δ Υ Ψ (

= Υ Ξ & 9 = ) %. Ο) Δ Υ Ψ &Ο. 05 3; Ι Ι + 4) &Υ ϑ% Ο ) Χ Υ &! 7) &Ξ) Ζ) 9 [ )!! Τ 9 = Δ Υ Δ Υ Ψ ( ! # %! & (!! ) +, %. ( +/ 0 1 2 3. 4 5 6 78 9 9 +, : % % : < = % ;. % > &? 9! ) Α Β% Χ %/ 3. Δ 8 ( %.. + 2 ( Φ, % Γ Η. 6 Γ Φ, Ι Χ % / Γ 3 ϑκ 2 5 6 Χ8 9 9 Λ % 2 Χ & % ;. % 9 9 Μ3 Ν 1 Μ 3 Φ Λ 3 Φ ) Χ. 0

More information

Α 3 Α 2Η # # > # 8 6 5# Ι + ϑ Κ Ι Ι Ι Η Β Β Β Β Β Β ΔΕ Β Β Γ 8 < Φ Α Α # >, 0 Η Λ Μ Ν Ο Β 8 1 Β Π Θ 1 Π Β 0 Λ Μ 1 Ρ 0 Μ ϑ Σ ϑ Τ Ο Λ 8 ϑ

Α 3 Α 2Η # # > # 8 6 5# Ι + ϑ Κ Ι Ι Ι Η Β Β Β Β Β Β ΔΕ Β Β Γ 8 < Φ Α Α # >, 0 Η Λ Μ Ν Ο Β 8 1 Β Π Θ 1 Π Β 0 Λ Μ 1 Ρ 0 Μ ϑ Σ ϑ Τ Ο Λ 8 ϑ ! # % & ( ) % + ( ), & ). % & /. % 0 1!! 2 3 4 5# 6 7 8 3 5 5 9 # 8 3 3 2 4 # 3 # # 3 # 3 # 3 # 3 # # # ( 3 # # 3 5 # # 8 3 6 # # # # # 8 5# :;< 6#! 6 =! 6 > > 3 2?0 1 4 3 4! 6 Α 3 Α 2Η4 3 3 2 4 # # >

More information

数学分析(I)短课程 [Part 2] 4mm 自然数、整数和有理数

数学分析(I)短课程 [Part 2]   4mm 自然数、整数和有理数 .. 数学分析 (I) 短课程 [Part 2] 自然数 整数和有理数 孙伟 华东师范大学数学系算子代数中心 Week 2 to 18. Fall 2014 孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014 1 / 78 3. 自然数理论初步 孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014

More information

习题一

习题一 . 计算下列二阶行列式 :. 解 :) (-) 5-(-) - b a a b ) log log ) x ( x+ y)( x y) y 4)(t+)(t -t+)-t 习题一 (A).. 解 :) (-)+ (-)+(-) -(-) (-)- -(-) - ) 5 (-)+ 6 +(-) (-) -(-) 5-6 -(-) (-)9 ) b c ac+ ( a) b c+ abc 4) + abc

More information

& & ) ( +( #, # &,! # +., ) # % # # % ( #

& & ) ( +( #, # &,! # +., ) # % # # % ( # ! # % & # (! & & ) ( +( #, # &,! # +., ) # % # # % ( # Ι! # % & ( ) & % / 0 ( # ( 1 2 & 3 # ) 123 #, # #!. + 4 5 6, 7 8 9 : 5 ; < = >?? Α Β Χ Δ : 5 > Ε Φ > Γ > Α Β #! Η % # (, # # #, & # % % %+ ( Ι # %

More information

( ) Wuhan University

( ) Wuhan University Email: huangzh@whueducn, 47 Wuhan Univesity i L A TEX,, : http://affwhueducn/huangzh/ 8 4 49 7 ii : : 4 ; 8 a b c ; a b c 4 4 8 a b c b c a ; c a b x y x + y y x + y x x + y x y 4 + + 8 8 4 4 + 8 + 6 4

More information

4 # = # 4 Γ = 4 0 = 4 = 4 = Η, 6 3 Ι ; 9 Β Δ : 8 9 Χ Χ ϑ 6 Κ Δ ) Χ 8 Λ 6 ;3 Ι 6 Χ Δ : Χ 9 Χ Χ ϑ 6 Κ

4 # = # 4 Γ = 4 0 = 4 = 4 = Η, 6 3 Ι ; 9 Β Δ : 8 9 Χ Χ ϑ 6 Κ Δ ) Χ 8 Λ 6 ;3 Ι 6 Χ Δ : Χ 9 Χ Χ ϑ 6 Κ ! # % & & ( ) +, %. % / 0 / 2 3! # 4 ) 567 68 5 9 9 : ; > >? 3 6 7 : 9 9 7 4! Α = 42 6Β 3 Χ = 42 3 6 3 3 = 42 : 0 3 3 = 42 Δ 3 Β : 0 3 Χ 3 = 42 Χ Β Χ 6 9 = 4 =, ( 9 6 9 75 3 6 7 +. / 9

More information

2003年

2003年 00 年数学考研试卷 - 线性代数部分试卷一 一 填空题 ( 每小题 4 分 ) () 曲面 z x y 与平面 x 4y z 0 平行的切平面的方程是 解 : x 4y z 5 设 ( x0, y0, z 0) 为与平面 x 4y z 0 平行的切平面的切点坐标, 则过 ( x0, y0, z 0) 的法向量为 { x0, y0, } 于是过 ( x0, y0, z 0) 的切平面方程为 x0 (

More information

Π Ρ! #! % & #! (! )! + %!!. / 0% # 0 2 3 3 4 7 8 9 Δ5?? 5 9? Κ :5 5 7 < 7 Δ 7 9 :5? / + 0 5 6 6 7 : ; 7 < = >? : Α8 5 > :9 Β 5 Χ : = 8 + ΑΔ? 9 Β Ε 9 = 9? : ; : Α 5 9 7 3 5 > 5 Δ > Β Χ < :? 3 9? 5 Χ 9 Β

More information

% % %/ + ) &,. ) ) (!

% % %/ + ) &,. ) ) (! ! ( ) + & # % % % %/ + ) &,. ) ) (! 1 2 0 3. 34 0 # & 5 # #% & 6 7 ( ) .)( #. 8!, ) + + < ; & ; & # : 0 9.. 0?. = > /! )( + < 4 +Χ Α # Β 0 Α ) Δ. % ΕΦ 5 1 +. # Ι Κ +,0. Α ϑ. + Ι4 Β Η 5 Γ 1 7 Μ,! 0 1 0

More information

第9章 排队论

第9章  排队论 9, 9. 9.. Nt () [, t] t Nt () { Nt ( ) t [, T]} t< t< t< t + N ( ( t+ ) i+ N( t) i, N( t) i,, N( t) i N + + N ( ( t ) i ( t ) i ) (9-) { Nt ( ) t [, T)} 9- t t + t, t,, t t t { Nt ( ) t [, T] } t< t,,

More information

8 9 : < : 3, 1 4 < 8 3 = >? 4 =?,( 3 4 1( / =? =? : 3, : 4 9 / < 5 3, ; > 8? : 5 4 +? Α > 6 + > 3, > 5 <? 9 5 < =, Β >5

8 9 : < : 3, 1 4 < 8 3 = >? 4 =?,( 3 4 1( / =? =? : 3, : 4 9 / < 5 3, ; > 8? : 5 4 +? Α > 6 + > 3, > 5 <? 9 5 < =, Β >5 0 ( 1 0 % (! # % & ( ) + #,. / / % (! 3 4 5 5 5 3 4,( 7 8 9 /, 9 : 6, 9 5,9 8,9 7 5,9!,9 ; 6 / 9! # %#& 7 8 < 9 & 9 9 : < 5 ( ) 8 9 : < : 3, 1 4 < 8 3 = >? 4 =?,( 3 4 1( / =? =? : 3, : 4 9 / < 5 3, 5 4

More information

9 : : ; 7 % 8

9 : : ; 7 % 8 ! 0 4 1 % # % & ( ) # + #, ( ) + ) ( ). / 2 3 %! 5 6 7! 8 6 7 5 9 9 : 6 7 8 : 17 8 7 8 ; 7 % 8 % 8 ; % % 8 7 > : < % % 7! = = = : = 8 > > ; 7 Ε Β Β % 17 7 :! # # %& & ( ) + %&, %& ) # 8. / 0. 1 2 3 4 5

More information

; < 5 6 => 6 % = 5

; < 5 6 => 6 % = 5 ! # % ( ),,. / 0. 1, ) 2 3, 3+ 3 # 4 + % 5 6 67 5 6, 8 8 5 6 5 6 5 6 5 6 5 6 5 9! 7 9 9 6 : 6 ; 7 7 7 < 5 6 => 6 % = 5 Δ 5 6 ; Β ;? # Ε 6 = 6 Α Ε ; ; ; ; Φ Α Α Ε 0 Α Α Α Α Α Α Α Α Α Α Α Α Α Β Α Α Α Α Α

More information

( ) : ( ) (CIP) /.. :,003. () ISBN O4 44 CIP (00) : : 7 : 7007 : (09 ) : : :850 mm 68 mm / 3 :0.5 :60 :00 0

( ) : ( ) (CIP) /.. :,003. () ISBN O4 44 CIP (00) : : 7 : 7007 : (09 ) :   : :850 mm 68 mm / 3 :0.5 :60 :00 0 ( ) ( ) : ( ) (CIP) /.. :,003. () ISBN 7 56 448 0.... O4 44 CIP (00) 007344 : : 7 : 7007 : (09 )8493844 : www.nwpup.com : :850 mm 68 mm / 3 :0.5 :60 :00 003 3 :0 006 000 :3: 00 00, ( ),,,,,,,, 003 8 (

More information

高等数学A

高等数学A 高等数学 A March 3, 2019 () 高等数学 A March 3, 2019 1 / 55 目录 1 函数 三要素 图像 2 导数 导数的定义 基本导数表 求导公式 Taylor 展开 3 积分 Newton-Leibniz 公式 () 高等数学 A March 3, 2019 2 / 55 函数 y = f(x) 函数三要素 1 定义域 2 值域 3 对应关系 () 高等数学 A March

More information

第12章_下_-随机微分方程与扩散.doc

第12章_下_-随机微分方程与扩散.doc Ω, F, P } B B ω, ω Ω { B ω ω Φ ω Φ Φ Φ ω ω B ω Φ Φ ω B ω [, ] < L < l l J l ω Φ ω B ω B ω Φ ω B ω l J ω l J ω Φ B l J ω l ω J 343 J J ω, ω Ω } { B : B J B ε > l P ω η ω > ε J Φ ω B ω Φ B η ΦB J, ] B B

More information

1 7 10 240 í é é í º 182 230nm A X 240

More information

线性变换的特征值与特征向量 线性变换的特征值与特征向量 本节内容参见蓝以中 特征值与特征向量的计算法 设 V 是数域 K 上的 n 维线性空间,A 是 V 内一个线性变换 我们需要解决下面两个问题 : 决定 K 内所有 A 的特征值 λ 对于属于特征值 λ 的特征子空间 V λ, 找出它的一组基 我

线性变换的特征值与特征向量 线性变换的特征值与特征向量 本节内容参见蓝以中 特征值与特征向量的计算法 设 V 是数域 K 上的 n 维线性空间,A 是 V 内一个线性变换 我们需要解决下面两个问题 : 决定 K 内所有 A 的特征值 λ 对于属于特征值 λ 的特征子空间 V λ, 找出它的一组基 我 矩阵对角化和 标准形 曾焰 版本, 最后修改于 摘要 蓝以中 关于矩阵对角化和 标准形的相关内容的摘要笔记 目录 线性变换的特征值与特征向量 特征值与特征向量的计算法 具有对角形矩阵的线性变换 不变子空间 实对称矩阵的对角化 矩阵的 标准形 幂零线性变换的 标准形 一般线性变换的 标准形 最小多项式 线性变换的特征值与特征向量 线性变换的特征值与特征向量 本节内容参见蓝以中 特征值与特征向量的计算法

More information

.., + +, +, +, +, +, +,! # # % ( % ( / 0!% ( %! %! % # (!) %!%! # (!!# % ) # (!! # )! % +,! ) ) &.. 1. # % 1 ) 2 % 2 1 #% %! ( & # +! %, %. #( # ( 1 (

.., + +, +, +, +, +, +,! # # % ( % ( / 0!% ( %! %! % # (!) %!%! # (!!# % ) # (!! # )! % +,! ) ) &.. 1. # % 1 ) 2 % 2 1 #% %! ( & # +! %, %. #( # ( 1 ( ! # %! % &! # %#!! #! %!% &! # (!! # )! %!! ) &!! +!( ), ( .., + +, +, +, +, +, +,! # # % ( % ( / 0!% ( %! %! % # (!) %!%! # (!!# % ) # (!! # )! % +,! ) ) &.. 1. # % 1 ) 2 % 2 1 #% %! ( & # +! %, %. #(

More information

# % & ) ) & + %,!# & + #. / / & ) 0 / 1! 2

# % & ) ) & + %,!# & + #. / / & ) 0 / 1! 2 !!! #! # % & ) ) & + %,!# & + #. / / & ) 0 / 1! 2 % ) 1 1 3 1 4 5 % #! 2! 1,!!! /+, +!& 2! 2! / # / 6 2 6 3 1 2 4 # / &!/ % ). 1!!! &! & 7 2 7! 7 6 7 3 & 1 2 % # ) / / 8 2 6,!!! /+, +! & 2 9! 3 1!! % %

More information

1. PDE u(x, y, ) PDE F (x, y,, u, u x, u y,, u xx, u xy, ) = 0 (1) F x, y,,uu (solution) u (1) u(x, y, )(1)x, y, Ω (1) x, y, u (1) u Ω x, y, Ωx, y, (P

1. PDE u(x, y, ) PDE F (x, y,, u, u x, u y,, u xx, u xy, ) = 0 (1) F x, y,,uu (solution) u (1) u(x, y, )(1)x, y, Ω (1) x, y, u (1) u Ω x, y, Ωx, y, (P 2008.9-2008.12 Laplace Li-Yau s Harnack inequality Cauchy Cauchy-Kowalevski H. Lewy Open problems F. John, Partial Differential Equations, Springer-Verlag, 1982. 2002 2008 1 1. PDE u(x, y, ) PDE F (x,

More information

: ; # 7 ( 8 7

: ; # 7 ( 8 7 (! # % & ( ) +,. / +. 0 0 ) 1. 2 3 +4 1/,5,6 )/ ) 7 7 8 9 : ; 7 8 7 # 7 ( 8 7 ; ;! #! % & % ( # ) % + # # #, # % + &! #!. #! # # / 0 ( / / 0! #,. # 0(! #,. # 0!. # 0 0 7 7 < = # ; & % ) (, ) ) ) ) ) )!

More information

: 29 : n ( ),,. T, T +,. y ij i =, 2,, n, j =, 2,, T, y ij y ij = β + jβ 2 + α i + ɛ ij i =, 2,, n, j =, 2,, T, (.) β, β 2,. jβ 2,. β, β 2, α i i, ɛ i

: 29 : n ( ),,. T, T +,. y ij i =, 2,, n, j =, 2,, T, y ij y ij = β + jβ 2 + α i + ɛ ij i =, 2,, n, j =, 2,, T, (.) β, β 2,. jβ 2,. β, β 2, α i i, ɛ i 2009 6 Chinese Journal of Applied Probability and Statistics Vol.25 No.3 Jun. 2009 (,, 20024;,, 54004).,,., P,. :,,. : O22... (Credibility Theory) 20 20, 80. ( []).,.,,,.,,,,.,. Buhlmann Buhlmann-Straub

More information