質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.33%

  • C

    4012questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    3795questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • アルゴリズム

    429questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ガウスの消去法の後退消去のプログラムを作る過程に関しての質問です。

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 683

carnage0216

score 124

環境

  • windows10
  • visual studio 2017

こちらは参考にしたサイトです。
リンク内容

b[2]=a[2][3]/a[2][2]

b[1]=a[1][3]/a[1][1]-a[1][2]/a[1][1]×b[2]

b[0]=a[0][3]/a[0][0]-a[0][1]/a[0][0]×b[1]-a[0][2]/a[0][0]×b[2]


#define  N 3 とfor(i= N-1;i>=0;i++)

より

b[i]=a[i][N]/a[i][i]

b[i]=a[i][N]/a[i][i]-a[i][i+1]/a[i][i]×b[i+1]

b[i]=a[i][N]/a[i][i]-a[i][i+1]/a[i][i]×b[i+1]-a[i][i+2]/a[i][i]×b[i+2]


から共通部分をfor文でまとめると

for(i=N-1;i>=0;i++){b[i]=1/a[i][i];}

としました。
残った部分の

b[i]=a[i][N]
b[i]=a[i][N]-a[i][i+1]×b[i+1]
b[i]=a[i][N]-a[i][i+1]×b[i+1]-a[i][i+2]×b[i+2]


をどの様にforでまとめるか大変悩んでいます。
j=i+1でまとめようと考えたのですが、
どうしていいのか途方に暮れています。
どうか知恵を貸して頂けないでしょうか?
私は答えというよりどうしたら導けるかの過程のやり方が知りたいです。

ただ、もう一つのやり方として

b[2]=a[2][3]/a[2][2]

b[1]=a[1][3]/a[1][1]-a[1][2]/a[1][1]×b[2]

b[0]=a[0][3]/a[0][0]-a[0][1]/a[0][0]×b[1]-a[0][2]/a[0][0]×b[2]


から共通部分をfor文でまとめると

for(i=N-1;i>=0;i++){b[i]=a[i][N]/a[i][i];}

として
残った部分の

b[i]=1

b[i]=-a[i][i+1]×b[i+1]

b[i]=-a[i][i+1]×b[i+1]-a[i][i+2]×b[i+2]


