09. Best Approximation in Inner-Product Spaces

Norms

Let $V$ be a vector space over field $F$ then

Mapping $||\cdot ||:V\to \mathbb{F}$ is a norm on $V$ if
1)

$$||f||\ge 0\text{ for all }f\in V\text{ with }||f||=0⟺f=0\in V$$

$$||\lambda f||=|l|||f||\text{ for all }\lambda \in \mathbb{F}\text{ and }f\in V$$

3. Triangle Inequality

$$||f+g||\le ||f||+||g||\text{ for all }f,g\in V$$

Link to original

Types of Norms

Vectors in ${\mathbb{R}}^n$

For $x\in {\mathbb{R}}^n$ where $x=(x_1,x_2,\cdots ,x_n{)}^T$ then

$$||x||\equiv ||x|{|}_2=(x_1^2+x_2^2+\cdots +x_n^2{)}^{\frac{1}{2}}=\sqrt{x^{T}x}$$

is the ${\ell }^2$- or vector two-norm

Continuous Function

For continuous functions on $[a,b]$

$$||f||\equiv ||f|{|}_{\infty }=\underset{x\in [a,b]}{\max }|f(x)|$$

Integrable Functions

For functions in $V$ where

$$V=L_w^2(a,b)\equiv \left\{f:[a,b]\to \mathbb{R}:{\int }_a^{b}w(x)[f(x){]}^{2}dx<\infty \right\}$$

for some weight function $w(x)>0$ then

$$||f||=||f|{|}_2={\left({\int }_a^{b}w(x)[f(x){]}^{2}dx\right)}^{\frac{1}{2}}$$

is the $L^2$- or two-norm

If $||f||=0$ then $f=0$ almost everywhere on $[a,b]$

Note that space $L^2(a,b)$ is a common abbreviation for $L_w^2(a,b)$ when $w(x)\equiv 1$

Link to original

Least Squares Polynomial Approximation

Consider $f\in L_w^2(a,b)$ need to find $p_n\in {\Pi }_n$ such that

$$||f-p_n|{|}_2\le ||f-q||\text{ for all }q\in {\Pi }_n$$

As $p_n$ is in form

$$p_n(x)=\sum _{k=0}^n{\alpha }_k{x}^k$$

Then results in minimisation problem

$$\underset{({\alpha }_0,\cdots ,{\alpha }_n)}{\min }{\int }_a^{b}w(x)\left[f(x)-\sum _{k=0}^n{\alpha }_k{x}^k\right]dx$$

with unique minimiser from linear system

$$\frac{\partial }{\partial {\alpha }_j}{\int }_a^{b}w(x){\left[f(x)-\sum _{k=0}^n{\alpha }_k{x}^k\right]}^{2}dx=0\text{ for all }j=0,1,\cdots ,n$$

Link to original

Real Inner Product Space

Real Inner Product Space is a vector space $V$ over $\mathbb{R}$ with inner product mapping

$$⟨\cdot ,\cdot ⟩:V\times V\to \mathbb{R}$$

such that

$$|v,v|\ge 0\text{ for all }v\in V\text{ and }⟨v,v⟩=0⟺v=0$$

$$⟨u,v⟩=⟨v,u⟩\text{ for all }u,v\in V$$

$$⟨\alpha u+\beta v,z⟩=\alpha ⟨u,z⟩+\beta ⟨v,z⟩\text{ for all }u,v,z\in V\text{ and all }\alpha ,\beta \in \mathbb{R}$$

Link to original

Properties of Inner Product Spaces

Let $V$ be an inner product space with inner product $⟨\cdot ,\cdot ⟩$

Norm on $V$

$$⟨v,v{⟩}^{\frac{1}{2}}$$

defines a norm on $V$

Orthogonality

For $u,v\in V$ then

$$⟨u,v⟩=0⟺u\text{ and }v\text{ are orthogonal}$$

Pythagoras Theorem:

For $u,v\in V$ such that $⟨u,v⟩=0$ then

$$||u\pm v|{|}^2=||u|{|}^2+||v|{|}^2$$

Proof

$$\begin{array}{rl}||u\pm v|{|}^2& =⟨u\pm v,u\pm v⟩=⟨u,u\pm v⟩\pm ⟨v,u\pm v⟩\\ & =⟨u,u\pm v⟩\pm ⟨u\pm v,u⟩\\ & =⟨u,u⟩\pm ⟨u,v⟩\pm ⟨u,v⟩+⟨v,v⟩\\ & =||u|{|}^2+||v|{|}^2\end{array}$$

Cauchy-Schwarz Inequality

For any $u,v\in V$

$$|⟨u,v⟩|\le ||u||||v||$$

Proof

For $\lambda \in \mathbb{R}$ then

$$0\le ⟨u-\lambda v,u-\lambda v⟩=||u|{|}^2-2\lambda ⟨u,v⟩+{\lambda }^2||v|{|}^2=\varphi (\lambda )$$

which is a quadratic in $\lambda$

