クラメルの公式

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

線型代数学におけるクラメルの法則あるいはクラメルの公式(クラメルのこうしき、: Cramer's rule; クラメルの規則)は、未知数の数と方程式の本数が一致し、かつ一意的に解ける線型方程式系の解を明示的に書き表す行列式公式である。これは、方程式の解を正方係数行列とその各列ベクトルを一つずつ方程式の右辺のベクトルで置き換えて得られる行列の行列式で表すものになっている。名称はガブリエル・クラーメル (1704–1752) に因むもので、クラーメルは任意個の未知数に関する法則を1750年に記している[1]。なお特別の場合に限れば、コリン・マクローリンが1748年に公表[2]している(また、恐らくはそれを1729年ごろにはすでに知っていたと思われる[3][4][5])。

主張[編集]

与えられた線型方程式が n 個の変数を持ち、同数 n 本の一次方程式からなる形:

で与えられているとする。あるいはこれを

と置いて Ax = b と行列の記法で書いていてもよい。この時さらに、係数行列 A正則(可逆)であるものと仮定する。これは det(A) ≠ 0 であることと同値。

これらの仮定の下、この方程式系は一意的に解くことができて、一意的な解 x の各成分 xi

で与えられる。ただし、ここで用いた行列 Ai は行列 A の第 i-列を形の右辺である b で置き換えて得られる行列

とする。

[編集]

二階線型方程式系[編集]

例えば、次の線型方程式系

を考える。この方程式系の拡大係数行列は

である。クラメルの法則により、系の解は

と求められる。ここで、縦棒は行列式を表す標準的な記号法に従ったものである。

三階線型方程式系[編集]

別な例として次の線型方程式系

をとる。拡大係数行列は

である。解をクラメルの法則に従って求めれば、

となる。

歴史[編集]

クラメルの法則は、ガブリエル・クラメルが1750年に出版した著書 «Introduction à l′analyse des lignes courbes algébriques» [1] の付録 1 に収録されている。クラメルは、より多くの本数の方程式を持つ系を解くための公式の作り方を述べるために、三本の方程式を持つ線型方程式系に対する明示公式を与えている。この頃にはまだ行列式の概念は存在していないので、クラメルは分母と分子が多項式であるような分数を用いて記述していた。以下はクラメルのオリジナルの論文からの抜粋である(これらは行列式に関するライプニッツの公式と同じものである)

クラメルの公式

この例においてクラメルが現代的なものとは違う記法を用いていることが見て取れる。これは現代的な記法で言えば

なることを示すものである。クラメル自身は一意的に解くことができない線型方程式系が存在することを知っていた[6]ベズーは1764年に、一意的に解くことができない線型方程式系では、この式の分母が 0 になることを示す[6]。クラメルもまた、この法則の証明を与えてはおらず、それが成されるのは1815年、コーシーの手によってである(今日用いられるクラメルの法則の記法を導入したのもコーシーである)。ライプニッツは1678年の手書きの論文において既にクラメルの法則を用いているが、しかしこれは後々まで発見されず、線型方程式系の解法の発展に影響を与えはしなかった[6]マクローリンは1748年の著書“Treatise on Algebra”において、方程式が二本または三本であるような場合の線型方程式に対する、クラメルの法則の特別の場合を述べている。マクローリンも、これらの公式をより方程式の本数が多い一般の場合へ拡張するアイデアを持っていたが、クラメルと違って多項式の符号を正しく定める方法が分からなかった[7]。20世紀になって、数学史家ボイヤーは、クラメルとマクローリンのどちらがこの公式を発見したのかという疑義を提示し、名称はマクローリン・クラメルの法則とすべしとした[8]

計算量[編集]

クラメルの法則を利用して n 個の未知数を持つ線型方程式系を解こうとすれば、n + 1 個の行列式を計算しなければならない。このアルゴリズムにおいて算術演算の数は専ら行列式の計算から生じる。

クラメルの法則に現れる行列式をライプニッツの公式に従って計算すれば、(n − 1)·n! 回の掛け算と n − 1 回の足し算をすることになる。これは4本の方程式を持つ系の場合でも、360回の掛け算、4回の割り算、115回の足し算をすることを意味する。これは他の方法に比べて極めて多くの計算を要する。行列式の計算により効率的なアルゴリズムを用いたとしても、線型方程式をクラメルの法則で解こうとすれば、ガウス消去法などよりもずっと大きな計算量が必要になる。

n × n 行列に対して、毎秒 108 回浮動小数点演算可能 (100 Mflops) な性能の計算機で計算すると、計算時間は次の表のようになる[9]:

n 10 12 14 16 18 20
計算時間 0.4秒 1分 3.6時間 41日 38年 16,000年

証明の概略と一般化について[編集]

証明のために、単位行列の第 i-列を方程式 Ax = b の変数ベクトル x に置き換えて得られる行列 Xi を考える。例えば n = 4 のときの X2

で与えられる。このとき、AAi = Xi および det(Xi) = xi となることが示せる。実際、いま挙げた例では

が成り立っている。また行列式の乗法性により

となる。仮定により det(A) ≠ 0 ゆえ det(A)−1 が存在することに注意。

証明の内容を省みれば、クラメルの法則の成立は以下の定理

正方線型方程式系 Ax = b が与えられたとき、x = (x1, x2, …, xn) がこの方程式系の解であるならば、各 i について det(A)xi = det(Ai) が成り立つ。

に集約されることがわかる。もちろん行列 Ai は行列 A の第 i-列を形の右辺である b で置き換えて得られる行列である。方程式の解が一意であるという仮定を外せば、割り算を実行することができないことも起こり得るが、いま述べた形の定理であれば、方程式系の係数が可換環に値をとる場合も含めて常に成立する[10]が、これはもはやクラメルの法則と呼ばれることはない。

応用[編集]

逆行列の計算[編集]

行列 A逆行列は単位行列の各列ベクトル ej に対して、線型方程式系 Axj = ej の解を求めれば求まる。これらの解をクラメルの法則によって求めれば、余因子行列 adj(A) を用いて公式

を得る。この公式は行列の成分が(実数体 R のような)とは限らない可換環 R に値をとるとしても成り立つ。従って、行列 A が可逆となることと det(A) が(R において)可逆単元)となることとが同値であることもわかる。R が体であるときは、この条件は det(A) ≠ 0 と同じである。

