第一章矩阵运算的计算机方法及稀疏距阵.ppt课件

第一章第一章 矩阵运算的计算机方法及稀疏距阵矩阵运算的计算机方法及稀疏距阵现代电路分析课程知识要点现代电路分析课程知识要点经典电路分析知识要点经典电路分析知识要点计算机辅助分析计算机辅助分析及工具运用及工具运用矩阵方程矩阵方程建立初步建立初步矩阵方程建立矩阵方程建立的普通方法的普通方法矩阵运算的矩阵运算的计算机方法计算机方法非线性电路非线性电路分析初步分析初步非线性电路方程非线性电路方程建立的普通方法建立的普通方法有源滤波电路有源滤波电路分析初步分析初步电路的电路的参数分析参数分析本章主要内容及要求本章主要内容及要求了解了解LU分解法解线性方程组原理、运用及算法分解法解线性方程组原理、运用及算法了解高斯消元法解线性方程组原理、运用及算法了解高斯消元法解线性方程组原理、运用及算法了解稀疏矩阵原理了解稀疏矩阵原理 第一节第一节 计算数学的几个根本概念计算数学的几个根本概念 利用计算机处理实践问题，通常要按以下步骤进利用计算机处理实践问题，通常要按以下步骤进展：展：1建立数学模型，即把实践问题笼统为一个数建立数学模型，即把实践问题笼统为一个数学问题，他可以是一个方程组学问题，他可以是一个方程组、一个函数、一个微、一个函数、一个微分方程等。

分方程等2选择数值方法，要思索所能到达的精度，计选择数值方法，要思索所能到达的精度，计算量，方法对数据微小扰动的灵敏度算量，方法对数据微小扰动的灵敏度3编写程序，上机计算编写程序，上机计算计算数学的几个根本概念计算数学的几个根本概念 1、算法、算法 2、计算量、计算量 例：计算例：计算 x255 按原型计算，计算量按原型计算，计算量254次浮点运算次浮点运算 改用改用x255=x*x2*x4*x8*x16*x32*x64*x128 只需只需14次浮点运算次浮点运算计算数学的几个根本概念计算数学的几个根本概念 例：设例：设A，B，C，D分别为分别为 10*20，20*50，50*1，1*100的矩阵的矩阵 用不同算法求矩阵乘积，用不同算法求矩阵乘积，E=ABCD根据矩阵乘除法的结合率，采用以下三种算法：根据矩阵乘除法的结合率，采用以下三种算法：1E=(AB)CD 计算量是计算量是 11500次浮点运算次浮点运算2E=AB(CD)计算量是计算量是 125000次浮点运算次浮点运算3E=A(BC)D 计算量是计算量是 2200次浮点运算次浮点运算 显然算法显然算法3效率最高效率最高计算数学的几个根本概念计算数学的几个根本概念 例：例：Cramer法那么求解法那么求解n元线性方程组元线性方程组 要计算要计算n+1个行列式和个行列式和n次除法次除法 计算一个计算一个n阶行列式的计算量约为阶行列式的计算量约为(n+1)(n!)求解求解n阶线性方程组的总计算量是阶线性方程组的总计算量是 N=(n+1)(n-1)(n!)+n次浮点运算。

