Polynomial Interpolation: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 8: | Line 8: | ||
== Parameters == | == Parameters == | ||
n: number of points | $n$: number of points | ||
d: dimension of space | $d$: dimension of space | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 33: | Line 33: | ||
[[File:Polynomial Interpolation - Time.png|1000px]] | [[File:Polynomial Interpolation - Time.png|1000px]] | ||
Latest revision as of 09:12, 28 April 2023
Description
Given a finite number of points $x_1, \ldots , x_n$, some real constants $y_1, \ldots , y_n$ and a subspace $V$ of $\Pi^d$, find a polynomial $p \in V$, such that
$p(x_j) = y_j$, $j = 1, ... , n$
Parameters
$n$: number of points
$d$: dimension of space
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Gaussian elimination | -150 | $O(n^{3})$ | $O(n^{2})$ | Exact | Deterministic | |
| Bjorck | 1970 | $O(n^{2})$ | $O(n)$ | Exact | Deterministic | Time & Space |
| Higham | 1988 | $O(n^{2})$ | $O(n)$ | Exact | Deterministic | Time & Space |
| Calvetti, Reichel | 1993 | $O(n^{2})$ | $O(n)$? | Exact | Deterministic | Time |
Time Complexity Graph
