Tema 4. APROXIMACIÓ DE FUNCIONS PER MÍNIMS QUADRATS
  1. Equacions normals:
Definició 16: Direm que dos vectors u, v són ortogonals respecte del producte escalar <,> si i solament si  <u,v>=0 .

Definició 17: Direm que v* és la projecció ortogonal d'un vector y sobre un subespai linial V1 si i solament si v*cV1 i, per a tot vcV1, <v,y-v*>=0 .

Definició 18: Definim la norma 2 o euclídea corresponent a un producte escalar <,> com ||u||2=<u,u>½ .

Teorema -6: Si u, v són ortogonals, <u,v>=0, aleshores ||u+v||22=||u||22+||v||22 (teorema de Pitàgoras).

Teorema 55: Si v* és la projecció ortogonal d'un vector y sobre un subespai lineal V1, aleshores,  per a tot vcV1, si v≠v*, aleshores ||y-v||2>||y-v*||2 .

Teorema 56: La projecció ortogonal f* d'una funció f sobre un subespai lineal de funcions F1 ={ Σj=0...n ajφj / (aj)j=1...ncRn }és la millor aproximació a f en F1 utilitzant com a mesura de distància la norma 2 o euclídea (mínims quadrats).

Teorema 57: Si f*=Σj=0...n a*jφj és la millor aproximació en F1 per mínims quadrats a una funció f, aleshores s'acompleix que, per a tot i=0...n, Σj=0...n <φi,φj>a*j = <φi,f> (equacions normals). Aquest sistema d'equacions Aa*=b té solució única si i solament si  les funcions bàsiques φi són linealment independents.

Teorema 58: Si f*=Σj=0...n a*jφj és la millor aproximació en F1 per mínims quadrats a una funció f & les funcions bàsiques φi són ortogonals, és a dir <φi,φj>=0 si i≠j, aleshores a*j = <φj,f>/<φj,φj> per a tot j=0...n .

Definició 18: Definim el producte escalar continu de les funcions integrables f, g en l'interval [a,b] com <f,g>=∫ab f(x)g(x)dx .

Definició 19: Definim el producte escalar discret de les funcions f, g en els nodos (xk)k=0...m , amb m≥n, com <f,g>=Σk=0...mf(xk)g(xk) (prenem com a equivalents les funcions que coincideixen en els nodos).

Teorema 59: El sistema d'equacions normals Aa*=b per a determinar la millor aproximació en F1 per mínims quadrats a una funció f en els nodos (xk)k=0...m , amb m≥n, vindrà donat per A=MTM & b=MTy, amb Mkj=φj(xk) & yk=f(xk) per a tot k=0...m , j=0...n .

Teorema 60: Si Ma*=y, aleshores a* acompleix el sistema d'equacions normals i a més ||f-f*||2=0.

Definició 20: Direm que una matriu Q és ortogonal si i solament si QTQ=D, on D és una matriu diagonal tal que Dij=Diiδij per a tot i, j .

Teorema 61: Si M=QR, on Q és ortogonal i R és una matriu triangular superior tal que Rij=0 per a tot i>j, aleshores si Ra*=D-1QTy, on D=QTQ, aleshores a* acompleix el sistema d'equacions normals.
  1. Ortogonalització de Householder:
Teorema 62: Si M=QR, on Q és ortonormal i simètrica i R és una matriu triangular superior tal que Rij=0 per a tot i>j, aleshores si Ra*=ŷ, tal que ŷk=(Qy)k per a tot k=0...n, aleshores a* dóna el mínim valor de ||Ma*-y||2 .

Teorema 63: Si M té rang n+1 & Q=PnPn-1···P1 on P1, P2,...Pn són matrius de Householder tals que (QM)kj=0 per a tot k=n+1...m, j=0...n & Rkj=(QM)kj per a k,j=0...n és una matriu triangular superior, aleshores si Ra*=ŷ, tal que ŷk=(Qy)k per a tot k=0...n , aleshores f*=Σj=0...n a*jφj és la millor aproximació a la funció f en F1 per mínims quadrats.

Algoritme 10: Per a obtenir la millor aproximació f*=Σj=0...n a*jφj en F1 per mínims quadrats a una funció f  per ortogonalització de Householder:
  1. Prendre i=0 .
  2. Prendre x=M(i:m,i), 
  3. Calcular v=x+signe(xi)||x||2ei .
  4. Calcular M(i)=PiM=(I-2vvT/(vTv))M , y(i)=Piy .
  5. Prendre M=M(i), y=y(i) .
  6. Si i<n, prendre i=i+1 & tornar al pas 2 .
  7. Prendre R=M(0:n,0:n), ŷ=y(0:n) .
  8. Resoldre el sistema triangular superior Ra*=ŷ .
  1. Ortogonalitzacions de Gram-Schmidt:
Teorema 64: Per a tot parell de funcions f, g,  g-(<f,g>/<f,f>)f és ortogonal a f .

Teorema 65: Per a tot conjunt de funcions ortogonals {ψi}i=0...n tal que, per a tot j=0...n, φj=Σi=0...n Rijψi , la millor aproximació en F1 per mínims quadrats a una funció f en els nodos (xk)k=0...m , amb m≥n, serà f*=Σj=0...n a*jφj =Σj=0...n c*iψi , amb c*i=<ψi,f>/<ψi,ψi> & Σj=0...nRija*j=c*i per a tot i=0...n (equivalent a Ra*=D-1QTy si Qkj=ψj(xk) per a tot k=0...m , j=0...n & D=QTQ) .