からfor文でまとめられないか今現在、紙に書いて行っております。
これでできない場合は前者の方法に移ります。
マルチポスト

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • carnage0216

    2018/07/30 07:48

    おぉ、なんだが胸にざっくりきますねぇ。読めなかったらプログラマへの夢が絶えそうです。(苦笑い

    キャンセル

  • mkgrei

    2018/07/30 07:59 編集

    プログラミングは機械に実行の手順を指示するものです。その際にどんな言語を使うのかは特に重要ではありません。でもどんな手順を踏むべきかを人間がわかっていないのなら機械もそれを忖度してやってくれるわけではありません。アセンブリレベルまで下がるとメモリのデータを入れ替えたり、単純な足し算に全て落とし込むことになります。でもそれは人間にとって理解しやすくありません。適切なレベルで物事を理解することが大事です。今の場合わからないのはCの文法ではなくアルゴリズムのように見えるので、とりあえず何をしているのかの理解に努めてはいかがでしょう。

    キャンセル

  • swordone

    2018/07/30 10:08

    そもそも配列インデックスに3が入ってるのがおかしい気がするんだが…

    キャンセル

回答 2

checkベストアンサー

+1

i = 0のとき
b[i]×a[i][i]=a[i][N]-a[i][i+1]×b[i+1]-a[i][i+2]×b[i+2]

右辺を
a[i][N]-(a[i][i+1]×b[i+1]+a[i][i+2]×b[i+2])

適当に()内をKと置き、j=i+1と置く
K=a[i][i+1]×b[i+1]+a[i][i+2]×b[i+2]=a[i][j]×b[j]+a[i][j+1]×b[j+1]
j+1=i+1+1=2で終了


同様にi=1のとき
b[i]×a[i][i]=a[i][N]-(a[i][i+1]×b[i+1])=a[i][N]-K
K=a[i][i+1]×b[i+1]=a[i][j]×b[j]
j=i+1=2で終了


i=2のとき
b[i]×a[i][i]=a[i][N]-(0)=a[i][N]-K
K=0
j=i+1=3で実行せずに終了


大事なこと
なお、上記式は今回の場合N=3の時のみ正しいと証明され
その他の場合にも適用できるか?となると
きちんと定義から式を作る必要があります。
(今回は偶然同じ式ができるので適用可能ではあるが)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/07/30 13:08

    解答ありがとうございます。
    定義から書かないと解けないものもあるのですね。
    では、こちらの2つのサイトのガウス法でも定義までは書いていないため万能ではないのですね。
    https://qiita.com/haya_walker/items/d64a5fc624c65a324fa2


    https://www.mk-mode.com/octopress/2013/09/24/cpp-simultaneous-equation-by-gauss-elimination/

    キャンセル

  • 2018/07/30 13:21 編集

    やっぱり完璧なプログラムはないのですね。
    ちなみに、定義から式を作るとはどういう事でしょうか?
    変数に範囲を付けるという事でしょうか?
    仮にそうならば、範囲から逆算して式を作るならば、確かに解なしなどはないかもしれません。

    キャンセル

  • 2018/07/30 13:27

    前者は上三角行列に変形して対角項を1にするという定義がなされ、それに沿ったプログラムが多分作成されてるのだと思います。
    この場合、Nが1以上であれば成立します。

    後者についてもN行・N列の行列に対してアルゴリズムが解説されています。

    対して、今回行ってる作業はN=3の時の計算式のみに注目しているため
    N=100などに対して果たしてそのまま適用できるか?という点で疑問が残るわけです。

    キャンセル

  • 2018/07/30 13:48

    あぁ、やはりどんな方程式も解くプログラムを作るのは不可能だったみたいです。
    ですが、まぁ、行いたい処理ができるよう工夫してみます。
    asmさん、どうもありがとうございました。

    キャンセル

  • 2018/07/30 13:51

    ちなみに、
    >>i=2のとき
    b[i]×a[i][i]=a[i][N]-(0)=a[i][N]-K
    K=0
    j=i+1=3で実行せずに終了
    に関してはK=0より
    a[2][3]に関しては変数の解が出ないのですよね?

    キャンセル

  • 2018/07/30 13:53

    b[3]なんてないですしね

    キャンセル

  • 2018/07/30 14:52 編集

    あ、、、確かに。
    私はなんてアホなんだ...。
    強欲ながら、どんな方程式でも解が出せるプログラムを作りたかった...。
    だとしたら、i=2で展開していくより、b[i+1]の時点でb[3](存在しない変数が生まれるので)計算できないとわかったのかも...。

    キャンセル

  • 2018/07/30 19:58

    > あぁ、やはりどんな方程式も解くプログラムを作るのは不可能だったみたいです。

    よくわかりませんけど、少なくとも
    https://qiita.com/haya_walker/items/d64a5fc624c65a324fa2
    はNが3以外でも有効ですよ。
    (ガウスの消去法で解きたい線型方程式に対しての話ですが)

    あなた(carnage0216さん)の定式化によってfor文が一つベタ書きされているせいで書けなくなっているだけです。

    キャンセル

  • 2018/07/30 20:56 編集

    mkgreiさん。どうもありがとうございます。
    >>あなた(carnage0216さん)の定式化によってfor文が一つベタ書きされているせいで書けなくなっているだけです。
    そうだとは知りませんでした。まだまだ書くスキルが足りないので頑張ります。
    度々すいません。
    >>for文が一つベタ書きされているせいで書けなくなっているだけです。
    とのことですが、どこの部分がべた書きなのでしょうか?

    キャンセル

  • 2018/07/31 01:11

    >>https://qiita.com/haya_walker/items/d64a5fc624c65a324fa2
    はNが3以外でも有効ですよ。(ガウスの消去法で解きたい線型方程式に対しての話ですが)
    に関してですが、どんな係数でも線型方程式なら解けるのでしょうか?

    キャンセル

  • 2018/07/31 01:56 編集

    解が一意に求められる線形連立方程式ならば

    ダメな例としては
    x+y+z=0
    2x+2y+2z=0
    3x+3y+3z=0

    あと、このままでは一番上の式の最初の係数が0の場合などもダメですね

    キャンセル

  • 2018/07/31 06:58

    > どんな係数でも線型方程式なら解けるのでしょうか?

    連立方程式が解を持つかどうかは数学的な問題です。
    これに対して、N変数、N条件式に対してガウスの消去法の掃き出しができるかは別の問題として考えなければなりません。

    asmさんはわかっていらっしゃると思うのですが、carnage0216さん向けの話ですが、
    掃き出しにおいて、係数を割って、引くという操作があります。
    http://www.slis.tsukuba.ac.jp/~fujisawa.makoto.fu/cgi-bin/wiki/index.php?%A5%D4%A5%DC%A5%C3%A5%C8%C1%AA%C2%F2
    この操作では係数が非ゼロのものを選ぶ処理が本来必要です。やることとしては単純で、割る処理に入る前にゼロだったら他の行を見て、非ゼロのものと入れ替えればよいことになります。

    また解が存在するための条件があって、係数行列のランクが未知変数の数と同じである必要があります。
    もっとも単純なケースではN変数に対して、条件式がN個あって場合で、係数行列がランク落ちせずに、ランクがNである場合になります。

    でもこのような特殊なケースを考える前に、Nが3以外でも本来は手続きが問題なく実行できることを理解できる必要があります。

    キャンセル

  • 2018/07/31 18:56

    返信ありがとうございます。
    >>Nが3以外でも本来は手続きが問題なく実行できることを理解できる必要があります。
    プログラムを見ればなんとなく理解できるのですが、深く考えることが出来ません。
    多元線形方程式を解くプログラムに唯一の弱点としてはメモリだと思います。
    どんな多元線形方程式を解くにしてもメモリがいっぱいになってしまえば誤算が生じます。

    キャンセル

  • 2018/07/31 23:28

    例えば8gbのメモリで解ける方程式の最大の次元は何ですか?
    途中の値は全てdoubleと仮定して。

    Nが任意といっても、無限大にしてメモリをオーバーフローさせることを先に考えますか?
    計算時間は考慮しましたか?

    キャンセル

  • 2018/07/31 23:42

    解くだけならば係数を管理する配列以外のメモリはほとんど消費しないはずですが。

    キャンセル

0

[ご参考]

連立方程式:
AX = B
A: a[N][N]
B: b[N]
X: x[N]

の第i行は
1) Σ(a[i][j]・x[j]) = b[i] (j = 0,1... ,N-1)

