クラメルの公式

提供: testwiki
ナビゲーションに移動 検索に移動

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

主張

与えられた線型方程式n 個の変数を持ち、同数 n 本の一次方程式からなる形:{a11x1+a12x2++a1nxn=b1,a21x1+a22x2++a2nxn=b2,an1x1+an2x2++annxn=bn で与えられているとする。あるいはこれを A:=[a11a12a1na21a22a2nan1an2ann],x:=[x1x2xn],b:=[b1b2bn] と置いて テンプレート:Math と行列の記法で書いていてもよい。この時さらに、係数行列 テンプレート:Mvar正則(可逆)であるものと仮定する。これは テンプレート:Math であることと同値。

これらの仮定の下、この方程式系は一意的に解くことができて、一意的な解 テンプレート:Mvar の各成分 テンプレート:Mvarxi=det(Ai)det(A) で与えられる。ただし、ここで用いた行列 テンプレート:Mvar は行列 テンプレート:Mvar の第 テンプレート:Mvar-列 (テンプレート:Math) を系の右辺である テンプレート:Mvar で置き換えて得られる行列 Ai:=[a1,1a1,i1b1a1,i+1a1,na2,1a2,i1b2a2,i+1a2,nan,1an,i1bnan,i+1an,n] とする。

二階線型方程式系

例えば、次の線型方程式系 {1x1+2x2=34x1+5x2=6 を考える。この方程式系の拡大係数行列は (Ab)=[123456] である。クラメルの法則により、系の解は x1=det(A1)det(A)=|3265||1245|=33=1,x2=det(A2)det(A)=|1346||1245|=63=2 と求められる。ここで、縦棒は行列式を表す標準的な記号法に従ったものである。

三階線型方程式系

別な例として次の線型方程式系 {82x1+45x2+9x3=127x1+16x2+3x3=19x1+5x2+1x3=0 をとる。拡大係数行列(Ab)=[8245912716319510] である。解をクラメルの法則に従って求めれば、x1=det(A1)det(A)=|14591163051||8245927163951|=11=1,x2=det(A2)det(A)=|82192713901||8245927163951|=11=1,x3=det(A3)det(A)=|8245127161950||8245927163951|=141=14となる。

歴史

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

クラメルの公式
クラメルの公式

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

x1=b1a22a33b1a32a23b2a12a33+b2a32a13+b3a12a23b3a22a13a11a22a33a11a32a23a21a12a33+a21a32a13+a31a12a23a31a22a13

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

計算量

クラメルの法則を利用して テンプレート:Mvar 元線型方程式系を解こうとすれば、テンプレート:Math 個の行列式を計算しなければならない。このアルゴリズムにおいて算術演算の数は専ら行列式の計算から生じる。

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

テンプレート:Mvar 元一次連立方程式に対して、毎秒 10テンプレート:Sup 回浮動小数点演算可能 (100 Mflops) な性能の計算機で計算すると、計算時間は次の表のようになる[9]:

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

証明の概略と一般化について

証明のために、単位行列の第 テンプレート:Mvar-列を方程式 テンプレート:Math の変数ベクトル テンプレート:Mvar に置き換えて得られる行列 テンプレート:Mvar を考える。例えば テンプレート:Math のときの テンプレート:MathX2=[1x1000x2000x3100x401] で与えられる。このとき、テンプレート:Math および テンプレート:Math となることが示せる。実際、いま挙げた例では AX2=[a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44][1x1000x2000x3100x401]=[a11a11x1+a12x2+a13x3+a14x4a13a14a21a21x1+a22x2+a23x3+a24x4a23a24a31a31x1+a32x2+a33x3+a34x4a33a34a41a41x1+a42x2+a43x3+a44x4a43a44]=[a11b1a13a14a21b2a23a24a31b3a33a34a41b4a43a44]=A2 が成り立っている。また行列式の乗法性により det(A)det(Xi)=det(Ai)det(A)xi=det(Ai)xi=det(Ai)det(A)1 となる。仮定により テンプレート:Math ゆえ テンプレート:Math が存在することに注意。

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

正方線型方程式系 テンプレート:Math が与えられたとき、テンプレート:Math がこの方程式系の解であるならば、各 テンプレート:Mvar について テンプレート:Math が成り立つ。

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

応用

逆行列の計算

テンプレート:Main 行列 テンプレート:Mvar逆行列は単位行列の各列ベクトル テンプレート:Mvar に対して、線型方程式系 テンプレート:Math の解を求めれば求まる。これらの解をクラメルの法則によって求めれば、余因子行列 テンプレート:Math を用いて公式 A1=1det(A)adj(A) を得る。この公式は行列の成分が(実数体 テンプレート:Mathbf のような)とは限らない可換環 テンプレート:Mvar に値をとるとしても成り立つ。従って、行列 テンプレート:Mvar が可逆となることと テンプレート:Math が(テンプレート:Mvar において)可逆単元)となることとが同値であることもわかる。テンプレート:Mvar が体であるときは、この条件は テンプレート:Math と同じである。

斉次方程式系の解法

クラメルの法則を使えば、テンプレート:Math のとき斉次方程式系が自明な解 テンプレート:Math を唯一の解として持つことは容易に示せる。各 テンプレート:Mvar について テンプレート:Mvar の第 テンプレート:Mvar-列を零ベクトルで置き換えて得られる行列 テンプレート:Mvar は、列ベクトルの全体がもはや線型独立ではなく、従って テンプレート:Math が成り立つ。これにより テンプレート:Math が結論付けられる。

上記性質により、線型方程式系 テンプレート:Math の核が零ベクトルのみからなることが従い、従ってそれが唯一の解である。

低次線型方程式系に対する行列式公式

線型方程式系 {ax+by=ecx+dy=f あるいは行列記法で [abcd] [xy]=[ef] を考え、テンプレート:Math と仮定すると、テンプレート:Mvar および テンプレート:Mvar はクラメルの法則で計算できて x=|ebfd| |abcd|=edbfadbc,y=|aecf| |abcd|=afecadbc を得る。三次の場合も同様で、線型方程式系 {ax+by+cz=jdx+ey+fz=kgx+hy+iz=l あるいは [abcdefghi] [xyz]=[jkl] に対して、 x, y, zx=|jbckeflhi||abcdefghi|,y=|ajcdkfgli||abcdefghi|,z=|abjdekghl||abcdefghi| で求められる。

微分幾何

クラメルの法則は微分幾何学における問題を解くのにもきわめて有効である。二つの方程式 テンプレート:Math および テンプレート:Math を考える。テンプレート:Mvarテンプレート:Mvar とが独立変数のとき、テンプレート:Mathテンプレート:Math が陰伏的に定まる。

テンプレート:Math に対する方程式を求めることは、クラメルの法則の自明な応用である。

まず テンプレート:Math2 それぞれの一階微分を計算する: dF=Fxdx+Fydy+Fudu+Fvdv=0,dG=Gxdx+Gydy+Gudu+Gvdv=0,dx=Xudu+Xvdv,dy=Yudu+Yvdv. テンプレート:Mathテンプレート:Math に代入して dF=(Fxxu+Fyyu+Fu)du+(Fxxv+Fyyv+Fv)dv=0,dG=(Gxxu+Gyyu+Gu)du+(Gxxv+Gyyv+Gv)dv=0 を得る。テンプレート:Mvar は独立変数だから テンプレート:Math の係数は テンプレート:Math でなければならない。故に係数に関する方程式を立てれば、{Fxxu+Fyyu=FuGxxu+Gyyu=GuFxxv+Fyyv=FvGxxv+Gyyv=Gv を得る。ここでクラメルの法則を使えば、xu=|FuFyGuGy||FxFyGxGy| が得られる。これは二つの函数行列式 xu=((F,G)(u,y))((F,G)(x,y)) を使って書き表される公式である。同様の公式が テンプレート:Math2 からもそれぞれ導かれる。

整数計画法

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

常微分方程式

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

幾何学的解釈

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

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

方程式系 a11x1+a12x2=b1a21x1+a22x2=b2 はベクトルの間の方程式 x1[a11a21]+x2[a12a22]=[b1b2] と見做すことができる。テンプレート:Mathテンプレート:Math の張る平行四辺形の面積は系の係数行列の行列式 |a11a12a21a22| で与えられる。一般に、変数と方程式を増やして、長さ テンプレート:Mvarテンプレート:Mvar 本のベクトルを考えるとき、その行列式は テンプレート:Mvar-次元ユークリッド空間においてそれらのベクトルが張る平行体 (parallelepiped) の容積 (volume) を与える。

従って、テンプレート:Mathテンプレート:Math の張る平行四辺形の面積は、先ほどの面積の テンプレート:Math-倍である。この平行四辺形の面積は、カヴァリエリの原理により、 テンプレート:Mathテンプレート:Math の張る平行四辺形の面積に等しい。

最後とその前の平行四辺形の面積が等しいことは方程式 |b1a12b2a22|=|a11x1a12a21x1a22|=x1|a11a12a21a22| の成立を意味するが、これはクラメルの法則からも得られる。

不能や不定の場合

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

クラメルの法則は係数行列の行列式が テンプレート:Math でない場合にしか適用できないから、テンプレート:Math の系で行列式の値に基づく不能や不定の場合とは相容れない。

テンプレート:Math あるいはより高次の系に対して、係数行列の行列式が テンプレート:Math のときに言えるのは

(クラメルの公式の)分子になっている行列式のどれか一つでも テンプレート:Math でないならば、系は不能である。

ということだけである。逆は正しくなく、系が不能であっても全ての行列式が テンプレート:Math になる場合がある。例えば テンプレート:Math がそのような系である。

脚注

テンプレート:Reflist

関連文献

関連項目

外部リンク

テンプレート:Wikibooks

テンプレート:線形代数

  1. 1.0 1.1 テンプレート:Citation
  2. テンプレート:Cite book
  3. テンプレート:Cite book
  4. テンプレート:Cite book
  5. テンプレート:Citation
  6. 6.0 6.1 6.2 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.