02 - Approximations

Best Polynomial Approximations

Let $f\in C([-1,1])$

For $L_{\infty }$ norm where $||\cdot |{|}_{\infty }$ is defined by $||f|{|}_{\infty }={\sup }_{x\in [-1,1]}|f|$ then

There exists $p_n^{\ast }$ such that

$$||f-p_n^{\ast }|{|}_{\infty }=\underset{p_n\in {\Pi }_n}{\min }||f-p_n|{|}_{\infty }$$

Least Squares Problem

Consider $Ax=b$
As $Ax=b$ doesn’t always have a solution then consider

Least Squares Problem

$$\underset{x}{\min }||Ax-b||\text{ for }A\in {\mathbb{R}}^{m\times n},b\in {\mathbb{R}}^m,m\ge n$$

where

$$||y||:=\sqrt{y_1^2+y_2^2+\cdots +y_m^2}=\sqrt{y^{T}y}$$

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$$

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$$