5

Let's say I was given a set of $d+1$ distinct points known to be from a polynomial $P$ of degree $d$.

So:

$$P = a_dx^d + a_{d-1}x^{d-1} + ... a_1x + c$$

And I have pairs $(x_i, y_i)$ such that: $$P(x_1) = y_1$$ $$...$$ $$P(x_{d+1}) = y_{d+1}$$

My question is: what's the quickest way to find $c$?

The only option I've seen so far is building the Lagrange Polynomial and then evaluating $P(0)$, but it seems wasteful because it reconstructs all $a_i$ coefficients, resulting in $O(d^2)$ operations. Is there anything faster?

Note there are enough points to reconstruct the unique polynomial, and they all lie perfectly on the curve.

BoppreH
  • 1,026

2 Answers2

1

Given are the points

$$ \Big(x_d, y_d\Big),\ \textrm{for} : 1 \le d \le m. $$

and we try to fit them on

$$ f(x) = \sum_{k=0}^n a_k x^k. $$

The quality factor is defined as

$$ Q = \sum_{\ell=1}^m \Big( \sum_{k=0}^n a_k x_\ell^k - y_\ell\Big)^2. $$

Perfect fit means $Q = 0$, best fit means

$$ \frac{\partial Q}{\partial a_\jmath} = 0, $$,

whence

$$ \sum_{k=0}^n \left( a_k \sum_{\ell=1}^m x_\ell^\jmath x_\ell^k -n \sum_{\ell=1}^m x_\ell^\jmath y_\ell \right) = 0, $$

therefore

$$ \boxed{ a_k = n \frac{ \displaystyle \sum_{\ell=1}^m x_\ell^\jmath y_\ell } { \displaystyle \sum_{\ell=1}^m x_\ell^\jmath x_\ell^k }.} $$

So the best fit is given by

$$ \boxed{ f(x) = \sum_{k=0}^n \left\{ n \frac{ \displaystyle \sum_{\ell=1}^m x_\ell^\jmath y_\ell } { \displaystyle \sum_{\ell=1}^m x_\ell^\jmath x_\ell^k } \right\} x^k. } $$

As for your $c$:

$$ \boxed{ c = n \frac{ \displaystyle \sum_{\ell=1}^m x_\ell^\jmath y_\ell } { \displaystyle \sum_{\ell=1}^m x_\ell^\jmath x_\ell^0 }. } $$

johannesvalks
  • 6,407
1

I'd use Cramer's Rule. Set up the system of matrix equations $Ac=y$. Let $A$ be the matrix whose rows are $x^n, x^{n-1}, ...x, 1$ (where $n$ is the degree of the polynomial), where each row's x is one of the given x coordinates. Let $y$ be the column vector whose rows are $y_n$, which each correspond to the x coordinate in the same row. Then $c$ will be a column vector, and it's bottommost entry will be the constant term of the polynomial. Finally, let $A_c$ be the vector formed by replacing the column of ones in $A$ by $y$, then $$c= \frac{\det(A_c)}{\det(A)} $$

Clay Thomas
  • 229
  • 1
  • 7