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

《第一章矩阵运算的计算机方法及稀疏距阵.ppt》由会员分享，可在线阅读，更多相关《第一章矩阵运算的计算机方法及稀疏距阵.ppt（59页珍藏版）》请在三一文库上搜索。

1、国家电工电子教学基地 电路理论系列课程组 2005.3,第一章 矩阵运算的计算机方法及稀疏距阵,现代电路分析,国家电工电子教学基地 电路理论系列课程组 2005.3,现代电路分析课程知识要点,经典电路分析知识要点,计算机辅助分析 及工具应用,矩阵方程 建立初步,矩阵方程建立 的一般方法,矩阵运算的 计算机方法,非线性电路 分析初步,非线性电路方程 建立的一般方法,有源滤波电路 分析初步,电路的 参数分析,国家电工电子教学基地 电路理论系列课程组 2005.3,本章主要内容及要求,了解LU分解法解线性方程组原理、应用及算法,了解高斯消元法解线性方程组原理、应用及算法,了解稀疏矩阵原理,国家电工电

2、子教学基地 电路理论系列课程组 2005.3,第一节 计算数学的几个基本概念,现代电路分析第一章,国家电工电子教学基地 电路理论系列课程组 2005.3,利用计算机解决实际问题，通常要按以下步骤进行： （1）建立数学模型，即把实际问题抽象为一个数学问题，他可以是一个方程组 、一个函数、一个微分方程等。,（2）选择数值方法，要考虑所能达到的精度，计算量，方法对数据微小扰动的灵敏度。,（3）编写程序，上机计算。,计算数学的几个基本概念,国家电工电子教学基地 电路理论系列课程组 2005.3,1、算法 2、计算量 例：计算 x255 按原型计算，计算量254次浮点运算 改用x255=x*x2* x4

3、* 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,例：Crame

4、r法则求解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、误差的基本概念： 准确值和近似值之间的差异就是所谓的误差。 误差产生主要是以下四个来源： （） 模型误差 （） 观测误差 （） 截断误差 （） 舍入误差 绝对误差、相对误差、有效数字,计算数

5、学的几个基本概念,国家电工电子教学基地 电路理论系列课程组 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 显然这是一个病态问题。,计算数学的几个

6、基本概念,国家电工电子教学基地 电路理论系列课程组 2005.3,若把方程的系数取三位小数,计算数学的几个基本概念,国家电工电子教学基地 电路理论系列课程组 2005.3,假定计算机字长为8，解为,计算机字长为8，解为,计算数学的几个基本概念,国家电工电子教学基地 电路理论系列课程组 2005.3,数值计算中值得注意的事项: （1） 要避免两个相近的数相减 。 （2） 防止大数吃掉小数。 （3） 防止接近零的数作除数。 （4） 减少运算次数。 （5） 防止舍入误差被放大。,计算数学的几个基本概念,国家电工电子教学基地 电路理论系列课程组 2005.3,习 题,1.1,计算数学的几个基本概念,国

7、家电工电子教学基地 电路理论系列课程组 2005.3,第二节 高斯消元法解线性方程组,矩阵运算的计算机方法,国家电工电子教学基地 电路理论系列课程组 2005.3,线性方程组的一般形式,国家电工电子教学基地 电路理论系列课程组 2005.3,nn矩阵的行列式：需要(n-1) n!次复数乘法,对11个节点的电路需要：32659200次乘法,对21个节点的电路需要：4.6 1019次乘法,用每秒亿次计算机：,高斯法约为330次乘除运算,高斯法约为2660次乘除运算,线性方程组经典解法（克莱姆法则 ）,国家电工电子教学基地 电路理论系列课程组 2005.3,举例说明高斯消元法,初等行变换,回代,原理

8、：通过初等变换化为三角矩阵,国家电工电子教学基地 电路理论系列课程组 2005.3,高斯消元算法说明,将第一个方程除以a11，并把它写成为,其中,将上式乘以-ai1，加到下面的n-1个方程上，得到,国家电工电子教学基地 电路理论系列课程组 2005.3,方程组变为,下一步我们排除第一行和第一列，对第二个方程至第个方程施以同样的处理，其公式变为,高斯消元算法说明,国家电工电子教学基地 电路理论系列课程组 2005.3,最后所得的方程组,系数矩阵为上三角矩阵,回代过程：求出未知量 xi,高斯消元算法说明,国家电工电子教学基地 电路理论系列课程组 2005.3,选主元素举例,3位有效数字,注意：由于

9、除以较小数， 会得到较大的系数,注意：这是一个较小的数 与较大的数的差,注意：近似后误差较大,国家电工电子教学基地 电路理论系列课程组 2005.3,改变主元素,注意：由于除以较大数， 会得到较小的系数,注意：这是一个较小的数 与较小的数的差,选主元素举例,国家电工电子教学基地 电路理论系列课程组 2005.3,取3位有效数字,注意：近似后有较小误差,结论 主元素（对角线上的元素）越大，精度越高。,选主元素举例,国家电工电子教学基地 电路理论系列课程组 2005.3,选主元素,改善线性方程组解的精度,使计算能够进行,交换系数矩阵行/ 列，使|aii|尽量大,列主元素,从当前列系数中选择一个绝对

