%%  chapter-01.tex
%%  Approximation Theory: Chapter 1
%%  Neal L. Carothers
%%  Bowling Green State University
%%  Bowling Green, Ohio  43403
%%  carother@math.bgsu.edu
%%  http://www.bgsu.edu/~carother/


\input 680-setup.tex

\parskip = 6 true pt minus 2 true pt

\chaptertitle = {Preliminaries}

\centerline{\hfil\tf Preliminaries\hfil}
\vskip-\baselineskip
\line{\sc Math 680 \hfil 6/27/94}

\noindent{\bf Introduction}

\noindent
In 1853, the great Russian mathematician, P.\ L.\ Chebyshev
[\v Ceby\v sev], while working on a problem of {\sl linkages},
devices which translate the linear motion of a steam engine
into the circular motion of a wheel, considered the following
problem:

{\narrower\noindent
Given a continuous function $f$ defined on a closed interval
$[\,a,b\,]$ and a positive integer $n$, can we ``represent''
$f$ by a polynomial $p(x)=\sum_{k=0}^na_kx^k$, of degree at
most $n$, in such a way that the maximum error at any point
$x$ in $[\,a,b\,]$ is controlled?  In particular, is it 
possible to construct $p$ in such a way that the error
$\Max_{a\le x\le b}|f(x)-p(x)|$ is minimized?\par}

\noindent
This problem raises several questions, the first of which
Chebyshev himself ignored:

\itemitem{--}
Why should such a polynomial even {\sl exist\/}?
\itemitem{--}
If it does, can we hope to {\sl construct\/} it?
\itemitem{--}
If it exists, is it also {\sl unique\/}?
\itemitem{--}
What happens if we change the measure of the error to,
say, $\int_a^b|f(x)-p(x)|^2\,dx$\/?

The problem is perhaps best understood by rephrasing it
in modern terms.  What we have here is a problem of
{\sl linear approximation\/} in a {\sl normed linear space}.
Recall that a {\sl norm\/} on a (real) {\sl vector space\/}
$X$ is a nonnegative function on $X$ satisfying
\itemitem{}
{$\Vert x\Vert\ge0$ and $\Vert x\Vert=0\iff x=0$\par}
\itemitem{}
{$\Vert \alpha x\Vert=|\alpha|\Vert x\Vert$ for $\alpha\in\R$\par}
\itemitem{}
{$\Vert x+y\Vert\le\Vert x\Vert+\Vert y\Vert$ for any $x$, $y\in X$.\par}
\par\noindent
Any norm on $X$ induces a metric or distance function by setting
${\rm dist}(x,y)=\Vert x-y\Vert$.  The abstract version of our
problem(s) can now be restated:

\itemitem{--}
Given a subset (or even a {\sl subspace\/}) $Y$ of $X$ and a
point $x\in X$, is there an element $y\in Y$ which is
``nearest'' to $x$; that is, can we find a vector $y\in Y$
such that $\Vert x-y\Vert=\Inf_{z\in Y}\Vert x-z\Vert$\/?
If there is a ``best approximation'' to $x$ from elements
of $Y$, is it unique?  

\filbreak

\noindent{\bf Examples}

\item{1.}
In $X=\R^n$ with its usual norm 
$\Vert (x_k)_{k=1}^n\Vert_2=\left(\sum_{k=1}^n|x_k|^2\right)^{1/2}$,
the problem has a complete solution for any subspace
(or, indeed, any {\sl closed convex set\/}) $Y$.
This problem is often considered in Calculus or Linear
Algebra where it is called ``least-squares approximation.''
A large part of the current course will be taken up with
least-squares approximations, too.  For now let's simply
note that the problem changes character dramatically if
we consider a different norm on $\R^n$.  

\item{}
Consider $X=\R^2$ under the norm $\Vert(x,y)\Vert=\max\{|x|,|y|\}$,
and consider the subspace $Y=\{(0,y):y\in\R\}$ (i.e., the $y$-axis).  
It's not hard to see that the point $x=(1,0)\in\R^2$ has infinitely
many nearest points in $Y$; indeed, every point $(0,y)$, $-1\le y\le1$,
is nearest to $x$.  

