月間ラム 1980年10月号

キーフレーズ

マイコン -4 プログラム -2 000 LPRINT BASIC システム RAM THEN -3 インタフェイス NEXT データ 649 GOTO 入力 計算 800 標準価格 FOR 出力 使用 ソフトウェア 文字 機能 コンピュータ -1 場合 メモリ レベル ディスプレイ シャープ ROM LPR 表示 () 可能 Tel カラー Apple 東京 80K PET VDD 日立 8001 バイト ソフト INT ポード ショップ TRS 名古屋 グラフィック RINT 必要 プログラ クラブ 100 プリンタ 32K REM 回路 日本 DATA for 命令 できる 機種 しよう ゲーム カセット パソコン 処理 電圧 BAS 地区 変更 センター アドレス 使っ CPU 大阪 言語 操作 シリーズ CMOS

目次ページ

されたことになります。〃元の連立 1 次方程式を上三 角の連立 1 次方程式に変換するためには , ー 1 回の消 去ステップが必要となりますが , 第 1 消去ステップで は次のように消去演算が行なわれます。 for / = 2 , 3 , ・ ( 1 ) 4 = = / 011 for ゾ = 2 , 3 , ・ ( 2 ) ( l) ( 1) 同様に , ピボット要素佖芻が零でないものとして , 第 2 消去ステップ , すなわち佖品 ) を消去しましよう。 ( ) を消去するには , 式 ( 2 ) 2 の両辺に佖なを掛けた 次のようになり ものを式 ( 3 ) 2 から引きます。つまり , ます。 ⅲ ) ある 1 次方程式を他の 1 次方程式に加える を行ない , 次のような上三角の連立 1 次方程式に変換 します。 ( これを前進消去法といいます ) 。 ( 1 工ー - に斗・ 0 日工 3 ( 2 ) ( 2 ) 022 ヨ - 23 工 3 ( 3 ) 033 工 3 次に , 式 ( 3 ) 3 からェ 3 を , 式 ( 2 ) 2 からェ 2 を , 式 ( 1 ) から を , というように先程とは逆にェ 3 からへと , これ までに求めたズの値を代入しながらすべてのの値を 求めていきます ( これを逆代入法といいます ) 。これ がガウス消去法です。 それでは , 上三角の連立 1 次方程式に変換していき ましよう。ますの 1 ( これをピボット要素といいます ) が零でないものとして , 第 1 消去ステップ , すなわち ( いと“引を消去します。佖幻を消去するには , 式 ( 1 ) の両 辺に。幻なⅡを掛けたものを式 ( 2 ) から引きます。つまり , 次のようになります。 ( 2 ) 2 ( 3 ) 3 ( l) ( 2 ) ( 3 ) 2 ・ = 63 . 032 工 2 十 033 工 3 ( 2 ) ( 2 ) 032 032 ( 2 ) ・ ( 2 ) 2 ・ ・ 0 32 光 2 十一 -- 7 - ・ 023 工 3 ( 2 ) 022 22 ( 2 ) ( 2 ) 032 ( 2 ) ( 33 = 63 ( 2 ) 023 工 3 0 22 こで , 式 ( 3 ) 3 の係数と定数を , ( 3 ) 033 = ニ 32 ( 2 ) 32 ( 2 ) 佖 22 ( 2 ) ・ 62 = 62 ( 2 ) : 幻第十の 2 工 2 十 023 工 3 佖幻 X(I) : 0 幻第十一一・の 2 工 2 十・一一・の 3 工 3 = ( 2 ) 032 022 ( 2 ) ( 2 ) ( 3 ) 3 : (ZII 佖 ll 011 ( 2 ) 032 ( 2 ) 022 ( 2 ) ( 2 ) 032 63 22 式 ( 3 ) 3 は次のようになります。 とおくと , ( 3 ) ( 3 ) 033 工 3 = = 63 以上によって , 3 元の連立 1 次方程式の上三角への変 換が終了したことになります。この前進消去の計算過程 を表の形式で表わすと表 1 のようになります。このよ うにすると , より理解しやすいでしよう。〃元の連立 1 次方程式での第 2 消去ステップは次のようになります。 for / = 3 , 4 , ( 2 ) ( 2 ) 9 = の 2 / “ 22 for ノ = 3 , 4 , ・ ( 3 ) 0 幻 ll ( 2 ) ・ 23 ・の 2 ) ェ 2 十 ( の 3 ー こで , 式 ( 2 ) 2 の係数と定数を , 0 幻 ・の ) , ノ = 2 , 3 ェ 3 = 62 ー ( 2 ) 2 ( 2 ) ( 3 ) ・ 62 = 63 02 ) = : 佖 2 ) 021 佖 ll とおくと , 式 ( 2 ) 2 は次のようになります。 022 工 2 罸 - 023 工 3 = ニ 62 。引を消去するには , 式 ( 1 ) の両辺に。引 / ( を掛けたも のを式 ( 3 ) から引きます。つまり , 次のようになりま す。 = 63 ( 3 ) : ( 十の 2 工 2 十の 3 ( 1 ) : 引第十 - ー・山 2 ェ 2 十一一・の 3 = 011 ( 3 ) 3 ( 2 ) 2 ( 2 ) ( 2 ) 佖 23 033 佖ー 3 佖引 011 ・の 2 ) ェ 2 十 ( の 3 ー ll II こで , 式 ( 3 ) 2 の係数と定数を , ェ 3 = 63 ー ( 3 ) 2 : ーりーりーりーり 012 022 032 ( 2 ) 佖 3 ) 03 ) 2 ー 1 1 011 ( 2 ) ( 2 ) 23 ( 1 ) ( 122 : ( 2 ) 2 = とおくと , 式 ( 3 ) 2 は次のようになります。 ( 2 ) ( 幻 032 = 。工 2 ・十 033 以上の演算によって , 第 1 消去ステップが終了し , ピ ポット要素。Ⅱより下の第 1 列目の要素がすべて消去 3 ( 2 ) ( 2 ) 33 ( 2 ) 32 ( 3 ) 2 : ( 2 ) 2 61 ( 2 ) 62 012 ( 2 ) 022 013 ( 2 ) 佖 23 0 0 ガウス消去法にあける前進消去の計算過程 表 1 022 ( 3 ) : ( 3 ) 3 = ( 3 ) 2 ー ( 2 ) ( 2 ) 2 ( 3 ) 佖 33

これで上三角の連立 1 次方程式に変換されたので , 逆代入法を用いて〃元の連立 1 次方程式の解を求める , ことになります。逆代入法のアルゴリズムは次のよう になります。 アルゴリズム 2 : 逆代入法 input れ , 工れ = 6 ) / れ ( 用 for ん = 〃ー 1 , れ一 2 , ・ 1 ェ々 = ( 6 0 わ工ノ ) / 0 々々 output 工々れ このアルゴリズムに従って作成した BA S IC プログ ラムと実行例がリスト 1 に示してあります。連立 1 次 方程式を解く計算は元数が大きくなればなる程大きな 記憶場所が必要になり , 計算時間も長くなるので , プ ログラムを作成する場合には , 1 ) 記憶場所の節約をはかる 2 ) 計算のむだを省く 必要があります。こで示すプログラムは , この 2 つ を念頭において作成してあります。すなわち , 記憶場 所の節約のために , 定数伍 ) れは変数 ( ェの記憶場所に 入力し , 伍 ) という形で表面に出てきませんし , ( , 〃は同じ記憶場所を使用するように処理 ん = 1 , 2 , ・ を行なっています。このことは , プログラムを作成す るうえで大変重要なことです。 このガウス消去法に必要な演算回数は , 全体として 朝がある程度大きく , 〃 3 に対してれ 2 以下の項が無視 できるとすれば ) 約〃 3 / 3 の乗算と加算とがそれぞれ必 要となります。また , 計算時間は元数〃の 3 乗にほば 比例することが知られています。 ガウス消去法では , 係数行列の対角要素より下の要 素をゼロに変換しましたが , 同時に対角要素より上の 要素もゼロに変換する方法もあります。 この方法はガウス・ジョルダン法 ( 掃き出し法 ) と 呼ばれ , そのアルゴリズムは次のようになります。 同様にして , 第 ( れ一 1 ) 消去ステップまで消去演算を 行ないます。 これより , れ元の連立 1 次方程式を上三角化するた めのアルゴリズムは次のようになります。 アルゴリズム 1 : ガウス消去法 mput れ , 佖われ X れ , for ん = 1 , 2 , ・ for ~ = ん十 1 , ん十 2 , ・ ( 々 ) 9 = 鷦々 / 々 for ゾ = ん十 1 , ん十 2 , ・ ( 々十 1 ) ー . ( 々 ) 十 1 ) ( れ ) output ( り ( 々 ) ( 々 ) - リスト 4 ガウス消去法のプログラ乙とその実行例 - リ 0 十 - ・ 1 リ 0 ( 1 9 の i— 1 1 1 1 8 0 1 3 Z 1 ) 十 1 ミ 3 1 ⅵ 4 3 1 十 1 1 Z X 1 5 4 4 1 2 十 1 十 9 Z -1 ) ス” 3 0 「のヨい CL 7 1 3 の 1 1 - ・よ 1 4 2 の 1 Z の 3 ロ i— ( Z = X — 0 ョ 5 3 1 5 1 Z CL iZ O- 0 L.u Z Z 、・ X LL Z LL Z ののいのののいいのののののののののののいのののの 9 の 1 3 4 5 6 7 日 9 の 1 の 1 3 3 4 5 6 7 日 9 の 1 3 9 の 1 2 3 4 5 6 7 8 9 1 2 3 4 う 6 7 8 9 いの 1 「心 3 4 5 9 ののいのの 2 のの 1 1 3 2 2 2 2 2 「心 2 3 3 3 3 9 実行例 1 宀よ、↓ -1 よ 3 1 4 3 5 4 4 一 1 心 7 1 3 の 1 1 4 い 1 AJ -1 、よ 1 1 〕入〕ス X X ハ X ( 1 )

アルゴリズム 3 : ガウス・ジョルダン消去法 伍 ) れ れ X れ input 広 for み = 1 , 2 , ・ for ゾ = ん + 1 , ( 々十 l) ー / 21 / 22 1 ( 本日の試験 1 時限目学 300baud l-oadi ng N03 = 々 / 0 々々 ( 々十 l) for / = : for ゾ = 左 , ん + 1 , ~ = 応 , goto ん 1 ( 々十 1 ) ( 々 ) ( 々十 1 ) ( 々 ) 1 / 引 / 32 / 33 0 / 42 / 43 / 44 12 1 0 13 2 3 1 2 4 34 1 021 031 012 022 032 042 0 】 3 023 033 04 3 014 024 034 044 ます , んの各行い = 1 , 2 , 3 , 4 ) と U の第 1 列を掛ける ことにより , んの第 1 列の各要素が次のように求まり ( 々十 l) ( 々 ) output ( 三 ( れ十 1 ) ( ん十 1) ます。 = 1 , 2 , 3 , 4 こ ( 15 ) このガウス・ジョルダン消去法は , 逆代入法を必要 としないので , プログラムが簡単になる利点がありま すが , 必要な演算回数が多い朝がある程度大きい数 だと , 乗算と加算とを約 3 / 2 回必要とし , ガウス消 去法に比べて約 50 % 多い ) 欠点があります。したがっ て大きな問題にはなるべくガウス消去法やこれから述 べる LU 分解法などを用いるほうがよいでしよう。 2. ム U 分解法 連立 1 次方程式の係数行列 .4 を下三角行列んと上 三角行列 U にはっきり分解しておくと便利です。ーっま = U たとえば , 逆行列や行列式の計算とか , 右辺の定数 6 だけが異なる問題を解くときなどに有効性がありま す。実質的には , ガウス消去法も U 分解法も同じな のですが , こではクラウト法とも呼ばれるん U 分解 次に , んの第 1 行と U の各列い = 2 , 3 , 4 ) を掛けるこ とにより , U の第 1 行の各要素が次のように求まりま す。 山 ) = のノ / 11 , ノ = 2 , 3 , 4 また , んの各行い = 2 , 3 , 4 ) と U の第 2 列を掛けるこ とにより , んの第 2 列の各要素は次のように求まります。 ~ = 2 , 3 , 4 U の第 2 行の各要素は , んの第 2 行と U の各列 0 = 3 , 4 ) を掛けることにより , 次のように求まります。 ー / 2 レ ) / Z22 , ノ = 3 , 4 2 ) 同様にして , の第 3 列の各要素は次式で求まります。 ( 山 3 十 2 観 3 , ー = 3 , 4 ん 3 = = 0 ー・ さわに , れ 34 と / 44 は次式で求まります。 ー ( 山 4 十 / 32 観 4 盟 33 3 4 ・一 - 034 ( 20 ) ( / 41 山 4 十 Z42 観 4 十 14 34 ) / 44 ・ = ・ 044. ー 以上の計算によって行列 A はんと U に分解されたこ とになります。このことは nx 〃係数行列の場合にも 簡単に拡張することができます。 すなわち , んの第 1 列と U の第 1 行の各要素はおの おの次のようになります。 法を紹介しましよう。 ます , 係数行列、 4 がと U に分解されているとす = 1 , 2 , ・ レ = 0 レ / ム 1 , ( 21 ) れば , れ元の連立 1 次方程式、 4 = ろは , Ux= 6 となります。 , こで , 補助べクトルを用いて , U ェ = とおくと , 式 ( (l) は次のようになります。 また , んの第 2 列と U の第 2 行の各要素はおのおの 次のようになります。 な 2 = : 0 1 に ( 13 ) ( 12 ) したがって , 、 4 ズ = 6 を解くということは式 ( 12 ) , ( 13 ) の 2 つの三角な連立 1 次方程式を解くこと , つまり 代入法と逆代入法によってを求めることになりま す。 それでは , どのようにして .4 をと U に分解する かを〃 = 4 の場合について説明しましよう。 2 ノ = = ( ae 丿 - ー / 21 レ このようにして , 行列と U の各要素の一般式は次 のようになります。 の ) ー ) わ々わ 91 ります。 これより , U 分解法のアルゴリズムは次のようにな ( 22 ) (23)