microbeの活動日記

プログラミングコンテストとかいろいろ

ガウスの消去法をC言語で実装

この記事は熊本高専Advent Calendar 8日目の記事です.

 

本日AdventCalendarに書く人がいなかったため,それを埋めるついでにガウスの消去法をC言語で実装したので紹介しようと思います.

 

ガウスの消去法とは

ガウスの消去法は,連立一次方程式を解くための多項式時間アルゴリズムになります.他に連立一次方程式の解を明示的に表すことができるものとしてクラメルの公式がありますが,クラメルの公式で大規模な問題を解こうとすると計算量が爆発してしまうためあまり計算機で解くことにおいてはおすすめしません.

ガウスの消去法は,前進消去と後退代入という2つの操作からなります.文字だけで見ると少し難しく感じてしまいますがアイデア的には中学数学レベルで解けるようなものでとても簡単です.

 

本当にその場しのぎみたいな記事で,詳しく解説する時間がなかったので詳しいところは以下のサイトを参考にしていただけると幸いです.

ガウスの消去法 - Wikipedia

 

ソースコード

gist2a2c29a2ae3da762f1cb226f9a7a8e10