第四章解线性方程组的迭代法 /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
81 Norms of Vectors and Matrices-Matrix Norms 注: Frobenius范数不是算子范数。 矿我们只关心有相军性的范数,算子范数总是相容的。 矿即使A中元素全为数,其特征根和相应特征向量 * eigenvector*仍可自(数。将上述定义中绝对值换 成复数模均成立。 >谱半径 T' spectral radius 卜范数 n=‖TF≠maxp(4) 定义短啡谱半径记为 成 R (4)=max|x1,其中为 A的特征根
§1 Norms of Vectors and Matrices – Matrix Norms 注： Frobenius 范数不是算子范数。 我们只关心有相容性的范数，算子范数总是相容的。 即使 A中元素全为实数，其特征根和相应特征向量 /* eigenvector */ 仍可能是复数。将上述定义中绝对值换 成复数模均成立。 若不然，则必存在某个向量范数 || · ||v 使得 对任意A 成立。 v v F x Ax A x || || || || || || max 0 = Counterexample ? 1 || || || || || || max 0 = = v v F x I x n I x ➢ 谱半径 /* spectral radius */ 定义 矩阵A的谱半径记为 (A) = ，其中i 为 A 的特征根。 max | | 1 i i n Re Im (A)
8 1 Norms of Vectors and Matrices- Spectral radius 定理|对任意算子范数|:|有风(451A41 证明:由算子范数的相容性,得到‖A‖≤‖A‖·‖c‖ 将任意一个特征根λ所对应的特征向量代入 All=|man=|sAl:|l■ 定理若称,则有AlP A对称 证明:‖A2=m(4A=√不m(4 若是A的一个特征相则a必是A2的特征根 →am(42)=x(4)个A的特征根成立 又:对称矩阵的 激即22(4)为非负实数, 所以2范数亦称为 故得证。 谱范数
§1 Norms of Vectors and Matrices – Spectral Radius 定理 对任意算子范数 || · || 有 (A) || A|| 证明：由算子范数的相容性，得到 || Ax || || A|| || x || 将任意一个特征根 所对应的特征向量 u 代入 || Au || || A|| || u || | | || u || = || u || = 定理 若A对称，则有 || || ( ) A 2 = A 证明： || || ( ) ( ) 2 A 2 max A A max A T = = A对称 若 是 A 的一个特征根，则 2 必是 A2 的特征根。 又：对称矩阵的特征根为实数，即 2 (A) 为非负实数， 故得证。 ( ) ( ) 2 2 max A = A 对某个 A 的特征根 成立 所以2-范数亦称为 谱范数
8 1 Norms of Vectors and Matrices- Spectral radius 定理若矩阵B对某个算子范数满足<D,则必有 ①+B可逆;②N+6)1-B 证明:⑨着不然,则(±B)x=0有非零解,即存在非零向 量x使得±Bn=-‖多(NB≥n√ ②(±B)±B(Ⅰ±B)=(I±B)(I±B)=I →(I±B)=ⅠB(I±B) →‖(I±B)‖≤1+‖B‖‖(Ⅰ±B)
§1 Norms of Vectors and Matrices – Spectral Radius 定理 若矩阵 B 对某个算子范数满足 ||B|| < 1，则必有 ① I B 可逆； ② ( ) 1 || || 1 1 B I B − − 证明：① 若不然，则 有非零解，即存在非零向 量 使得 ( ) 0 I B x = 0 x 0 0 Bx x = − 1 || || || || 0 0 = x Bx || B || 1 ✓ ② I B I B = I −1 = ( )( ) −1 −1 (I B) B(I B) 1 1 ( ) ( ) − − I B = I B I B || ( ) || 1 || || || ( ) || −1 −1 I B + B I B