求符号系统函数的新算法——状态空间树法

D0I:10.13374/j.iss1001-053x.1990.0M.026 第12老第4期 北京科技大学学报 Vol.12 No.4 1990年7月 Journal of University of Science and Technology Beijing July 1990 求符号系统函数的新算法 状态空间树法 黄汝激· 清要：应用LIF0分支-定界搜素法和状态空间树概念，提出了求符号行列式的新算 法SSTMSD一行列式的状态空间树法（它是Mity算法的发展和改进），根据它并应用 变形田麻念提出了求符号系统函数的新算法SSTMSF一一系联函数的状态空间树法。 关铺词：符号系统函数，状态空间树，变形图 A New Algorithm for Finding Symbolic System Functions -State Space Tree Method Huang Ruji* ABSTRACT:A new algorithm SSTMSD for finding symbolic determinants-sta- te space tree method for determinants is presented by applying LIFO branch-and- bound search technique and the concept of state space tree (it is the development and improvement of Minty algorithm).Based on it and by applying the concept of modified graphs,a new algorithm SSTMSF for finding symbolic system functions-state space tree method for system functions is proposed.As compared with the current conventional methods (e.g.signal flow graph method and directed tree method,etc.),SSTMSF has the following two advantages:(1) Its computing efficiency is higher and its resulted expressions are shorter.(2) The denominator (determinant)and numerator (cofactor)of a symbolic system function can be separately found by repeatedly call the same one procedure 1989-06-23收稿 ·月动化系(Department of Automation and Control Engineering) 356

第 卷第 期 年 月 北 京 科 技 大 学 学 报 碑子 ， 求符号 系统函数的新算法 — 状态 空 间树法 洲 护 黄汝激 ， 摘 要 应 用 分支 一 定 界搜素 法和状 态空间树概念 ， 提出 了求符号 行列 式 的新算 法 — 行 列 式的 状 态空间 树法 它 是 算法 的 发 展 和 改进 ， 根 据它 井 应 用 变形图 旅念提 出了求符号 系统 函数的新算祛 —系联 函数 的 状态空间树法 。 关锐 词 符号系统函数 ， 状 态空 间 树 ， 变形 图 一 万 ， 夕 ‘ —一 卜 ， 人 一 手 ， 一 手 。 、 ， ， 入 ， 一 。 · 、 · ， 。 ， 歹 丁 手 · ， 一 一 一 收 稿 自动化 系 ” 母 DOI ：10．13374／j ．issn1001—053x．1990．04．026

SSTMSD.] KEY WORDS:symbolic system function,state space trec,modified graph 符号系统函数T:是表征线性系统的重要函数。应用它可以直观地洞察系统特性与系统 参数之间的函数关系，而且当求T对于某一参数，例如频率的关系曲线时，只需对若干个 不同的f值计算对应的T:(f)值，这比多次重复分析整个系统（重复求解系统方程）要简单 得多。从它还可导出符号灵傲度函数，从而大大简化一个系统的优化设计工作。 求符号系统函数的常用的非分解的图论方法有：Mason信号流图法r1),Coates流图 法r2?,Mayeda完全树法rs),Chcn负根有向树法r4?,Roland信号流图法和作者提出的 正根有向树法6)及主子图法：7)。它们有两个共同缺点：(1)对应于行列式各项的子图、完 全树或有向树是一个一个地求出的，所以计算效率较低，所得表达式较长。例如，有向树法 的表达式含有n:项，计算复杂度为O(en:),这里n:和e各为有向图的有向树数和边数。(2) 符号系统函数的分母（行列式）和分子（余因式）的拓扑表达式不相同，因此或者要用两个 不同的子程序进行计算‘14？，或者用一个子程序但要从结果中把分母项与分子项分开3，？) 这增加了程序长度和计算时间。本文目的是克服这两个缺点。 1基本原理 考虑一个线性系统S,它的复频域矩阵方程（系统方程）为： YV=J,Y=〔-yax,J=〔J,x1,V=〔Vx1 (1) 式中J为输入列向量，V为输出列向量，Y为系统参数矩阵，则从输入变量J到输出变量V,的 传递函数（系统函数）为： T=么分，D=Y,D=Yw (2) 式中D和D!分别为矩阵Y的行列式和一阶余因式。若系统参数不用数值表示，而用变量符号 y表示，则T1是y,的函数，称为符号系统函数。 首先，应用状态空问树概念？8)和LIFO分支-定界搜索法8设计了一个求符号行列式D 的新算法SSTMSD一状态空间树法。它是Minty算法的改进和发展。Minty算法是较好 的求树算法，但它是逐个地求出无向树，得到的是展开了的无向树权多项式，含有：项，计 算复杂度为O(n:),这里n,为图的无向树数。所以它也有计算效率较低、表达式较长的缺 点，而且它仅适用于无向图，即仅适用于求对称的符号行列式。为了克服这些缺点和计算一般 非对称的符号行列式，算法SSTMSD中应用正根树概念把Mity算法发展成适用于有向图； 更主要的是应用LIFO分支-定界搜索法中状态空间树概念和下文中的定理1把Minty算法改 进成计算效率较高的算法，即不是逐个地求正根树，而是直接求出一个等于行列式D的紧凑 的（非展开了的）正根树权多项式（这是SSTMSD与Minty算法的主要区别）。它的计算时 间复杂度为O(en1),这里e为混合图的边数，n1为算法中状态空间树的叶数。通常n1《n:, 所以算法SSTMSD的计算效率高于上述的常用图论方法（包括Minty算法）。 357

