一類非線性遞推的變距二分算法

1、 本文由xs5p6p99jy貢獻 pdf文檔可能在WAP端瀏覽體驗不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機查看。 第 卷（ 第 ） 期 汁算機與數(shù)字工程 一 類非線性遞推 的變距二分算法 李 薇 張 建軍 紀祥 鯤 武漢 ） （ 軍工 程大學(xué)理學(xué)院 海 摘 要 提 出了一種有效求解 一類 非線性遞推問題的并行算 法 。比較求 解此類 問題的奇偶二 分法 ， 變距 二分算法 顯 非線性 遞推 二 分算 法 著節(jié)省了總運算量 ； 比較約簡二分法 ， 變距二分算法僅含消元過程 ， 算法結(jié)構(gòu)簡單 。 關(guān)鍵詞 中圖 分 類 號 （ ） ， ， ， ， ， 引言 眾所周 知 ， 推 問題 的 算法

2、是 算 法研 究 的 遞 ， ，一 ， ， （ ，） ： ： （ ） ， ： 其 中 ， 是給 定 的 常數(shù) ， 是 滿 足下 和 ，和 基礎(chǔ) ， 文獻 提出 了求解一階線性遞推 的遞歸 倍增法 ， 文獻 在研究 一類連續(xù)運算 的并行 算 法 基 礎(chǔ) 上 提 出 了求 解 一 階 線 性 遞 推 的 一 算 列條件的函數(shù) ： 條件 是可結(jié) 合 的 ： 廠 （ ） ， ， 。 ， （ ） ） ） ， 法， 文獻 出 了計算 階線 性 遞歸 方 程 提 組的并行算法 ， 文獻 在此基礎(chǔ)上提 出了一種 對齊算法 ， 文獻 進一步提 出了計算 階線性 遞 歸 方 程 組 的一 種 新 方 法 。非 線

3、 性 遞 推 的 并 行算法研究 較線 性 遞推 復(fù) 雜 ， 于本 文 研究 的 對 一 條件 對是可分配的： ） （ （ ，（ ） （ ，） ， ，），） 條件 是半結(jié)合的， 即存在 函數(shù) 使得 ， ） （ （ ，） （ ， （ ，） ， ） ： 下面 ， 我們 推導(dǎo)它 的變距 二分算 法 。 類非線性遞推問題 ， 文獻 出了求 解它 的 提 不失一般性 ， ， 設(shè) ， 利用上述條件 ， 我們有 奇偶二分法 和 約 簡二分 法 ， 奇偶 二分 法 計算 量 較 大 ， 約 簡 二 分 法 含 約 簡 過 程 和 回代 過 程 ， 而 算 法結(jié)構(gòu) 復(fù)雜 。本 文提 出 的變 距二 分算 法 ，

4、 不僅 顯著節(jié) 省了總運算量 ， 而且算 法結(jié)構(gòu)簡單 ， 并行 性能好 。 ， （ ） ， ， 利 【 （ ， ） ， 用 條件 有 ， （， ） ） 一類非線性遞推 的變距二分 算法 考 慮如 非線性 遞 推問題 ： ， （ ， ，（ ， ） ） （ ： （ ） ） ， ， （ ） （ ， ， 廠 ： （ ： ， （ （ ， ， ） ） ） 收到本文時 間： 年 月 日 一類非線性遞推的變距二 分算 法 ： 第 卷 再 利用 條件 得 （ 口 ） ， ） ） ， 口 （ ， ） ， （ ，（ ） ， 一 ） ， 一一 （ ） （ ） ） （ ） ， ；） 一 一 最后利用條件 得出 （ ）

5、，（ （ ， ） ， （ ） ） ） ， 一 一 ， ” 日 令 ： （ ， ， ， ， ， 一， ） ） 【 （ ） ， 則有 特例分析 我們來看一個例子 ： 中 ， 在（ ） 取 ，） ， 這樣定義 的函數(shù)滿足條 （ ，） ，（ ，） 件 這樣遞推問題 （ ） ， ， 可寫成 ： ，（ ， ） ， ， ：） ： ， 一 這樣加工得出的遞推關(guān) 系與原遞推關(guān)系具有 相同的形式 ， 只是步長為 同理可以加工步長為 ， 的遞 推公 式 ， 工 加 次 即可 獲得 所 求解。 ：（ ， ， ） ） 設(shè) 上 面推 導(dǎo) 的問 題 （ ） 由 的變 距二 分 這樣 ， 我們可以寫出非線性遞推問題 （ ）

6、的變 距二分算法如下 ： 第 ： ， 的倍數(shù) 分類 ， 公式 步 將 按 按 計算 算法 ， 快 可 以 寫 出遞 推 問題 （ ） 很 的變 距 二分 算法。 算法如下 ： ， ， 對 （ ） ） ， 計算 一 ， ， ， 。 一 二 二 ： ，： ） （） ， ， 一 ， ， ， ： 。 ，一， ， ：， ， 第 步 ： ， 按 將 的倍數(shù)分 類 ， 按公 式 計算 （ ） （ ） ） （ 二 ：， ， 一 （ ， ） （： ） ： ： 結(jié)果 ： （： ，） ；： ； 衛(wèi) ， ， ， ， ， ， 一 ： 一， ， ， ， ， 上述算法在 方向串行 ， ，方向并行計算。 （ ， ， ） （