次浮点运算当当n=20 时，计算量为时，计算量为9.707*1020假设在每秒亿次运算速度的计算机上运转假设在每秒亿次运算速度的计算机上运转需求需求31.2万年，这对于高阶方程组是毫无适用价值万年，这对于高阶方程组是毫无适用价值计算数学的几个根本概念计算数学的几个根本概念 3、误差的根本概念：、误差的根本概念：准确值和近似值之间的差别就是所谓的误差准确值和近似值之间的差别就是所谓的误差误差产生主要是以下四个来源：误差产生主要是以下四个来源：模型误差模型误差 观测误差观测误差 截断误差截断误差 舍入误差舍入误差 绝对误差、相对误差、有效数字绝对误差、相对误差、有效数字计算数学的几个根本概念计算数学的几个根本概念 4、良态与病态问题：良态与病态问题：假设初始数据的微小变化导致计算结果的猛烈假设初始数据的微小变化导致计算结果的猛烈变化，这样的问题称之为病态问题他是问题固变化，这样的问题称之为病态问题他是问题固有的一种属性有的一种属性1150)(2xxxf6.53/100）（f28)33(f 数据的变化小于数据的变化小于0.34，而函数的变化，而函数的变化22.4，因此，因此在接近根处是一个病态问题。

在接近根处是一个病态问题计算数学的几个根本概念计算数学的几个根本概念上式根为上式根为1，2，320左边展开后，左边展开后，x的的19次方的系数为次方的系数为-210 假设换为假设换为-210.000000119，其他各项不变，其他各项不变再求解，那么根再求解，那么根20变为变为20.847根根18和和19那么变为一对共轭复数那么变为一对共轭复数19.5021.940i显然这是一个病态问题显然这是一个病态问题0)20 x).(3x)(2x)(1x(方程计算数学的几个根本概念计算数学的几个根本概念6047x51x41x311213x41x31x21611x31x21x321321321线性方程组1xxx321根为78.020.025.033.01.125.033.050.08.133.050.0321321321xxxxxxxxx65.33x,25.38x,222.6x321解变为 假设把方程的系数取三位小假设把方程的系数取三位小数数计算数学的几个根本概念计算数学的几个根本概念010 x110(x992）方程a2ac4bb2,12x第一种求根公式12a2ac4b)b(gnsinb1ax/cx,x2第二种求根公式1x,10 x291根为0,10291xx1,10291xx假定计算机字长为假定计算机字长为8，解为，解为 计算机字长为计算机字长为8，解为，解为 计算数学的几个根本概念计算数学的几个根本概念 数值计算中值得留意的事项数值计算中值得留意的事项:1 要防止两个相近的数相减要防止两个相近的数相减。

2 防止大数吃掉小数防止大数吃掉小数3 防止接近零的数作除数防止接近零的数作除数4 减少运算次数减少运算次数5 防止舍入误差被放大防止舍入误差被放大计算数学的几个根本概念计算数学的几个根本概念习习 题题1.1计算数学的几个根本概念计算数学的几个根本概念 第二节第二节 高斯消元法解线性方程组高斯消元法解线性方程组BAX n21n21nnn2n12n22211n1211bbbxxxaaaaaaaaa线性方程组的普通方式线性方程组的普通方式AkAbxkdetdet列列而而得得到到的的矩矩阵阵的的第第代代替替用用nn矩阵的行列式：需求矩阵的行列式：需求(n-1)n!次复数乘法次复数乘法对对11个节点的电路需求：个节点的电路需求：32659200次乘法次乘法对对21个节点的电路需求：个节点的电路需求：4.6 1019次乘法次乘法用每秒亿次计算机：用每秒亿次计算机：万年万年5.1100000000606024365!2019高斯法约为高斯法约为330次乘除运算次乘除运算高斯法约为高斯法约为2660次乘除运算次乘除运算线性方程组经典解法克莱姆法那线性方程组经典解法克莱姆法那么么 举例阐明高斯消元法举例阐明高斯消元法2875342622321321321xxxxxxxxx2875622342321321321xxxxxxxxx初等行变换初等行变换1319170963423232321xxxxxxx1319170233423232321xxxxxxx13213023342332321xxxxxx回代回代132123xxx原理：经过初等变换化为三角矩阵原理：经过初等变换化为三角矩阵2031002/310421321xxx高斯消元算法阐明高斯消元算法阐明a11x1+a12x2+a1nxn=a1,n+1a21x1+a22x2+a2nxn=a2,n+1 an1x1+an2x2+annxn=an,n+1将第一个方程除以将第一个方程除以a11，并把它写成为，并把它写成为)1(1,1)1(12)1(121nnnaxaxax=)1(12a1112aa)1(11)1(jiijijaaaa1,.,2,1,.,3,2njni其中其中将上式乘以将上式乘以-ai1，加到下面的，加到下面的n-1个方程上，得到个方程上，得到)1(1,)1(2)1(2)1(1,2)1(12)1(12)1(1,1)1(12)1(121nnnnnnnnnnnnaxaxaaxaxaaxaxax方程组变为方程组变为 下一步我们排除第一行和第一列，对第二个方程至第下一步我们排除第一行和第一列，对第二个方程至第个方程施以同样的处置，其公式变为个方程施以同样的处置，其公式变为)1()1()(kkkkkjkkjaaa)()1()1()(kkjkikkijkijaaaak=1,2,ni=k+1,nj=k+1,n+1高斯消元算法阐明高斯消元算法阐明)1(1,1)1(13)1(132)1(121.nnnaxaxaxax)2(1,2)2(23)2(232.nnnaxaxax)3(1,3)3(33.nnnaxax)(1,nnnnax最后所得的方程组最后所得的方程组系数矩阵为上三角矩阵系数矩阵为上三角矩阵回代过程：求出未知量回代过程：求出未知量 xi)(1,nnnnaxnijjijniixaax11,1,2,1nni高斯消元算法阐明高斯消元算法阐明选主元素举例选主元素举例755.125.1225.625.1000125.02121xxxx755.125.1250000100002121xxxx6249255.1249875000010000221xxx99989999.400010001.121xx6250001250005000010000221xxx5021xx3位有效数字位有效数字留意：由于除以较小数，留意：由于除以较小数，会得到较大的系数会得到较大的系数留意：这是一个较小的数留意：这是一个较小的数 与较大的数的差与较大的数的差留意：近似后误差较大留意：近似后误差较大改动主元素改动主元素25.625.1000125.0755.125.122121xxxx25.625.1000125.062121xxxx249925.6249875.16221xxx留意：由于除以较大数，留意：由于除以较大数，会得到较小的系数会得到较小的系数留意：这是一个较小的数留意：这是一个较小的数 与较小的数的差与较小的数的差选主元素举例选主元素举例取取3位有效数字位有效数字5121xx249925.6249875.16221xxx25.625.16221xxx留意：近似后有较小误差留意：近似后有较小误差结论结论主元素对角线上的元素越大，精度越高。

主元素对角线上的元素越大，精度越高选主元素举例选主元素举例选主元素选主元素改善线性方程组解的精度改善线性方程组解的精度使计算可以进展使计算可以进展交换系数矩阵行交换系数矩阵行/列，使列，使|aii|尽量大尽量大列主元素列主元素从当前列系数中选择一个绝对值最大的元素从当前列系数中选择一个绝对值最大的元素这种方法不需求改动变量的顺序，只交换行这种方法不需求改动变量的顺序，只交换行全主元素全主元素在整个剩余的矩阵中搜索绝对值最大的元素在整个剩余的矩阵中搜索绝对值最大的元素全主元素那么需求改动变量的顺序，需求交换列全主元素那么需求改动变量的顺序，需求交换列选主元素选主元素高斯法求逆矩阵自证高斯法求逆矩阵自证 100010001212222111211nnnnnnaaaaaaaaaIAnnnnnnaaaaaaaaaAI2122221112111100010001初等行变换初等行变换BAX BAX1习题与补充习题与补充P 1.2，1.5补充补充2：读懂给出的矩阵求逆程序，读懂给出的矩阵求逆程序，画出简单流程图画出简单流程图补充补充1：读懂给出的高斯消元法程序，用读懂给出的高斯消元法程序，用 程序计算求解程序计算求解xi 第三节第三节 LU分解法解线性方程组分解法解线性方程组算法阐明算法阐明设有方程组设有方程组其系数矩阵其系数矩阵A可以分解成下三角阵可以分解成下三角阵L与上三角阵与上三角阵U的乘积的乘积即即其中其中nnnnlllllllllL213232312221111111,122311312nnnnuuuuuuUBAX LUA BLUX YUXBLY先解出先解出Y再解出再解出X LU分解法特点分解法特点1LU分解法：分解法：1次次LU分解，分解，1次前代，次前代，1次回代。

次回代乘除次数与高斯消元法相当乘除次数与高斯消元法相当BAX LUA BLUX YUX 2矩阵矩阵L和和U的值只与的值只与A的值有关，与的值有关，与B无关，反复解无关，反复解 B变化变化A不变的方程组时，只进展一次分解即可不变的方程组时，只进展一次分解即可.算法阐明算法阐明根据根据A A求得求得L L和和U ULULU分解分解nnnnlllllllll213332312221111111,122311312nnnnuuuuuunnnnnnaaaaaaaaa212222111211li1ai1u1j=a1j/l11=a1j/a11 L第第1列列U第第1行行i=1，2，nj2，3，n以以L的第行乘以的第行乘以U的第列的第列ij：ijjijjjijijialululul,11,22,11,i j：),1,;,2,1(11njjinjulalkjjkikijijijjiiijijiaululul,22,11,),2,1;,2,1()(111niijniulalukjikikijiiij根据根据A A求得求得L L和和U ULULU分解分解矩阵矩阵LULU分解举例分解举例333231222111000llllllL100101231312uuuU33233213313212313123221321221221211311121111lulullullulullullulullLU矩阵矩阵LULU分解举例分解举例175122421A111l221l531l212u413u6)2(2212212222ulal17)2(5712313232ulal236421lulau2213212323213)23(17451ululal233213313333简介简介LULU分解法求逆矩阵分解法求逆矩阵设设A=LU的逆矩阵为的逆矩阵为Z100010001ILUZWUZ 设ILW nnilwlIwipiipjipijij,1,1/)(111W为为L的逆矩阵，由于的逆矩阵，由于 L为下三角矩阵，所以为下三角矩阵，所以 W也是下三角矩阵。

也是下三角矩阵2由前代可得由前代可得W1,1,/)(1nnilzuwznipiipjipijij习题与补充习题与补充P 1.2，1.5 补充补充1：读懂给出的读懂给出的LU分解法程序，用分解法程序，用 程序计算求解程序计算求解xi 第四节第四节 稀稀 疏疏 矩矩 阵阵 原原 理理稀疏矩阵稀疏矩阵大部分元素是零的矩阵叫稀疏矩阵大部分元素是零的矩阵叫稀疏矩阵用高斯法或用高斯法或LU分解来解方程组所需的运算量近似于分解来解方程组所需的运算量近似于 33n不进展这些与零有关的运算不进展这些与零有关的运算节省运算量节省运算量不存储零元素不存储零元素减少存储量减少存储量稀疏矩阵算法：稀疏矩阵算法：不存储零元素，也不对零元素进展运算不存储零元素，也不对零元素进展运算运算量及存储量近似与成比例运算量及存储量近似与成比例节点方程：节点方程：个不接地的节点，个不接地的节点，B个两端无源元件，那么矩阵个两端无源元件，那么矩阵Y最多包含最多包含2B个非零元素个非零元素普通大规模的电路来讲，元件的数目是节点数目的二倍到四倍普通大规模的电路来讲，元件的数目是节点数目的二倍到四倍非零元素非零元素元素总数元素总数n23331222113121100aaaaaaa假设进展假设进展LU分解不选主元素分解不选主元素313121211111alalalUL123132122122221112120ullulallau233213313333221321231113130ululallululau填入：零元素变为非零元素填入：零元素变为非零元素稀疏矩阵选主元例题稀疏矩阵选主元例题把元素把元素 a33 作为主元素，即用行、列对换的方法将它放作为主元素，即用行、列对换的方法将它放在左上角位置在左上角位置3312132122313300aaaaaaa3331222113121100aaaaaaa13312133110allalLU12322222120alalu2332133111332212123113113ululallaulau原矩阵的分解需求原矩阵的分解需求8次乘除和次乘除和5次减，次减，改动后的矩阵仅仅需求改动后的矩阵仅仅需求4次乘除和次乘除和2次减次减适当地选择主元素可降低运算次数适当地选择主元素可降低运算次数矩阵内的零元矩阵内的零元素经过素经过LU分分解依然为零解依然为零稀疏矩阵选主元例题稀疏矩阵选主元例题再排序的实现再排序的实现在稀疏矩阵技术中，选择主元素被称之为再排序在稀疏矩阵技术中，选择主元素被称之为再排序再排序再排序简化搜索方法简化搜索方法矩阵的特性矩阵的特性部分优化准那么部分优化准那么主元次序最好主元次序最好方法简单方法简单权衡，折中权衡，折中 对角元素非零对角元素非零非零构造通常近似对称非零构造通常近似对称以节点导纳矩阵为例：以节点导纳矩阵为例：坚持构造对称性，即坚持坚持构造对称性，即坚持L的非零构造与的非零构造与Ut 的非零构造一样的非零构造一样主元素的搜索限制在对角元素上主元素的搜索限制在对角元素上常用的选主元素的准那常用的选主元素的准那么么1不进展再排序不进展再排序2方程式按照非零元素的数目排序，将有最少方程式按照非零元素的数目排序，将有最少 非零元素的行首先编号，对列进展相应的排序。

非零元素的行首先编号，对列进展相应的排序3按最小非零元素规那么，逐次陈列各行，按最小非零元素规那么，逐次陈列各行，同时进展符号分解同时进展符号分解4使目前的处置阶段产生最少的填入：使目前的处置阶段产生最少的填入：最少部分填入准那么最少部分填入准那么例例:图图 中的中的90分相网络，它有分相网络，它有17个不接地节点，个不接地节点，其节点方程中包含其节点方程中包含77个非零元素个非零元素 J R2 L7 L5 L3 L1 L2 L4 L6 L8 R3 L9 L11 L13 L15 L10 L12 L14 L16 521 173321JBBC2C5C7C8C10C12C14C16R1C1C3C4C6C9C11C13C15选主元素的准那么举例选主元素的准那么举例不同的排序技术对不同的排序技术对LU分解运算中存储和计算量的影响分解运算中存储和计算量的影响用用“x表示原始的非零元素，用圆圈表示分解中的填入表示原始的非零元素，用圆圈表示分解中的填入对原始满阵完成对原始满阵完成LU分解计算零元素大约要分解计算零元素大约要1550次运算次运算选主元素的准那么举例选主元素的准那么举例 17161514131211109876543211716151413121110987654321 1.不重排不重排完成完成LU分解分解:有有68个填入个填入377次加乘次加乘选主元素的准那么举例选主元素的准那么举例161512118743117141310965216151211874311714131096522.首先陈列首先陈列具有最少非零具有最少非零元素的方程元素的方程LU分解分解:填入量填入量32运算量运算量209选主元素的准那么举例选主元素的准那么举例151413121611171019837465215141312161117101983746523.用最少非零用最少非零参数排序参数排序LU分解分解:填入量填入量14运算量运算量147选主元素的准那么举例选主元素的准那么举例117109216118315127414136511710921611831512741413654.用最少部分用最少部分参量填入排序参量填入排序LU分解分解:填入量填入量12运算量运算量141选主元素的准那么举例选主元素的准那么举例稀疏矩阵存储稀疏矩阵存储仅存储稀疏矩阵中非零元素的信息仅存储稀疏矩阵中非零元素的信息方法方法1：用：用3个数组个数组B、IB、JB存储稀疏矩阵存储稀疏矩阵A中非零元素中非零元素 的信息，包括非零元素的数值、列号、行号信息。

的信息，包括非零元素的数值、列号、行号信息数组数组B：BK按先行后列顺序存储矩阵按先行后列顺序存储矩阵A中第中第K个非零元素个非零元素 AI，J的数值的数值数组数组JB：JBK是数值为是数值为BK表示的非零元素表示的非零元素AI，J 在矩阵在矩阵A中的列号，即中的列号，即JBK=J数组数组IB：N+1维维N+1个元素辅助整数相量个元素辅助整数相量 IBM是是A中第中第M行的起始位置在行的起始位置在JB和和B中所对应中所对应 的位置的位置20010001411000096005084100735432154321AA：有：有12个非零元素的个非零元素的55矩阵矩阵JB：存储：存储BK对应的非零元素对应的非零元素AI，J 在在A中的列号中的列号B：顺序存储：顺序存储A中中12个非零元素个非零元素52433242152121014119658417312111098765432113119741B=JB=IB=IB：IBM是是A中第中第M行的起始位置行的起始位置 在在JB和和B中所对应的位置中所对应的位置稀疏矩阵存储举例稀疏矩阵存储举例 第五节第五节 复复 频频 率率 与与 复复 平平 面面 单边拉普拉斯变换单边拉普拉斯变换 tdtetfsFst0,)()(0 单边函数单边函数f(t)的拉普拉斯变换：的拉普拉斯变换：其中：其中：js 拉普拉斯反变换：拉普拉斯反变换：tdsesFjtfstjj0,)(21)(拉普拉斯变换对：拉普拉斯变换对：)()(tfsF)()(1sFtf 拉普拉斯变换主要性质拉普拉斯变换主要性质)()(2211tfktfk)()(2211sFksFk线性线性 dttdf/)()0()(fssF微分微分 tdf0)()(1sFs积分积分 根本元件拉氏变换域根本元件拉氏变换域VARVAR模型模型 电阻：电阻：)()(tRitv)()(sRIsV 阻抗阻抗Z导纳导纳YRR/1dttdiLtv)()()()(ssLIsV 电感：电感：零初值零初值sLsL/1dttdvCti)()()(1)(sIsCsV 电容：电容：零初值零初值sC/1sC 普通方式普通方式)()()(sIsZsV)()()(sVsYsI)(1)(sYsZ基尔霍夫约束的拉氏变换域模型基尔霍夫约束的拉氏变换域模型 0)(ti 0)(tu 0)(sI 0)(sV拉氏变换域分析举例拉氏变换域分析举例 CL)(tiR0t)(tvKsC/1sL)(sIR0t)(sVK)()1()(1)()()(sIsCsLRsIsCssLIsRIsV)()(1)()(sZsVsCsLRsVsIsCsLRsZ/1)(其中其中 假设鼓励电压源为一频率为假设鼓励电压源为一频率为00的余弦信号：的余弦信号：)Re()cos()(00tjmvmeVtVtv其中：其中：VjmmeVV那那么：么：0)(0jsVeVsVmtjm所以：所以：)()(1)()(sZsVsCsLRsVsI)()(0sZjsVm221100ssKssKjsK基尔霍夫约束拉氏变换举例基尔霍夫约束拉氏变换举例 由反变换求时域解：由反变换求时域解：Re)(Re)(2102101tststjeKeKeKsIti拉氏变换求解电路的根本步骤拉氏变换求解电路的根本步骤1 1由时域电路模型画出拉氏域电路模型由时域电路模型画出拉氏域电路模型2 2由拉氏域电路模型的由拉氏域电路模型的VARVAR及及KLKL建立代数方程；建立代数方程；3 3求拉氏域解；求拉氏域解；4 4经过拉氏反变换及取实部运算后，就得到时域解。

经过拉氏反变换及取实部运算后，就得到时域解复频率与复平面复频率与复平面由于由于s1s1和和s2s2与与j0j0具有一样的量纲，因此被称为复频率具有一样的量纲，因此被称为复频率 复频率复频率s=+js=+j：虚部：虚部具有频率的意义，具有频率的意义，称为实频率称为实频率rad/s)rad/s)；实部实部反映了时域解的幅度增长或衰减，反映了时域解的幅度增长或衰减，称为虚频率称为虚频率(Np/s)(Np/s)固有振荡频率：固有振荡频率：s1和和s2是网络阻抗是网络阻抗Z(s)=0的根，的根，称为称为Z(s)的零点，的零点，他们仅与网络的构造及元件值有关他们仅与网络的构造及元件值有关,因此和又被称为网络的固有振荡频率因此和又被称为网络的固有振荡频率s=+js=+j可用如下可用如下s s复平面上的点表示复平面上的点表示0j复频率与复平面复频率与复平面。