8
votes
1answer
126 views

is there any such result about Bernstein polynomials?

It is well known that for any lipschitz function $f:[0,1]\rightarrow [0,1]$, we can approximate it by $\sum_{i=1}^n f(i/n) {n\choose i} x^i (1-x)^{n-i}$, and the $L_\infty$ error is $O(1/\sqrt{n})$. ...
0
votes
0answers
51 views

unique positive real root fast computation

What is the fastest way to compute the value of the unique positive real root corresponding to the following polynom: :p(x) = a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x - f = 0 where a, b, c, d, e, f are ...
4
votes
1answer
107 views

Do interpolation nodes have to be dense?

Let $f(x) = \exp(x)$ and $(\xi_i)_{i=0}^\infty, \, \xi_i \in (0,1)$ be a sequence of points from the unit interval. For $n \in \mathbb{N}$ let $P_n$ be a polynomial of degree $n$ that interpolates ...
2
votes
4answers
921 views

Solving a System of Quadratic Equations

I have many polynomial equations in many variables which I want to jointly minimize (in a mean square sense, but you could pick a different reasonable measure which favors anything where all ...
1
vote
1answer
295 views

Is there a quick way to find all roots of a real polynomial with multiple variables?

If I am asked to find the roots of a polynomial of one variable, I will use a computer to estimate the eigenvalues of its companion matrix. Now suppose I'm given a real polynomial of multiple ...
7
votes
2answers
174 views

Finding a low-degree polynomial vanishing on half the zeroes of a polynomial system

Let $f(x)$ be a real polynomial of degree $2d$ without real roots. Let the complex roots be $z_1$, $\bar{z_1}$, $z_2$, $\bar{z_2}$, ..., $z_d$, $\bar{z_d}$ with $z_i$ in the upper half plane. Let ...
4
votes
0answers
155 views

Pair of two-variable polynomial equations of high order

I have the following pair of equations to be solved for two variables $\rho$ and $D$ resulting from a certain Maximum Likelihood Estimation for a time series $X_n > 0$, $n=0, \ldots, N+1$ with $N ...
1
vote
2answers
200 views

Approximation by polynom 1) with respect to supremum-norm 2) I need F_{approx} > F_{exact}

Given a function F, how to find polynom which is best/good approximate with respect supreremum-norm, i.e. minimize over P_{approx} sup|F-P_{approx}| ? I am intersted in polynoms in two variables of ...
12
votes
0answers
254 views

Descartes rule of signs for a noncommutative polynomial in matrix variables

Recently, while studying certain notions of "averaging" a set of input matrices, I obtained a nonlinear polynomial in matrix variables. A simple example is \begin{equation*} \mathcal{G}(X) := X^n - ...
3
votes
2answers
738 views

How to solve a fifth degree polynomIal

Charles Hermite have created a method using elliptic fonctions, to solve fifth degree polynomial, to get around the theory of gallois. Can someone explan me it and give a simple exemple ? Tank you
5
votes
3answers
363 views

Error in Polynomial Root Finding Algorithm with Synthetic Division

I have written a program which finds the roots of polynomial using Newton's Method. After finding the first root to within a tolerance (note that this also finds complex roots), I use synthetic ...
2
votes
1answer
123 views

Spline fit with bounded derivations

How can I do a Spline Fit with bounds on some derivations? Problem Given: Set of data points $t_k, x_k$ Set of nodes $n_i$ order $D$ of the spline (in my case $D=5$) lower and upper bounds ...
14
votes
2answers
951 views

Minimal polynomial with a given maximum in the unit interval

Find the lowest degree polynomial that satisfies the following constraints: i) $F(0)=0$ ii) $F(1)=0$ iii)The maximum of $F$ on the interval $(0,1)$ occurs at point $c$ iv) $F(x)$ is positive ...
2
votes
5answers
4k views

Newton's Method for Finding Multiple Roots

Is it feasible to use Newton's method to find all the roots (if more than one) of a polynomial? Are there any efficient algorithms for finding all the roots?
10
votes
3answers
1k views

Counting roots: multidimensional Sturm's theorem

Sturm's theorem gives a way to compute the number of roots of a one-variable polynomial in an interval [a,b]. Is there a generalization to boxes in higher dimensions? Namely, let $P_1,\dotsc,P_n\in ...
0
votes
0answers
288 views

Value of coefficient in estimation of computational complexity of polynomial division algorithm

Do you know value of coefficient $C$ at $C*n*log(n)$ in $O(n*log(n))$ estimation of complexity of polynomial division algorithm? It would be great if you give me links to paper with information about ...
5
votes
10answers
3k views

Finding all roots of a polynomial

Is it possible, for an arbitrary polynomial in one variable with integer coefficients, to determine the roots of the polynomial in the Complex Field to arbitrary accuracy? When I was looking into ...
3
votes
3answers
748 views

Constraining a least squares minimization to fit a single root?

I have an algorithm that segments depth images using surface fitting. At the moment the algothim uses least squares polymonial fitting, but polynomials are not powerful enough to fit the shapes that ...