。 〕 乃 · ， ， 符 号系 统 函数 ， 是 表征线 性 系统的 重要 函数 。 应 用它 可 以直观 地洞察系统特性 与 系统 参数之 间的 函数关 系 ， 而且当 求 ，、对于 某一 参数 ， 例如频率 的关 系曲线 时 ， 只需对若 干个 不 同的 值计算对应的 、 值 ， 这比 多次重 复分析 整个 系统 重 复求解系 统 方程 要 简单 得 多 。 从它 还可 导 出符 一 号灵敏度 函数 ， 从而大大简化一 个系统的优化设计工作 。 求 符号系统 函数 的常用 的非 分 解 的 图 论 方 法有 信 号流 图法 〔 ’ 〕 ， 流 图 法 〔 〕 ， 完全树法 〔 “ ’ ， 负根 有 向树法 〔 ‘ 〕 ， 信 号流 图法 〔 〕 和作者 提 出的 正根 有向树 法 叮 “ 〕 及 主 子 图法 〔 〕 。 它们 有 两个共 同缺点 对应于 行列 式 各项 的子 图 、 完 全树或 有向树是一 个一 个地求 出的 ， 所 以计算效 率较 低 ， 所得表达式较 长 。 例如 ， 有 向树法 的 表达式含 有 、 项 ， 计算复 杂度 为 。 。 ， 这 里 ，和 。 各为 有 向图的 有 向树数 和 边数 。 符号系统函 数 的 分 母 行列式 和 分子 余因 式 的 拓 扑 表达式不相 同 ， 因 此或 者要 用 两个 不 同的子程 序进 行计算 〔 ” ‘ 〕 ， 或 者用一个子程 序 但要 从结 果 中把 分 母项 与分 子项 分开 〔 ，” ’ ， 这增 加 了程 序 长 度和 计算时 间 。 本 文 目的是克 服 这 两 个 缺点 。 基 本 原 理 考虑一 个线 性 系 统 ， 它 的复频域矩 阵方程 系统方程 为 犷 了 ， 〔 一 夕 ‘ 〕 。 、 ， ， 〔 ‘ 〕 。 、 ， 犷 〔犷 〕 。 、 、 、 式 中 为输入 列向 量 ， 犷为 输 出列 向 量 ， 为 系统 参数矩 阵 ， 则 从输人 变 量 、 到 输 出变 量犷 ，的 传递 函数 系统函数 为 ， ‘ ， 一 二 一 “ “ 一 亏万 万 ， 刀 “ ， 刀 “ 艺 ‘ ，‘ ， 加 式 中 和 。 分别 为矩阵 的行列 式和一阶余因式 。 若 系统参数不用数值表示 ， 而 用变 量符号 ‘ ，表示 ， 则 ， 是 ‘ ，的 函数 ， 称为 符号系统 函 数 。 首先 ， 应 用 状 态空 间树概 念 〔 ’ 和 工 分支 一 定界搜索 法 〔 “ 〕 设 计 了一 个求 符 号行 列式刀 的新算法 — 状 态空间树法 。 它 是 算法 亡 ” “ 的改 进和发展 。 算法是较好 的求树算法 ， 但它 是逐个地求出无 向树 ， 得到 的是展开 了的无 向树权多项式 ， 含有 项 ， 计 算复杂度为 、 ， 这 里 。 ，为 图的无 向树数 。 所 以它 也 有 计算效 率 较低 、 表 达式较长的缺 点 ， 而且它 仅适 用 于 无 向图 ， 即仅适 用于求对称 的 符号行 列式 。 为 了克服这些 缺点和计算一般 非对称 的 符号行列 式 ， 算法 中应用 正根树 概念把 算法发展 成适用于 有向图 更主要 的 是应用 分支 一 定界搜索法 中状态空 间树概 念 和下 文 中的定理 把 算法 改 进成计算效率较 高的算法 ， 即不 是逐个 地求 正根树 ， 而是 直接 求 出一 个等于 行列 式 的紧凑 的 非展开 了的 正根树 权 多项 式 这是 与 算 法的主要 区别 。 它 的 计算时 间复杂度为 。 ， 这 里 为 混合 图的边数 ， 为 算法 中状态空间树的 叶数 。 通 常 《 。 、 ， 所 以算法 的计算效率高于 上述 的常 用 图论方法 包括 算法