\item{2.}
There are many norms we might consider on $\R^n$.  Of particular
interest are the $\ell_p$-norms; that is, the scale of norms:
$$\eqalignno{%
\Vert(x_i)_{i=1}^n\Vert_p&=\left(\sum_{k=1}^n|x_k|^p\right)^{1/p},
	\qquad 1\le p<\infty,\cr
\noalign{and}
\Vert(x_i)_{i=1}^n\Vert_\infty&=\Max_{1\le i\le n}|x_i|.\cr
}$$
It's easy to see that $\Vert\cdot\Vert_1$ and $\Vert\cdot\Vert_\infty$
define norms.  The other cases take a bit more work; we'll supply
full details later.

\item{3.}
Our original problem concerns $X=C[\,a,b\,]$, the space of all
continuous functions $f:[\,a,b\,]\to\R$, under 
the {\sl uniform norm}, $\Vert f\Vert=\Max_{a\le x\le b}|f(x)|$.
The word ``uniform'' is used because convergence in this
norm is the same as uniform convergence on $[\,a,b\,]$:
$$\Vert f_n-f\Vert\to0\iff f_n\uniformto f \hbox{ on } [\,a,b\,].$$
In this case we're interested in approximations by elements of
$Y={\cal P}_n$, the {\sl subspace\/} of all polynomials of degree
at most $n$ in $C[\,a,b\,]$.  It's not hard to see that ${\cal P}_n$
is a finite-dimensional subspace of $C[\,a,b\,]$ of dimension
exactly $n+1$.  (Why?)

\item{}
If we consider the subspace $Y={\cal P}$ consisting of {\sl all\/}
polynomials in $X=C[\,a,b\,]$, we readily see that the existence 
of best approximations can be problematic.  It follows from the
Weierstrass theorem, for example, that each $f\in C[\,a,b\,]$ has
distance $0$ from ${\cal P}$ but, since not every $f\in C[\,a,b\,]$ is 
a polynomial (why?),\ we can't hope for a best approximating
polynomial to exist in every case.  For example, the function
$f(x)=x\sin(1/x)$ is continuous on $[\,0,1\,]$ but can't possibly
agree with any polynomial on $[\,0,1\,]$.  (Why?)

The key to the problem of polynomial approximation is the fact
that each ${\cal P}_n$ is {\sl finite-dimensional}.  To see this,
it will be most efficient to consider the abstract setting of
finite-dimensional subspaces of arbitrary normed spaces.

\noindent{\bf ``Soft'' Approximation}

\proclaim Lemma.
Let $V$ be a finite-dimensional vector space.  Then,
all norms on $V$ are equivalent.  That is, if $\Vert\cdot\Vert$
and $\trivert\cdot\trivert$ are norms on $V$, then there
exist constants $0<A,B<\infty$ such that
$$A\,\Vert x\Vert\le\trivert x\trivert\le B\,\Vert x\Vert$$
for all vectors $x\in V$.

\proof
Suppose that $V$ is $n$-dimensional and that $\Vert\cdot\Vert$
is a norm on $V$.  Fix a basis $e_1,\ldots,e_n$ for $V$ and 
consider the norm
$$\left\Vert\sum_{i=1}^na_ie_i\right\Vert_1
	=\sum_{i=1}^n|a_i|=\Vert(a_i)_{i=1}^n\Vert_1$$
for $x=\sum_{i=1}^na_ie_i\in V$.  Since $e_1,\ldots,e_n$ is a
basis for $V$, it's not hard to see that $\Vert\cdot\Vert_1$ is, 
indeed, a norm on $V$.  It now suffices to show that
$\Vert\cdot\Vert$ and $\Vert\cdot\Vert_1$ are equivalent.
(Why?)

