🤖

123. 掃き出し法

2023/03/22に公開

【問題概要】
掃き出し法を用いて、与えられた係数行列の拡大行列を上三角行列に変換するプログラムを作成せよ。

【解説】
掃き出し法は、連立一次方程式を解くための手法の一つであり、係数行列の拡大行列を上三角行列に変換することができます。掃き出し法の基本的なアルゴリズムは、以下の通りです。

係数行列の左上の要素をピボットとする。
ピボット要素を用いて、下の行の同じ列の要素を 0 にする。
次のピボット要素を選択し、同じ操作を繰り返す。
最終的に、係数行列の拡大行列が上三角行列に変換される。
この問題では、掃き出し法のアルゴリズムを実装し、与えられた係数行列の拡大行列を上三角行列に変換するプログラムを作成する必要があります。ただし、与えられる係数行列は正方行列であるとは限らないため、アルゴリズムの実装には注意が必要です。

具体的には、ピボット要素を選択する際に、最大値を選択する方法を用いることが一般的です。また、ピボット要素が 0 の場合は、行を入れ替えて非ゼロの要素をピボットとすることが必要です。

掃き出し法は、連立一次方程式を解くための手法として応用されるほか、特異値分解や固有値分解などの行列の分解手法にも使用されます。

【関連する問題】
Atcoderの「Linear Approximation」問題が、本問題と関連があります。以下は、その問題の情報です。

「Linear Approximation」

レーティング難易度(★): 1900
ACした回答者に絞った場合のレーティング帯の範囲(数値): 1517 - 2176
レーティング難易度(%): 47.6%
レーティング(数値): 1847
AC率(%): 10.7%
ACしたスコアの高い回答者: https://atcoder.jp/users/TaninA
解説ブログ: https://atcoder.jp/contests/abc186/editorial/409