Chebyshev 近似計算機

 (stuffmatic.com)
2 ポイント 投稿者 GN⁺ 2024-10-06 | 1件のコメント | WhatsAppで共有
  • Chebyshev approximation calculator は、数学関数の近似コードをWeb上で生成してくれるツール
  • ユーザーは f(x)、x min、x max、Terms で近似する関数と区間、項数を指定できる
  • Match x min x max オプションと Coefficients 領域を通じて、区間境界と係数値を確認または調整する流れを提供する
  • Generated code 領域には計算結果がコード形式で表示され、例示画面では c0 から c10 までの係数が見える
  • GitHub リポジトリが連携されており、Webツールの実装コードを直接確認できる

Chebyshev 近似コード生成器

  • Chebyshev approximation calculator は、数学関数を効率的に近似するためのコードを生成する
  • Web UI で近似条件を入力する
    • f(x): 近似する関数
    • x min: 区間の最小値
    • x max: 区間の最大値
    • Terms: 使用する項数
    • Match x min x max: 区間境界に関するオプション

係数の確認と生成コード

  • 画面は Coefficients 領域と Generated code 領域に分かれている
  • 例として表示された係数は c0 から c10 まで確認できる
    • c0 = 0.16793649417016518
    • c1 = -0.12411164956092625
    • c2 = -0.09756341588422193
    • c3 = 0.1800765790518846
    • c4 = -0.06972963647223016
    • c5 = -0.09250127939333941
    • c6 = 0.18076946080324185
    • c7 = 0.15990613621816677
    • c8 = -0.028659588693985123
    • c9 = -0.09494966104347571
    • c10 = -0.04980429834982578
  • 画面には c11 から c39 までの係数項目も表示される

コードリポジトリ

関連記事