斉次方程式系の解法[編集]

クラメルの法則を使えば、det(A) ≠ 0 のとき斉次方程式系が自明な解 x1 = x2 = … = xn = 0 を唯一の解として持つことは容易に示せる。各 i について A の第 i-列を零ベクトルで置き換えて得られる行列 Ai は、列ベクトルの全体がもはや線型独立ではなく、従って det(Ai) = 0 が成り立つ。これにより xi = 0 が結論付けられる。

上記性質により、線型方程式系 Ax = b (det(A) ≠ 0) の核が零ベクトルのみからなることが従い、従ってそれが唯一の解である。

低次線型方程式系に対する行列式公式[編集]

線型方程式系

あるいは行列記法で

を考え、adbc ≠ 0 と仮定すると、x および y はクラメルの法則で計算できて

を得る。三次の場合も同様で、線型方程式系

あるいは

に対して、 x, y, z

で求められる。

微分幾何[編集]

クラメルの法則は微分幾何学における問題を解くのにもきわめて有効である。二つの方程式 F(x, y, u, v) = 0 および G(x, y, u, v) = 0 を考える。uv とが独立変数のとき、x = X(u, v) と y = Y(u, v) が陰伏的に定まる。

xu に対する方程式を求めることは、クラメルの法則の自明な応用である。

まず F, G, x, y それぞれの一階微分を計算する:

dx, dydFdG に代入して

を得る。u, v は独立変数だから du, dv の係数は 0 でなければならない。故に係数に関する方程式を立てれば、

を得る。ここでクラメルの法則を使えば、

が得られる。これは二つの函数行列式

を使って書き表される公式である。同様の公式が xv, yu, yv からもそれぞれ導かれる。

整数計画法[編集]

クラメルの法則は、制約行列が完全単模 (totally unimodular) で、右辺値が整数、基本解も整数であるような整数計画問題を解くのにも利用できる。これにより整数問題を解くことが大幅に容易になる。

常微分方程式[編集]