其次，应用变形图概念和算法SSTMSD提出了一个求符号系统函数的新算法SSTMSF, 其中重复调用引同一个子程序SSTMSD就可分别求出紧凑的分母表达式和分子表达式，省去了 文献〔3，T)等中从结果内把分母项与分子项分开的闲雅工作。因此，新算法SSTMSF克服了 上述常用图论方法的两个缺点。 2求符号行列式D的新算法SSTMSD 设系统参数矩阵Y=〔-y:,门、，是非奇异的，m=n+1,若添上如下的第m行和第m列： -y=B,j=1,2,…,n (3a) 少=沿y,i=1,2,…,m (3b) 则得一等余因式阵Y,，称为系统S的不定参数矩阵。它的伴随混合图记作G·(对于电网 络，它的不定导纳阵Y·及其伴随混合图G·可直接从电路图得到)。设G·的有向边(Y·的非 零非对称元素)数为a,无向边（非零对称元素对)数为4，则总边数e=a+“。规定边的编 号顺序：先有向边，后无向边。定义G·的混合关联阵A如下： (1,若点是边h的起点（若h为有问 边)或顶点（若h为无向边）， A(i,h)= -1,若点是有向边h的终点影 (4) 0,若点不是边h的顶点。 Y·的任一元素的一阶余因式就是|Y|。为了减小叶数1，可选出度较小的点（例如k) 为正根r,根据文献〔6)有D=IY|=G·中所有带正根k的有向树的权之和DTS。(5) 为了简化算法，就不一一地求正根树，而是应用LI℉O分支-定界搜索法及其状态空间树 概念【)从G·中求得一个等于DTS的正根树权多项式DTP,该算法记作SSTMSD。这个算 法克服了“前言”中提到的常用图论方法（包括Mity算沾）的第一个缺点。 引人下列记号：E,E2一存贮混合图G中e条边之起点号和终点号的二数组，A(:, )一混合关联阵的第行；HE一正根关联向量；M一融点数组，B一移边数组，XE, YE一存：缩减边组集合的二数组，FL一父号数组影VS一子数数组；df一状态空间树T的 节点号，ef一YE的计数器，f1一父号，ns一子数，n1一叶数；q一融合点数；t一栈指针， e=a+一G·的边数，w=m-2一栈长，n。,一T的节点总数（根点0除外)多n。【一缩减边 总数。选点k为正根r,则算法SSTMSD的步骤如下。 算法SSTMSD: (1)初始化：q-1,t4-0,w-m-2:df0,ef←1，f1←-0，n:-0,M-(1…1), M(r)0,B(1…1),HEA(r,)；令G·对应于T的状态节点0（根），赋于权SE(0)= 1。 (2)从IIE找出并移去指向正根r的所有有向边h,B(h)0(因为这些边不属于任正 根树)。 358

