30

サイズの行列の行列式の値を見つけるのに最適なアルゴリズムはどれか教えてもらえますN x Nか?

4

4 に答える 4

34

ここに広範な議論があります。

アルゴリズムはたくさんあります。

簡単なものは、LU分解を取ることです。それから、以来

 det M = det LU = det L * det U

Lとの両方が三角形の場合、行列式はとUの対角要素の積です。それはです。より効率的なアルゴリズムが存在します。LUO(n^3)

于 2010-03-12T19:27:29.240 に答える
11

行削減

nxn 行列の行列式を見つける最も簡単な方法 (実際には悪い方法ではありません) は、行削減によるものです。行列式に関するいくつかの簡単な規則を念頭に置くことで、次の形式で解くことができます。

det( A ) = α * det( R )、ここで、Rは元の行列Aの行階層形式であり、α は何らかの係数です。

行エシュロン形式の行列式を見つけるのは非常に簡単です。対角線の積を見つけるだけです。元の行列A の行列式を解くと、単純に α を計算することになり、行エシュロン形式Rが見つかります。

知っておくべきこと

行エシェロンフォームとは？

簡単な定義については、この [リンク](http://stattrek.com/matrix-algebra/echelon-form.aspx) を参照してください
**注:** すべての定義で先頭のエントリに 1 が必要なわけではありません。アルゴリズム。

基本的な行操作を使用して R を見つけることができます

行の交換、別の行の倍数の追加など。

行列式の行操作のプロパティから α を導出します

  1. Bが、 Aの行にゼロ以外の定数 ß を掛けて得られる行列である場合、

    det( B ) = ß * det( A )

    • つまり、行列式の前に定数を引き出すだけで、行から定数を本質的に「因数分解」できます。

  2. BがA の2 つの行を交換して得られる行列である場合、

    det( B ) = -det( A )

    • 行を入れ替える場合は、記号を裏返します。

  3. BがA のある行の倍数を別の行に加算して得られる行列である場合、

    det( B ) = det( A )

    • 決め手は変わりません。

ほとんどの場合、ルール 3 (A の対角線にゼロがない場合) だけで行列式を見つけることができ、すべての場合でルール 2 と 3 だけで見つけることができることに注意してください。ルール 1 は、人間が数学を行うのに役立ちます。分数を避けようとする紙。

例

（各ルールをより明確に示すために不要な手順を実行します） 

  | | 2 3 3 1 |
A =| 0 4 3 -3 |
  | | 2 -1 -1 -3 |
  | | 0 -4 -3 2 |
R 2   R 3 , -α -> α (ルール 2)
  | | 2 3 3 1 |
 -| 2 -1 -1 -3 |
  | | 0 4 3 -3 |
  | | 0 -4 -3 2 |
R 2 - R 1 -> R 2 (ルール 3)
  | | 2 3 3 1 |
 -| 0 -4 -4 -4 |
  | | 0 4 3 -3 |
  | | 0 -4 -3 2 |
R 2 /(-4) -> R 2 , -4α -> α (ルール 1)
  | | 2 3 3 1 |
 4| 0 1 1 1 |
  | | 0 4 3 -3 |
  | | 0 -4 -3 2 |
R 3 - 4R 2 -> R 3、R 4 + 4R 2 -> R 4 (ルール 3、2 回適用)
  | | 2 3 3 1 |
 4| 0 1 1 1 |
  | | 0 0 -1 -7 |
  | | 0 0 1 6 |
R 4 + R 3 -> R 3
  | | 2 3 3 1 |
 4| 0 1 1 1 | = 4 (2 * 1 * -1 * -1) = 8
  | | 0 0 -1 -7 |
  | | 0 0 0 -1 |

def echelon_form(A, size):
    for i in range(size - 1):
        for j in range(size - 1, i, -1):
            if A[j][i] == 0:
                continue
            else:
                try:
                    req_ratio = A[j][i] / A[j - 1][i]
                    # A[j] = A[j] - req_ratio*A[j-1]
                except ZeroDivisionError:
                    # A[j], A[j-1] = A[j-1], A[j]
                    for x in range(size):
                        temp = A[j][x]
                        A[j][x] = A[j-1][x]
                        A[j-1][x] = temp
                    continue
                for k in range(size):
                    A[j][k] = A[j][k] - req_ratio * A[j - 1][k]
    return A
于 2016-07-02T04:19:12.700 に答える
8

最初の調査を行った場合、N>=4 の場合、行列式の計算が非常に複雑になることがわかっているでしょう。アルゴリズムに関しては、ウィキペディアのマトリックス行列式の記事、特に「アルゴリズムの実装」セクションを参照してください。

私自身の経験から、 Alglibなどの既存の行列ライブラリで LU または QR 分解アルゴリズムを簡単に見つけることができます。ただし、アルゴリズム自体はそれほど単純ではありません。

于 2010-03-12T19:27:55.763 に答える