PlanetMath: proof of Weierstrass approximation theorem

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (22)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

proof of Weierstrass approximation theorem

(Proof)

To simplify the notation, assume that the function is defined on the interval . This involves no loss of generality because if is defined on some other interval, one can make a linear change of variable which maps the domain of to .

The case $f(x) = 1 - \sqrt{1 - x}$

Let us start by demonstrating a few special cases of the theorem, starting with the case $f(x) = 1 - \sqrt{1 - x}$ . In this case, we can use the ancient Babylonian method of computing square roots to construct polynomial approximations. Define the polynomials $P_0, P_1, P_2, \ldots$ recursively as

$\displaystyle P_0 (x) = 0$

$\displaystyle P_{n+1} (x) = {1 \over 2} \left( P_n(x)^2 + x \right)$

It is an obvious consequence of this definition that, if $0 \le x \le 1$ then $0 \le P_n (x) \le 1$ for all

. It is equally obvious that each

is a monotonically increasing function on the interval

. By subtracting the recursion from itself, cancelling, and factoring, we obtain the relation

$\displaystyle P_{n+2} (x) - P_{n+1} (x) = {1 \over 2} (P_{n+1} (x) + P_n (x)) (P_{n+1} (x) - P_n (x))$

From this relation, we conclude that $P_{n+1} (x) \ge P_n (x)$ for all

and all

. This implies that $\lim_{n \to \infty} P_n (x)$ exists for all

. Taking the limit of both sides of the recursion that defines

and simplifying, one sees that $\lim_{n \to \infty} P_n (x) = 1 - \sqrt{1-x}$ . The relation also implies that $P_{n+1} (x) - P_n (x)$ is also a monotonically increasing function of

in the interval

for all

. Therefore,

$\displaystyle P_{n+1} (x) - P_n (x) \le P_{n+1} (1) - P_n (1)$

Summing over

and cancelling, one sees that

$\displaystyle P_{m} (x) - P_n (x) \le P_{m} (1) - P_n (1)$

whenever

. Taking the limit as

approaches infinity, one concludes that

$\displaystyle 1 - \sqrt{1-x} - P_n(x) \le 1 - P_n (1)$

Since the

's converge, for any $\epsilon > 0$ , there exists an

such that $1 - P_n (1) < \epsilon$ . For this value of

, $\vert f(x) - P_n (x)\vert < \epsilon$ , so the Weierstrass approximation theorem holds in this case.

The case $f(x) = \vert x-c\vert$

Next consider the special case $f(x) = \vert x-c\vert$ , where $0 \le c \le 1$ . A little algebra shows that

$\displaystyle \sqrt{(x-c)^2 + \epsilon^2 / 4} - \vert x-c\vert \le \epsilon / 2$

By the case of the approximation theorem already proven, there exists a polynomial

such that

$\displaystyle \vert\sqrt{(x-c)^2 + \epsilon^2 / 4} - P(x)\vert < \epsilon / 2$

when $x \in [0,1]$ . Combining the last two inequalities and applying the triangle inequality, one sees that $\vert f(x) - P(x)\vert < \epsilon$ , so the Weierstrass approximation theorem holds in the case $f(x) = \vert x-c\vert$ .

The case of piecewise linear functions

A corollary of the result just proven is the Weierstrass appriximation theorem for piecewise linear functions. Any piecewise linear function $\phi$ can be expressed as

$\displaystyle \phi(x) = b + \sum_{m=0}^N a_m \vert x-c_m\vert$

for suitable constants $a_0, \ldots , a_N, b, c_0, \ldots , c_N$ . By the result just proven, there exist polynomials $P_0, \ldots,P_N$ such that

$\displaystyle \left\vert a_m \vert x - c_m\vert - P_m \right\vert < \epsilon / N$

By the triangle inequality,

$\displaystyle \left\vert \phi (x) - b - \sum_{m=0}^N P_m \right\vert < \epsilon$

The general proof

Having succeeded in proving all these special cases, we now have the courage to attack the general theorem. In light of the case just proven, it suffices to show that if

is continuous on [0,1] then for all $\epsilon > 0$ there exists a piecewise-linear function $\phi$ such that for all

, $\vert f(x) - \phi (x)\vert < \epsilon / 2$ . For, if such a function exists, then there also exists a polynomial

such that $\vert\phi(x) - P(x)\vert < \epsilon / 2$ , but then $\vert f(x) - P(x)\vert < \epsilon$ .

Since the interval is compact, is uniformly continuous. Hence, for all $\epsilon > 0$ there exists an integer such that $\vert f(x) - f(y)\vert < \epsilon / 2$ whenever $\vert x - y\vert \le 1/N$ .

Define $\phi$ by the following two conditions: If is an integer between and , $\phi (m/N) = f (m/N)$ . On any interval , $\phi$ is linear.

For every point in the interval , there exists an integer such that lies in the subinterval . Since a linear function is bounded by its values at the endpoints, $\phi(x)$ lies between $\phi(m/N) = f(m/N)$ and $\phi((m+1)/N) = f((m+1)/N)$ . Since $\vert f(m/N) - f((m+1)/N)\vert \le \epsilon/2$ , it follows that $\vert f(m/N) - \phi(x)\vert \le \epsilon/2$ . Because $\vert x - m/N\vert \le 1/N$ , it is also true that $\vert f(m/N) - f(x)\vert \le \epsilon/2$ . Hence, by the triangle inequality, $\vert f(x) - \phi(x)\vert < \epsilon$ .