One inequality is easy to show; indeed, notice that
$$\left\Vert \sum_{i=1}^na_ie_i\right\Vert 
	\le \sum_{i=1}^n|a_i|\,\Vert e_i\Vert
	\le \left(\Max_{1\le i\le n}\Vert e_i\Vert\right)\sum_{i=1}^n|a_i|
	=B\,\left\Vert \sum_{i=1}^na_ie_i\right\Vert_1.$$
The real work comes in establishing the other inequality.

To begin, notice that we've actually set-up
a correspondence between $\R^n$ and $V$; specifically, the
map $(a_i)_{i=1}^n\mapsto \sum_{i=1}^na_ie_i$ is obviously
both one-to-one and onto.  Moreover, this correspondence is
an {\sl isometry\/} between $(\R^n,\Vert\cdot\Vert_1)$
and $(V,\Vert\cdot\Vert_1)$.  

Now the inequality we've just established shows that the 
function $x\mapsto \Vert x\Vert$ is {\sl continuous\/} on the 
space $(V,\Vert\cdot\Vert_1)$ since 
$$\bigl|\,\Vert x\Vert-\Vert y\Vert\,\bigr|
	\le\Vert x-y\Vert\le B\,\Vert x-y\Vert_1$$
for any $x$, $y\in V$.  Thus, $\Vert\cdot\Vert$ assumes a
{\sl minimum\/} value on the {\sl compact\/} set
$$S=\{x\in V:\Vert x\Vert_1=1\}.$$
(Why is $S$ compact?)  In particular, there is some $A>0$
such that $\Vert x\Vert\ge A$ whenever $\Vert x\Vert_1=1$.
(Why can we assume that $A>0$\/?)  The inequality we need 
now follows from the homogeneity of the norm:
$$\left\Vert {x\over{\Vert x\Vert}_1}\right\Vert\ge A
	\implies \Vert x\Vert\ge A\,\Vert x\Vert_1.\eqno\qed$$

\proclaim Corollary.
Given $a<b$ {\rm(}fixed\/{\rm)} and a positive integer $n$, 
there exist $0<A_n,B_n<\infty$ {\rm(}constants which may depend 
on $n$\/{\rm)} such that
$$A_n\sum_{k=0}^n|a_k|
	\le\Max_{a\le x\le b}\left|\sum_{k=0}^na_kx^k\right|
	\le B_n\sum_{k=0}^n|a_k|.$$

\noindent{\bf Exercise}

\noindent
Find explicit ``formulas'' for $A_n$ and $B_n$, above.
(This can be done without any fancy theorems.)
If it helps, you may consider the case $[\,a,b\,]=[\,0,1\,]$.

\proclaim Corollary.
Let $Y$ be a finite-dimensional normed space and let $M>0$.
Then, any closed ball\/ $\{y\in Y:\Vert y\Vert\le M\}$
is compact.  

\proof
Again suppose that $Y$ is $n$-dimensional and that 
$e_1,\ldots,e_n$ is a basis for $Y$.  From our previous
lemma we know that there is some constant $A>0$ such that 
$$A\,\sum_{i=1}^n|a_i|\le\left\Vert\sum_{i=1}^na_ie_i\right\Vert$$
for all $x=\sum_{i=1}^na_ie_i\in Y$.  In particular,
$$\left\Vert\sum_{i=1}^na_ie_i\right\Vert\le M
	\implies |a_i|\le {M\over A} \hbox{ for } i=1,\ldots,n.$$
Thus, $\{y\in Y:\Vert y\Vert\le M\}$ is a {\sl closed\/} subset 
(why?)\ of the {\sl compact\/} set
$$\left\{x=\sum_{i=1}^na_ie_i:|a_i|\le {M\over A},\ i=1,\ldots,n\right\}.
	\eqno\qed$$

\proclaim Corollary.
Every finite-dimensional normed space is complete.  In particular,
if $Y$ is a finite-dimensional subspace of a normed linear space
$X$, then $Y$ is a closed subset of $X$.

