第四章解线性方程组的迭代法 /R Iterative Techniques for Solving Linear Systems */ G求解Ax=b 思与解∫(x)=0的不动点迭代相似,将Ax=b等价 路改写为x=Bx+f形式,建立迭代x=Bx6+f。 从初值x出发,得到序列{x()} 计算精度可控,特别适用于求解系数为大型稀疏 矩阵/ sparse matrices*的方程组。 研究内容: a如何建立迭代格式? 收敛速度? 向量序列的收敛条件? 误差估计
第四章 解线性方程组的迭代法 /* Iterative Techniques for Solving Linear Systems */ 求解 Ax b = 思 路 与解 f (x)=0 的不动点迭代相似 ……，将 Ax b 等价 = 改写为 形式，建立迭代 。 从初值 出发，得到序列 。 x B x f = + x B x f k k = + ( +1) ( ) (0) x { } (k ) x 计算精度可控，特别适用于求解系数为大型稀疏 矩阵 /* sparse matrices */ 的方程组。 研究 内容： 如何建立迭代格式？ 收敛速度？ 向量序列的收敛条件？ 误差估计？
s1向量和矩阵范数/ Norms of vectors and matrices 为了误差的度量 >向量范数/ vector norms 定义R空间的向量范数‖·对任意xp蒲足下列条件: (1)‖x‖≥0;‖x‖=0x=0(正定性/ positive definite+/) (2)|axl‖l=al‖x‖对任意aeC(齐次性/ homogeneous+) (3)‖x+y‖s‖‖+‖(三角不等式/ triangle inequality 纔常用向量范数: H=∑|x :=1EIx ILIlp-2Ix, P'f =1 maxx 注:lim‖x,=‖xl I≤iSn
§1 向量和矩阵范数 /* Norms of Vectors and Matrices */ —— 为了误差的度量 ➢ 向量范数 /* vector norms */ 定义 Rn空间的向量范数 || · || 对任意 满足下列条件： n x y R , (1) || || 0 ; || || 0 0 x x = x = （正定性 /* positive definite */ ) (2) || x || | | || x || = 对任意 C (齐次性 /* homogeneous */ ) (3) || x y || || x || || y || + + （三角不等式 /* triangle inequality */ ) 常用向量范数： = = n i x xi 1 1 || || | | = = n i i x x 1 2 2 || || | | p n i p x p x i 1 / 1 || || = | | = || || max | | 1 i i n x x = 注： → lim || x || = || x || p p
81 Norms of Vectors and Matrices-Vector Norms 定义向量序列{x收敛于向量x是指对每一个1≤im都 有imx)=x1。可以理解为‖()-x|→>0 k→)oo 定义若存在常数C>0使得对任意∈R"有XC1,则 称范数‖·|4比范数‖·lg强。 定义若范数‖·4比:强,同时、电比·|强,即 存在常数C1、C2>0使得‖xeS≤C ,则称 ‖·4和·|g等价。 定理c上-切范数都价同田m
§1 Norms of Vectors and Matrices – Vector Norms 定义 向量序列 收敛于向量 是指对每一个 1 i n 都 有 。 { } (k ) x x* ( ) * lim i k i k x = x → 可以理解为 || *|| 0 x (k ) − x → 定义 若存在常数C > 0 使得对任意 有 , 则 称范数 || · ||A 比范数 || · ||B 强。 n x R A B || x || C || x || 定义 若范数 || · ||A 比|| · ||B 强，同时|| · ||B 也比|| · ||A 强，即 存在常数 C1、C2 > 0 使得 ，则称 || · ||A 和|| · ||B 等价。 B A B C || x || || x || C || x || 1 2 定理 Rn 上一切范数都等价。 可以理解为对任何 向量范数都成立。 HW: p.62 #6, #7
81 Norms of Vectors and Matrices-Matrix Norms >矩阵范数/ matrix norms 定义Rm空间的矩阵范数‖·对任意A,B∈满足: (1)‖A‖0;‖A=0分A=0(正定性/ positive definite*) (2)|aA‖=|al·A对任意aEC(齐次性/ homogeneous+) (3)‖4+BsA+‖B‖(三角不等式/ triangle inequality) (4)‖AB|S‖A‖·‖B‖(相容/ consistent!当m=n时) When you have to analyze the error bound of AB- imagine you doing it without a consistent matrix norm
§1 Norms of Vectors and Matrices – Matrix Norms ➢ 矩阵范数 /* matrix norms */ 定义 Rmn空间的矩阵范数 || · || 对任意 满足： m n A B R , (1) || A|| 0 ; || A|| = 0 A = 0 （正定性 /* positive definite */ ) (2) || A|| = | | || A|| 对任意 C (齐次性 /* homogeneous */ ) (3) || A+ B || || A|| + || B || （三角不等式 /* triangle inequality */ ) (4)* || AB || || A || · || B || （相容 /* consistent */ 当 m = n 时) In general, if we have || AB || || A || · || B || , then the 3 norms are said to be consistent. Oh haven’t I had enough of new concepts? What do I need the consistency for? When you have to analyze the error bound of AB – imagine you doing it without a consistent matrix norm…
81 Norms of Vectors and Matrices-Matrix Norms 常用矩阵范数: Frobenius范数‖A| ∑ ∑|an2一向量l的直接推广 对方阵A∈R以及x∈R"有‖A2Apxl2 算子范数 /*operator norm 由向量范数|·导出关于魈岬不等武数: xy≤‖!x‖ 则 可证。 ll Ax I A=max AB,Bll ‖I矩阵A4的最大V|4|l| 特征根/ eigenvalue 特别有:‖A|=mx 双) HW:p62A=max2为1(列和范数) #2,#4,#5 V/max (4A)(谱范数/ spectral norη)
§1 Norms of Vectors and Matrices – Matrix Norms 常用矩阵范数： Frobenius 范数 = = = n i n j A F aij 1 1 2 || || | | — 向量|| · ||2的直接推广 对方阵 A R nn 以及 x R n 有 2 2 || Ax || || A|| || x || F 利用Cauchy 不等式 | x y | || x ||2 || y ||2 可证。 算子范数 /* operator norm */ 由向量范数 || · ||p 导出关于矩阵 A Rnn 的 p 范数: p x p p p Ax x Ax A p x max || || || || || || || || max 0 | | | | 1 = = = 则 p p p p p p Ax A x AB A B || || || || || || || || || || || || 特别有： = = n j A aij i n 1 || || max | | 1 （行和范数） = = n i A aij j n 1 1 || || max | | 1 （列和范数） || || ( ) A 2 max A A T = （谱范数 /* spectral norm */ ） 矩阵 ATA 的最大 特征根 /* eigenvalue */ HW: p.62 #2, #4, #5