10、值最大的元素 这种方法不需要改变变量的顺序，只交换行,全主元素,在整个剩余的矩阵中搜索绝对值最大的元素 全主元素则需要改变变量的顺序，需要交换列,选主元素,国家电工电子教学基地 电路理论系列课程组 2005.3,高斯法求逆矩阵（自证）,初等行变换,国家电工电子教学基地 电路理论系列课程组 2005.3,习题与补充,P 1. 2，1. 5,补充2： 读懂给出的矩阵求逆程序， 画出简单流程图,补充1： 读懂给出的高斯消元法程序，用 程序计算求解xi,国家电工电子教学基地 电路理论系列课程组 2005.3,第三节 LU分解法解线性方程组,矩阵运算的计算机方法,国家电工电子教学基地 电路理论系列课程组

11、 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）,国家电

12、工电子教学基地 电路理论系列课程组 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分解法程序

13、，用 程序计算求解xi,国家电工电子教学基地 电路理论系列课程组 2005.3,矩阵运算的计算机方法,第四节 稀 疏 矩 阵 原 理,国家电工电子教学基地 电路理论系列课程组 2005.3,稀疏矩阵,大部分元素是零的矩阵叫稀疏矩阵,用高斯法或LU分解来解方程组所需的运算量近似于,不进行这些与零有关的运算,节省运算量,不存储零元素,减少存储量,稀疏矩阵算法：,不存储零元素，也不对零元素进行运算,运算量（及存储量）近似与成比例,节点方程：,个不接地的节点，B个两端无源元件，则矩阵Y最多包含2B个非零元素。,一般大规模的电路来讲，元件的数目是节点数目的二倍到四倍。,非零元素元素总数n2,国家电工电子

14、教学基地 电路理论系列课程组 2005.3,若进行LU分解（不选主元素）,填入：零元素变为非零元素,稀疏矩阵选主元例题,国家电工电子教学基地 电路理论系列课程组 2005.3,把元素 a33 作为主元素，即用行、列对换的办法将它放在左上角位置,原矩阵的分解需要8次乘（除）和5次减， 改变后的矩阵仅仅需要4次乘（除）和2次减,适当地选择主元素可降低运算次数,矩阵内的零元素经过LU分解仍然为零,稀疏矩阵选主元例题,国家电工电子教学基地 电路理论系列课程组 2005.3,再排序的实现,在稀疏矩阵技术中，选择主元素被称之为再排序,再排序,简化搜索方法,主元次序最好,方法简单,权衡，折中,对角元素非零

15、非零结构通常近似对称,以节点导纳矩阵为例：,保持结构对称性，即保持L的非零结构与Ut 的非零结构相同 主元素的搜索限制在对角元素上,国家电工电子教学基地 电路理论系列课程组 2005.3,常用的选主元素的准则,1不进行再排序,2方程式按照非零元素的数目排序，将有最少 非零元素的行首先编号，对列进行相应的排序。,3按最小非零元素规则，逐次排列各行， 同时进行符号分解,4使目前的处理阶段产生最少的填入： 最少局部填入准则。,国家电工电子教学基地 电路理论系列课程组 2005.3,例 : 图 中的90分相网络，它有17个不接地节点， 其节点方程中包含77个非零元素,选主元素的准则举例,国家电工电子教

16、学基地 电路理论系列课程组 2005.3,不同的排序技术对LU分解运算中存储和计算量的影响,用“x”表示原始的非零元素，用圆圈表示分解中的填入,对原始满阵完成LU分解（计算零元素）大约要1550次运算,选主元素的准则举例,国家电工电子教学基地 电路理论系列课程组 2005.3,1. 不重排,完成LU分解: 有68个填入 377次加乘,选主元素的准则举例,国家电工电子教学基地 电路理论系列课程组 2005.3,2. 首先排列 具有最少非零 元素的方程,LU分解: 填入量32 运算量209,选主元素的准则举例,国家电工电子教学基地 电路理论系列课程组 2005.3,3. 用最少非零 参数排序,LU

17、分解: 填入量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

18、维（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)的拉普拉斯变换：,

19、其中：,拉普拉斯反变换：,拉普拉斯变换对：,拉普拉斯变换主要性质,线性,微分,积分,国家电工电子教学基地 电路理论系列课程组 2005.3,基本元件拉氏变换域VAR模型,电阻：,阻抗Z,导纳Y,电感： 零初值,电容： 零初值,一般形式,国家电工电子教学基地 电路理论系列课程组 2005.3,基尔霍夫约束的拉氏变换域模型,拉氏变换域分析举例,其中,国家电工电子教学基地 电路理论系列课程组 2005.3,若激励电压源为一频率为0的余弦信号：,其中：,则：,所以：,基尔霍夫约束拉氏变换举例,由反变换求时域解：,国家电工电子教学基地 电路理论系列课程组 2005.3,拉氏变换求解电路的基本步骤,（1）

20、由时域电路模型画出拉氏域电路模型 （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复平面上的点表示,复频率与复平面,