【TypeScript】連立方程式の答えを求めるアルゴリズム『二分探索』

やりたいこと

こういう連立方程式の解を求めたいときがあります。

4x+y = 10
3x+y = 6

例えばアニメーションで衝突するところを判定したいとか、
経営シミュレーションで固定人変動費を元に最適化したいとか。

図示

グラフに書くとこうなります。

ゴール

要するにこの二つのグラフの交わるところを求めればいいです。

手段

学校で習ったように方程式を解くことで厳密な答えを出すこともできます。
しかし、大体近しい解を出すだけならもっと簡単な方法があります。
for文を使って適当な値を何回か代入すればいいのです。

やり方はこうです。

アルゴリズム

1. とても大きな値(10000など)を右端、とても小さな値(-10000など)を左端とする
2. 右端と左端の中央の値を仮のxとする
3. 仮のxを二つの式に代入してみる
   1. オレンジのyの方が青のyより下に来るなら解はもっと右側にあるはず
   2. オレンジのyの方が青のyより上に来るなら解はもっと左側にある
4. 今度はそれを元にもっと狭い範囲内で2から繰り返す

だいたいこれを100回から1000回くらい繰り返せばほぼ近い解が求まります。

コード

function f1(x: number): number {
  return 10 - 4 * x;
}

function f2(x: number): number {
  return 6 - 3 * x;
}

function main() {
  let left: number = -10000;
  let right: number = 10000;

  for (let i = 0; i < 100; i++) {
    let mid = (left + right) / 2;
    let y1 = f1(mid);
    let y2 = f2(mid);

    if (y1 < y2) right = mid;
    else left = mid;
  }

  console.log(`x = ${left}, y = ${f1(left)}`);
}

main();

x = 4.000000000000001, y = -6.0000000000000036

拡張

ちなみに、このままのコードでは二つの式の上下関係が逆だった場合うまく動きません。
なので、x=-10000の時にどっちが上かでf1とf2を入れ替える処理を入れるともう少し汎用的に使えます。