$\varphi (\lambda )$ has a minimiser at ${\lambda }_{\ast }=\frac{⟨u,v⟩}{||v|{|}^2}$
So as $\varphi ({\lambda }_{\ast })\ge 0$ then

$$||u|{|}^2-\frac{⟨u,v{⟩}^2}{||v|{|}^2}\ge 0$$

Hence we get inequality

Triangle Inequality

For $u,v\in V$ then

$$||u+v||\le ||u||+||v||$$

Proof

$$||u+v|{|}^2=⟨u+v,u+v⟩=||u|{|}^2+2⟨u,v⟩+||v|{|}^2$$

By Cauchy-Schwarz Inequality then

$$||u+v|{|}^2\le ||u|{|}^2+2||u||||v||+||v|{|}^2=(||u||+||v||{)}^2$$

Hence

$$||u+v||\le ||u||+||v||$$

Link to original

Best Approximation by Orthogonal Projection

Let

$$⟨f,g⟩={\int }_a^{b}w(x)f(x)g(x)dx\text{ and }||f|{|}_2^2=⟨f,f⟩$$

where $w(x)>0$ for all $(a,b)$

If $f\in L_w^2(a,b)$ and $p_n\in {\Pi }_n$ such that

$$⟨f-p_n,r⟩=0\forall r\in {\Pi }_n$$

Then

$$||f-p_n|{|}_2\le ||f-r|{|}_2\forall r\in {\Pi }_n$$

so $p_n$ is a best (weighted) lest-squares approximation to $f$ on $[a,b]$

Proof

$$\begin{array}{rl}||f-p_n|{|}_2^2& =⟨f-p_n,f-p_n⟩\\ & =⟨f-p_n,f-r⟩+⟨f-p_n,r-p_n⟩\forall r\in {\Pi }_n\\ & =⟨f-p_n,f-r⟩\text{ as }⟨f-p_n,r-p_n⟩=0\text{ by assumption}\\ & \le ||f-p_n|{|}_2||f-r|{|}_2\\ & \\ ⟹||f-p_n|{|}_2& \le ||f-r|{|}_2\end{array}$$

Link to original

Normal Equation Best Approximation

Consider best approximation to find $p_n(x)=\sum _{k=0}^n{\alpha }_k{x}^k$ such that

$${\int }_a^{b}w(x)\left(f-\sum _{k=0}^n{\alpha }_k{x}^k\right)x^{i}dx=0\text{ for }i=0,1,\cdots ,n$$

Then this can be represented by matrix equation with $A=(a_{ij})$ and $\psi =(f_0,f_1,\cdots ,f_n{)}^T$

$$A\delta =\psi$$

where

$$a_{i,k}={\int }_a^{b}w(x)x^{k+1}dx\text{ and }{f}_i={\int }_a^{b}w(x)f(x)x^{i}dx$$

for $1\le i,k\le n$

Proof

Suppose

$${\int }_a^{b}w(x)\left(f-\sum _{k=0}^n{\alpha }_k{x}^k\right)x^{i}dx=0\text{ for }i=0,1,\cdots ,n$$

Then

$${\int }_a^{b}w(x)\left(f-\sum _{k=0}^n{\alpha }_k{x}^k\right)\left(\sum _{i=0}^n{\beta }_i{x}^i\right)dx=0\forall q=\sum _{i=0}^n{\beta }_i{x}^i\in {\Pi }_n$$

Hence

$$\sum _{k=0}^n\left({\int }_a^{b}w(x)x^{k+1}dx\right){\alpha }_k={\int }_a^{b}w(x)f(x)x^{i}dx\text{ for }i=0,1,\cdots ,n$$

Which is the component-wise statement of

$$A\alpha =\psi$$

Link to original

Non-Singularity of Matrix of Normal Form

Coefficient Matrix $A$ from Normal Form $A\alpha =\psi$ is non singular

Proof

Suppose there $\exists \alpha \ne 0$ with $A\alpha =0$ hence

$${\alpha }^{T}A\alpha =0⟺\sum _{i=0}^n{\alpha }_i(A\alpha {)}_i=0⟺\sum _{i=0}^n{\alpha }_i\sum _{k=0}^n{a}_{ik}{\alpha }_k=0$$

As $a_{ik}={\int }_a^{b}w(x)x^k{x}^{i}dx$

$$⟺\sum _{i=0}^n{\alpha }_i\sum _{k=0}^n\left({\int }_a^{b}w(x)x^k{x}^{i}dx\right){\alpha }_k=0$$

Rearranging then

$${\int }_a^{b}w(x)\left(\sum _{i=0}^n{\alpha }_i{x}^i\right)\left(\sum _{k=0}^n{\alpha }_k{x}^k\right)dx=0$$

Thus

$${\int }_a^{b}w(x){\left(\sum _{i=0}^n{\alpha }_i{x}^i\right)}^{2}dx=0$$

Hence

$$\sum _{i=0}^n{\alpha }_i{x}^i=0$$

So

$${\alpha }_i=0\text{ for }i=0,1,\cdots ,n$$

This contradicts original assumption so $A$ is non-singular

Link to original