\proclaim Theorem.
Let $Y$ be a finite-dimensional subspace of a normed linear
space $X$, and let $x\in X$.  Then, there exists a 
{\rm(}not necessarily unique\/{\rm)} $y^*\in Y$
such that 
$$\Vert x-y^*\Vert=\Min_{y\in Y}\Vert x-y\Vert$$
for all $y\in Y$.  That is, there is a best approximation
to $x$ by elements of $Y$.

\proof
First notice that since $0\in Y$, we know that a nearest point 
$y^*$ will satisfy $\Vert x-y^*\Vert\le\Vert x\Vert=\Vert x-0\Vert$.
Thus, it suffices to look for $y^*$ among the vectors $y\in Y$
satisfying $\Vert x-y\Vert\le\Vert x\Vert$.  It will be 
convenient to use a slightly larger set of vectors, though.
By the triangle inequality,
$$\Vert x-y\Vert\le\Vert x\Vert\implies
	\Vert y\Vert\le\Vert x-y\Vert+\Vert x\Vert\le2\Vert x\Vert.$$
Thus, we may restrict our attention to those $y$'s in the
{\sl compact\/} set 
$$K=\{y\in Y:\Vert y\Vert\le2\Vert x\Vert\}.$$
To finish the proof, we need only notice that the function
$f(y)=\Vert x-y\Vert$ is {\sl continuous\/}:
$$|f(y)-f(z)|=\bigl|\,\Vert x-y\Vert-\Vert x-z\Vert\,\bigr|
	\le \Vert y-z\Vert,$$
hence attains a minimum value at some point $y^*\in K$.~\qed

\proclaim Corollary.
For each $f\in C[\,a,b\,]$, and each positive integer $n$,
there is a polynomial $p_n^*\in{\cal P}_n$ such that
$$\Vert f-p_n^*\Vert=\Min_{p\in{\cal P}_n}\Vert f-p\Vert.$$ 

\proclaim Corollary.
Given $a<b$ and a positive integer $n$ {\rm(}fixed\/{\rm)}, 
there exists a constant $R<\infty$ such that if
$$\left\Vert f-\sum_{k=0}^na_kx^k\right\Vert\le 2\Vert f\Vert,$$
then $\Max_{0\le k\le n}|a_k|\le R$.

\noindent{\bf Examples}

\noindent
Nothing in our Corollary says that $p_n^*$ will be a polynomial
of degree {\sl exactly\/} $n$---rather, a polynomial of degree
{\sl at most\/} $n$.  For example, the best approximation to
$f(x)=x$ by a polynomial of degree at most $3$ is, of course,
$p(x)=x$.  Even examples of non-polynomial functions are easy
to come by; for instance, the best linear approximation to
$f(x)=|x|$ on $[-1,1\,]$ is actually the constant function
$p(x)=1/2$, and this makes for an entertaining {\bf exercise}.

Before we leave these ``soft'' arguments behind, let's discuss
the problem of {\sl uniqueness\/} of best approximations.  First,
let's see why we want best approximations to be unique:

\proclaim Lemma.
Let $Y$ be a finite-dimensional subspace of a normed linear 
space $X$, and suppose that each $x\in X$ has a unique nearest 
point $y_x\in Y$.  Then, the nearest point map $x\mapsto y_x$
is continuous.

\proof
Let's write $P(x)=y_x$ for the nearest point map, and let's
suppose that $x_n\to x$ in $X$.  We want to show that 
$P(x_n)\to P(x)$, and for this it's enough to show that
there is a subsequence of $(P(x_n))$ which converges to $P(x)$.
(Why?)

Since the sequence $(x_n)$ is bounded in $X$, say $\Vert x_n\Vert\le M$
for all $n$, we have
$$\Vert P(x_n)\Vert\le\Vert P(x_n)-x_n\Vert+\Vert x_n\Vert
	\le 2\Vert x_n\Vert\le 2M.$$
