第2章线性代数方程组

第2章线性代数方程组内容摘要：

p计 算 量 : 次  3 on即 :推论 第 2章 线性代数方程组 矩阵分解 其它的三角分解 ,TTA A A L D MMLA L D L 特 别 地 , 当 为 对 称 矩 阵 时 存 在 的 分 解 式则 有 因 此 有 分 解 式 3 6no flo p计 算 量 :  3 on即 :第 2章 线性代数方程组 矩阵分解 对称正定矩阵 , TALD A L D L若 是 对 称 正 定 矩 阵 则 存 在 单 位 下 三 角 矩 阵 和 对 角 元 全 部 为正 数 的 对 角 矩 阵 满 足D由 于 的 对 角 元 全 部 为 正因 此C hole sk y称 为 分 解Cho le sk yG 称 为 三 角 阵12 G LD其 中12 12( , , . . . , )nD d ia g d d d,记TGGTA LDL1122 TLD D L 12 G L D记定理 第 2章 线性代数方程组 矩阵分解 对称正定矩阵 , TA G A G G任 何 对 称 正 定 矩 阵 都 存 在 唯 一 的 下 三 角 阵 满 足1121 2212n n nngggGg g g计 算 公 式 1 kik ip k ppi k g g 当 有1112 1 / 2kk11 g ( )iik ip k ppkkkk k k ppg g i kgg      ikg因 此 , 3 6no fl o p计 算 量 : 次n还 有 次 的 开 平 方 运 算定理 第 2章 线性代数方程组 矩阵分解 带状矩阵的分解 当 矩 阵 中 大 量 元 素 为 零 元 , 非 零 元 只 占 很 小 比 例 的 矩 阵称 为定 义稀 疏 矩 阵( ) , , 0.ijijA n n p qj i q i j pA q p     设 是 阶 方 阵 对 小 于 的 正 整 数 和当 或 时 , 有则 称 是 具 有 上 带 宽 和 下 带 宽 的 带定状 矩 阵义,n A L U A L U A qp L p U q 设 阶 矩 阵 有 分 解 如 果 是 上 下 带 宽 分 别 为和 的 带 状 矩 阵 则 是 带 宽 为 的 下 三 角 阵 是 带 宽 为 的 上 三 角 阵. 以 带 状 矩 阵 为 系 数 矩 阵 的 方 程 组 称 为 带 状 方 程 组定理 第 2章 线性代数方程组 矩阵分解 带状矩阵的分解 1ijm a x{ 1 , , }1m a x{ 1 , , }, , 1 , .. ., m in{ , } 1( ) , 1 , .. ., m in{ , }iij it tjt i p j qik i k i it tjt k p i qiil j i i n i ql l k i n i p               计 算 公 式 222211,26 11,26npq pq p pn p qTnpq qp q qn p q        运 算 量 3,3pqno 当 和 都 不 大 时其 运 算 量 比 小 很 多第 2章 线性代数方程组 矩阵分解 带状矩阵的分解 112 2 23 3 3 1 1 11 nnnnnpqbca b ca b cTa b cab当 时 , 此 时 的 带 状 矩 阵 称 为 三 对 角 阵 T L U由 定 理 知 , 存 在 分 解 第 2章 线性代数方程组 矩阵分解 带状矩阵的分解 112 2 23111111nnnnrlrL l Url                        其 中 1 1 1 111, , , . 2 , 3 , .. .,kk k k k k k kkb r cl b l r r c k n    因 此 得 到 计 算 公 式第 2章 线性代数方程组 矩阵分解 带状矩阵的分解  12, , . . . , TnT x dd d d d 求 解 三 对 角 方 程 组 其 中 111 , 2 , 3 , .. .,k k k kxyydy d l y k n   得 到 计 算 和 的 公 式,T L U L y d U x y  由 可 知 将 原 方 程 分 解 为 两 个 方 程 组 1/ 1( ) , 1 , 2 , .. ., 2 , 1n n nk k k kkxyx y r x k n n      追 的 过 程赶 的 过 程以 上 解 法 称 为 追 赶 法第 2章 线性代数方程组 矩阵分解 矩阵分解的应用 Ax b(1) 求 解 方 程 组 的 解1111, , 2 , 3 , .. .,kk k k j jjxyyy l y k n  得 到 计 算 的 公 式1/ / , 1 , 2 , .. ., 2 , 1n n nnnk k ik i k kikx y ux y l x u k n n      , Ly bA LU U x y 若 对 进 行 分 解 则 原 方 程 等 价 于 2()on时 间 复 杂 度2()on时 间 复 杂 度第 2章 线性代数方程组 矩阵分解 矩阵分解的应用 (2) 求 矩 阵 行 列 式1 1 2 2 d e t( ) d e t( ) nnAu   从 而A L U若 对 进 行 分 解, A LU有de t ( ) de t ( ) de t ( )A L U,则时间复杂度)( 3noLU 分解的时间复杂度为 )()d e t ( nou 的时间复杂度为)( 3no， 总的时间复杂度为因此第 2章 线性代数方程组 矩阵分解 矩阵分解的应用 (3) 求 矩 阵 的 逆TA LD UA LD L对 称 矩 阵 进 行 分 解 有 1 1 1TA L D L    1 1 1 112( , , ..., )nD diag d d d    , , 1 , 2 , ...,kkL S I L s e k n   有 知kLs 为 单 位 下 三 角 阵 , 是 其 逆 也 为 单 位 下 三 角 阵 , 记 为 S, 并 以 记 各 列 1 1. , ,TTL S L S A  由 追 赶 法 可 解 出 并 由 可 求 出第 2章 线性代数方程组 矩阵分解 矩阵分解的应用 (4) 求 解 成 组 方 程 组 ( 1 , .. ., , 1 )kA x B k m m  若 有 一 系 列 方 程 组 ,A L U A L U若 存 在 分 解 kkAx B L Ux B  (1) 对 矩 阵 A 进 行 LU 分 解。 计 算 过 程 : kLy BU x y  kkB L y B(2) 对 每 一 个 , 求 解 方 程 组U x y(3) 求 解 方 程 组。 同 时 , 以 上 方 法 也 用 于 方 程 组 的 迭 代 改 善 技 术第 2章 线性代数方程组 矩阵分解 小 结 ,A L U L UL U D o o lit tle 其 中 为 单 位 下 三 角 阵 为 上 三 角 阵 称 为 分 解 三 角 分 解 分 解 , ,A LD U L D ULD U 其 中 为 单 位 下 三 角 阵 为 对 角 阵 为 单 位 上 三 角 阵 称 为 分 解  TA G G GC h o le s k y 其 中 为 下 三 角 阵 称 为 分 解 带 状 矩 阵 分 解 追 赶 法: A条 件 是 对 称 正 定 阵第 2章 线性代数方程组 线性方程组解的可靠性 残向量 为 了 检 验 方 程 组 的 计 算 解 的 误 差 , 可 以 将 计 算 解 代 入 方 程 组 中 r b A x计 算 以 此 来 评残 向 量 价 解 的 误 差122. 00 0 3. 00 0 0. 49 9 1. 00 1 1. 50 0xx         例 线 性 方 程 组* (1 , 1 ) Tx 准 确 解 为 ( 00 , 00) Tx 若 求 出 的 计 算 解 为 ( 00 , 015 ) Tr 则 残 向 量 * 1 2 . 0 1 ,1 0 . 5 0 . 5e x x                   但 误 差 向 量 并 不 是 一 个 很 小 的 量会相差很大计算解与准确解之间仍残向量很小时 ，第 2章 线性代数方程组 线性方程组解的可靠性 * * * * *12( , , , ) ,TnA x b x x x x A x b  设 方 程 组 的 精 确 解 为 即12( , , , ) Tnx x x x计 算 解 为*e x x定 义 e称 为 误 差 向 量12n*11*22*nnxxxxxx 误差向量和范数 用 来 评 价 计 算 解 的 精 确 度第 2章 线性代数方程组 线性方程组解的可靠性 误差向量和范数 0( ) 0 0 0xxx x xxx    绝 对 值 函定 数当 当当义 ( 1 ) 0 , 0 0 ( 2) , ( 3 ) x x xxxx y x y      具 有 性 质 : 并 且 当 且 仅 当 时 , 有 对 任 意 实 数 有 非 负 性齐 次 性三 角 不 等 式第 2章 线性代数方程组 线性方程组解的可靠性 误差向量和范数 1212 ( , , .. ., ) ,( ) ( , , .. ., )(, )Tnnxx x x xx x x xxx对 向 量 具 有 如 下 类 似 性 质 的 函 数 称 为 记 为定 义向 量 的 范 数 或 模 或 长 度( 1 ) , 0 , 0nx R x x x     性 质 : 有 且 的 充 要。