1件のコメント

 
GN⁺ 2024-10-06
Hacker News のコメント

  • いいですね。1974年ごろ、IBM 360 アセンブリで平方根を計算する関数を書いて報酬をもらったことがあります
    学部の最終年で、できるだけ効率よく作ってほしいと頼まれました。入力を 0 と 1 の間にスケーリングしたうえで、初期推定にはチェビシェフ近似を使い、ニュートン法を展開した反復を 2 回か 3 回適用して解を求めました。コードを書いて得た初めての収入でした

    • こういう話は好きです。数値解析の最初の授業で、計算の可能性を初めて実感して目が開かれた記憶が今でも残っています

  • 本当に良くできています。こうした近似がどれほど効率的かに魅了されましたし、8ビットコンピュータで三角関数や他の数学関数の実装がなぜああいう形だったのかも、かなり理解できました
    1969年の BBC Research Department による、なぜこの方式が優れているのかを扱ったすばらしい原文資料もあります: https://downloads.bbc.co.uk/rd/pubs/reports/1969-10.pdf
    テイラー近似しか触れたことがないなら、最初は少し魔法のように見えるかもしれません

    • その通りです。数学的な面もそうですし、実際には数行のコードに落ち着くという点も、かなり魔法のように感じます

  • 以前 Sollya で良い結果を得たことがあります: https://www.sollya.org/
    ただし、結果は良かったものの、ソフトウェア自体は少し使いにくいです

    • Sollya はおそらく、この手の作業向けの現代的なツールとしては最高の部類でしょう。内部的にはレメズ近似を行ったあと、LLL で浮動小数点に量子化しており、チェビシェフを直接使っているわけではありません

  • Math.sin(x)/x、つまり sinc 関数を [-3,3] 区間で 7 項近似すると、係数 c0...c6 がすべて NaN になります。バグでしょうか？
    暫定対応として、x が 0 に近い場合は単に 1.0 に強制しました
    if(Math.abs(x) > 1e-8 ){ Math.sin(x)/x } else { 1.0 }

    • 厳密にはバグとは言いにくいです。コードはおそらく、チェビシェフ係数を求めるために x_j = (xmin) + (xmax - xmin)/2(1 + cos(pi[0..j-1]/(j-1)) のような格子点で関数を評価しているはずで、そのうちの 1 つがちょうど 0 だと Math.sin(0)/0 を計算することになり、NaN が出ます
      別の回避策としては、[-3,+3.0000001] のように少し非対称な範囲を使う方法があります
    • ここでの問題は、最初の式が x=0 で定義されておらず、近似コードがそこで転んでいるように見えることです。コードが少し惜しいですね
    • そう、バグです。関数がすべてのチェビシェフ節点で定義されていない場合、アプリはエラーを表示すべきです。すでに見つけているように、今は簡単に回避できます

  • チェビシェフ多項式は近似においてあまりに強力で万能なので、人々は良すぎて詐欺みたいだと思い、かえって使いません
    最初に試す方法はチェビシェフであるべきです。ニューラルネットワークは最後の手段として使うべきです

  • すばらしいです。最近こういうことをやりたいと思っていたのですが、近似を計算するコードを見つけるのが驚くほど難しかったです
    次に関数を高速に近似する必要があるときのためにブックマークしました

    • 実際に動くチェビシェフ近似コードを見つけるのが、私も驚くほど難しかったです。このプロジェクトがそれを変えてくれるといいですね

  • チェビシェフは黒魔術のようです。大学院の授業で導出過程を見ても、そう感じます

  • Nick Trefethen らの Chebfun にも必ず触れるべきです。これはこの内容を、考えられるほぼあらゆる方向に拡張したツールです
    Chebfuns は、実際の数学的な数に対する浮動小数点数のようなものの、関数に対する対応物と見なせます。本当に印象的なソフトウェアです
    https://www.chebfun.org

    • 同意します。あちらの手法は非常に強力で高速です。チェビシェフと超球面関数ベースの手法を使うと、ほとんどの関数を非常に速く機械精度レベルまで近似でき、その後でその表現をより簡単に操作できます
      そのおかげで、微分代数方程式の解を機械精度で求めたり、1次元関数の大域的な最小値・最大値を求めたりするなど、さまざまなことが可能になります
      今は別のアルゴリズムを使っていると理解していますが、Chebfun が以前使っていた基本的な方法論は Trefethen の本 Spectral Methods in Matlab の第6章で見ることができます。超球面関数を使う最新の方法論は、Olver と Townsend の SIAM Review 論文 A Fast and Well-Conditioned Spectral Method に出ています

  • 気になることがあるのですが、ここで聞いていいのか分かりません。以前、Nintendo 64 はサイン関数を計算する能力がなかったため、0 から 2π までのルックアップテーブルを使い、テーブルサイズを減らす賢い手法も使っていた、という動画を見ました
    ニューラルネットワークを学習させて重みを保存したり、関数を作って係数を保存したりして、サイン・コサインを計算することも可能だったのでしょうか？

    • ニューラルネットワークは内部的に三角関数を使うことが多いので、必要以上にはるかに多くの計算が入るでしょう
      CPU サイクルに少し余裕があるなら、粗いルックアップテーブルの値を初期推定として使い、数値近似手法を数回反復するハイブリッド近似を使えます。あるいは元記事のように、多項式近似の先頭側の係数をいくつか保存するだけでもよいです
    • なじみがなければ CORDIC を調べてみるとよいです。昔は一般的な三角関数の裏技で、今でも組み込み方面ではある程度使われています
      ニューラルネットワークは、ある関数のサンプルはあるがどう近似すればよいか分からない場合には有用かもしれませんが、ここではそういうケースではありません
    • どんな関数でも計算するようにニューラルネットワークを学習させることは当然可能ですが、サインのようなよく知られた関数にはまったく筋が悪いです
      ニューラルネットワークは、数学的に解析しにくい対象を評価しなければならないときには優れた解法ですが、三角関数を計算・近似する既知の手法はすでに多数あります
      サインを計算するためにニューラルネットワークを学習させるのは、文字列の反転に LLM を使う数学版のようなものです。できはしますが、より直接的なアプローチで本質的に解ける問題だと知らないときにだけ思いつく発想です
      AI/ML 手法を使う前に、数学者たちがすでに解法を持っているか調べてみる価値は常にあります。最近は、開発者が知らないだけで既知で効率的、さらには最適な解法がある問題に AI/ML を適用することに、多くの労力が費やされている可能性が高いです
    • ニューラルネットワークは本質的に曲線フィッティングなので、可能ではあります。この動画が参考になるかもしれません: https://www.youtube.com/watch?v=FBpPjjhJGhk But what is a neural network REALLY?
      ニューラルネットワークの主な強みは、入力が数個ではなく非常に多いときに発揮されます。sin(x) のような単純な場合には、ここに投稿されているツールのような別の方法があります
    • よく使われる節約手法は、0 から π/2 までだけをテーブルに保存し、追加のインデックスビット 2 個で残りの 3 つの象限を生成する方式です

  • とてもいいですね。遊び心で、どれだけ早くうまく近似できない関数を作れるか試してみたくなりました
    今のところは Math.cos(x * Math.exp(Math.cos(x * x))) が一番よかったです。合成が多く入っているため高速な振動と急な勾配が生じ、チェビシェフでは簡単に近似しにくくなります