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

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