（计算数学专业论文）几类特殊矩阵的新算法和性质.pdf

几类特殊矩阵的新算法和性质 摘要 本文给出了关于分块三对角矩阵、 分块五对角矩阵及分块周期三对角矩阵求 解线性万程组及逆矩阵的新算法。这类矩阵的研究有着活跃的探究， 这由于此类 矩阵经常出现在计算数学和数理统计等领域中， 再者他们有着许多重要的显著的 特征。此外，本文给出了广义 p a s c a l 矩阵的性质。 本文的内容安排如下: 第一章给出了问题的应用背景及相关的定义与结论。 第二章给出了 求解以分块三 对角矩阵、 分块五对角 矩阵为系数矩阵的 线性方 程组的新算法 变参数追赶法，并通过算 例将新算法与著名的追赶法作了比 较。 第三章根据带状矩阵求逆 矩阵的 有关结论， 推导了求分块三对角矩阵、 分块 五对角矩阵及分块周期三对角矩阵的逆矩阵的快速算法，并给出了数值算例。 第四章运用递推的方法导出了求分块三对角矩阵、 分块五对角矩阵及分块周 期三对角矩阵的逆矩阵的决速算法，给出了相应的数值算例。 第五章研究了广义 p a s c a l 矩阵的性质。 关键词:分块三对角矩阵:分块五对角矩阵;分块周期三对角矩阵:带状矩 阵;逆矩阵:p a s c a l 矩阵 n e w a l g o r i t h m s a n d p r o p e r t i e s f o r s o me s p e c i a l m a t r i c e s abs t r a c t t h is p a p e r p r e s e n t s n e w a l g o r i th m s f o r s o lv i n g l in e a r e q u a ti o n s a n d in v e r s e c o n c e rn in g b l o c k t r i d i a g o n a l m a t r i x ， b lo c k p e n t a d i a g o n a l m a tr ix a n d b l o c k p e r io d t r id ia g o n a l m a t r ix . t h e s t u d y o f t h e s e m a t r i c e s h a s b e e n a n a c t i v e f i e l d o f r e s e a r c h . t h e f i r s t r e a s o n f o r t h i s c i r c u ms t a n c e i s t h e f a c t th a t s u c h m a t r ic e s o c c u r in a l a rg e v a r i e ty o f a r e a s in c o m p u ta t i o n a l ma t h e ma t i c s a n d ma t h e ma t i c a l s t a t i s t i c s e t c . t h e s e c o n d r e a s o n i s t h a t th e y h a v e a l o t o f s i g n if i c a n t c h a r a c t e r is t ic p r o p e r t ie s . a l s o , n e w p r o p e r t i e s o f g e n e r a l p a s c a l m a t r i c e s a r e g i v e n . t h e o r g a n i z a t i o n o f t h e p a p e r i s a s f o l l o w s . i n c h a p t e r l , d e l in e a t io n s a n d a p p l ic a ti o n o f s o m e s p e c i a l m a t r ic e s a r e d e s c r i b e d a n d t h e w e l l k n o w n t h o m a s a l g o r i t h ms a r e i n t r o d u c e d . i n c h a p te r 2 , v a r ia b le p a r a m e te r t h o m a s a lg o r it h m s o f s o l v i n g l in e a r s y s t e m s , w h ic h c o e ff ic ie n t m a t r ic e s a r e b l o c k t r id i a g o n a l m a t r ix a n d b l o c k p e n t a d i a g o n a l m a t r i x , a r e g i v e n. f u r th e r w e c o m p a r e t h e n e w a lg o r it h m s w i t h t h o m a s a lg o r it h m s b y n u m e r i c a l e x a m p l e s . i n c h a p t e r 3 , a c c o r d in g t o th e r e la t e d r e s u lt s o f th e b a n d m a t r i x , w e d e r i v e th e n e w a l g o r it h m s f o r i n v e r t in g b lo c k t r i d ia g o n a l m a t r ic e s ， b lo c k p e n t a d i a g o n a l m a t r i c e s a n d b l o c k p e r i o d t r i d i a g o n a l m a t r i x . a t t h e s a me t i m e w e g i v e n u me r i c a l e x a m p l e s . i n c h a p t e r 4 , n e w a l g o r it h m s fo r in v e r t in g b l o c k tr id ia g o n a l m a t r i c e s， b lo c k p e n t a d ia g o n a l m a tr ic e s a n d b lo c k p e r io d t r id ia g o n a l m a t r i c e s a r e d e r iv e d a c c o r d i n g t o th e r e c u rr e n c e m e t h o d s . l a s t w e g i v e n u m e r i c a l e x a m p l e s . i n c h a p t e r 5 , n e w p r o p e r t ie s o f g e n e r a l p a s c a l m a tr i c e s a r e o b t a i n e d . k e y w o r d s : b lo c k t r id ia g o n a l m a t r ix ; b l o c k p e n t a d ia g o n a l b lo c k p e r i o d tr i d ia g o n a l m a t r i x ; b a n d m a t r ix ; i n v e r s e m a tr ix ; m a t r ix ma t r i x ; pa s c a l 第一章绪论 1 . 1引 言 一、研究特殊矩阵计算的意义 特殊矩阵是计算数学的重要组成部分。 它是 研究 代数问 题的特殊矩阵快速算 法及有关理论的 一门学科， 它既 涉及数学理论方面的研究， 又涉及工程设计方面 的研究。随着科学技术的发展和计算机的普及， 矩阵理论和方法得到了越来越广 泛的应用。在近代数学、工程技术、经济理论及管理科学中，大量地涉及到矩阵 的理论， 特别是一些特殊矩阵( 具有特殊性质和特殊结构的矩阵) ，相应的计算规 模也越来越大。 近十几年来，国防科技和国民经济建设的许多领域中就不断提出 了大型或超大型科学计算问题。 由于矩阵在各个学术领域和重要应用课题中所起 的不可替代的作用，故有必要对其进行细致的研究。 科学技术和工程应用中需 要进行大量的矩阵计算， 而这些矩阵自 身往往具备 一些 特殊的结构及特殊的 性质， 这即是 所谓的 特殊矩阵。由 于特殊矩阵在数值分 析、 优化理论、自 动控制、 数字 信号处理、系 统辨识、 工程计算等领域中有重要 而 广泛的应用， 所以对特殊矩阵的研究一直是被关注的热点。 为提高 特殊矩阵的 运算效率， 通过运用特殊矩阵的特殊结构及性质， 使得有关计算问题降低一个数 量级， 研究特殊矩阵的快速算法及性质， 这是具有 一 重要的理论意义和现实意义的 研究课题。 在美国的 l i n e a r a l g e b r a a n d i t s a p p l i c a t i o n s ) , ( s i a m m a t r i x a n a l y s i s a n d i t s a p p l i c a t i o n s ) , ( m a t h e m a t i c c o m p u t a t i o n ) ) ,德国的 n u m e r . m a t h 和国内的 计算数学 、 数值计算与计算机应用 、 高等学校计算数学学 报 、 高校应用数学学报 、 数学的实践与认识等期刊上，已发表了为数众多 的相关论文。 分块三( 五) 对角矩阵及分块周期三对角矩阵是人们在实际问题中经常遇到 的矩阵， 例如在用差分方法求解常微分方程与偏微分方程的边值问题、 船体数学 放样中建立的二次样条插值函数的求解、 线性规划、网络分析、结构分析等问题 中， 经常需要求解以对角占优的分块三( 五) 对角矩阵及分块周期三对角矩阵为系 数矩阵的线性方程组， 且阶数一般较高。 从而研究这类矩阵的有关计算问题的快 速算法，如求解相应的线性方程组和求逆矩阵等，具有实际的意义。 p a s c a l三角形也叫杨辉三角形，它在组合数学、概率论、数论、代数、微 分方程等许多领域有着厂泛的应用;同时 p a s c a l 三角形中隐含着二项式系数的 许多相关性质。 从而对于山p a s c a l 三角形产生的 p a s c a l 矩阵的研究具有理论意 义和实际意义。 本文将对这些问题进行系统的研究。 二、有关求解特殊矩阵方程组及其逆的历史和研究现状 求解以分块三( 五) 对角矩阵和分块周期三对角矩阵为系数矩阵的大型线性 方程组最经典的方法是追赶法。 它是利用分块 三( 五) 对 一 角矩阵的l u 分解的 特殊 形式而得到的一种快速算法。由于这里的 l ( 0只有对角线及对角线下 ( 上) 两排 有非零元素，从而形成了一追一赶的过程。在 1 9 9 4年王纪林，周钢给出了把较 大方程组化为较小方程组的初参数方法， 并将三对角方程组作为特例给出了相应 的算法 a 7 。 继而在1 9 9 7 年， 周钢，胡芬 兰， 王纪林给出了 复系数线性带 状方程 第一章绪论 1 . 1引 言 一、研究特殊矩阵计算的意义 特殊矩阵是计算数学的重要组成部分。 它是 研究 代数问 题的特殊矩阵快速算 法及有关理论的 一门学科， 它既 涉及数学理论方面的研究， 又涉及工程设计方面 的研究。随着科学技术的发展和计算机的普及， 矩阵理论和方法得到了越来越广 泛的应用。在近代数学、工程技术、经济理论及管理科学中，大量地涉及到矩阵 的理论， 特别是一些特殊矩阵( 具有特殊性质和特殊结构的矩阵) ，相应的计算规 模也越来越大。 近十几年来，国防科技和国民经济建设的许多领域中就不断提出 了大型或超大型科学计算问题。 由于矩阵在各个学术领域和重要应用课题中所起 的不可替代的作用，故有必要对其进行细致的研究。 科学技术和工程应用中需 要进行大量的矩阵计算， 而这些矩阵自 身往往具备 一些 特殊的结构及特殊的 性质， 这即是 所谓的 特殊矩阵。由 于特殊矩阵在数值分 析、 优化理论、自 动控制、 数字 信号处理、系 统辨识、 工程计算等领域中有重要 而 广泛的应用， 所以对特殊矩阵的研究一直是被关注的热点。 为提高 特殊矩阵的 运算效率， 通过运用特殊矩阵的特殊结构及性质， 使得有关计算问题降低一个数 量级， 研究特殊矩阵的快速算法及性质， 这是具有 一 重要的理论意义和现实意义的 研究课题。 在美国的 l i n e a r a l g e b r a a n d i t s a p p l i c a t i o n s ) , ( s i a m m a t r i x a n a l y s i s a n d i t s a p p l i c a t i o n s ) , ( m a t h e m a t i c c o m p u t a t i o n ) ) ,德国的 n u m e r . m a t h 和国内的 计算数学 、 数值计算与计算机应用 、 高等学校计算数学学 报 、 高校应用数学学报 、 数学的实践与认识等期刊上，已发表了为数众多 的相关论文。 分块三( 五) 对角矩阵及分块周期三对角矩阵是人们在实际问题中经常遇到 的矩阵， 例如在用差分方法求解常微分方程与偏微分方程的边值问题、 船体数学 放样中建立的二次样条插值函数的求解、 线性规划、网络分析、结构分析等问题 中， 经常需要求解以对角占优的分块三( 五) 对角矩阵及分块周期三对角矩阵为系 数矩阵的线性方程组， 且阶数一般较高。 从而研究这类矩阵的有关计算问题的快 速算法，如求解相应的线性方程组和求逆矩阵等，具有实际的意义。 p a s c a l三角形也叫杨辉三角形，它在组合数学、概率论、数论、代数、微 分方程等许多领域有着厂泛的应用;同时 p a s c a l 三角形中隐含着二项式系数的 许多相关性质。 从而对于山p a s c a l 三角形产生的 p a s c a l 矩阵的研究具有理论意 义和实际意义。 本文将对这些问题进行系统的研究。 二、有关求解特殊矩阵方程组及其逆的历史和研究现状 求解以分块三( 五) 对角矩阵和分块周期三对角矩阵为系数矩阵的大型线性 方程组最经典的方法是追赶法。 它是利用分块 三( 五) 对 一 角矩阵的l u 分解的 特殊 形式而得到的一种快速算法。由于这里的 l ( 0只有对角线及对角线下 ( 上) 两排 有非零元素，从而形成了一追一赶的过程。在 1 9 9 4年王纪林，周钢给出了把较 大方程组化为较小方程组的初参数方法， 并将三对角方程组作为特例给出了相应 的算法 a 7 。 继而在1 9 9 7 年， 周钢，胡芬 兰， 王纪林给出了 复系数线性带 状方程 组的初参数追赶法多 。 在 1 9 9 2 年以前， 对p a s c a l 三角形的研究仅限 于对由其元素构成矩阵的行列 式性质的探讨。 在 1 9 9 2 年， r . b r a w e r 和m . p i r o v i n e 给出了p a s c a l 矩阵和 对 称 p a s c a l 矩阵的定义阴 ， 并对它们的 分解及逆进行了 研究，同时给出了一些 应用。在 1 9 9 3年， 丁 .s z a l k a :和 d . v e l l e m a n 给出了 p a s c a l 矩阵在概率论中 的应用 宝 “ 一。同年，g . s . c a l l和 d . j . v e l l e m a 。给出了它的台劳公式及两个 p a s c a l 矩阵相乘的结果， 最后还提到了 它的 一个重要应用: , 。 在 1 9 9 7年， z . z h i z h e n g 定 义了 三 类 一 元p a s c a l 函 数 矩 阵 巴 一， 前 两 类 都是 下 三 角 形 矩阵 ， 第三类为对称矩阵。接着，1 9 9 8 年 z . z h i z h e n g a n d l . m a i x u e在此基础上把 p a s c a l 矩阵推广到了二元的两大类p a s c a l 矩阵 i j 随后， 人们进一步将其推 广 到广义p a s c a l 矩阵， 得到了 许多 结果丁 ， ” 七 三 t 白” 。 在2 0 0 3 年， m o a w w a d e . a e l - m i k k a w v 给出了求对称 p a s c a l 矩阵的 逆及线性方程组的快速算法 i 三、本文的研究内容及安排 本文研究以分块三对角矩阵、分块五对角矩阵、 分块周期三对角矩阵为系数 矩阵的线性方程组的快速算法， 以 及求解这 些矩阵的 逆矩阵快速算法。 最后进一 步研究广义 p a s c a l 矩阵的性质。各章的安排如下。 第一章给出了问题的应用背景及相关的定义与结论: 第二章给出了以分块三 对角矩阵、分块五对角矩阵为系数矩阵的 线性方程组的变参数追赶法及数值算 例; 第三章以带状矩阵的逆矩阵的研究为起点， 运用得出的结论给出了分块三对 角矩阵、分块五对角矩阵、 分块周期三对角矩阵的逆矩阵的快速算法，并给出了 相应的数值算例; 第四章运用递推算法给出了分块三对角矩阵、 分块五对角矩阵、 分块周期三对角矩阵的 逆矩阵的快速算法， 给出了 相应的 数值算例; 第五章研究 广义 p a s c a l 矩阵的性质。 1 . 2几类特殊的矩阵 本节中， 将对论文中用到的儿类特殊知阵如分块带状矩阵、 分块三对角矩阵、 分块五对角矩阵、分块周期三对角矩阵、 对角占优矩阵的概念作简要的介绍。 p a s c a l 矩阵的有关概念将在第五章给出。 一、分块带状矩阵 定 义 ，如 果 分 块 矩 阵 a 一 归 j， 派满 足 氏一 0行 - i p 且 i - i 刃仅 . 功 其 中 a为m 阶 矩 阵 ， 则 称a 为( p ,9 ) 一 分 块带 状 矩阵。 定义 1 . 2 若分块矩阵a=具有如下形式 糕及. ( 1 . 2 ) 月直，2 了扮、ac ba c 其中a ，及 定义 1 c ， 为，阶方阵， 则称a为 分块三对角矩阵。 若 分 块 矩 阵 a 一 (a i 具 有 如 下 形 式 组的初参数追赶法多 。 在 1 9 9 2 年以前， 对p a s c a l 三角形的研究仅限 于对由其元素构成矩阵的行列 式性质的探讨。 在 1 9 9 2 年， r . b r a w e r 和m . p i r o v i n e 给出了p a s c a l 矩阵和 对 称 p a s c a l 矩阵的定义阴 ， 并对它们的 分解及逆进行了 研究，同时给出了一些 应用。在 1 9 9 3年， 丁 .s z a l k a :和 d . v e l l e m a n 给出了 p a s c a l 矩阵在概率论中 的应用 宝 “ 一。同年，g . s . c a l l和 d . j . v e l l e m a 。给出了它的台劳公式及两个 p a s c a l 矩阵相乘的结果， 最后还提到了 它的 一个重要应用: , 。 在 1 9 9 7年， z . z h i z h e n g 定 义了 三 类 一 元p a s c a l 函 数 矩 阵 巴 一， 前 两 类 都是 下 三 角 形 矩阵 ， 第三类为对称矩阵。接着，1 9 9 8 年 z . z h i z h e n g a n d l . m a i x u e在此基础上把 p a s c a l 矩阵推广到了二元的两大类p a s c a l 矩阵 i j 随后， 人们进一步将其推 广 到广义p a s c a l 矩阵， 得到了 许多 结果丁 ， ” 七 三 t 白” 。 在2 0 0 3 年， m o a w w a d e . a e l - m i k k a w v 给出了求对称 p a s c a l 矩阵的 逆及线性方程组的快速算法 i 三、本文的研究内容及安排 本文研究以分块三对角矩阵、分块五对角矩阵、 分块周期三对角矩阵为系数 矩阵的线性方程组的快速算法， 以 及求解这 些矩阵的 逆矩阵快速算法。 最后进一 步研究广义 p a s c a l 矩阵的性质。各章的安排如下。 第一章给出了问题的应用背景及相关的定义与结论: 第二章给出了以分块三 对角矩阵、分块五对角矩阵为系数矩阵的 线性方程组的变参数追赶法及数值算 例; 第三章以带状矩阵的逆矩阵的研究为起点， 运用得出的结论给出了分块三对 角矩阵、分块五对角矩阵、 分块周期三对角矩阵的逆矩阵的快速算法，并给出了 相应的数值算例; 第四章运用递推算法给出了分块三对角矩阵、 分块五对角矩阵、 分块周期三对角矩阵的 逆矩阵的快速算法， 给出了 相应的 数值算例; 第五章研究 广义 p a s c a l 矩阵的性质。 1 . 2几类特殊的矩阵 本节中， 将对论文中用到的儿类特殊知阵如分块带状矩阵、 分块三对角矩阵、 分块五对角矩阵、分块周期三对角矩阵、 对角占优矩阵的概念作简要的介绍。 p a s c a l 矩阵的有关概念将在第五章给出。 一、分块带状矩阵 定 义 ，如 果 分 块 矩 阵 a 一 归 j， 派满 足 氏一 0行 - i p 且 i - i 刃仅 . 功 其 中 a为m 阶 矩 阵 ， 则 称a 为( p ,9 ) 一 分 块带 状 矩阵。 定义 1 . 2 若分块矩阵a=具有如下形式 糕及. ( 1 . 2 ) 月直，2 了扮、ac ba c 其中a ，及 定义 1 c ， 为，阶方阵， 则称a为 分块三对角矩阵。 若 分 块 矩 阵 a 一 (a i 具 有 如 下 形 式 ( 1 . 3 ) |11.llwewe于ij d 5 几凡 几凡浅 从戈式 氏东c 氏c，;-只 几i，m 只 燕凡c 氏c只 干十1十11.1.1.j - 其中a ， ，b , , c，d，只 为。阶方阵， 则称a为分块五对角 矩阵。 分块三对角矩阵和分块五对角矩阵分别是 ( 1 , 1 )一 分块带状矩阵和 ( 2 , 2 ) 一 分块带状矩阵。 二、分 块周期三对角矩阵 定 义， . 4若 分 块 矩 阵 a 一 恤 。 九 。 具 有 如 下 形 式 ( 1 . 4 ) |!|lwell|j cb，氏 c b 鸿c药 广.1十1 一- a 其中a ， ，b ; , c为m阶方阵， 则称a为分块周期三对角矩阵。 三、对角占优矩阵 定 义， “设 矩 阵 “ 一 (q 9 ku * 满 足 la , : 酬a !i l td = 1 ,2 , - -, k ) ( 1 . 5 ) 则称a为按行对角占优矩阵;若 iq ,;i e lp l t 一 1 ,2 ， 二 ， 劝 ( 1 . 6 ) 成立，则称a为按行严格对角占优矩阵。 与上面定义 类似， 我们可以 定义按列( 严格) 对角占 优矩阵的 概念，按行对角 占优矩阵与按列对角占优矩阵统称为对角占优矩阵。 定 义1 . 6设 分 块 矩 阵 a = 恤). _， ， 其 中 戒 了 为 m 阶 方 阵 ， 若 下 列 不 等 式 成 立 iia ila : i 9a ; iim ( i 一 ，12 , - - ., n ) ( 1 . 7 ) 则称a为 按行分块对角占优矩阵， 简称为块对角占优矩阵。若式( 1 . 7 ) 中的大于 等于号换成大于号， 则称a为按行严格分块对角占 优矩阵， 简称为严格块对角 占优矩阵。 对角占优矩阵与分块对角占优矩阵有如下性质。 性质 1 若a为严格对角占优矩阵，则a可逆。 性 质2若 a 一 恤 。 九 。 为 严 格 块 对 角 占 优 矩 阵 ， 则 a 可 逆 。 1 . 3问题的提出 下面给出一些引入 ( 分块)三对角矩阵的例子。 问题 i求解微 分方积伪佰 f wl 颗 ( 1 . 3 ) |11.llwewe于ij d 5 几凡 几凡浅 从戈式 氏东c 氏c，;-只 几i，m 只 燕凡c 氏c只 干十1十11.1.1.j - 其中a ， ，b , , c，d，只 为。阶方阵， 则称a为分块五对角 矩阵。 分块三对角矩阵和分块五对角矩阵分别是 ( 1 , 1 )一 分块带状矩阵和 ( 2 , 2 ) 一 分块带状矩阵。 二、分 块周期三对角矩阵 定 义， . 4若 分 块 矩 阵 a 一 恤 。 九 。 具 有 如 下 形 式 ( 1 . 4 ) |!|lwell|j cb，氏 c b 鸿c药 广.1十1 一- a 其中a ， ，b ; , c为m阶方阵， 则称a为分块周期三对角矩阵。 三、对角占优矩阵 定 义， “设 矩 阵 “ 一 (q 9 ku * 满 足 la , : 酬a !i l td = 1 ,2 , - -, k ) ( 1 . 5 ) 则称a为按行对角占优矩阵;若 iq ,;i e lp l t 一 1 ,2 ， 二 ， 劝 ( 1 . 6 ) 成立，则称a为按行严格对角占优矩阵。 与上面定义 类似， 我们可以 定义按列( 严格) 对角占 优矩阵的 概念，按行对角 占优矩阵与按列对角占优矩阵统称为对角占优矩阵。 定 义1 . 6设 分 块 矩 阵 a = 恤). _， ， 其 中 戒 了 为 m 阶 方 阵 ， 若 下 列 不 等 式 成 立 iia ila : i 9a ; iim ( i 一 ，12 , - - ., n ) ( 1 . 7 ) 则称a为 按行分块对角占优矩阵， 简称为块对角占优矩阵。若式( 1 . 7 ) 中的大于 等于号换成大于号， 则称a为按行严格分块对角占 优矩阵， 简称为严格块对角 占优矩阵。 对角占优矩阵与分块对角占优矩阵有如下性质。 性质 1 若a为严格对角占优矩阵，则a可逆。 性 质2若 a 一 恤 。 九 。 为 严 格 块 对 角 占 优 矩 阵 ， 则 a 可 逆 。 1 . 3问题的提出 下面给出一些引入 ( 分块)三对角矩阵的例子。 问题 i求解微 分方积伪佰 f wl 颗 y (x ) y ( a ) = + p y ( x ) + q y (x ) = f (x ), a x b c 1, y (b ) = 。 ， 其中f ( x ) 是己 知实函数，p , q , cc : 为己 知数。 要找出此边值问题解的解析表达式是比较困难的，因此常求其数值解。 把区 r a , b 分成。 等份，令 x , = a + ih ( i = 0 ， 一 ， n ) , h 一 ( b 一 a ) / n y (x ) 一 y lx ,+ i) - y lx ,-) + o (h ) ( = 1,.,n - 1)2 h a x 卜 y (x,+i )- 2y (x ,h 丝 业 卫 十 乖 ) 一 1,.-,n 一 ， 替 代 微 分 方 程 中 的 ， (x ) 和 * (x , ) 。 并 当 * 充 分 小 时 ， 略 去 上 式 中 。 伪 ) 项 ， 经 整 理得微分方程的近似方程 ， 一 粤 ， ) 夕 其中 f二 f (x ) y ,-i + (- : 十 。 2q 卜 十 1 + 粤 ， 议， 二 h - f , 又乙少 利 用 边 界 条 件y o = cl ， y = l 2 ， 得 一 2 + h z q h i 一 百 p z + 夸 : 夸 ， 一 2 h zq - 一les.、.esesj yl凡:凡 |!1工es p h一2 + 电.1 此方程组的系数矩阵是三对角矩阵。 问题 n求解泊松方程边值问题 a u a l u 丽+ 矿十 q u 一 i v , y ), u x i ; u y i i u l = w ( x , y ) 其 中l 是 区 域g : o s x , y 1 的 边 界， so (x ,力为 定 义 在l 上的 已 知 函 数 。 由于难于找出其解的解析表达式， 因此常求其数值解。 将区域划分为有限个 正方形单元， 交点为网点。 令 x 一 ih ， * ， 一 j h ， u 。 一 u (x ， ， ) ， f ; 一 f ,r ， ， ， ) ， ， 。 = rp x ,， y , ) ， h 一 1/ n 用差商代替偏导数 a lu ) l a x - 夕 u , + t ,i 一 2 u , + u ,- , .i h - a zu ) 即. 少 u i + 1 一 2 u , + u , .， 一 】 代入偏微分方程得到差分方程 u ; 十 i ,l 十 u ,- , i + u i + i 十 伙 了 _ , 一 4 u , h - + q u 。 一 f , (i 、 i, j 、 n - i) t u , , = v o l , u , “ (p , , u 。 = (9 , 0 , u . = v , 引入向量与矩阵记号 v = ( u n , u， 二 u n - ,j , u ,1 , . ., u - i.= , , u tn - i ， ， un 一 1 ， 一 1) ru _ , _ , ) i t了_ 1 t 一 习 了厂_一 “ 一 _三 一 li f ,， 卜 1 ). ( o - , ) 式中i 是n 一 i 阶单位矩阵，而 一 4 + h zq 厂 = i 一 4 + h 2 q 于是差分方程可改写为 tv=b 此方程组的系数矩阵t是分块三对角矩阵。 问 题ir三次样条 插值问 题 给定 a , b 区间的分划 万:“ = x , x , ， 一 1 ,- , a 一 ， a (z ， 一5 1_z a t一5 1_z a - z- - ,-2 2 ， 一 i t- 2 a 一 ， o ) 二 。 o + z ) ， j 7( ) 一 。 . z ) z ) = 。 二 ， ， ,8 0( 对i 一 ，) 一 砰+ i) 一 。 a 0( + z ), 砂一 ， = 砂,l) 一 。 ， 。 卜， 此一 ， 二 a ( . ， 一 。 a 2(- 2 ) 叫侧侧 二 n 一2 ， 一 2 , 1 a l。 一 。 (,+z0 ) 一 。 + p a 。 一 毛 一 2 川 q i(r) = a (,+z ， 一 。 、 ，川少 一 t ,+z ( ) = a 2 ,+z ， 一 to。 ， (+ + , # z ， 一 t ,+ , jja (, (8 0 )( 10一 fi ,(2 ) ) + m 2 ) (1 )l 8 2 ( i 一 a ll) ( i 一 ,g 2(2 ) 一 # 2)# 2() 刀 ， ) + # ,1 2) , , i 一 例2 ， y i =t , x t)y , =u , x i + t z x z 对i 二 3 ， ， 一 ， n 十 2 y 二 9 _ : 一 s,-: 一 毛 一 2 戈 x =y+ _ ， x 。 一 =y+ i 一“ n x n 对i 二 n 一 2 ， 3 x= y ;. z 一 u i x i 一 t . + z x r+ z 变参数追赶法需进行2 6 n 一 1 5 次乘除运算，1 9 n 一 1 6 次加减运算。 2 . 3数值算例 我们对许多三( 五) 对角方程组及分块三( 五 ) 对角方程组在微机( c p u i . 5 0 g ， 内 存 2 5 6 m b ) 上用 f u r t r a n 语言编程计算，结果表明当分块三( 五) 对角矩阵严格对角 占优或不可约对角占优时，本文所给的变参数追赶法对适当 选取的参数矩阵 ( l u , ， 使 得 入 u , 十 坷 逆) 或参 数( 1 u . 使 得 卜 l , u , $ 0 ) 都可 以 求 得 相 应 方 程组 的 解。 虽然变参数追赶法的 计算量比 追赶法大些， 但对某些适当 选取的 参数矩阵 算法2 . 4 ( 求解五对角方程组的变参数追赶法) ( 任 取s i ,t i ,l , ,us z t z ， 使 得s ,t, + 1 ,u , + 1 x 。 ) v ,= 对 i : a , s , t , +i , u , + i : 3 , - , n t 一 二， v ,2 b , u 2 = 一 1 1 2v ， 二 一a 2 .兰 2 u 2 1 一 s z u , u z +s z t 2 iz = 全一 : 2 。 u=生一 ; 1 ; _ , v ， = a一 p ; t ， 一 ( c ， 一 p , u , - i ) u ， 一 鱼，1 一 丘 一 : ;u ;_ 片刃 对 i 二1 , 关-叭 一一 g 。 ，) 二 0 , a oz ， 二 0 ,。 ， 二 ; . ，。 ， ， = 。 ; ，a z ， 一 。 ，a zz ) = tz 对i 二3 , - n 十 2 a oi = s - 2 一 s ,- 2 a 一 ， ) 一 i ,_z a o一 ， 。 ， = - s ,_2 a _ ， 一 1 ,- , a 一 ， a (z ， 一5 1_z a t一5 1_z a - z- - ,-2 2 ， 一 i t- 2 a 一 ， o ) 二 。 o + z ) ， j 7( ) 一 。 . z ) z ) = 。 二 ， ， ,8 0( 对i 一 ，) 一 砰+ i) 一 。 a 0( + z ), 砂一 ， = 砂,l) 一 。 ， 。 卜， 此一 ， 二 a ( . ， 一 。 a 2(- 2 ) 叫侧侧 二 n 一2 ， 一 2 , 1 a l。 一 。 (,+z0 ) 一 。 + p a 。 一 毛 一 2 川 q i(r) = a (,+z ， 一 。 、 ，川少 一 t ,+z ( ) = a 2 ,+z ， 一 to。 ， (+ + , # z ， 一 t ,+ , jja (, (8 0 )( 10一 fi ,(2 ) ) + m 2 ) (1 )l 8 2 ( i 一 a ll) ( i 一 ,g 2(2 ) 一 # 2)# 2() 刀 ， ) + # ,1 2) , , i 一 例2 ， y i =t , x t)y , =u , x i + t z x z 对i 二 3 ， ， 一 ， n 十 2 y 二 9 _ : 一 s,-: 一 毛 一 2 戈 x =y+ _ ， x 。 一 =y+ i 一“ n x n 对i 二 n 一 2 ， 3 x= y ;. z 一 u i x i 一 t . + z x r+ z 变参数追赶法需进行2 6 n 一 1 5 次乘除运算，1 9 n 一 1 6 次加减运算。 2 . 3数值算例 我们对许多三( 五) 对角方程组及分块三( 五 ) 对角方程组在微机( c p u i . 5 0 g ， 内 存 2 5 6 m b ) 上用 f u r t r a n 语言编程计算，结果表明当分块三( 五) 对角矩阵严格对角 占优或不可约对角占优时，本文所给的变参数追赶法对适当 选取的参数矩阵 ( l u , ， 使 得 入 u , 十 坷 逆) 或参 数( 1 u . 使 得 卜 l , u , $ 0 ) 都可 以 求 得 相 应 方 程组 的 解。 虽然变参数追赶法的 计算量比 追赶法大些， 但对某些适当 选取的 参数矩阵 或 参数 ，计 算的 结果较 著名 的追 赶法 有 更高的 计 算稳定性( 采用ia x - f iif 或 11-4 - 一 f ii: 来 度量 )。 特别 是 对于 用追 赶 法 计 算失 效的 一 些分 块 三( 五 ) 对角 方 程 组及三( 五) 对角方程组， 用选取适当参数矩阵或参数的变参数追赶法计算仍可得 到好的结果。部分算例如下。 例 2 . 1 求解分块三对角线性方程组a x二f，其 中 5 6一1 0 一 1 5 6 月 二4 1 。 ( i =1 ,2 , , n )4 1 , 5 6 0一1 n。门 广les一 - 月几 a c , = - 4 7，双 分别采用追赶法和算法 2 . 1 见表 2 . 1 =- 3 h 2 , . , n ) 朋- ，月.一.1.一(i 00-156 ( 选取参数矩阵l二 2 式 ， ，u ; = 3 7) 进行计算，结果 追赶法 新方法 6 . 3 6 x 1 0 - 4 . 8 3 x 1 0 - 表 2 ， 1 80 9 . 3 4 x 1 0 - x 7 . 1 6 x 1 0 - 1 4 1 0 01 5 0 1 . 1 7 x 1 0 - 9 . 0 5 x 1 0 一 1 . 8 0 x 1 0 一 3 1 . 3 4 x 1 0 - 例 2 . 2 求解分块三对角线性方程组a x二f，其中 5 5一1 a 二i 一1 5 5 仁 0 一 1 b =c =一 几 分别采用追赶法和算法 2 . of 一1 ， p =i, ( i =1 .2n ) 5 5 ( i =2 , . . , n ) ( 选取参数矩阵l , = u , = 1 3 ) 进行计算，结果见表 2 . 2 n 5 0 0 0 表 2 . 2 1 0 0 0 0 追赶法 新方法 5 . 4 3 x 1 0 - 2 . 7 2 x 1 0 7 . 6 9 x 1 0 - 3 . 8 4 x 1 0 - 1 00 0 0 0 2 . 4 3 x 1 0 - 1 . 2 2 x1 0 - 5 . 4 4 x 1 0 - 2 . 7 2 x 1 0 - 3 例 2 . 3 求解三对角线性方程组a x = f, a ; = 4 4 ，厂= 2 ( i = 1 , 2 ， 一 ， n ) b= c ,. = i ( i = 2 ， 二 、 n ) 分 别 采 用 追 赶 法 和算 法2 . 2 ( 选 取 参 数1 , = - 3 , 表 2 . 3 其中 “ ， = 1 ) 进行计算，结果见表2 . 3 n 1 00 00 1 0 0 0 0 01 0 0 0 0 0 0 20 0 0 0 0 0 追赶法 新方法 4 . 4 4 x 1 0 - 8 . 3 1 x 1 0 - 1 . 4 0 x 1 0 一 3 8 . 3 1 x 1 0 - 6 4 . 4 4 x 1 0 - 1 3 8 . 3 1 x1 0 - 6 . 2 8 x 1 0 - 8 . 3 1 x 1 0 - 0 例2 . 4 求解三对角线性方程组a x = 了， 其中 a , = 2，f二1 5，a ， 二9 ，式= 1 2 ( i 二 2 ， 一， n ) 乓“3 ，c ， 二 6 ( i 二2二， 的 追赶 法 解 此 线 性方 程 组失 效， 采 用 算 法2 . 2 ( 选 取 参 数2 ， 之 3 .、 、 = 幼进 行 计 算 ， 结果见表 2 . 4 表 2 . 4 1 0 0 0 0 2. 2 4x1