Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [polynomials]

The tag has no usage guidance, but it has a tag wiki.

9
votes
2answers
159 views

Numerical stability of higher order Zernike polynomials

I'm trying to calculate higher order (e.g., m=0, n=46) Zernike moments for some image. However, I'm running into a problem ...
1
vote
0answers
58 views

Solve system of polynomial equations with Python

I have 5 at most 4th order polynomials in 5 variables, $$p_i(x_1,x_2,x_3,x_4,x_5) \qquad i = 1, \ldots, 5$$ where all coefficients are either rational or floating point. I'd would like to get the ...
5
votes
2answers
152 views

Polynomial approximation spaces

I often see people using products of 1-D polynomials to do interpolation or projection of smooth multivariate functions over grids or cells because it is intuitive and simple to implement. What are ...
2
votes
1answer
44 views

Test on a set of high degree polynomials whose coefficients in {-1,0,1}

I'm looking for the best way of implementing the following algorithm: consider the set of all polynomials with a high degree (say, degree 30) whose coefficients ranges from a given set of values (say, ...
1
vote
0answers
52 views

Numerical analysis: Chebyshev coefficient representation error

If $x_k$ are the Chebyshev nodes, that is for $n \in \mathbb{N}^*$, we have $x_k = \cos(\pi \frac{2k + 1}{n})$. Now suppose you have approximated values of $x_k$ and $x_{k'}$ for $k,k' \leq n$. In the ...
3
votes
0answers
33 views

Can I expect reasonable results when expanding in scaled Legendre polynomials?

Imagine I want to compute the eigenvalues of an operator $\hat O$ defined on $ L^2(\mathbb{R})$, however using a properly scaled N-dimensional polynomial basis of $ L^2([-a,a]) $ which fulfills ...
3
votes
2answers
413 views

Polynomial Interpolation with Matlab polyfit

Given $N$ data points, does polyfit of degree $N-1$ produces the unique interpolating polynomial? For concreteness, here is a code example: ...
6
votes
2answers
115 views

Building Gaussian-type quadrature schemes with Zernike polynomials

The abscissas for Gauss quadrature are given by the zeros of the Legendre polynomials. The Legendre polynomials form an orthogonal set over $[-1, 1]$, and it is shown in (for instance) Kress that the ...
0
votes
1answer
45 views

Chebychev Polynomial derivatives at zero points and extreme points

I was looking for some help with derivatives of Chebychev polynomials at zero points. The recursive expression, $$ T_{(j+1)}(x) = 2xT_j(x) - T_{(j-1)}(x) $$ has the derivative $$ T'_{j+1}(x) = 2T_j(...
0
votes
1answer
133 views

Derivatives of a Chebychev polynomial

I am using Chebychev collocation nodes for approximation, and my problem requires me to calculate derivatives of the polynomial. I have been reading from a few sources, but I am not sure I understand ...
4
votes
2answers
102 views

Intervals where the sign of a polynomial can be computed reliably

This is a follow-up of a previous question. Let $p$ be a polynomial with floating-point coefficients. Is there a method for finding intervals where evaluating $p$ in floating-point arithmetic always ...
6
votes
3answers
116 views

Accurate evaluation of the sign of a polynomial

Let $p$ be a polynomial with floating-point coefficients and let $a$ be a floating-point value. Is there a method for accurately evaluating the sign of $p(a)$ in floating-point arithmetic? I don't ...
1
vote
0answers
302 views

Polynomial approximation - Vandermonde matrix creation - precision

I am trying to fit a polynomial through 340 points in a 3D space, i.e. $$f(x,y,z) = k$$ I asked previously about the theory behind polynomial interpolation here -> Polynomial interpolation Few ...
0
votes
1answer
98 views

Underdetermined/overdetermined polynomial interpolation

I am trying to apply a polynomial interpolation to 340 points in a 4D space, i.e., $$f(x,y,z)=k\, .$$ What I would like to understand is this: if I use a 6th order polynomial I will end up with 343 ...
4
votes
1answer
179 views

Interpolating a mathematical function using a Hermite Cubic Finite Element Space

I have a Hermite Cubic Finite Element Space on a computer in the form of Matlab m-files. More specifically, I can evaluate four "shape functions" $N_1, N_2, N_3,$ and $N_4$, for which the following ...
3
votes
1answer
66 views

Legendre expansion of $r(x) = f(x)/g(x)$ using a finite number of samples from $f(x)$ and $g(x)$

I have two finite sets of events $\{x_1, ..., x_N\}$ and $\{y_1, ..., y_N\}$ that are sampled from the PDFs $f(x)$ and $g(x)$, respectively, where $x \in [-1,+1]$. I want to estimate the Legendre ...
1
vote
0answers
70 views

Quadrature in finite element methods | How should I compute integrals involving the solution of the last time step?

Let $\Delta\subseteq\mathbb R^2$ denote the triangle spanned by $(0,0)$, $(1,0)$ and $(0,1)$ and $$\mathbb P_r(\Delta):=\left\{p:\Delta\to\mathbb R\mid p(x)=\sum_{|\alpha|\le r}\lambda_\alpha x^\alpha\...
1
vote
0answers
54 views

How to sort 13 enormous polynomials, each having terms with 5 variables ($1>h_0>h_1>h_2>h_3>h_4$)?

Both algebraically or with software (numerically/computationally, for example) is acceptable. Here is a how one of the polynomials looks like ($L<1$ is a constant). I have attached a text file ...
4
votes
0answers
83 views

Closed form PDF/CDF using Orthogonal Polynomial Expansion (gPC)

Consider a random variable which is given by an orthogonal polynomial expansion in one parameter (or polynomial chaos expansion PCE), i.e. , $$ f(\alpha) = \sum\limits_{n=0}^{\infty} \hat{f} (n) \psi ...
1
vote
1answer
190 views

Matlab symbolic differentiation of Legendre polynomials

Consider $f(x)= \sum\limits_{n=0}^N a_n p_n (x)$, where $p_n$ are the Legendre polynomials. If one wants to differentiate $f'$ symbolically, i.e. to compute $$f'(x) = \sum\limits_{n=0}^{N-1} b_n p_n (...
7
votes
1answer
201 views

Numerically stable computation of the Characteristic Polynomial of a matrix for Cayley-Hamilton Theorem

I was wondering if there is any known way to compute the Charactaristic Polynomial P of a matrix A numerically stable in the sense of realizing the Cayley-Hamilton Theorem, i.e. that P(A)=0. I've ...
6
votes
0answers
104 views

How to optimally choose points for multivariable Hermite interpolation?

I have a multi-variate, continuous function $f$ from $R^n$ to $R$, which I can query for its output for any input. I would like to create interpolation polynomial for it. In one-dimensional case ...
1
vote
0answers
68 views

A linear polynomial that is the minimax (best) approximation to $f(x)$ on the interval $[-1,1]$

Suppose you have the following analytical information about a function $f(x)$ on $[-1,1]$: \begin{align*} f(x) &= \frac{1}{x+3}\\ f'(x) & = -\frac{1}{(x+3)^2}\\ f^{''}(x) &= \frac{2}{(x+3)...
2
votes
0answers
95 views

Is the numerical resolution of this huge sparse polynomial system tractable?

I'd like to find numerically a solution to a sparse system of 2000000 polynomial equations of degree 3 with 50000 variables and integer coefficients (or at least to decide whether or not a solution ...
5
votes
1answer
138 views

Computing size of N-Dimensional Polynomial Basis and Efficient Representation of Basis

A problem I have had on my mind recently has been a compact way to compute the size of an $N$-Dimensional Polynomial basis of some order $p$, where a linear basis is $p=1$. I have attempted searching ...
6
votes
1answer
287 views

Polynomial order of an approximation of a section of sine and numerical accuracy

I was playing with the idea that a sine function is periodic. But even within one period there are symmetries, namely the second fourth of a period is the mirror image of the first fourth and the ...
1
vote
0answers
165 views

Calculating lagrange polynomial for 100 points?

I need to calculate the lagrange polynomial which approximates $e^x$ at $101$ points, the points $\frac{k}{101^2}$ for $k\in\{0,1,2\dots 100\}$. I tried the following code: ...
3
votes
0answers
24 views

Choosing suitable polynomial degree based on information in advection stencil

I'm working on a finite volume advection scheme for unstructured meshes which uses a multidimensional polynomial weighted least squares fit for interpolating from cell centres onto faces. In 2D, the ...
10
votes
3answers
596 views

Benchmarks for Gröbner bases and polynomial system solution

In the recent question Solving system of 7 nonlinear algebraic equations symbolically, Brian Borchers experimentally confirmed that Maple can solve a polynomial system that Matlab/Mupad cannot handle. ...
2
votes
1answer
194 views

How to compute the Jacobi matrix (tridiagonal matrix) of a polynomial with a recurrence relationship?

I am looking at Trefethen and Bau Exercise 37.1: I have two normalizations of the Legendre polynomials with corresponding recurrence relations: $$P_n(1)=1$$ which follows $$P_n(x) = \frac{2n-1}{n} x ...
1
vote
1answer
180 views

Approximate function following interpolation (Matlab)

How do you approximate a function for interpolated points? I use the natural cubic spline to interpolate points as follows for n = 500 points: ...
4
votes
1answer
201 views

Chebyshev and Legendre expansions

I am looking at approximating my function $f(x)$ using a Chebyshev and Legendre series and I ran into this question. Is interpolation using $n+1$ Chebyshev nodes the same as representing the ...
4
votes
1answer
205 views

Problems Implementing the Remez Algorithm

So first off: *** This code is not being used in production software. It is a personal project of mine, trying to understand approximation theory and advanced curve fitting. In other words, I'm ...
1
vote
0answers
52 views

Comparison between of higher order interpolations

A while ago I came up with an algorithm which can be used to numerically solve optimal control problems, which basically came down to discretizing the control input $u(t)$ and interpolating this to ...
1
vote
2answers
305 views

Polynomial approximation

Is there any universal method to fill this matrix for any $n$ value: $\textbf{A} = \left[ \matrix{n & \sum x_i & \sum x_i^2 & \cdots & \sum x_i^n \cr \sum x_i & \sum ...
1
vote
0answers
98 views

C++ Library: What is the Most Efficient Library that Factorizes a Polynomial?

I need to know what library is the fastest one that can factorize a polynomial of large degree whose coefficients are big integers. I have tried NTL library to factorize a monic polynomial but it is ...
3
votes
2answers
2k views

C++ Library: What is the common libraries that do polynomial arithmetic?

I need to know what libraries (in C++) support polynomial arithmetic specially over a field. So I can give to it an array of coefficients of polynomial over a field and it returns the roots of ...
2
votes
0answers
94 views

C++: How to find the roots of polynomial modulus N [duplicate]

I need to know what library, given a vector of coefficients and modulus N return the roots of polynomial modulus N. The library should support big integer. I'm coding in C++.
0
votes
1answer
78 views

Representation of polynomial order in CFD codes

I am currently working on a CFD code over a cubic grid. Now, the number of elements used in the simulation is decomposed among the number of processors. Each of those processors (a section of the cube)...
0
votes
1answer
97 views

Spectral Coefficients of Implicit Finite Difference Solution

This is something I've been trying to figure out for a long time, and all I have is vague numerical results. I'm trying to answer the following question analytically: Suppose I have a time dependent ...
6
votes
1answer
295 views

roots of polynomials with small coefficients

I would like to compute the roots of a polynomial with exponentially small coefficients. $$ \sum_{n=0}^N a_n \frac{z^n}{\sqrt{n!}} \tag{$\ast$}$$ where $a_n$ are Normal random variables with mean $0$...
0
votes
1answer
558 views

roots of polynomials of high degree: LinAlgError: Eigenvalues did not converge

I wrote a simple script to generate random polynoimals $\displaystyle f(z)= \sum_{k=0}^N a_k \frac{z^k}{\sqrt{k!}} $ of high degree and find their roots. For more discussion on random polyomials see ...
5
votes
2answers
172 views

What are the numerical methods for huge polynomial systems?

Let a system of $n$ polynomial equations of degree $d$ with $m$ variables. I'm interested in a sparse system with $d = 3$, $n \sim 2000000$, $m \sim 50000$ and integer coefficients. What techniques ...
6
votes
1answer
574 views

Accurate Polynomial Evaluation in Floating Point

What are the most accurate algorithms for evaluating a polynomial using floating point arithmetic? The internet seems to suggest that Horner's method is commonly used. In particular I have a cubic ...
2
votes
1answer
881 views

rational functions in Python

I would like use Python to verify the following identities: $ \frac{1}{1-z} = 1 + z + z^2 + z^3 + \dots $ $ \frac{1}{1-z - z^2} = 1 + z + 2z^2 + 3z^3 + \dots $ $ q \prod_{n \geq 1} (1 - q^n)^{24} = ...
1
vote
0answers
81 views

Prove $T_n(x)$ of Chebyshev Polynomial given the recurrence relation [closed]

Using the recursion formula for Chebyshev polynomials, show that $T_n(x)$ can be written as $$T_n(x)=2^{n-1}(x-x_1)(x-x_2)...(x-x_n)$$ where $x_i$ are the $n$ roots of $T_n$ The recurrence relation:...
1
vote
1answer
76 views

Transfrom a Legendre polynomial from $\int_{-1}^{1}\phi_j(x)\phi_k(x)dx $ into $\int_{a}^{b}\phi_j(t)\phi_k(t)dt$ given $t=\dfrac{1}{2}[(b-a)x+(a+b)]$

The Legendre polynomials satisfy $$\int_{-1}^{1}\phi_j(x)\phi_k(x)dx = \begin{cases} 0 &j\neq k\\\\ \dfrac{2}{2j+1} &j=k \end{cases}$$ Suppose that the best fit problem is given on the ...
2
votes
1answer
1k views

Multivariate Orthogonal Polynomial Generation

I'm trying to apply the stochastic galerkin method to partial differential equation with multiple uniform random coefficients. I'm puzzled as to how to extend the corresponding orthogonal (legendre) ...
1
vote
1answer
68 views

Determine low-order polynomial lower bound

I have a function $f$ I'd like to determine numerically and I have a bunch of $(x, y)$ pairs which approximate the function in the following sense: all of the points satisfy $f(x) \leq y$, most of the ...
3
votes
1answer
149 views

What is the most efficient way to represent a 1D function using $hp$-finite element basis functions

Given a one-dimensional function (let's say infinitely differentiable) and a prescribed accuracy of an L2 (or H1) norm, what is the optimal mesh and (in general arbitrary) polynomial orders on each ...