有理多項式補間

説明

このタスクでは、 N ポイント(x 1 、y 1
)、…、(x <�別の
x i
の値を使用して多項式を補間することですこれらの点。ラグランジュ補間が何であるか知っていれば、このセクションをスキップすることができます。

多項式補間の目的は、(一意の)多項式の p(x)を構築することです。 p(x
i )= y i
N-1 すべての i
= 1 … N
に対して これを行う1つの方法は、 N
ラグランジュ基底多項式を構築し、線形結合を形成することです。このような基底多項式は、以下のように定義される。

                          l_i(x) := cfrac{x-x_1}{x_i-x_1}cdotscfrac{x-x_{i-1}}{x_i-x_{i-1}}cdotcfrac{x-x_{i+1}}{x_i-x_{i+1}}cdotscfrac{x-x_N}{x_i-x_N}

x 1 、…、x i-1 のポイントで l i
、x i + 1 、… 、x N は構造によって0であり、x i
に対して1であり、y i
に設定し、y i
に設定します。今度は、N個のそのような多項式を0以外のすべての点で1つを除いて単純に追加して、目的の結果を得ることができます。したがって、最終的な解決策は次のとおりです。

                                                        p(x) = overset{N}{underset{i=1}{sum}} y_i cdot l_i(x)

チャレンジ

  • 入力は任意の合理的なフォーマット(タプル、ポイント、セットなどのリスト)で N
    データポイントで構成されます。
  • 座標はすべて整数値になります
  • 出力は任意の合理的な形式の多項式である:係数のリスト、多項式オブジェクトなど
  • 出力が正確でなければならない – いくつかの解が有理係数を持つことを意味する
  • 1/2 の書式設定は重要ではありません( 1 の代わりに
    2/2 または 1%2 >など)を使用することができます。
  • 無効な入力を処理する必要はありません(空の入力や x 座標が繰り返される入力など)。

テストケース

これらの例は、係数を降順にリストします(たとえば、 [1,0,0] は多項式の x
2
に対応します)。

[(0,42)] -> [42]
[(0,3),(-18,9),(0,17)] -> undefined (you don't have to handle such cases)
[(-1,1),(0,0),(1,1)] -> [1,0,0]
[(101,-42),(0,12),(-84,3),(1,12)] -> [-4911/222351500, -10116/3269875, 692799/222351500, 12]
ベストアンサー

Pari/GP, 14 bytes

polinterpolate

[x1、...、xn][y1、...、yn]
の2つのリストを入力として受け取ります。多項式を出力します。

オンラインで試す!


Pari/GP, 37 bytes, without built-in

f(x,y)=y/matrix(#x,#x,i,j,x[j]^(i-1))

[x1、...、xn][y1、...、yn]
の2つのリストを入力として受け取ります。係数のリストを出力します。

オンラインで試してみてください!

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です