Approximation theory/Proofs


Approximation theory/Proofs

Proof that an "N"th-degree polynomial that gives rise to an error function that has"N" + 2 maxima, of alternating signs and equal magnitudes, is optimal in the sense of approximation theory. Such an optimal polynomial gives the minimum value, over all polynomials, of the maximum error of that polynomial. The maximum error of a polynomial "P" is the maximum, over the domain of approximation, of |"P"("x") − "f"("x")|.

This is most easily seen with a graph. Let "N" = 4 in the example. Suppose "P"("x") isan "N"th-degree polynomial that is level, in the sense that "P"("x") − "f"("x") oscillates among "N" + 2 maxima, of alternating signs, at +ε and −ε.

The error function "P"("x") − "f"("x") might look like the red graph:

"P"("x") − "f"("x") achieves "N" + 2 maxima (2 at the end points), that have the same magnitude -- just over 6 divisions on the above graph.

Now suppose "Q"("x") is another "N"th-degree polynomial that is strictly better than "P".That means that the maxima of its error function must all have strictly smaller magnitudethan ε, so that it lies strictly inside the error graph for "P"("x").The error function for "Q"("x") might look like the blue graph above. This means that ["P"("x") − "f"("x")] − ["Q"("x") − "f"("x")] must alternate between strictly positive nonzero numbers andstrictly negative nonzero numbers, a total of "N" + 2 times. But ["P"("x") − "f"("x")] − ["Q"("x") − "f"("x")] is just "P"("x") − "Q"("x"), an "N"th-degree polynomial. It must have at least"N" + 1 roots between the "N" + 2 places where it has these alternating nonzero values. By the fundamental theorem of algebra, that is impossible.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Theory of cognitive development — The Theory of Cognitive Development (one of the most historically influential theories) was developed by Jean Piaget, a Swiss Philosopher (1896–1980). His genetic epistemological theory provided many central concepts in the field of developmental …   Wikipedia

  • Diophantine approximation — In number theory, the field of Diophantine approximation, named after Diophantus of Alexandria, deals with the approximation of real numbers by rational numbers. The absolute value of the difference between the real number to be approximated and… …   Wikipedia

  • Number theory — A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… …   Wikipedia

  • Analytic number theory — In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve number theoretical problems. [Page 7 of Apostol 1976] It is often said to have begun with Dirichlet s introduction of… …   Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

  • Transcendence theory — In mathematics, transcendence theory is a branch of number theory that investigates transcendental numbers, in both qualitative and quantitative ways.TranscendenceThe fundamental theorem of algebra tells us that if we have a non zero polynomial… …   Wikipedia

  • Bass–Serre theory — is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees. The theory relates group actions on trees with decomposing groups as iterated… …   Wikipedia

  • Piaget's theory of cognitive development — For more information, see Neo Piagetian theories of cognitive development. Piaget s theory of cognitive development is a comprehensive theory about the nature and development of human intelligence first developed by Jean Piaget. It is primarily… …   Wikipedia

  • Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia

  • Effective results in number theory — For historical reasons and in order to have application to the solution of Diophantine equations, results in number theory have been scrutinised more than in other branches of mathematics to see if their content is effectively computable. Where… …   Wikipedia