CodeIQ MAGAZINECodeIQ MAGAZINE

プログラミング言語Egisonによるガロア理論入門 (1) ―2次方程式の解の導出

2017.05.09 Category:技術コラム Tag: , , ,

  • 11
  • このエントリーをはてなブックマークに追加

プログラムにより代数方程式を解くとはどういうことなのか。今回は代数方程式の例の中で、最も単純な代数方程式である2次方程式の解を導出するプログラムをEgisonで書いてみます。
本連載では、いくつかの代数方程式を解くプログラムを分析し、ガロア理論としてまとめられている代数方程式を解くアルゴリズムに潜む法則をプログラミングしながら感じることです。
by 江木聡志(楽天技術研究所・Egison作者)

プログラムで代数方程式を解く

数式処理システムの機能を持つプログラミング言語Egisonでは、√2や√3のような数を浮動小数点数として近似することなくプログラム上で扱うことができます。

この機能を用いると、2次方程式、3次方程式、4次方程式を始めとする代数方程式の解を求めるプログラムを記述することができます。

実は、2次方程式、3次方程式、4次方程式や、x^n – 1 = 0のような様々な種類の代数方程式を解くアルゴリズムには、一般的な法則が潜んでいることが知られています。

本記事では、まず、最も単純な代数方程式である2次方程式の解を導出するプログラムをEgisonで書いてみます。

数式処理システムとは

数式処理システムとは、シンボリックな計算を実行することができる言語処理系のことをいいます。

シンボリックな計算とは、例えば、x + x = 2x(x + y)^2 = x^2 + 2 x y + y^2のようにxyのような変数をシンボルとしてプログラム上で数と同様に扱い計算することです。

Egisonでは未定義の変数は全てシンボルとして扱われるようになっています。

シンボリックな計算をサポートしている既存の数式処理システムとしては、Mathematicaや、Maxima、Pythonの拡張ライブラリとして実装されているSymPyなどが有名です。

その中でEgisonは微分幾何学の計算を簡潔に表現することに特化した数式処理機能を持っています。 特にテンソル計算を簡潔に記述するための添字記法をプログラムでも自然に使うことができるのが大きな特徴です。

公式ウェブサイトには、学部レベルの数学の計算から、最近発表された数学論文でなされている特性類の計算までを含むEgisonの数式処理機能を用いたデモを公開しています。 ぜひこちらもご覧になってみてください。

代数的な数をコンピューターで扱ってみる

シンボリックな計算は、代数的数を浮動小数点数で近似することなく、扱うことを可能にします。

以下の例では、平方根を浮動小数点数で近似することなく扱っています。

例えば、√3は、二乗したら整数3になる数としてプログラム上でも表現することができます。

sqrt関数は、引数で与えられた数の平方根を返す関数です。

sqrt関数の引数に4を渡すとその平方根である2を返します。

sqrt関数の引数に3を渡すと、この式はこれ以上簡単にできないので(sqrt 3)をそのまま返します。

(sqrt 3)を2つ掛け合わせると、3になります。

(sqrt 2)(sqrt 3)を掛け合わせると、(sqrt 6)となります。

(sqrt 12)は、√12が2√3と簡約化されるのと同様に、(* 2 (sqrt 3))となります。

虚数iを扱うことも可能になっています。

iは2乗すると-1になる数となっています。

本節で登場したsqrt関数やiの挙動は、Egisonを起動した際に自動的に読み込まれるEgisonライブラリの中で、Egisonのパターンマッチを用いて定義されています。

2次方程式の解法

この節では、2次方程式a x^2 + b x + c = 0の解法を復習します。

2次方程式は以下の4ステップのアルゴリズムで解くことができます。

  • ステップ1: x^2の係数で方程式全体を割り、x^2の係数を1にします。
  • ステップ2: xの係数がbであるとすると、x = y - b / 2で置換します。
  • ステップ3: y^2 + c = 0の解を得ます。
  • ステップ4: ステップ3で求めたyの値をx = y - b / 2に代入することにより、xの値を求めます。

2次方程式の解を導出するプログラム

本節では、前節で復習した2次方程式の解法をプログラムとして実装します。

q-f関数は、引数として式と変数を取ります。

1引数目の式は、2引数目の変数についての2次式である必要があります。

結果として、1引数目の2次式が0に等しいとしたときの解を返します。

以下では方程式x^2 - 2 x + 1 = 0の解を求めています。

2次方程式は2つの解を持ち、この場合は1を重解として解に持つので、1を2つ含むタプル[1 1]を返しています。

q-f'関数は、引数として2次方程式の係数を取ります。

上の例と同じ方程式x^2 - 2 x + 1 = 0の解を求めるには以下のようにします。

q-fq-f'関数の動作については、次節に多くの例を載せましたので、そちらもぜひ参照してください。

では、q-f関数の実装をみていきましょう。

q-f関数の中ではcoefficients関数が使われています。

coefficients関数は、引数として式と変数を取り、係数(coefficients)をリストとして返します。

この関数を用いて、q-f'関数に渡す引数を抽出する操作が、q-f関数の定義の中では記述されています。

次に、q-f'関数の実装をみていきます。

この関数は、以下の3つのパターンで分岐しています。

  • パターン1: x^2 + c = 0
  • パターン2: x^2 + b x + c = 0
  • パターン3: a x^2 + b x + c = 0

パターン3、パターン2、パターン1の順番で説明していきます。

パターン3:a x^2 + b x + c = 0は3つ目のマッチ節により処理されます。

ここでは、前節のステップ1の処理が行われています。

全ての係数をaで割り、再帰的にq-f'に渡します。

それにより、次はパターン1かパターン2に該当する方程式として次は処理されます。