其次 ， 应 用变形 图概念和算法 了 提出 了一 个求符 号系统函数的新算法 ， 其 中重 复调 用 同一 个 子程 序 就可分 别求 出紧 凑的 分 母表 达 式和分 子表 达 式 ， 省 去 了 文献 〔 ， 〕 等中从结 果 内把 分 母项 与 分 子项 分开 的 困 难 工 作 。 因此 ， 新 算法 克 服 了 上 述 常 用 图 论方法的 两个 缺点 。 求符号行列式 的新算 法 设 系统 参数矩阵 〔 一 ‘ ， 〕 。 是非奇异的 ， “ ” ， 若 添上如 下的 第， 行 和 第， 列 一 ， 二 ，， ， ， … ， 心一 一 ‘ 二 二 ‘ ， ， 二 ， ， 一 ， 阴 一 则得 一等 余 因式 阵 ， 称 为 系 统 的 不 定 参数 矩阵 。 它 的伴 随 混 合 记 作 对 于 电网 络 ， 它 的不 定导纳阵 及 其伴随 混 合 图‘ 可直接 从 电路 图得 到 。 设‘ 的 有向边 的 非 零非 对 称元 素 数 为 。 ， 无向 边 卜零对 称 元 素对 数 为 ， 则 总边 数 。 二 十 “ 。 规 定边的 编 号顺 序 先有向边 ， 后 无向 边 。 定 义 ’ 的 混合 关联 阵 如下 一 ， ， 若 点 是 边 的起 点 若 为 有向 边 或顶点 若 为 无向边 ， 若 点‘是 有 向边 的 终点 若 点 不 是 边 的 顶 点 。 、 一 份 力 、产 的 任 一 元 素的 一阶 余因 式就是 。 为 了减 小叶 数 ” ， ， 可 选 出度较小的点 例如幻 为 正 根 ， ， 根 据 文献 〔的 有 ’ 中所 有带 正根寿的 有 向树的 权之 和 。 为 了简化 算法 ， 就不 一 一地求 正根 树 ， 而是 应 用 分 支 一 定界搜 索 法及其状 态 空间树 概 念 〔 ’ 从 ’ 中求 得 一 个等于 的 正 根树 权 多项 式 ， 该算 法 记作 。 这 个 算 法克 服 了 “ 前言 ” 中提到 的常 用 图论 方 法 包活 算法 的 第一 个缺点 。 引人 下 列记 一 号 ，， 一存贮 混 合图 ’ 中 仑 条 边 之 起 点号和终 点 一 号的 二数 组 ’ ， 一 混 合关 联阵述 的 第 讨了 一 正 根关 联 向 量 ， 一融 点 数 组 一 移 边数组 ， 一存贮 缩减 边组 集 合的 二 数组 一 父 号数 组 一子 数 数组 一状 态空间树 的 节点 号 一 的 计数 器 一 父 号 ” ‘ 一 子 数 ， ” ￡一叶 数 一融 合 点 数 卜栈指针 。 二 。 一‘ · 的边数 。 一 一 栈 长 。 ‘ ， 一 的 节点 总 数 根 点 。 除 外 ， ” ，一 缩减 边 总数 。 选 点 九为 正 根 ， 则 算法 的步骤 如 下 。 法 护 初 始 化 ， ， 。 附 一 ， ， ， ， ， ， ， 一 卜 · ， ， 令 ’ 对 应于 的 状 态节 点 根 ， 一 ， 赋于 权 二 从 找 出 片移 去指向 正 根 的所 有 有向边 ， ‘ 一 因 为这 些 边不 属 于 任何 正 根树

