《第一章矩阵运算的计算机方法及稀疏距阵》由会员分享，可在线阅读，更多相关《第一章矩阵运算的计算机方法及稀疏距阵（59页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章矩阵运算的计算机方法及稀疏距阵矩阵运算的计算机方法及稀疏距阵现代电路分析现代电路分析国家电工电子教学基地 电路理论系列课程组 2005.3现代电路分析课程知识要点现代电路分析课程知识要点经典电路分析知识要点经典电路分析知识要点计算机辅助分析计算机辅助分析及工具应用及工具应用矩阵方程矩阵方程建立初步建立初步矩阵方程建立矩阵方程建立的一般方法的一般方法矩阵运算的矩阵运算的计算机方法计算机方法非非线性电路线性电路分析初步分析初步非非线性电路方程线性电路方程建立的一般方法建立的一般方法有源有源滤波电路滤波电路分析初步分析初步电路的电路的参数分析参数分析国家电工电子教学基地 电路理论系列课程
2、组 2005.3本章主要内容及要求本章主要内容及要求了解了解LU分解法解线性方程组原理、应用及算法分解法解线性方程组原理、应用及算法了解高斯消元法解线性方程组原理、应用及算法了解高斯消元法解线性方程组原理、应用及算法了解稀疏矩阵原理了解稀疏矩阵原理国家电工电子教学基地 电路理论系列课程组 2005.3第一节第一节计算数学的几个基本概念计算数学的几个基本概念现代电路分析第一章现代电路分析第一章国家电工电子教学基地 电路理论系列课程组 2005.3利利用用计计算算机机解解决决实实际际问问题题，通通常常要要按按以以下下步步骤骤进进行：行：（1）建立数学模型，即把实际问题抽象为一个数）建立数学模型，即
3、把实际问题抽象为一个数学问题，他可以是一个方程组学问题，他可以是一个方程组、一个函数、一个微、一个函数、一个微分方程等。分方程等。（2）选择数值方法，要考虑所能达到的精度，计）选择数值方法，要考虑所能达到的精度，计算量，方法对数据微小扰动的灵敏度。算量，方法对数据微小扰动的灵敏度。（3）编写程序，上机计算。）编写程序，上机计算。计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.31、算法、算法2、计算量、计算量例：计算例：计算x255按原型计算，计算量按原型计算，计算量254次浮点运算次浮点运算改用改用x255=x*x2*x4*x8*x16*x32
4、*x64*x128只需只需14次浮点运算。次浮点运算。计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.3例：设例：设A，B，C，D分别为分别为10*20，20*50，50*1，1*100的矩阵的矩阵用不同算法求矩阵乘积，用不同算法求矩阵乘积，E=ABCD。根据矩阵乘除法的结合率，采用下列三种算法：根据矩阵乘除法的结合率，采用下列三种算法：（1）E=(AB)CD计算量是计算量是11500次浮点运算次浮点运算（2）E=AB(CD)计算量是计算量是125000次浮点运算次浮点运算（3）E=A(BC)D计算量是计算量是2200次浮点运算次浮点运算显然算法
5、显然算法3效率最高。效率最高。计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.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万年，这对于高阶方程
6、组是毫无实用价值万年，这对于高阶方程组是毫无实用价值计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.33、误差的基本概念：、误差的基本概念：准确值和近似值之间的差异就是所谓的误差。准确值和近似值之间的差异就是所谓的误差。误差产生主要是以下四个来源：误差产生主要是以下四个来源：（）（）模型误差模型误差（）（）观测误差观测误差（）（）截断误差截断误差（）（）舍入误差舍入误差绝对误差、相对误差、有效数字绝对误差、相对误差、有效数字计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.34、良态与病态问题：良态与
7、病态问题：如如果果初初始始数数据据的的微微小小变变化化导导致致计计算算结结果果的的剧剧烈烈变变化化，这这样样的的问问题题称称之之为为病病态态问问题题。他他是是问问题题固固有的一种属性。有的一种属性。数数据据的的变变化化小小于于0.34，而而函函数数的的变变化化22.4，因因此此在接近根处是一个病态问题。在接近根处是一个病态问题。计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.3上式根为上式根为1，2，320左边展开后，左边展开后，x的的19次方的系数为次方的系数为-210若换为若换为-210.000000119，其余各项不变，其余各项不变再求解，
8、则根再求解，则根20变为变为20.847根根18和和19则变为一对共轭复数则变为一对共轭复数19.5021.940i显然这是一个病态问题。显然这是一个病态问题。计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.3若若把方程的系数取三位小数把方程的系数取三位小数计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.3假定计算机字长为假定计算机字长为8，解为，解为计算机字长为计算机字长为8，解为，解为计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.3数值计算中值得
9、注意的事项数值计算中值得注意的事项:（1）要避免两个相近的数相减要避免两个相近的数相减。（2）防止大数吃掉小数。防止大数吃掉小数。（3）防止接近零的数作除数。防止接近零的数作除数。（4）减少运算次数。减少运算次数。（5）防止舍入误差被放大。防止舍入误差被放大。计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.3习习题题1.1计算数学的几个基本概念计算数学的几个基本概念国家电工电子教学基地 电路理论系列课程组 2005.3第二节第二节高斯消元法解线性方程组高斯消元法解线性方程组矩阵运算的计算机方法矩阵运算的计算机方法国家电工电子教学基地 电路理论系列
10、课程组 2005.3线性方程组的一般形式线性方程组的一般形式国家电工电子教学基地 电路理论系列课程组 2005.3nn矩阵的行列式：需要矩阵的行列式：需要(n-1)n!次次复数乘法复数乘法对对11个节点的电路需要：个节点的电路需要：32659200次乘法次乘法对对21个节点的电路需要：个节点的电路需要：4.61019次乘法次乘法用每秒亿次计算机：用每秒亿次计算机：高斯法约为高斯法约为330次乘除运算次乘除运算高斯法约为高斯法约为2660次乘除运算次乘除运算线性方程组经典解法（克莱姆法则线性方程组经典解法（克莱姆法则 ）国家电工电子教学基地 电路理论系列课程组 2005.3举例说明高斯消元法举例
11、说明高斯消元法初初等等行行变变换换回代回代原理：通过初等变换化为三角矩阵原理：通过初等变换化为三角矩阵国家电工电子教学基地 电路理论系列课程组 2005.3高斯消元算法说明高斯消元算法说明a11x1+a12x2+a1nxn=a1,n+1a21x1+a22x2+a2nxn=a2,n+1 an1x1+an2x2+annxn=an,n+1将第一个方程除以将第一个方程除以a11，并把它写成为并把它写成为 = 其中其中将上式乘以将上式乘以-ai1，加到下面的加到下面的n-1个方程上，得到个方程上，得到国家电工电子教学基地 电路理论系列课程组 2005.3方程组变为方程组变为下一步我们排除第一行和第一列，
12、对第二个方程至第下一步我们排除第一行和第一列，对第二个方程至第个方程施以同样的处理，其公式变为个方程施以同样的处理，其公式变为k=1,2,ni=k+1,nj=k+1,n+1高斯消元算法说明高斯消元算法说明国家电工电子教学基地 电路理论系列课程组 2005.3最后所得的方程组最后所得的方程组系数矩阵为上三角矩阵系数矩阵为上三角矩阵回代过程：求出未知量回代过程：求出未知量xi高斯消元算法说明高斯消元算法说明国家电工电子教学基地 电路理论系列课程组 2005.3选主元素举例选主元素举例3位有效数字位有效数字注意：由于除以较小数，注意：由于除以较小数，会得到较大的系数会得到较大的系数注意：这是一个较小
13、的数注意：这是一个较小的数与较大的数的差与较大的数的差注意：近似后误差较大注意：近似后误差较大国家电工电子教学基地 电路理论系列课程组 2005.3改变主元素改变主元素注意：由于除以较大数，注意：由于除以较大数，会得到较小的系数会得到较小的系数注意：这是一个较小的数注意：这是一个较小的数与较小的数的差与较小的数的差选主元素举例选主元素举例国家电工电子教学基地 电路理论系列课程组 2005.3取取3位有效数字位有效数字注意：近似后有较小误差注意：近似后有较小误差结论结论主元素（对角线上的元素）越大，精度越高。主元素（对角线上的元素）越大，精度越高。选主元素举例选主元素举例国家电工电子教学基地 电
14、路理论系列课程组 2005.3选主元素选主元素改善线性方程组解的精度改善线性方程组解的精度使计算能够进行使计算能够进行交换系数矩阵行交换系数矩阵行/列，使列，使|aii|尽量大尽量大列主元素列主元素从当前列系数中选择一个绝对值最大的元素从当前列系数中选择一个绝对值最大的元素这种方法不需要改变变量的顺序，只交换行这种方法不需要改变变量的顺序，只交换行全主元素全主元素在整个剩余的矩阵中搜索绝对值最大的元素在整个剩余的矩阵中搜索绝对值最大的元素全主元素则需要改变变量的顺序，需要交换列全主元素则需要改变变量的顺序，需要交换列选主元素选主元素高斯法求逆矩阵（自证）高斯法求逆矩阵（自证） 初初等等行行变变
15、换换国家电工电子教学基地 电路理论系列课程组 2005.3习题与补充习题与补充P1.2，1.5补充补充2：读懂给出的矩阵求逆程序，读懂给出的矩阵求逆程序，画出简单流程图画出简单流程图补充补充1：读懂给出的高斯消元法程序，用读懂给出的高斯消元法程序，用程序计算求解程序计算求解xi国家电工电子教学基地 电路理论系列课程组 2005.3第三节第三节LU分解法解线性方程组分解法解线性方程组矩阵运算的计算机方法矩阵运算的计算机方法国家电工电子教学基地 电路理论系列课程组 2005.3算法说明算法说明设有方程组设有方程组其系数矩阵其系数矩阵A可以分解成下三角阵可以分解成下三角阵L与上三角阵与上三角阵U的乘
16、积的乘积即即其中其中国家电工电子教学基地 电路理论系列课程组 2005.3先解出先解出Y再解出再解出XLU分解法特点分解法特点（1）LU分解法：分解法：1次次LU分解，分解，1次前代，次前代，1次回代。次回代。乘除次数与高斯消元法相当。乘除次数与高斯消元法相当。（2）矩阵矩阵L和和U的值只与的值只与A的值有关，与的值有关，与B无关，重复解无关，重复解B变化变化A不变的方程组时，只进行一次分解即可不变的方程组时，只进行一次分解即可.算法说明算法说明国家电工电子教学基地 电路理论系列课程组 2005.3根据根据A A求得求得L L和和U U（LULU分解）分解）li1ai1u1j = a1j /
17、l11=a1j / a11 L第第1列列U第第1行行（i=1，2，n）（j2，3，n）国家电工电子教学基地 电路理论系列课程组 2005.3以以L的第的第行乘以行乘以U的第的第列列（ij）：）：（i j）：）：根据根据A A求得求得L L和和U U（LULU分解）分解）国家电工电子教学基地 电路理论系列课程组 2005.3矩阵矩阵LULU分解举例分解举例国家电工电子教学基地 电路理论系列课程组 2005.3矩阵矩阵LULU分解举例分解举例国家电工电子教学基地 电路理论系列课程组 2005.3简介简介LULU分解法求逆矩阵分解法求逆矩阵设设A=LU的逆矩阵为的逆矩阵为Z（1）W为为L的逆矩阵，由
18、于的逆矩阵，由于L为下三角矩阵，所以为下三角矩阵，所以W也是下三角矩阵。也是下三角矩阵。（2）由前代可得）由前代可得W。国家电工电子教学基地 电路理论系列课程组 2005.3习题与补充习题与补充P1.2，1.5补充补充1：读懂给出的读懂给出的LU分解法程序，用分解法程序，用程序计算求解程序计算求解xi国家电工电子教学基地 电路理论系列课程组 2005.3矩阵运算的计算机方法矩阵运算的计算机方法第四节第四节稀稀疏疏矩矩阵阵原原理理国家电工电子教学基地 电路理论系列课程组 2005.3稀疏矩阵稀疏矩阵大部分元素是零的矩阵叫稀疏矩阵大部分元素是零的矩阵叫稀疏矩阵用高斯法或用高斯法或LU分解来解方程组
19、所需的运算量近似于分解来解方程组所需的运算量近似于不进行这些与零有关的运算不进行这些与零有关的运算节省运算量节省运算量不存储零元素不存储零元素减少存储量减少存储量稀疏矩阵算法：稀疏矩阵算法： 不存储零元素，也不对零元素进行运算不存储零元素，也不对零元素进行运算运算量（及存储量）近似与成比例运算量（及存储量）近似与成比例节点方程：节点方程：个不接地的节点，个不接地的节点，B个两端无源元件，则矩阵个两端无源元件，则矩阵Y最多包含最多包含2B个非零元素。个非零元素。一般大规模的电路来讲，元件的数目是节点数目的二倍到四倍。一般大规模的电路来讲，元件的数目是节点数目的二倍到四倍。非零元素非零元素元素总数
20、元素总数n2国家电工电子教学基地 电路理论系列课程组 2005.3若进行若进行LU分解（不选主元素）分解（不选主元素）填入：填入：零元素变为非零元素零元素变为非零元素稀疏矩阵选主元例题稀疏矩阵选主元例题国家电工电子教学基地 电路理论系列课程组 2005.3把元素把元素a33作为主元素，即用行、列对换的办法将它放作为主元素，即用行、列对换的办法将它放在左上角位置在左上角位置原矩阵的分解需要原矩阵的分解需要8次乘（除）和次乘（除）和5次减，次减，改变后的矩阵仅仅需要改变后的矩阵仅仅需要4次乘（除）和次乘（除）和2次减次减适当地选择主元素可降低运算次数适当地选择主元素可降低运算次数矩阵内的零元矩阵内
21、的零元素经过素经过LU分分解仍然为零解仍然为零稀疏矩阵选主元例题稀疏矩阵选主元例题国家电工电子教学基地 电路理论系列课程组 2005.3再排序的实现再排序的实现在稀疏矩阵技术中，选择主元素被称之为再排序在稀疏矩阵技术中，选择主元素被称之为再排序再排序再排序简化搜索方法简化搜索方法矩阵的特性矩阵的特性局部优化准则局部优化准则主元次序最好主元次序最好方法简单方法简单权衡，折中权衡，折中对角元素非零对角元素非零非零结构通常近似对称非零结构通常近似对称以节点导纳矩阵为例：以节点导纳矩阵为例：保持结构对称性，即保持保持结构对称性，即保持L的非零结构与的非零结构与Ut的非零结构相同的非零结构相同主元素的搜
22、索限制在对角元素上主元素的搜索限制在对角元素上国家电工电子教学基地 电路理论系列课程组 2005.3常用的选主元素的准则常用的选主元素的准则1不进行再排序不进行再排序2方程式按照非零元素的数目排序，将有最少方程式按照非零元素的数目排序，将有最少非零元素的行首先编号，对列进行相应的排序。非零元素的行首先编号，对列进行相应的排序。3按最小非零元素规则，逐次排列各行，按最小非零元素规则，逐次排列各行，同时进行符号分解同时进行符号分解4使目前的处理阶段产生最少的填入：使目前的处理阶段产生最少的填入：最少局部填入准则。最少局部填入准则。国家电工电子教学基地 电路理论系列课程组 2005.3例例:图图中的
23、中的90分相网络，它有分相网络，它有17个不接地节点，个不接地节点，其节点方程中包含其节点方程中包含77个非零元素个非零元素C2C5C7C8C10C12C14C16R1C1C3C4C6C9C11C13C15选主元素的准则举例选主元素的准则举例国家电工电子教学基地 电路理论系列课程组 2005.3不同的排序技术对不同的排序技术对LU分解运算中存储和计算量的影响分解运算中存储和计算量的影响用用“x”表示原始的非零元素，用圆圈表示分解中的填入表示原始的非零元素，用圆圈表示分解中的填入对原始满阵完成对原始满阵完成LU分解（分解（计计算零元素）大约要算零元素）大约要1550次运算次运算选主元素的准则举例
24、选主元素的准则举例国家电工电子教学基地 电路理论系列课程组 2005.31.不重排不重排完成完成LU分解分解:有有68个填入个填入377次加乘次加乘选主元素的准则举例选主元素的准则举例国家电工电子教学基地 电路理论系列课程组 2005.32.首先排列首先排列具有最少非零具有最少非零元素的方程元素的方程LU分解分解:填入量填入量32运算量运算量209选主元素的准则举例选主元素的准则举例国家电工电子教学基地 电路理论系列课程组 2005.33.用最少非零用最少非零参数排序参数排序LU分解分解:填入量填入量14运算量运算量147选主元素的准则举例选主元素的准则举例国家电工电子教学基地 电路理论系列课
25、程组 2005.34.用最少局部用最少局部参量填入排序参量填入排序LU分解分解:填入量填入量12运算量运算量141选主元素的准则举例选主元素的准则举例国家电工电子教学基地 电路理论系列课程组 2005.3稀疏矩阵存储稀疏矩阵存储仅仅存储稀疏矩阵中非零元素的信息存储稀疏矩阵中非零元素的信息方法方法1：用：用3个数组个数组B、IB、JB存储稀疏矩阵存储稀疏矩阵A中非零元素中非零元素的信息，包括非零元素的数值、列号、行号信息。的信息，包括非零元素的数值、列号、行号信息。数组数组B：B（K）按先行后列顺序存储矩阵按先行后列顺序存储矩阵A中第中第K个非零元素个非零元素A（I，J）的数值的数值数组数组JB
26、：JB（K）是是数值为数值为B（K）表示的非零元素表示的非零元素A（I，J）在矩阵在矩阵A中的中的列号列号，即，即JB（K）=J数组数组IB：N+1维（维（N+1个元素）辅助整数相量个元素）辅助整数相量IB（M）是是A中第中第M行的起始位置在行的起始位置在JB和和B中所对应中所对应的位置的位置国家电工电子教学基地 电路理论系列课程组 2005.3A：有有12个非零元素的个非零元素的55矩阵矩阵JB：存储存储B（K）对应的非零元素对应的非零元素A（I，J）在在A中的列号中的列号B：顺序存储顺序存储A中中12个非零元素个非零元素B=JB=IB=IB：IB（M）是是A中第中第M行的起始位置行的起始位
27、置在在JB和和B中所对应的位置中所对应的位置稀疏矩阵存储举例稀疏矩阵存储举例国家电工电子教学基地 电路理论系列课程组 2005.3第五节第五节复复频频率率与与复复平平面面矩阵运算的计算机方法矩阵运算的计算机方法国家电工电子教学基地 电路理论系列课程组 2005.3 单边拉普拉斯变换单边拉普拉斯变换 单边函数单边函数f(t)的拉普拉斯变换：的拉普拉斯变换：其中：其中：拉普拉斯反变换：拉普拉斯反变换：拉普拉斯变换对：拉普拉斯变换对：拉普拉斯变换主要性质拉普拉斯变换主要性质线性线性微分微分积分积分国家电工电子教学基地 电路理论系列课程组 2005.3基本元件拉氏变换域基本元件拉氏变换域VARVAR模
28、型模型 电阻：电阻：阻抗阻抗Z导纳导纳Y电感：电感：零初值零初值电容：电容：零初值零初值一般形式一般形式国家电工电子教学基地 电路理论系列课程组 2005.3基尔霍夫约束的拉氏变换域模型基尔霍夫约束的拉氏变换域模型 拉氏变换域分析举例拉氏变换域分析举例其中其中国家电工电子教学基地 电路理论系列课程组 2005.3若激励电压源为一频率为若激励电压源为一频率为0 0的的余弦信号余弦信号：其中：其中：则：则：所以：所以：基尔霍夫约束拉氏变换举例基尔霍夫约束拉氏变换举例 由反变换求时域解由反变换求时域解：国家电工电子教学基地 电路理论系列课程组 2005.3拉氏变换求解电路的基本步骤拉氏变换求解电路的
29、基本步骤（1 1）由时域电路模型画出拉氏域电路模型由时域电路模型画出拉氏域电路模型（2 2）由拉氏域电路模型的由拉氏域电路模型的VARVAR及及KLKL建立代数方程；建立代数方程；（3 3）求拉氏域解；）求拉氏域解；（4 4）经过拉氏反变换及取实部运算后，就得到时域解。）经过拉氏反变换及取实部运算后，就得到时域解。 国家电工电子教学基地 电路理论系列课程组 2005.3复频率与复平面复频率与复平面由于由于s s1 1和和s s2 2与与j j0 0具有相同的量纲，因而被称为复频率具有相同的量纲，因而被称为复频率 复频率复频率s s = =+j+j：虚部虚部具有频率的意义，具有频率的意义， 称为
30、实频率（称为实频率（radrad/s)/s)； 实部实部反映了时域解的幅度增长或衰减，反映了时域解的幅度增长或衰减， 称为虚频率称为虚频率( (NpNp/s) /s) 。固有振荡频率：固有振荡频率：s1和和s2是网络阻抗是网络阻抗Z(s)=0的根，的根，（称为（称为Z(s)的零点），的零点），他们仅与网络的结构及元件值有关他们仅与网络的结构及元件值有关,因而和又被称为网络的固有振荡频率。因而和又被称为网络的固有振荡频率。国家电工电子教学基地 电路理论系列课程组 2005.3s s = =+j+j可用如下可用如下s复平面上的点表示复平面上的点表示复频率与复平面复频率与复平面国家电工电子教学基地 电路理论系列课程组 2005.3
