x1
+x1
+x1
+x1
+x2
+x2
+x2
+x2
+x3
+x3
+x3
+x3
+x4
=x4
=x4
=x4
=数値形式
解法コメント
説明なし
a
b
c
d
x
y
z
clear
i
Randomize
3131313131351515151515≈83137
モンタンテ法（Bareiss アルゴリズム）を用いた連立方程式の解き方
Bareiss 形式の整数保存消去を拡大行列に適用します。各ピボット操作は前のピボットで正確に除算されるため、中間値が全て整数のままです。最終的な簡約形式から解を読み取ります。
モンタンテ（Bareiss）— 計算例（5 元方程式）
連立方程式を行列式形式で書きましょう:
5
1
0
1
0
1
5
1
0
1
0
1
4
1
0
1
0
1
5
1
0
1
0
1
4
7
8
6
8
6
連立方程式の解を求めるには、
モンタンテ (Bareiss アルゴリズム)
メソッドを使用して、連立方程式の行列形式を変換して、左側の行列が単位行列になり、右側に解が得られるようにします。
2
イテレーション 1A0
=
5
1
0
1
0
1
5
1
0
1
0
1
4
1
0
1
0
1
5
1
0
1
0
1
4
7
8
6
8
6
最初のイテレーションでは、前のピボット要素は常に 1 に等しくなります:
p0
=
1
;
現在のピボット要素は、前の行列 (
A0
) の要素で、インデックスが
1
,
1
のものです:
p1
=
a0
0
1,1
=
5
;
前の行列 (
A0
) に基づいて次の行列 (
A1
) を計算します。
1)
ピボット要素がある行は、次の行列に変更なく書き直されます。2)
ピボット要素自体を除いて、ピボット要素が配置されている列のすべての要素にゼロを書き込みます。初期行列
A1
を書き出し、求めたい要素を未知数としてマークする:
A1
=
5
0
0
0
0
1
0
1
0
7
不明な要素を見つけるには、次の式を使用します:
a1
0
i,j
=
a0
0
i,j
*
p1
-
a0
0
1,j
*
a0
0
i,1
p0
p0
は前のピボット要素です。p1
は現在のピボット要素です。a0
は、前のイテレーションで計算された前の行列の要素です。a1
は、現在のイテレーションで計算された次の行列の要素です。i
は行番号j
は列番号Ɐ(
i, j
)
∈ {2, 3, 4, 5} × {2, 3, 4, 5, 6}
A1
=
5
0
0
0
0
1
24
5
-1
5
0
5
20
5
0
1
-1
5
24
5
0
5
0
5
20
7
33
30
33
30
3
イテレーション 2現在のピボット要素は、前の行列 (
A1
) の要素で、インデックスが
2
,
2
のものです:
p2
=
a1
0
2,2
=
24
;
前の行列 (
A1
) に基づいて次の行列 (
A2
) を計算します。
1)
ピボット要素がある行は、次の行列に変更なく書き直されます。2)
ピボット要素自体を除いて、ピボット要素が配置されている列のすべての要素にゼロを書き込みます。3)
以前のすべてのピボット要素を p2 に置き換えます。初期行列
A2
を書き出し、求めたい要素を未知数としてマークする:
A2
=
24
0
0
0
0
0
24
0
0
0
××××
5
××××
-1
××××
5
××××
33
不明な要素を見つけるには、次の式を使用します:
a2
0
i,j
=
a1
0
i,j
*
p2
-
a1
0
2,j
*
a1
0
i,2
p1
p1
は前のピボット要素です。p2
は現在のピボット要素です。a1
は、前のイテレーションで計算された前の行列の要素です。a2
は、現在のイテレーションで計算された次の行列の要素です。i
は行番号j
は列番号Ɐ(
i, j
)
∈ {1, 3, 4, 5} × {3, 4, 5, 6}
A2
=
24
0
0
0
0
0
24
0
0
0
-1
5
91
25
-5
5
-1
25
115
25
-1
5
-5
25
91
27
33
111
165
111
4
イテレーション 3現在のピボット要素は、前の行列 (
A2
) の要素で、インデックスが
3
,
3
のものです:
p3
=
a2
0
3,3
=
91
;
前の行列 (
A2
) に基づいて次の行列 (
A3
) を計算します。
1)
ピボット要素がある行は、次の行列に変更なく書き直されます。2)
ピボット要素自体を除いて、ピボット要素が配置されている列のすべての要素にゼロを書き込みます。3)
以前のすべてのピボット要素を p3 に置き換えます。初期行列
A3
を書き出し、求めたい要素を未知数としてマークする:
A3
=
91
0
0
0
0
0
91
0
0
0
0
0
91
0
0
××××
25
××××
-5
××××
111
不明な要素を見つけるには、次の式を使用します:
a3
0
i,j
=
a2
0
i,j
*
p3
-
a2
0
3,j
*
a2
0
i,3
p2
p2
は前のピボット要素です。p3
は現在のピボット要素です。a2
は、前のイテレーションで計算された前の行列の要素です。a3
は、現在のイテレーションで計算された次の行列の要素です。i
は行番号j
は列番号Ɐ(
i, j
)
∈ {1, 2, 4, 5} × {4, 5, 6}
A3
=
91
0
0
0
0
0
91
0
0
0
0
0
91
0
0
20
-9
25
410
100
-4
20
-5
100
344
107
102
111
510
444
5
イテレーション 4現在のピボット要素は、前の行列 (
A3
) の要素で、インデックスが
4
,
4
のものです:
p4
=
a3
0
4,4
=
410
;
前の行列 (
A3
) に基づいて次の行列 (
A4
) を計算します。
1)
ピボット要素がある行は、次の行列に変更なく書き直されます。2)
ピボット要素自体を除いて、ピボット要素が配置されている列のすべての要素にゼロを書き込みます。3)
以前のすべてのピボット要素を p4 に置き換えます。初期行列
A4
を書き出し、求めたい要素を未知数としてマークする:
A4
=
410
0
0
0
0
0
410
0
0
0
0
0
410
0
0
0
0
0
410
0
××××
100
××××
510
不明な要素を見つけるには、次の式を使用します:
a4
0
i,j
=
a3
0
i,j
*
p4
-
a3
0
4,j
*
a3
0
i,4
p3
p3
は前のピボット要素です。p4
は現在のピボット要素です。a3
は、前のイテレーションで計算された前の行列の要素です。a4
は、現在のイテレーションで計算された次の行列の要素です。i
は行番号j
は列番号Ɐ(
i, j
)
∈ {1, 2, 3, 5} × {5, 6}
A4
=
410
0
0
0
0
0
410
0
0
0
0
0
410
0
0
0
0
0
410
0
-40
100
-50
100
1440
370
510
360
510
1440
6
イテレーション 5現在のピボット要素は、前の行列 (
A4
) の要素で、インデックスが
5
,
5
のものです:
p5
=
a4
0
5,5
=
1440
;
前の行列 (
A4
) に基づいて次の行列 (
A5
) を計算します。
1)
ピボット要素がある行は、次の行列に変更なく書き直されます。2)
ピボット要素自体を除いて、ピボット要素が配置されている列のすべての要素にゼロを書き込みます。3)
以前のすべてのピボット要素を p5 に置き換えます。初期行列
A5
を書き出し、求めたい要素を未知数としてマークする:
A5
=
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
××××
1440
不明な要素を見つけるには、次の式を使用します:
a5
0
i,j
=
a4
0
i,j
*
p5
-
a4
0
5,j
*
a4
0
i,5
p4
p4
は前のピボット要素です。p5
は現在のピボット要素です。a4
は、前のイテレーションで計算された前の行列の要素です。a5
は、現在のイテレーションで計算された次の行列の要素です。i
は行番号j
は列番号Ɐ(
i, j
)
∈ {1, 2, 3, 4} × {6}
A5
=
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
1440
1440
1440
1440
1440
7
連立一次方程式行列の非ゼロ要素すべてを
1440
で割ります。
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
Answer
Ax = bx
0
1
=
1
;
x
0
2
=
1
;
x
0
3
=
1
;
x
0
4
=
1
;
x
0
5
=
1
;
サイズ5×6方法モンタンテ (Bareiss アルゴリズム)