パターン2:x^2 + b x + c = 0は2つ目のマッチ節により処理されます。

ここでは、前節のステップ2とステップ4の処理が行われています。

まず、x = y - b / 2という置換を行い、その結果得られたyについての2字方程式をq-f関数を用いて解いています。

この変数置換のために、with-symbols式とsubstitute関数が使われています。

with-symbols式は、第1引数に与えられたシンボルを第2引数に与えられた式の内部で使える局所シンボルとして生成するための構文です。

substitute関数は、第1引数で与えられた転置を第2引数に与えられた式に適用する関数です。

その結果得られたyについての2つの解のそれぞれから、関数2#[(+ (* -1 (/ b 2)) %1) (+ (* -1 (/ b 2)) %2)]により、’b/2’を引くことにより、xについての解を求めています。

パターン1:x^2 + c = 0は1つ目のマッチ節により処理されます。

ここでは、前節のステップ3の処理が行われています。

単純に定数項を移項したものの平方根を返します。

‘√-c’と’-√-c’という2つの解を返しています。

プログラムの検証

本節では、前節で定義したq-f関数を実際に動かしてみます。

また、2次式の係数を変数abcにすると中学校や高校で習う解の公式を得ることができます。

q-f'関数は、引数として2次方程式の係数を取ります。

ところで、関数q-f'は、2次方程式の解の公式を用いて、以下のようにシンプルに実装し直すことが可能です。

まとめ

本記事では、2次方程式の解を求めるプログラムを書きました。

同じように、3次方程式と4次方程式の解の公式や、1のn乗根を求めるプログラムも記述できます。

2次方程式の解を求めるアルゴリズムは、本記事で解説したように単純でしたが、3次方程式や4次方程式を解くアルゴリズムは複雑です。

これらのアルゴリズムを分析すると、代数方程式を解くアルゴリズムの一般的な法則を観察することができます。

次回以降の記事では、3次方程式を解くプログラムを分析し、その法則を観察してみたいと考えています。

次回予告

3次方程式を解くプログラムの構造は、2次方程式を解くプログラムと非常によく似ていて、以下のようになります。

c-f関数は以下のように動作します。

c-f関数を使って、3次方程式の解の公式を得ることもできます。

次回以降の記事ではこのプログラムについて解説し、代数方程式の解法の法則について触れたいと考えています。

ご期待ください。

CodeIQ運営事務局よりお知らせ

楽天技術研究所・江木聡志さんから、Egisonに関するプログラミング問題を出題していただきました。ぜひ、チャレンジしてみてくださいね!

  • 11
  • このエントリーをはてなブックマークに追加

■この記事を書いた人

avatar

江木聡志(楽天技術研究所・Egison作者)

楽天技術研究所 研究員 1986年生まれ。2010年、東京大学理学部情報科学科卒業。2012年、同大学院情報理工学系研究科修士(コンピュータ科学)。2010年、プログラミング言語Egisonの設計・開発を開始。2011年度未踏IT人材発掘・育成事業スーパークリエータ受賞。2013年11月に楽天技術研究所に入所し現職。2015年2月、ソフトウェアジャパンアワード受賞。2015年10月、日本OSS奨励賞受賞。

■関連記事

数式処理システムとしてのプログラミング言語Egisonの紹介... シンボリックな計算とは シンボリックな計算とは、x + x = 2xや(x + y)^2 = x^2 + 2 x y + y^2のようにxやyといったシンボルをプログラム上で数と同様に扱い計算することをいいます。 シンボリックな計算をサポートしている既存の数式処理システムとしては、Mathema...
エンジニアにこそ求められる?「ビジネス数学」を学んでみよう!... 学校の数学と何が違う? 学生生活でたくさん勉強したはずの数学。でも仕事をする上で役に立っていないと感じている人も多いのではないでしょうか。 高校生の頃から文系に進み、受験勉強や大学でも数学を避けてきた人も多くいます。実際、多くの会社員にとって、仕事で三角形の合同を証明することはありませんし、微分...
アドテクの裏側で暗躍!?ユーザーの嗜好を紐解くベイジアンネットワークとは... ベイジアンネットワーク -「因果」のモデリング ベイズの定理を説明した前編では、以下のような問いを設定していました。 患者Aは咳が出て節々が痛く、喉が腫れている。病名は何? プリンターが不調。縦線のノイズが入る。どこが故障している? それぞれ、医師やカスタマーサポートであれば解決できる...
「機械学習クラスタのベイズって何?」という人へ──まずは『ベイズの定理』を学んでみよう... 「ベイズ」や「ベイジアン」を聞き流し続けているあなたへ この記事では分かりやすく、ベイズ統計の基本中の基本である「ベイズの定理」の使い方について説明していきます。 実例で分かるベイズの定理 – 感染検査薬の実用性を測る あなたは某大手製薬会社で、ある伝染病の検査薬開発に関わる研究開発社員だ...
Egison独自の機能の紹介──パターンマッチ指向プログラミング言語Egison紹介(第3回)... パターンマッチとは パターンマッチは、複雑なデータの操作を簡潔な記述で扱うための機能です。 パターンマッチにより、複数の何重にもネストするアクセサー関数やループ、条件分岐を記述せずに、簡潔なパターンを記述するだけで、複雑なデータ型の操作をプログラマは記述できるようになります。 図1. パタ...
Egisonによる関数型プログラミング入門──パターンマッチ指向プログラミング言語Egison紹介(... 関数型プログラミングとは 関数型プログラミング言語とは、関数が第一級オブジェクトであるプログラミング言語のことを言います。 関数が第一級オブジェクトであるというのは、数のようなデータと同じように、関数自体を関数の引数として渡せ、返り値として返せるということです。この機能は、関数の高度なモジュール...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