前進消去により a[i][j] = 0 (where: i > j) であるから (1)は
2) Σ(a[i][j]・x[j]) = b[i] (j = i, i+1... ,N-1)

左辺第1項(i=jの項)を分離すると
3) a[i][i]・x[i] + Σ(a[i][j]・x[j]) = b[i] (j = i+1, i+2... ,N-1)

左辺第2項を移項して
4) a[i][i]・x[i] = b[i] - Σ(a[i][j]・x[j]) (j = i+1, i+2... ,N-1)

両辺を a[i][i] で除すると
5) x[i] = (b[i] - Σ(a[i][j]・x[j])) / a[i][i] (j = i+1, i+2... ,N-1)

※ 上式では、x[i] を求めるには x[i+1], x[i+2]...を必要とするため、
i = N-1, N-2, ... 0 の順で計算することになる(すなわち後退代入)

※ さらに x[t], b[t] が a[t][N] であるなら
5') a[i][N] = (a[i][[N] - Σ(a[i][j]・a[j][N])) / a[i][i] (j = i+1, i+2... ,N-1)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/07/30 19:34

    解答大変ありがたいのですが、なかなか難しいです。
    理解することができる...ように頑張ります。
    あの、わからない部分があった際は質問してもよいでしょうか。
    できる限り自分で解きますので。

    キャンセル

  • 2018/07/30 19:41

    質問するのはご自由に。

    キャンセル

  • 2018/07/31 18:07

    今の私には理解するには大変難しいので保留させて頂きます。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.33%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • C

    4012questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    3795questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • アルゴリズム

    429questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。