Algoritme 11: Per a obtenir la millor aproximació f*=Σj=0...n a*jφj en F1 per mínims quadrats a una funció f  per ortogonalització de Gram-Schmidt clàssica:
  1. Prendre i=0
  2. Per a tot j=0...i-1, calcular Rji=<φi,ψj>/dj .
  3. Prendre ψi(x)=φi(x)-Σj=0...i-1 Rjiψj(x) , di=<ψi,ψi>, Rii=1 .
  4. Si i<n, prendre i=i+1 & tornar al pas 2 .
  5. Prendre Rji=0 per a tot j>i .
  6. Calcular c*i=<ψi,f>/<ψi,ψi>= per a tot i=0...n .
  7. Resoldre el sistema triangular superior Ra*=c* .
Algoritme 12: Per a obtenir la millor aproximació f*=Σj=0...n a*jφj en F1 a una funció f per mínims quadrats amb el producte escalar discret en els nodos (xk)k=0...m per ortogonalització de Gram-Schmidt modificada:
  1. Prendre i=0 .
  2. Per a tot j=i...n, prendre Mj=M(0:m,j)
  3. Prendre qi=Q(0:m,i)=Mi , di=Dii=qiTqi .
  4. Per a tot j=i...n, calcular Rij=(qiTMj)/di .
  5. Per a tot j=i+1...n, prendre M(0:m,j)=Mj-Rijqi
  6. Si i<n, prendre i=i+1 & tornar al pas 2 .
  7. Prendre Rij=0 per a tot i>j .
  8. Resoldre el sistema triangular superior Ra*=D-1QTy .
  1. Aproximació polinomial:
Teorema 66: Tant amb el producte escalar continu com amb el producte escalar discret de dues funcions f, g s'acompleix que <xf,g>=<f,xg> .

Teorema 67: Si F1 és el conjunt del polinomis de grau menor o igual que n, apliquem l'ortogonalització de Gram-Scmidt clàssica amb producte escalar continu o discret amb polinomis φi de grau i prenent ψ0=φ0=A0≠0 & per a j=0...n-1 prenent successivament φj+1=αjxψj amb αj≠0, aleshores s'acomplirà:
  1. Si p és un polinomi de grau i<j≤n, <p,ψj>=0 .
  2. Per a tot j=0...n-1, i=0...j, Ri,j+1=αj<ψj,xψi>/di .
  3. Per a tot j=0...n-1, ψj+1 és un polinomi de grau j+1, amb un coeficient Aj+1=αjAj≠0 de xj+1.
  4. Per a tot j=1...n-1, i=0...j-2, Ri,j+1=0 .
  5. ψ1=α0xψ0-R0,1ψ0 & ψj+1=αjxψj-Rj,j+1ψj-Rj-1,j+1ψj-1 per a tot j=1...n-1 .
  6. Per a tot j=1...n, dj=<ψj,ψj>=αj-1<ψj,xψj-1> .
Algoritme 13: Per a obtenir la millor aproximació polinomial pn*=Σj=0...n c*jψj :
  1. Prendre j=0
  2. Escollir Aj≠0 .
  3. Si j=0, prendre ψj=Aj .
  4. Si j>0, prendre αj-1=Aj/Aj-1, βj-1=<ψj-1,xψj-1>/<ψj-1,ψj-1>
  5. Si j=1, prendre ψj=αj-1(x-βj-1)ψj-1 .
  6. Si j>1, prendre γj-1=αj-1<ψj-1,ψj-1>/(αj-2<ψj-2,ψj-2>) .
  7. Si j>1, prendre ψj=αj-1(x-βj-1)ψj-1-γj-1ψj-2 .
  8. Calcular c*j=<ψj,f>/<ψj,ψj> .
  9. Si j<n, prendre j=j+1 & tornar al pas 2 .
  10. Aplicar l'Algoritme 14:
Algoritme 14: Regla de Clenshaw:
  1. Prendre j=n+2
  2. Si j>n, prendre qj=0 .
  3. Si j≤n, prendre qj=αj(x-βj)qj+1-γj+1qj+2+c*j .
  4. Si j>0, prendre j=j-1 & tornar al pas 2.
  5. Prendre pn*(x)=A0q0 .
  1. Aproximacions trigonomètriques:
Definició 21: Definim l'espai Tn de sumes trigonomètriques de grau menor o igual que n com {tn(θ)=a0/2+Σj=1...najcos(jθ)+Σj=1...nbjsin(jθ) / ajcR per a tot j=0...n & bjcR per a tot j=1...n} .

Teorema 68: tota funció tncTn és periòdica de periode 2π .

Teorema 69: Les funcions 1, cos(θ), sin(θ), cos(2θ), sin(2θ),..., cos(jθ), sin(jθ),... són ortogonals respecte del producte escalar continu en l'interval [0,2π] .

Teorema 70: Les funcions 1, cos(θ), sin(θ), cos(2θ), sin(2θ),..., cos(nθ), sin(nθ) són ortogonals respecte del producte escalar discret en els nodos θk=Φ+2πk/(m+1) per a k=0...m, amb m≥2n .

Teorema 71: La millor aproximació tn*(θ)=a0*/2+Σj=1...naj*cos(jθ)+Σj=1...nbj*sin(jθ) en Tn a una funció f  amb el producte escalar continu en l'interval [0,2π] ve donada per
Teorema 72: La millor aproximació tn*(θ)=a0*/2+Σj=1...naj*cos(jθ)+Σj=1...nbj*sin(jθ) en Tn a una funció f  amb el producte escalar discret en els nodos θk=Φ+2πk/(m+1) per a k=0...m, amb m≥2n, ve donada per