Thus, $(P(x_n))$ is a bounded sequence in $Y$, a finite-dimensional
space.  As such, by passing to a subsequence, we may suppose that 
$(P(x_n))$ converges to some element $P_0\in Y$.  (How?)  Now we 
need to show that $P_0=P(x)$.  But
$$\Vert P(x_n)-x_n\Vert\le\Vert P(x)-x_n\Vert,$$
for any $n$, and hence, letting $n\to\infty$, 
$$\Vert P_0-x\Vert\le\Vert P(x)-x\Vert.$$
Since nearest points in $Y$ are unique, we must have $P_0=P(x)$.~\qed

It should be pointed out that the nearest point map is, in general,
{\sl nonlinear\/} and, as such, can be very difficult to work with.  
Later we'll see at least one case in which nearest point maps always
turn out to be linear.

We next observe that the set of best approximations
is always pretty reasonable:

\proclaim Theorem.
Let $Y$ be a subspace of a normed linear space $X$, and let $x\in X$.
The set $Y_x$, consisting of all best approximations to $x$ out of $Y$,
is a bounded, convex set.

\proof
Recall that a subset $K$ of a vector space $V$ is said to be 
{\sl convex\/} if $K$ contains the line segment joining any
pair of its points.  Specifically, $K$ is convex if
$$x,y\in K, \ 0\le\lambda\le1\implies \lambda x+(1-\lambda)y\in K.$$
Now, $y_1$, $y_2\in Y_x$ means that
$$\Vert x-y_1\Vert=\Vert x-y_2\Vert=\Min_{y\in Y}\Vert x-y\Vert.$$
Next, given $0\le\lambda\le1$, set $y^*=\lambda y_1+(1-\lambda)y_2$.
We want to show that $y^*\in Y_x$, but notice that we at least
have $y^*\in Y$.  Finally, we estimate:
$$\eqalign{%
\Vert x-y^*\Vert&=\Vert x-(\lambda y_1+(1-\lambda)y_2)\Vert\cr
	&=\Vert\lambda(x-y_1)+(1-\lambda)(x-y_2)\Vert\cr
	&\le\lambda\Vert x-y_1\Vert+(1-\lambda)\Vert x-y_2\Vert\cr
	&=\Min_{y\in Y}\Vert x-y\Vert.\cr
}$$
Hence, $\Vert x-y^*\Vert=\Min_{y\in Y}\Vert x-y\Vert$; that is,
$y^*\in Y_x$.~\qed

\noindent{\bf Exercise}

\noindent
If, in addition, $Y$ is finite-dimensional, show that $Y_x$ is 
{\sl closed\/} (hence {\sl compact\/}).

If $Y_x$ contains more than one point, then, in fact, it contains
an entire line segment.  Thus, $Y_x$ is either empty, contains 
exactly one point, or contains infinitely many points.  This 
observation gives us a {\sl sufficient condition\/} for uniqueness
of nearest points: If our normed space $X$ contains no line
segments on any sphere $\{x\in X:\Vert x\Vert=d\}$, then any
best approximation (out of any set) will be unique.  

A norm $\Vert\cdot\Vert$ on a vector space $X$ is said to be
{\sl strictly convex\/} if, for any $x\ne y\in X$ with 
$\Vert x\Vert=d=\Vert y\Vert$, we always have 
$\Vert\lambda x+(1-\lambda)y\Vert<d$ for any $0<\lambda<1$.
That is, the open line segment between any pair of points on the 
surface of the ball of radius $r$ in $X$ lies entirely inside the 
ball.  We often simply say that the space $X$ is strictly convex,
with the understanding that a property of the norm in $X$
is implied.  Here's an immediate corollary to our last result:

\proclaim Corollary.
If $X$ has a strictly convex norm, then, for any subspace $Y$ of
$X$ and any $x\in X$, there can be at most one best approximation
to $x$ out of $Y$.  That is, $Y_x$ is either empty or consists
of a single point.

In order to arrive at a condition that's somewhat easier to
check, let's translate our original definition into a statement
about the triangle inequality in $X$.

