# Algebraic degree of accuracy of a quadrature formula

Given points $$\{x_1, x_2,...,x_n\}$$, in quadrature formula $$\int_{a}^{b}{f(x)}dx \approx \sum_{k=1}^{n}{A_kf(x_k)}$$ prove that there exist coefficients $$A_k$$, $$k = \overline{1, n}$$, for which given formula has algebraic degree of accuracy of $$n-1$$. Can this formula have algebraic degree of accuracy of $$2n$$?

I've solved the first part. If we try to solve the system:

\begin{align*} f_1(x_1)A_1 + f_1(x_2)A_2 + ... + f_1(x_n)A_n &= \,\int_{a}^{b}{f_1(x)}dx \\ f_2(x_1)A_1 + f_2(x_2)A_2 + ... + f_2(x_n)A_n &= \,\int_{a}^{b}{f_2(x)}dx \\ \vdots\\ f_n(x_1)A_1 + f_n(x_2)A_2 + ... + f_n(x_n)A_n &= \,\int_{a}^{b}{f_n(x)}dx \end{align*}

and we take $$f_i(x) = x^{i-1}$$, $$i = \overline{1, n}$$, the system becomes:

\begin{align*} 1A_1 + 1A_2 + ... + 1A_n &= \,\int_{a}^{b}{1}dx \\ x_1A_1 + x_2A_2 + ... + x_nA_n &= \,\int_{a}^{b}{x}dx \\ \vdots\\ x_1^{n-1}A_1 + x_2^{n-1}A_2 + ... + x_n^{n-1}A_n &= \,\int_{a}^{b}{x^{n-1}}dx \end{align*}

The matrix of this system is transposed Vandermonde matrix, so the determinant is nonzero and we have an unique solution that satisfies that $$\int_{a}^{b}{f(x)}dx = \sum_{k=1}^{n}{A_kf(x_k)}$$ for every polynomial $$f$$ that has a degree less than or equal to $$n-1$$.

I am struggling with the second part, I have no idea how to prove it. I know that it can happen that this quadrature formula has an algebraic degree of accuracy of more than $$n-1$$ (although we can only guarantee degree of accuracy of $$n-1$$), but I don't know what's so special about $$2n$$ and why can it never be achieved.

• Just to clarify, you're asking whether it's possible to have a degree $2n$ polynomial $f$ such that there exists $A_1,\ldots,A_n$ satisfying the first equality? Or are you asking whether it's possible to have all degree $2n$ polynomials satisfy the first equality? Commented Aug 1 at 15:15
• I m asking if there exists $A_1, A_2,...,A_n$ such that the equality is satisfied for every polynomial of degree less than or equal to $2n$. If equality holds for polynomials $1, x, x^{2},...x^{2n}$ it holds for every polynomial of degree less than or equal to $2n$. Commented Aug 1 at 15:22
• Try $f(x)=\prod_{i=1}^n(x-x_i)^2$. This polynomial has degree $2n$ and the obvious roots. Commented Aug 1 at 19:21
• Probably I wasn't clear enough, sorry about that. I need to check if $\int_{a}^{b}{f(x)}dx =\sum_{k=1}^{n}{A_kf(x_k)}$ can hold for $f_i(x) = x^{i-1}$, $i = \overline{1, 2n+1}$. Commented Aug 1 at 21:32
• If we don't consider the general case, and we are in some sense lucky with $x_k$ that we are given, we can construct a Gaussian quadrature and get the algebraic degree of accuracy of $2n-1$. But I still don't know can we ever achieve degree of accuracy of $2n-1$. Commented Aug 1 at 21:35