第六章 逐次逼近法 第六章 逐次逼近法 6.1 基本概念§ 6.2 线性方程组的迭代法§ 6.3 非线性方程组的迭代法§ 6.4 矩阵特征值问题的数值算法§ 6.5 迭代法的加速§ 本章要点 本章主要介绍线性方程组的迭代法 、 非线性方程组 的数值方法 主要方法 基本迭代法 、 G-J迭代法 、 G-S迭代法 、 Newton迭代法 、 SOR方法和 Aitken加速方法 6.1 基本概念§ "范数 "是对向量和矩阵的一种度量 ,实际上是二维 和三维向量长度概念的一种推广 数域 : 数的集合 ,对加法和乘法封闭 线性空间 : 可简化为向量的集合 ,对向量的加法和 数量乘法封闭 , 二维向量和三维向量都可以度量其大小和长度 高维向量的 "长度 "能否定义呢 ? 也称为向量空间 定义 1. ,xRn n中任意一个向量维向量空间对于 一 、 向量和矩阵的范数 对应 ， 且满足与若存在唯一一个实数 xRx ∈ ;00,,0)()1( =?=∈?≥ xxRxx n且正定性 ;,)()2( RRxxx n ∈∈??= aaa ，齐次性 .,)()3( nRyxyxyx ∈?+≤+ ，三角不等式 .的范数为向量则称 xx 定义中的向量范数可以类似对于复线性空间 nC T n nn xxxxCR ),,,(,)( 21 L=设中在向量空间 的范数有常用的向量 x 2x 2122 2 2 1 )( nxxx +++= L 范数或欧氏范数的 ?2x 1x nxxx +++= L21 范数的 ?1x ∞x ini x≤≤= 1max 范数或最大范数的 ?∞x --------(1) --------(2) --------(3) px pp n pp xxx 1 21 )( +++= L 1, ≥? ppx 范数的 2x和1x显然 时的特例和在是 21 == ppx p 并且由于 pp n pp xxx 1 21 )( +++ L≤≤≤ ini x1max pp ini xn 1 1 )max( ≤≤ ≤ ini p xn ≤≤ = 1 1 max )(max 1 ∞→→ ≤≤ pxi ni ∞x所以 的特例也是 px --------(4) ),( 时∞→→ ∞ pxx p 12 xxx ≤≤∞且 例 1.求下列向量的各种常用范数 Tx )1,3,4,1( ?= 解 : 1x 421 xxx +++= L 9= 2x 21242221 )( xxx +++= L 3327 == ∞x ii x41max≤≤= 4= 定义 2. ,AR nn 中任意一个矩阵对于空间 × 对应 ， 且满足与若存在唯一一个实数 ARA ∈ ;00,,0)()1( =?=∈?≥ × AARAA nn且正定性 ;,)()2( RRAAA nn ∈∈??= × aaa ，齐次性 .,)()3( nnRBABABA ×∈?+≤+ ，三角不等式 .的范数为矩阵则称 AA 定义中的矩阵范数可以类似对于复空间 nnC × .,)4( nnRBABAAB ×∈??≤ ， 例 2. nnijaAn ×= )(阶方阵设 21 1 1 2 ?? ? ? ??? ?= ∑∑ = = n i n j ijF aA设 不难验证其满足定义 2的 4个条件 是一种矩阵范数因此 FA 称为 Frobenius范数 ,简称 F-范数 ( ) ( ) 2121 )()( TTF AAtrAAtrA ==而且可以验证 tr为矩阵的迹 --------(5) --------(6) 类似向量的 2-范数 为一种向量范数设 u?∈∈ × ,, nnn RARx 令有最大值对所有的则 ,0≠xxAx u u ?? ??? ?? ???= ≠ u u u x AxA x 0 max 个条件的满足定义可以验证 42uA 定义 3. --------(7) 的矩阵范数范数 称为从属于给定向量式确定的由 u u x A)7( 简称为从属范数或算子范数 uuu xAAx ≤ 显然 ， 由定义不难推出 定义 4. ,mu ?? 和矩阵范数对于给定的向量范数 都有若 ,, nnn RARx ×∈∈? umu xAAx ≤ .相容和矩阵范数则称所给的向量范数 mu ?? 由 (8)式 ,可知 算子范数和其对应的向量范数是相容的 --------(8) --------(9) 根据向量的常用范数可以得到常用的矩阵算子范数 ??????= ≠ 1 1 01 max)1( xAxA x ∑=≤≤ = n i ijnj a 11 max ,大值的每列绝对值之和的最A 的列范数称 A ??????= ∞ ∞ ≠∞ x AxA x 0 max)2( ∑ =≤≤ = n j ijni a 11 max ,大值的每行绝对值之和的最A 的行范数称 A ??????= ≠ 2 2 02 max)3( xAxA x )(max AA Tl= 大值的特征值的绝对值的最为 AAAA TT )(maxl 范数 的称 ?2 A --------(10) --------(11) --------(12) 例 3. 21 1 1 2 ?? ? ? ??? ?= ∑∑ = = n i n j ijF aA 是不是算子范数范数的判别矩阵 FAFrobeniusA 解 : 范数为的 ?FA 类似于向量的 2-范数 的算子范数并不是从属于但 2xA F I考虑单位矩阵 FI n= ??????= ≠ u u u x IxI x 0 max ??????= ≠ u u xx x 0 max 1= 的矩阵范数数是不从属于任意向量范因此 u?FA 数并不完全是一回事故而矩阵范数和算子范 不过 222 xAAx ≤ 21 1 2 ?? ? ? ??? ?= ∑∑ = = n i n j ijF aA ( ) ( ) 2 121 )()( TT AAtrAAtr == 2A )(max AA Tl= 2xA F≤ FA≤ 相容与因此 2xA F 例 4. 求矩阵 A的各种常用范数 ?? ? ? ? ?? ? ? ? ??= 110 121 021 A 解 : 1A ∑ =≤≤ = n i ijnj a 11 max 2 5 2 3 4 2 5}2,5,2{max 1 == ≤≤ nj ∞A ∑ =≤≤ = n j ijni a 11 max 4}2,4,3{max 1 == ≤≤ ni 2A )(max AA Tl=由于 的特征值因此先求 AAT AAT ??? ? ? ?? ? ? ? ??? 110 121 021 ?? ? ? ? ?? ? ? ? ? ? = 110 122 011 ?? ? ? ? ?? ? ? ? ? ?= 211 190 102 特征方程为 )det( AAI T?l ??? ? ? ?? ? ? ? ?? ? ?? = 211 190 102 l l l 0= 的特征值为可得 AAT 9361.0,9211.2,1428.9 321 === lll 1428.9)(max =AATl 2A )(max AA Tl= 0237.3= FA )( AAtr T= 292 ++= 6056.3= 1A ∞A 2A FA 容易计算 计算较复杂 对矩阵元素的 变化比较敏感 不是从属范数 较少使用 使用最广泛 性质较好 定义 5. 称的特征值为设 ,,,, 21 nnnRA lll L×∈ },,,max{)( 21 nA lllr L= 的谱半径为矩阵 A ,uu Ax 和算子范数对于某种向量范数 uuu xAAx ≤ uu lxAx = ul x?=而 因此 ul x? uu xA≤ --------(13) 显然 2A )(max AATl= )( AATr= ul A≤ ur AA ≤)( 任何一种算子范数的谱半径不超过矩阵的即矩阵 A 即 所以 定理 1. ,, nnnn RBR ×× ∈? 上的一种算子范数是设 且非奇异则满足若 ,,1 BIBB +< BBI ?<+ ? 1 1)( 1 --------(14) 证明略 )(1,1 ,,,, 1 1 摄动定理可逆 ， 且则且 且可逆推论 ： 设 ab aab ba ?≤< ≤?∈≤∈ ? ×?× CC CARCARA nnnn 定义 6. ."". "","", , , 的良态否则称为阵 矩病态为的病态则称该方程组是巨大变化 就会引起方程组解的的元素的微小变化常数项 或如果系数矩阵对于线性方程组 A b AbAx = 二 、 误差分析简介 响的扰动对方程组解的影常数项 b.1 为其精确解为非奇异矩阵为一线性方程组设 xAbAx ,,= xbb dd 则解也应存在误差存在误差若常数项 , 即有 bbxxA dd +=+ )( --------(15) bxA dd = bAx dd 1?= bAx dd 1?= bA d?≤ ?1 Axb = xA ?≤ b A x ≤ 1 b bAA x x dd ??≤ ?1 --------(16) --------(17) --------(18) 所以 又因为 可得 (16)和 (17)两式相乘 ,得 相对误差 (18)式表明 ,由常数项产生的误差 ,最多可将解的 相对误差放大 倍1?? AA 响的扰动对方程组解的影系数矩阵 A.2 bxxAA =++ ))(( dd xAA dd 则解也应存在误差存在误差若系数矩阵 , 0=?++? xAxAxA dddd xAxAA ??=+ ddd )( 在上式能直接使用范数吗 ？ --------(19) )()( 1 AAIAAA dd ?+=+ 11 <? AA d如果假设 则由定理 1.,可知 非奇异AAI d1?+ AAAAI dd 1 11 1 1)( ? ?? ?≤+且 (19)式化为 xAxAAIA ??=+ ? ddd )( 1 xAAAAIx ?+?= ??? ddd 111 )( --------(20) --------(21) xAAAAIx ???+≤ ??? ddd 111 )( AA AA x x d dd 1 1 1 ? ? ? ?≤ AA AA d d ?? ?≤ ? ? 1 1 1 A AAA A AAA d d ??? ?? = ? ? 1 1 1 --------(22) 定义 7. 称为非奇异矩阵设 ,A ., 为某种算子范数其中的条件数为 ?A 1)( ??= AAAcond --------(23) 显然 1)( ??= AAAcond 1?≥ AA I= 1= 即任意方阵的条件数必不小于 1 根据算子范数的不同也有不同的条件数 : 1 1 11)( ??= AAAcond ∞ ? ∞∞ ?= 1)( AAAcond 2 1 22)( ??= AAAcond )( 1)( min max AAAA T T ll= )( )( min max AA AA T T l l= b bAcond x x dd )(≤ --------(18) x xd A AAcond A AAcond d d )(1 )( ? ≤ --------(22) 根据定义 7的定义 ,(18)式和 (22)式可表示为 A AAcond d)(≈ )1( 时<< A Ad -----(24) 倍放大倍数不超过 误差的扰动引起的解的相对和常数项由系数矩阵 )(Acond bA 解的影响的指标是刻划原始数据变化对即条件数 )(Acond 大解的相对误差也可能越越大一般 ,)(Acond 方程组病态就可能是很大时因此 "",)( bAxAcond = 矩阵病态就可能是而 ""A 实验 : Hilbert矩阵和病态方程组