\proclaim Lemma.
$X$ has a strictly convex norm if and only if the triangle
inequality is strict on non-parallel vectors; that is, if
and only if
$$x\ne\alpha y,\ y\ne\alpha x,\ \hbox{all}\ \alpha\in\R\implies
	\Vert x+y\Vert<\Vert x\Vert+\Vert y\Vert.$$

\proof
First suppose that $X$ is strictly convex, and let
$x$ and $y$ be non-parallel vectors in $X$.  Then, 
in particular, the vectors $x/\Vert x\Vert$ and
$y/\Vert y\Vert$ must be different.  (Why?)  Hence,
$$\left\Vert\,\left({{\Vert x\Vert}\over{\Vert x\Vert+\Vert y\Vert}}\right)
	{x\over{\Vert x\Vert}} \ + \ 
	\left({{\Vert y\Vert}\over{\Vert x\Vert+\Vert y\Vert}}\right)
	{y\over{\Vert y\Vert}}\,\right\Vert<1.$$
That is, $\Vert x+y\Vert<\Vert x\Vert+\Vert y\Vert$.

Next suppose that the triangle inequality is strict on
non-parallel vectors, and let $x\ne y\in X$ with
$\Vert x\Vert=d=\Vert y\Vert$.  If $x$ and $y$ are
parallel, then we must have $y=-x$.  (Why?)  In this case,
$$\Vert\lambda x+(1-\lambda)\,y\Vert=|2\lambda-1|\,\Vert x\Vert
	<d,$$
since $|2\lambda-1|<1$ whenever $0<\lambda<1$.  Otherwise,
$x$ and $y$ are non-parallel.  In this case, for any $0<\lambda<1$,
the vectors $\lambda x$ and $(1-\lambda)\,y$ are likewise
non-parallel.  Thus, 
$$\Vert\lambda x+(1-\lambda)\,y\Vert
	<\lambda\Vert x\Vert+(1-\lambda)\Vert y\Vert=d.\eqno\qed$$

\noindent{\bf Examples}

\item{1.}
The usual norm on $C[\,a,b\,]$ is {\sl not\/} strictly convex
(and so the problem of uniqueness of best approximations is
all the more interesting to tackle).  For example, if $f(x)=x$
and $g(x)=x^2$ in $C[\,0,1\,]$, then $\Vert f\Vert=1=\Vert g\Vert$,
$f\ne g$, while $\Vert f+g\Vert=2$.  (Why?)

\item{2.}
The usual norm on $\R^n$ is strictly convex, as is any one of
the norms $\Vert\cdot\Vert_p$, $1<p<\infty$.  (We'll prove
these facts shortly.)  The norms $\Vert\cdot\Vert_1$ and
$\Vert\cdot\Vert_\infty$, on the other hand, are {\sl not\/}
strictly convex.  (Why?)

\noindent{\bf Appendix}

\noindent
For completeness, we supply a few of the missing details concerning
the $\ell_p$-norms.  We begin with a handful of classical inequalities
of independent interest.  First recall that we have defined a scale
of ``norms'' on $\R^n$ by setting:
$$\eqalignno{%
\Vert x\Vert_p&=\left(\sum_{i=1}^n|x_i|^p\right)^{1/p},
	\qquad 1\le p<\infty,\cr
\noalign{\hbox{and}}
\Vert x\Vert_\infty&=\Max_{1\le i\le n}|x_i|,\cr
}$$
where $x=(x_i)_{i=1}^n\in\R^n$.  Please note
that the case $p=2$ gives the usual Euclidean norm
on $\R^n$ and that the cases $p=1$ and $p=\infty$ clearly
give rise to legitimate norms on $\R^n$.  