(3)处理目前子图（缩减图G。或出栈的部分图G,:从HE搜索根r的一条射出边g及其 所有并联边，找出边9的另-一端点。对于边g及其并联边，只有两种可能：①它们不属于将 要寻找的正根树，可把它们移去；②它们中之一条属于将要寻找的某个正根树，可将它们缩 减。因此节点df分成两支：①移去搜索到的那些边，得一部分图G。(它的父号fI=df,若 G,中点r的射出边数不为0(21=1)而且点的射入边数不为0(22=1)，则将Gp存人栈，即t t+1,Sq(t)q,SfI(t)f1,SM(t,）←M,SB(t,)B,SHE(t,）HE, NS(f1)←NS(fI)+1;②缩减搜索到的那些边，得一缩减图Gc(它的父号f1=df),令它 对应于第df+1号状态节点，即df←df+1,XE(df)←f,FL(df)←fl,NS(f1)← NS(f1)+1,把缩减边组存人数组{YE(XE(df),…,YE(XE(df+1)-1)},赋于节 点df以权SE(df)=YE(XE(df)+…+YE(XE(df+1)-1),f1←df,把点融合到根r,即 q-q+1,M(i)-0,HE←〔HE+A(i,)〕*B,若G.中根r的射出边数不为0(21=1)， 则回到(2)（继续处理该缩减图G。),否则转到(4）。 (4)若g0，则出栈，即取出一个部分图G,回到(3)（处理该G)。 (7)若=0，则停止搜素，搜索过程形成了一棵正根状态空间树8T,从T按下面定理 1所述方法可打印出所要求的正根树权多项式DTP。 定理」按状态空间树T中节点标号df的顺序写下它的所有节点权SE(df),并插人一些 符号‘+’、‘(：和‘)”，使得每深子树的权等于该子树的根权乘以其所有子子树权之 和，这样构成一个多项式P,就是混合图G'的正根树权多项式DTP,它的展开式的每一项 P,恰是G·的一棵正根树的权，而且从T的根0到每个叶点的通路的权恰是G·的一个正根树 组的权。 证：注意G·的对成于每项P,的子图包含m-1条边而且不含回路，因此它是G·的一棵 树，步骤(2)~(4)保证它是一棵正根树。对于任一边h,仅有G·的两类正根树，一类含有边 ,另一类不含边h,所以步骤(3)、(5)和(6)保证无重复地产生全部正根树，从而DTP= DTS,证毕。 3求符号系统函数的新算法SSTMSF 、 把等余因式阵Y·的第m行加到第k行，第m列加到第I列后，去掉第m行和第m列，所得 矩阵记作Y“。显然Y“仍是一个等余因式阵，它的一阶余因式Y)=Y)=D:。 Y·的伴随混合图记作G·,从G·去掉射入点1的边y,m,i=1,，…,”,所得图称作G的 变形图，记作G“。根据式(5)和定理1可得： 推论1非奇异方阵Y的一阶余因式D:可通过变形图G表达成： D,=卫·=G'中所有带正根1的有向树的权之和DTS =G'的正根树权多项式DTP (6) 若选点1为正根，则射入点1的有向边（对应于Y·中第I列元素）将被去掉。因此实际上 不必把Y·的第m列加到第！列，只需把第m行加到第行；这对应于在G·中移去点m的所有射 入边后，把点m融合到点k,得到图G“;还对应于从A(m,)中去掉所有元素-1后， 359

处 理 目前子 图 缩减 图 。 或 出栈 的部分 图 口。 从 搜索根 的一 条射 出边 及其 所 有 并联边 ， 找 出边 的另 一端点 。 对于 边 及 其并联 边 ， 只有 两种可 能 ①它 们不属于将 要 寻找 的正根树 ， 可 把它 们移去 ②它 们 中之一 条属 于将 要 寻找的 某个 正根 树 ， 可将它 们 缩 减 。 因 此节点 分成两 支 ①移 去 搜索到 的 那些 边 ， 得一 部分 图 ‘ 。 它 的 父 号 ， 若 中点 的射 出边 数不为 。 而且 点 的射入 边数不为 。 二 ， 则将 存 人栈 ， 即 ， ， “ ， 万 ， ， ， ， ， ， 万 十 ②缩减 搜 索 到 的 那 些边 ， 得一缩减 图 ‘ 它 的父 号 二 ， 令它 对 应 于 第 号 状 态 节 点 ， 即 ， 汀 ， 小 ， 万 ， 把 缩减边 组 存 人数组 ， … ， 一 ， 赋 于 节 点 以 权 … 一 ， ，把点 融合到 根 ， 叩 ， ， 万 〔 ， 〕 朱 ， 若 。 中根 的 射 出 边 数 不为。 ， 则 回到 继续处 理 该缩减 图 。 ， 否则转 到 。 若 。 不连通 ， 则 去掉 该 ， 即清除状态 节 点 所 属 的分 支 ， 转到 。 若 ， 则 节点 是叶 ， 并 已产 生它 的对 应 正 根 树 组 ， 。 。 ， 十 ， 转到 。 若 ， 则出栈 ， 即 取出 一 个部分 图口 ， 回到 处 理该 。 若 ， 则停止搜 索 搜 索过 程形成 了一棵 正根 状 态 空 间树 〔 “ 】 ， 从 按下 面定理 所 述方法可打 印出所 要 求的正 根树 权 多项 式 。 定 理 按状态 空 间树 中韦点 标 号 的顺序写 下它 的所 有 节点权 ， 并擂人 一 些 符 号 ‘ 十 ’ 、 ‘ ’ 和 ‘ ’ ， 使 得每裸 子树 的权等于该 子树 的根权乘 以其所 有子子树 权之 和 ， 这 样构成 一个多项 式 ， 就是 混 合 图 ’ 的正 根树权 多项 式 ， 它 的展开 式的每 一项 尸 、 恰 是 ’ 的 一棵 正 根 树 的权 ， 而且 从 的根 。 到 每个叶点 的通 路的权恰是 的一个正 根 材 组 的权 。 证 注 意 ’ 的对应于每项尸 的 子 图包含 一 条边而 且 不 含 回路 ， 因此它是 的 一裸 树 步 骤 一 保证它 是 一棵 正根树 。 对于 任 一边 ， 仅有 ‘ 的两 类正根树 ， 一类含有边 ， 另 一 类不含边 ， 所 以步骤 、 和 保证 无 重 复 地 产 生全部 正根树 ， 从而 ， 证 毕 。 、 、 · 、 ‘ ‘ 求符号系统函数 的新算法 把等余因 式阵犷 ‘ 的第。 行 加到 第及行 ， 第二 列 加到 第 列 后 ， 去掉第 川 行和 第优列 ， 所 得 矩阵记作 ’ 。 显 然 ’ ‘ 仍是 一个等余 因式 阵 ， 它 的 一 阶 余 因 式 〔 〕 份六 二 兮六 二 ‘ ， 。 ” 的 伴随 混 合 图记作 “ ， 从“ ’ 去 掉射人 点 的边 少 ， ， 二 ， … ， ， 所 得 图 称 作 ’ 的 变形 图 ， 记作 寿 ‘ 。 根据 式 和定理 可 得 推 论 非奇异方阵 的 一阶余因式 、 ，可 通过变形 图 为 ‘表 达成 、 牡 “ 中所 有带 正根 的有 向树 的权之和 二 儿 ‘的正 根树权 多项 式 若选 点 为 正 根 ， 则射人点 的有 向边 对应 于 ” 中第 列 元 素 将被去掉 。 因此 实际上 不 必把 ’ 的 第 列 加到 第 列 ， 只需把 第。 行加 到 第舟行 这对 应 于 在‘ ’ 中移去点 的所有射 入 边后 ， 把 点 爪 融 合到 点 ， 得到 图 趾 ’ 还对 应于从 ， ， 中 去 掉所 有元 素 一 后

A(k,）-A(k,）+A(m,)。“副去第m行”对应于m←m-1,“选点1为正根r”对 应于r←1。于是可调用子程序SSTMSD求D。这克服了“前言”中提到的常用图论方法的 第二个缺点。 根据上述原理和算法，可编出采用SPAPK语言t8的求符号系统函数T:,的程序SSTMSF 如下。 Program SSTMSF //Given the indefinite parameter matrix Y=[-y.of a systcm S,find its transfer function T(1,k)=D(k,1)/D by the pesitive-rooted-tree-polynomial algorthm.// global n,a,u,k,1,Ei(e),Ea(e) integer h,i,j,m,e,r array E(e),A(m,e),B(e) 1.read n,a,u,k,1,E1,Ea 2。m-n+1;e-a+ugrs-h 3.for i+-1 t)m d.for h+-1 to e do A(i,h)+-0 repeat repcat forh←1 to a do i-E1(h)；j←E,(h);A(i,h)←1；A(i,h)+-1,E(h)←-1 repeat for h+-a+1 to e do i+E:(h);j+-E2(h);A(i,h)+-1:A(j,h)+1;E(h)+-1 repeat for h+-1 to e do B(h)+-1;HE(h)+A(r,h)repeat 4,print‘D=;call SSTMSD(a,e,m,r,A),r←1 5.for h+1 to e do ifA(m,h)=-1 then B(h)←O,HE(h)←0 else B(h)←-l;HE(h)←A(r,h) endif if A(m,h)=1 then A(k,h)-A(k,h)+A(m,h) ifh>a then j←E1(h)+E,(h)-m;A(j,h)←A(k,h)-2,E(h)←-1 endif endif repeat;m+-m-l,n←n-1s 6.print‘D('k‘,’l)=’;call SSTMSD(a,e,m,r,A) 7.print T('1‘,'k‘)=D('k‘,,l‘)lD' 8.end SSTMSF 程序SSTMSF的计算时间复杂度（主要决定于-子程序SSTMSD是O(er,),打印时间复 杂度是O(n。t),空间复杂度对于输出数组XE、YE、FL和NS是n。t+3(n:r+1),对于其 他数组是O(ne)。通常n:远小于混合图G中有向树的总数n:,所以正根树多项式法的计算 效率远高于有向树法等惯用方法。 4应用举例 例.已知一线性系统S,具有参数矩阵 360

， ， 一 掩 ， 用 ， 。 ，’ 删去 第“ 行 ” 对应 于 ， 一 ， “ 选点 为 正 根 ” 对 应 于 ， 。 于 是可 调 用 子程序 入巧 求 ‘ 。 这 克 服 了 “ 前言 ” 中 提到 的 常用 图论 方法 的 第二 个缺 点 。 根据 上述 原 理和 算法 ， 可 编 出采用 语 言 ‘ 吕 ’ 的求 符 号系统 函 数 ‘ 。 的程序 入 如 下 。 二 〔 一 夕 ‘ ， 〕 、 ， 歹 ， ， 儿 九 ， 刀 一 一 一 。 ” ， ， ， ， ， ， ， ‘ ， ， 川 ， ， ， 用 ， ， ， ， 。 ， 舟 ， ， ， 阴 月 ， ，一 “ 儿 、 ‘ 、 ‘ ， 〔 ’ ， 一 八 ， ， ， ， ， 一 ， 一 ‘ 十 ， ， ， ， ， ， ， ， ， ， ， ， ‘ ’ ， ， ， ， 月 ， ， 十 阴 ， 一 ， ， ， ， ，刁 ， 优 ， 一 ， ， ， 阴 ， ， ， 一 川 ， ， 掩 ， 一 ， 一 优 ‘ 优 一 卜 一 ‘ ’ ‘ ， ’ ‘ ， ， ， 口 ， ， ， ， ‘ ’ ‘ ， ’ ‘ ’ ‘ ， ’ ‘ ’ 。 入 程序 的计 算时 间复杂度 上要 决 定 于 子 程 序 是 。 。 ， 打 印时 间复 杂度是 。 。 ， 空 间 复杂度对 于输 出数组 、 、 和 是 ， 。 。 ， ， 对 于其 他 数 组是 。 。 通常 ” ， 远 小 于 混 合 图夕 ’ 中有向树的总 数” ‘ ， 所 以 正根 树多项 式法的 计算 效率 远 高于 有向树法等惯 用 方法 。 户声 ‘ 尸声 ， 产 应 用 举 例 例 已 知一 线性 系统 ， 具有 参数 矩阵

/-y11-y120 0 -y21-y22-y23-y24 Y= -y31-y32-y330 0 -y42-y43-y44 y12+ys1-y12 0 0 -y21 y12+y32+y42+y52-y23 -y24 -y31 -y32 y23+y43+y530 0 -y42 -y43 y24+y54 式中y21=y12+91,y31=-91,y3?=y2a+91,y43=y24,y43=-92,y53=y35+ g:(实际上，这里的系统S是一个二级晶体管放大器的等效电路，Y是它的节点导纳矩阵， g1和g是电路中两个晶体管的互导，y12、y23、y24、y35、y。1、y52和y4是支路导纳)。 求系统S的符号传递函数T41(即电路从输入口(1,5)到输出口(4,5)的开路转移阻抗)。 解：因n=4,m=5,=1,1=4,根据式(3a)和(3b)可得等余因式阵Y·的第5行元素 为y51,y52,y53和y5,第5列元素为y15=y51,y25=y52,y35,y45=y54+g2, y=y51+y52+y53+y4。据据第2、3节所述原理，从Y·可求得混合图G·和变形图 G1‘,如图1(a)和()所示，图中边旁整数为边号，a=10,u=3,e=13。从而E1=(1,2, 3,2,3,4,3,5,4,5,1,2,2),E2=(2,1,1,3,2,3,5,3,5,4,5,4,5)。 根据程序SSTMSF可求得G·和G1‘的对应状态空间树T和T14,如图1(c)和(d)所示。图中圆圈 内的整数为状态节点号，圆圈下的表达式中的整数为被缩减的并联边号，“+”表示并联。 12 12 11 13 10 (b) (a) 1 ① 11 0 ② 18 ③ ④ f12 13 6 ©@②④國國 ① 7:11-1312 810+126 5+1310 ② 12+134 12 ④ ⑦ ⑨ 5+12 ⊙⑥⑨①@© ④②由⑦③m ② ③ ① 16+12910+1267+98 10+1212512+134 12 61+5+12+13 2 1+8 (e)T (d) T14 图1系统S的混合图(a)G·、(b)G及其状态空间付(C)T、(d)T1 Fig.1 The Composite graphs (a)c',(b)Gi and their state space tress (c)T,(d)Tis of a system S 361

厂 一 夕 ’ ‘ 一 少 ‘ 断 ’ ‘ 一 一 一 一 夕 ‘ 、 、 一 夕 一 一 一 夕 一 、一 … 引 一 一 一 夕 一 一 令 夕 一 夕 一 一 弓 七了、 一 气 式中夕 工 夕 工 夕 ， 夕 一 夕 工 ， 夕 夕 ， 夕 ‘ 夕 ， 夕 一 ， 夕 少 。 实际 上 ， 这 里 的 系统 是一 个二级 晶体管放 大器 的等效 电路 ， 是 它 的 节点 导纳 矩阵 ， ，和 是 电路 中两个 品 体管的 互 导 ， 夕 、 夕 、 夕 、 夕 、 。 工、 。 和夕 是 支 路 导纳 。 求 系 统 的 符 号传 递 函数 即 电路从输 入 口 ， 到输 出 口 ， 的开 路转移阻抗 。 解 因 ， 连， 。 ， 人 ， ， 根据 式 和 可 得等余 因 式阵 的 第 行元 素 为夕 。 ， 夕 ， 夕 和夕 ， 第 列 元 素 为 夕 夕 ， 夕 夕 ， 夕 ， 夕 少 夕 ， 少 。 少 ， 。 少 。 。 。 据 据 第 、 节所述原理 ， 从 ‘ 可 求 得 混 合 图 ’ 和 变形 图 召 ’ ，如 图 和 所 示 。 图 ‘ “ 边旁整数为 边 号 ， ， ， 。 。 从 而 ， ， ， ， ， 谨， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 。 根据程 序 可 求 得 ’ 和 ’ 毛 的对应状态空 间树 和 “ ， 如 图 。 和 所 示 。 图 中圆 圈 内的 整数为状态节点 号 ， 圆圈下 的 表达式 中的整数为被 缩减 的 并联边号 ， “ ” 表示并联 。 、 、 通 、 妙土感 老志 一 乙古去志去占舀舀 一 二 十 百去舀昌 丁 图 系统 的 混 合 划 “ 、 ’ ‘ 及 其状 态 空 间树 、 妾 ， 丁

从而得 D|Y|=y1:(y23((y3s+y13+y2s)(y54+y24)+y24y45)+(y16+y25)(ys3(y54 +y24)+(y54+y24)y3)+y24(y43(y35+y4s)+y45ys3))+y1s(y53((y32 +y25)(y64+y2)+ys4y24)+y54(y43(y32+y24+y25)+(y24+y25)y23) +y25(y23y24+y24y13)) D14=Y(14)=y43(y31(y12+y33+y24+y25)+（y32+y24)y21) +y24(y21(y23+y53)+y23y31) T41=D14/D 直接展开行列式！'I和Y1,可以鉴证上述结果的正确性。若用类似于Minty算法的有向树 法求得的D将含行n,=30项，每项含4个y因子；D,将含有9项，每项含3个y因子。显 然，上述长达式比有向树法等惯用方法更紧谈更简沾，计算时间也较短，因为对于T有 n,=12n,=30,对于T14有n,=4n,=9。 5结 论 本文提出的应用状态空间树和变形图概念的求符号系统函数新算法SSTMSF与目前常用 方法（信号流图法和有向树法等）相比，有两个优点：(1)计算效率较高，所得表达式较 短；(2)重复调用同一个子程序SSTMSD就可分别求出符号系统函数的分母（行列式）和分 子（余因式）。 参考文献 1 Mason S J.Proc IRE,1953,41:1144 2 Coates C L.IRE Trans.Circuit Theory,1959,6:170 3 Mayeda W.Proc.Nat.Elec.Conf.,1958;15:1 4 Chen W K.IEEE Trans.Circuit Theory,1965,12:85 5 Roland R M.IEEE Trans.,1978,25:331 6黄汝激.电科学学刊，195,7：81 7黄汝敬.电子科学学刊，1986,8：335 8 Hlorowitz E and Sahni S.Iundamentals of Computer Algorithms.Computer Science Press,Potomac,Mary land.1978 9 Mint:G J.IEEE Trans.,1965,12 (1):120 362

从而 得 夕 夕 夕 。 夕 。 夕 石 少 、 夕 、 夕 夕 夕 ，。 夕 。 少 夕 。 夕 ， 夕 ‘， 夕 少 夕 。 少 夕 夕 ， 夕 夕 。 。 ‘ ‘ 。 声产 ， ， 一 ‘ 、 ， 十 一 一 二 ， 尸口 直接 展 开 行列 式 和 、 ， ‘ 、 可以验 证上述 结 果 的 正 确性 。 若 用 类似 于 。 妙 算法的 有向树 法求 得 的 将 含有 、 二 项 ， 征项 含 个 因 子 ， ‘ 将 含 有 项 ， 征项 含 个 因 子 。 显 然 ， 上 述 一 友达 式 比 有向树 法等惯 用 方法 更紧 头更简 洁 ， 计算时 间 也 较 短 ， 因 为 对 于 有 ， 认 ， ， 对 于 ‘ 今 有 ， 二 《 ” ， 。 结 论 本 文 提 出的 应 用状 态 空 间树 和变形 图概 念 的 求 符 号系统 函 数 新 算法 与 目前常用 方法 信 一 号流 图法和 有向树 法等 相 比 ， 有 两个优点 计 算 效 率 较 高 ， 所得表达式较 短 重 复调 用 同一 个子程 序 就可分别求 出符号 系统 函数的分 母 行列式 和分 子 余 因 式 。 参 考 文 献 入 、 ， ， ‘ 。 ， ， ， 人 手 · · ， 、 ’ ， ， 入 ‘ ， ， 黄汝 激 电 户科 学 学 ， ， 黄汝 激 匕 气 科 学 学 ， ， 、、 · 乙 认 【 了一 、 〕 。 ” ， 〕 。 、 。 ， 入 、 少 人 二 ， 二 巨 ’ 、‘ ， ， 并