7、） 假設(shè)處理機臺數(shù) 并且設(shè)乘法運行時間 ， 為 丁， 指數(shù)運算運行時間為 ， 則我們 可以對上述 變距二分算法進行效能分析 ： 運行 時間 ： （ ） ） 一 一 ， 衛(wèi) ， 衛(wèi)） ：。 ：） （ ） 一 ， ， ：， ：， ： 魯 第 ： ， 步 將 按 的倍數(shù)分 類 ， 公 式 按 串行計算問題（ ） 所需時間：帛 （ ） 二分法加齜 計算 一 ） （ ） （ ） 葉 二分法效率： 岫 ， ， 一 “ 二 ， 一 下面列出此算法與奇偶二分法 、 約簡二分法的 加速比和效率比較 （ 丁 盯 ： 設(shè) ： ， ） ， （ 下轉(zhuǎn) 第 頁） 第 （ 第 卷 ） 期 計算機與數(shù)字 程 二 配 置表 中

8、 ， 沒有 是 子句 的 語句 。它 特 性 。該 映射 機 制 對 于 有 行 業(yè) 共 享 標 準 的 電 子 在應(yīng)用加入交換系統(tǒng)時設(shè)定 ， 與應(yīng)用系統(tǒng)的數(shù)據(jù)庫 資源相對應(yīng)。在執(zhí)行應(yīng)用關(guān)系數(shù)據(jù)向 文檔轉(zhuǎn) 換時， 根據(jù) 請 求 文檔 頭 部 的 資 源標 識 選 擇 要 政務(wù)系統(tǒng)都可適用 。在交換 網(wǎng)關(guān) 中實現(xiàn)了 消息 的路 由， 由算法 通過 給 文檔 包裝 頭 路 部信息實現(xiàn) ， 交換系統(tǒng)有統(tǒng) 的交換格式 使 提 高了模塊的通用性 。本地 通訊 接 口與交換 網(wǎng)關(guān) 之 間使用 與 相 結(jié) 合 的技術(shù) 實現(xiàn) 消息 的異步安全傳輸 ， 保證 了原 型 系統(tǒng) 消息 的 安全可靠傳輸 。 該原型系

9、統(tǒng)設(shè)計 目前僅考慮 了傳輸 的基本需 求， 作為一個完整 的數(shù)據(jù)交換系統(tǒng)， 還有待于將數(shù) 據(jù)的傳輸備份、 交換過程監(jiān)控管理 、 交換 日志等模 執(zhí)行 的 語句 ， 加上請求文檔 中 子句構(gòu) 成一個完整的請求 ， 在數(shù)據(jù)庫中執(zhí)行該請求可得到 滿足共享規(guī)范的 文檔。 映 射 子句 生 毫 映 圖 擴 展 模 板 驅(qū) 動 模型 塊考 慮其 中 。 參 考 文 獻 總結(jié) 電子政務(wù)交換原型系統(tǒng)采用星形樹 網(wǎng)絡(luò)交換 結(jié)構(gòu) ， 與行業(yè) 內(nèi)物理網(wǎng)絡(luò)架構(gòu)一致同時反映交換管 理權(quán)限控制的區(qū)域分級特點。原型系統(tǒng)在星形樹 交換結(jié)構(gòu)的基礎(chǔ)上按功能歸屬分為本地通訊接 口 和交換網(wǎng)關(guān)兩個部分。本地通訊接 口封裝 了 朱勤

10、陸建新 陳 繼紅 基于 的異 構(gòu)數(shù)據(jù) 交換 技術(shù)及其 實現(xiàn) 計算機應(yīng)用與軟件 ， 中凱 李 與 雙 向數(shù) 據(jù)轉(zhuǎn)換 接 口的設(shè)計 計算機與現(xiàn)代化 ， ） （ ： ， ， ， ， ， ： ： ， ， ， ， 文檔與關(guān)系數(shù)據(jù)庫 的映射功能和 文檔收 發(fā) 處理功能。 文檔與關(guān) 系數(shù)據(jù)庫的映射擴展了 基于模板驅(qū)動的映射， 充分利用 了行業(yè)數(shù)據(jù)的共享 胡朝 暉， 基于 的數(shù)據(jù)庫總體分析 出乖 出毋出乖出 乖出 （ 接第 上 頁 ） 表 變距 、 奇偶 、 約簡算法加速比和效率 比較 變距 二分算法顯著節(jié)省了總運算量 ， 比較約簡二分法 ， 變距二分算法僅含消元過程， 算法結(jié)構(gòu)簡單。不足之 處是當較大時 ， 此算法需要的處理機臺數(shù)也較大。當 處理機臺數(shù)不夠時， 可以采用分段技術(shù)。 參 考 文 獻 ， ， 一 ： ， （ ） 從表中可 以看到 ， 當處理機臺數(shù) 時 ， 變 崔國華 ， 洪帆 ， 鵬軍 ， 珊 柳 計算 一類連續(xù)運 算 的有效 并 距二分算法的加速 比和效率都是最高 的。更重要 行算法 華 中理工大學(xué)學(xué)報 （ ） 的是 當處理機 臺數(shù)有限時 ， 變距二分算法由于總運 張德富 ， 盛藍 計算 序線性遞歸 方程組 的一種有效 算量少 ， 其效率明顯高于奇偶二分法。 并行方法 計算機學(xué)報 ， （ ） ， ： 算法小結(jié) 的前 提下反復(fù)加工所給遞推公式 ， 在加工 過程 中充分