Common parlance is to
refer to these expressions as $\ell_p$-norms and to refer to
the space $(\R^n,\Vert\cdot\Vert_p)$ as $\ell_p^n$.  
The space of all infinite sequences $x=(x_n)_{n=1}^\infty$ 
for which the analogous infinite sum (or supremum) $\Vert x\Vert_p$ 
is finite is referred to as $\ell_p$.  What's more, there is
a ``continuous'' analogue of this scale: We might also consider
the norms
$$\eqalignno{%
\Vert f\Vert_p&=\left(\int_a^b|f(x)|^p\,dx\right)^{1/p},
	\qquad 1\le p<\infty,\cr
\noalign{\hbox{and}}
\Vert f\Vert_\infty&=\Sup_{a\le x\le b}|f(x)|,\cr
}$$
where $f$ is in $C[\,a,b\,]$ (or is simply Lebesgue integrable).  
The subsequent discussion actually covers all of these cases, 
but we will settle for writing our proofs in the $\R^n$ setting only. 

\proclaim Lemma. \ {\rm(Young's inequality):} \ 
Let $1<p<\infty$, and let $1<q<\infty$ be defined by
${1\over p}+{1\over q}=1$; that is, $q={p\over{p-1}}$.
Then, for any $a$, $b\ge0$, we have 
$$ab\le{1\over p}\,a^p+{1\over q}\,b^q.$$
Moreover, equality can only occur if $a^p=b^q$.
{\rm(Please note that the case $p=q=2$ yields
the familiar arithmetic-geometric mean inequality.)}

\proof
A quick calculation before we begin:
$$q-1={p\over{p-1}}-1={{p-(p-1)}\over{p-1}}={1\over{p-1}}.$$
Now we just estimate areas; for this you might find it helpful
to draw the graph of $y=x^{p-1}$ (or, equivalently, the graph of
$x=y^{q-1}$\/).  Comparing areas we get:
$$ab \le \int_0^ax^{p-1}\,dx+\int_0^by^{q-1}\,dy
	={1\over p}\,a^p+{1\over q}\,b^q.$$
The case for equality also follows easily from the graph of
$y=x^{p-1}$ (or $x=y^{q-1}$\/), since $b=a^{p-1}=a^{p/q}$
means that $a^p=b^q$.~\qed

\proclaim Corollary. \ {\rm(H\"older's inequality):} \ 
Let $1<p<\infty$, and let $1<q<\infty$ be defined by
${1\over p}+{1\over q}=1$.  Then, for any $a_1,\ldots,a_n$
and $b_1,\ldots,b_n$ in $\R$ we have:
$$\sum_{i=1}^n|a_ib_i|\le\left(\sum_{i=1}^n|a_i|^p\right)^{1/p}
	\left(\sum_{i=1}^n|b_i|^q\right)^{1/q}.$$
{\rm(Please note that the case $p=q=2$ yields the familiar
Cauchy-Schwarz inequality.)}

\proof
Let $A=\left(\sum_{i=1}^n|a_i|^p\right)^{1/p}$ and let
$B=\left(\sum_{i=1}^n|b_i|^q\right)^{1/q}$.  We may clearly
assume that $A$, $B\ne0$ (why?),\ and hence we may divide
(and appeal to Young's inequality):
$${{|a_ib_i|}\over{AB}}\le{{|a_i|^p}\over{pA^p}}+{{|b_i|^q}\over{qB^q}}.$$
Adding, we get:
$${1\over{AB}}\sum_{i=1}^n|a_ib_i|\le
	{1\over{pA^p}}\sum_{i=1}^n|a_i|^p+{1\over{qB^q}}\sum_{i=1}^n|b_i|^q
	={1\over p}+{1\over q}=1.$$
That is, $\sum_{i=1}^n|a_ib_i|\le AB$.~\qed

The case for equality in H\"older's inequality follows from what
we know about Young's inequality:  Equality in H\"older's
inequality means that either $A=0$, or $B=0$, or else 
$|a_i|^p/pA^p=|b_i|^q/qB^q$ for all $i=1,\ldots,n$.  In short,
there must exist nonnegative scalars $\alpha$ and $\beta$ such that 
$\alpha\,|a_i|^p=\beta\,|b_i|^q$ for all $i=1,\ldots,n$.  

Notice, too, that the case $p=1$ ($q=\infty$\/) works, and is easy:
$$\sum_{i=1}^n|a_ib_i|\le\left(\sum_{i=1}^n|a_i|\right)
	\left(\Max_{1\le i\le n}|b_i|\right).$$

\noindent{\bf Exercise}

\noindent
When does equality occur in this case?

Finally, an application of H\"older's inequality leads to an
easy proof that $\Vert\cdot\Vert_p$ is actually a norm.  It will
help matters here if we first make a simple observation: If
$1<p<\infty$ and if $q={p\over{p-1}}$, notice that 
$$\bigl\Vert\,(\,|a_i|^{p-1})_{i=1}^n\bigr\Vert_q
	=\left(\sum_{i=1}^n|a_i|^p\right)^{(p-1)/p}
	=\Vert a\Vert_p^{p-1}.$$

\proclaim Lemma. \ {\rm(Minkowski's inequality):} \ 
Let $1<p<\infty$ and let $a=(a_i)_{i=1}^n$, $b=(b_i)_{i=1}^n\in\R^n$.
Then, $\Vert a+b\Vert_p\le\Vert a\Vert_p+\Vert b\Vert_p$.

\proof
In order to
prove the triangle inequality, we once again let $q$ be defined by 
${1\over p} + {1\over q} = 1$, and now we use H\"older's inequality
to estimate:
$$\eqalign{
\sum_{i=1}^n |a_i + b_i|^p  \ 
	&= \ \sum_{i=1}^n |a_i + b_i|\cdot|a_i + b_i|^{p-1}\cr
	&\le \ \sum_{i=1}^n |a_i|\cdot|a_i + b_i|^{p-1} \
		+ \ \sum_{i=1}^n |b_i|\cdot|a_i + b_i|^{p-1}\cr
	&\le \ \Vert a\Vert_p\cdot\Vert\,(\,|a_i + b_i|^{p-1})_{i=1}^n\Vert_q  \
		+ \ \Vert y\Vert_p\cdot\Vert\,(\,|a_i + b_i|^{p-1})_{i=1}^n\Vert_q\cr
	&= \ \Vert a + b\Vert_p^{p-1} 
		\left(\,\Vert a\Vert_p + \Vert b\Vert_p\right).\cr
}$$
That is, $\Vert a + b\Vert_p^p \le \Vert a + b\Vert_p^{p-1} 
		\left(\,\Vert a\Vert_p + \Vert b\Vert_p\right)$,
and the triangle inequality follows.~\qed

If $1<p<\infty$, then equality in Minkowski's inequality can
only occur if $a$ and $b$ are parallel; that is, the $\ell_p$-norm
is {\sl strictly convex\/} for $1<p<\infty$.  Indeed, if
$\Vert a+b\Vert_p=\Vert a\Vert_p+\Vert b\Vert_p$, then 
either $a=0$, or $b=0$, or else $a$, $b\ne0$ and we have equality 
at each stage of our proof.  Now equality in the first inequality
means that $|a_i+b_i|=|a_i|+|b_i|$, which easily implies that 
$a_i$ and $b_i$ have the same sign.  Next, equality in our application 
of H\"older's inequality implies that there are nonnegative scalars
$C$ and $D$ such that $|a_i|^p=C\,|a_i+b_i|^p$ and 
$|b_i|^p=D\,|a_i+b_i|^p$ for all $i=1,\ldots,n$.  Thus,
$a_i=E\,b_i$ for some scalar $E$ and all $i=1,\ldots,n$.

Of course, the triangle inequality also holds in either of
the cases $p=1$ or $p=\infty$ (with much simpler proofs).

\noindent{\bf Exercises}

\noindent
When does equality occur in the triangle inequality in 
cases $p=1$ or $p=\infty$\/?  In particular, show that 
neither of the norms $\Vert\cdot\Vert_1$ or $\Vert\cdot\Vert_\infty$
is strictly convex.



\bye


%%  end of chapter-01.tex