クラメルの法則は非斉次の線型微分方程式の一般解を定数変化法で導く場合にも利用できる。

幾何学的解釈[編集]

クラメルの法則の幾何学的解釈: 二つ目と三つ目の影を付けた平行四辺形の面積は等しく、一つ目のそれの x1-倍である。この等値性はクラメルの法則から従う。

クラメルの法則を幾何学的に解釈することもできて、それは証明や幾何学的な性質を詳しく見ることによって得られる。この幾何学的な論法は、以下に例示する二次元の場合のみならず、一般の場合においても通用する。

方程式系

はベクトルの間の方程式

と見做すことができる。t(a11, a21) と t(a12, a22) の張る平行四辺形の面積は系の係数行列の行列式

で与えられる。一般に、変数と方程式を増やして、長さ nn 本のベクトルを考えるとき、その行列式は n-次元ユークリッド空間においてそれらのベクトルが張る平行体 (parallelepiped) の容積 (volume) を与える。

従って、x1t(a11, a21) と t(a12, a22) の張る平行四辺形の面積は、先ほどの面積の x1-倍である。この平行四辺形の面積は、カヴァリエリの原理により、 x1t(a11, a21) + x2t(a12, a22) と t(a12, a22) の張る平行四辺形の面積に等しい。

最後とその前の平行四辺形の面積が等しいことは方程式

の成立を意味するが、これはクラメルの法則からも得られる。

不能や不定の場合[編集]

方程式系が、不能 (incompatible) であるとは解が存在しないことを言う。また不定 (indeterminate) であるとは、一つ以上の解を持つことを言う。線型方程式の場合(基礎体が無限体であるとすると)、それが不定な系ならば一つ以上の変数が任意の値を取り得るから、解は無数に存在する。

クラメルの法則は係数行列の行列式が 0 でない場合にしか適用できないから、2 × 2 の系で行列式の値に基づく不能や不定の場合とは相容れない。

3 × 3 あるいはより高次の系に対して、係数行列の行列式が 0 のときに言えるのは

(クラメルの公式の)分子になっている行列式のどれかが 0 でないならば、系は不能である。

ということだけである。逆は正しくなく、系が不能であっても全ての行列式が 0 になる場合がある。例えば x + y + z = 1, x + y + z = 2, x + y + z = 3 がそのような系である。

脚注[編集]

  1. ^ a b Cramer, Gabriel (1750) (French), Introduction à l'Analyse des lignes Courbes algébriques, Geneva: Europeana, pp. 656-659, http://www.europeana.eu/resolve/record/03486/E71FE3799CEC1F8E2B76962513829D2E36B63015 2012年5月18日閲覧。 
  2. ^ MacLaurin, Colin (1748). A Treatise of Algebra, in Three Parts.. http://archive.org/details/atreatisealgebr03maclgoog. 
  3. ^ Boyer, Carl B. (1968). A History of Mathematics (2nd ed.). Wiley. pp. 431. 
  4. ^ Katz, Victor (2004). A History of Mathematics (Brief ed.). Pearson Education. pp. 378–379. 
  5. ^ Hedman, Bruce A. (1999), “An Earlier Date for "Cramer's Rule"”, Historia Mathematica 4(26): 365–368, doi:10.1006/hmat.1999.2247 
  6. ^ a b c Jean-Luc Chabert et al.. A History of Algorithms. Form of the Pebble to the Microchip. Springer-Verlag, 1999, ISBN 3-540-63369-3, pp. 284–287. (クラメルのオリジナルの本の英語訳も載っている)
  7. ^ Antoni A. Kosinski: Cramer's Rule Is Due to cramer. In: Mathematics Magazine. Bd. 74, Nr. 4, Oktober 2001, S. 310–312.
  8. ^ Bruce A. Hedman: An Earlier Date for „Cramer's Rule“ In: Historica Mathematica. Bd. 24, 1999, S. 365–368.
  9. ^ W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler, Springer, 2006, ISBN 3-540-25544-3
  10. ^ Serge Lang: Algebra. 2. Auflage. Addison-Wesley, 1984, ISBN 0-201-05487-6, S. 451.

関連文献[編集]

関連項目[編集]

外部リンク[編集]