Studente Claudia Puzzo

Il motivo per cui si introducono i polinomi ortogonali è legato all'approssimazione ai minimi quadrati di funzioni continue.Problema continuo.Trovare il polinomio di grado n assegnato che approssima ai minimi quadrati la funzione f(x), continua sull'intervallo [a,b]. Detto quindi pn(x)=a0xn+a1xn-1+a2xn-2+…+an-1x+an

il polinomio e, chiamato a=(a0, a1, a2, …, an-1, an) il vettore costituito dai suoi coefficienti, la quantità che ci si propone di minimizzare è la funzione

J(a)= Si può dimostrare che, tra tutti i polinomi di grado n assegnato, quello che minimizza la distanza è il polinomio:

dove pi(x) sono i primi n+1 polinomi di una famiglia di polinomi ortogonali su [a,b] e i ci sono i coefficienti di Fourier.Allora il polinomio “più vicino” a ƒ sarà quello che (ammesso che esista, che sia unico), tra tutti i polinomi di grado n, minimizza la distanza tra f e p.

 

2( ) ( ) ( )b

n

a

f x p x w x dx

1 0

( ) ( )n

n i iQ x c p x

Def 1.

I polinomi p0(x), p1(x),…,pn(x)…, ciascuno di grado pari al proprio indice, costituisconouna famiglia di polinomi ortogonali rispetto alla funzione peso w(x) sull'intervallo [a,b] se vale la condizione:

i ≠ j mentre

Def 2.

I polinomi p0(x), p1(x),…,pn(x)…, ciascuno di grado pari al proprio indice, costituiscono una famiglia di polinomi ortonormali rispetto alla funzione peso w(x) sull'intervallo [a,b]se vale la condizione:

i ≠ j mentre

NB. La funzione peso w(x) è continua (e quindi integrabile) su (a,b) e ivi positiva.La denominazione ortogonale proviene dalla fisica; nel senso che, dati due vettori (nello spazio

a tre vettori), ad esempio, a(n) = a(n)1, a(n)

2,a(n)3 e a(m) = a(m)

1, a(m)2,a(m)

3 si dicono ortogonali se il loro prodotto interno

a(m) * a(n) = a(n)1 a(m)

1 + a(n)2 a(m)

2 + a(n)3 a(m)

3 =0, per cui, passando dal discreto al continuo, si trova una profonda analogia con Pn(x) .

Ortogonalizzazione di Gram-Schmidt

Mediante il metodo di Gram-Schmidt è possibile ottenere un sistema di polinomi ortogonali a partire da polinomi linearmente indipendenti.

Enunciato

Sia {x1, x2, …, x n} un insieme di vettori linearmente indipendenti.

E’ possibile costruire una famiglia ortonormale {e1, e2, …, en} in modo tale che,

per ogni indice K compreso tra 1 ed n, il vettore ek sia combinazione lineare dei vettori {x1, x2, …, xk}, e quindi {x1, x2, …, xk}= {e1, e2, …, ek}.

Il procedimento di ortogonalizzazione consente di generare due successioni di polinomi:

sono ortonormali

sono ortogonali

Poniamo q0(x)=1 e definiamo:

Per k=1,..,n poniamo:

e

La successione è costituita da polinomi ortogonali. Pertanto a norma di

definizione si ha:

La successione è costituita da polinomi ortonormali. Quindi:

Scegliendo tali successioni la matrice del sistema di equazioni è diagonale, quindi non

più mal condizionata.

Il procedimento Gram ammette la seguente conseguenza: se lo spazio V ha

dimensione n, dunque possiede una base costituita da n vettori, allora esso possiede

anche una base ortogonale costituita da altrettanti vettori.

Si tratta di polinomi ortogonali su [-1,1] con peso e sono definiti dallarelazione:

Se consideriamo, nell’intervallo [-1.1], il cambiamento di variabile otteniamo:Dalle formule sulla somma dei coseni si ha:

Da cui segue:

E quindi otteniamo la seguente relazione di ricorrenza:

ovvero

Poichè si tratta di polinomi di grado n, l’uguaglianza stabilita vale per ogni x є R.

Poiché T0(x)=1 e T1(x)=x vede facilmente che Tn(x) є Pn per ogni n

Tenendo presente che: T0(x)=1 e T1(x)=x si ha: n=1,2,3,4

T2(x)=2x2 – 1

T3(x)=4x3 – 3x …

ed inoltre il coefficiente principale di xn è 2n-1

Il polinomio Tn (x) è ovviamente definito su tutto R, ma soltanto in [-1,1] coincide con la funzione cos(n arccos(x)).

Osserviamo che moltiplicare la distanza per una funzione

significa richiedere approssimazione molto precisa soprattutto agli estremi dell'intervallo [-1,1].

Infatti la w(x) vale 1 nell'origine, mentre agli estremi dell'intervallo essa tende ad infinito, pur mantenendosi integrabile.

Quindi nel minimizzare la funzione J(a) si mantengono i valori della distanza effettiva fra la funzione da approssimare e il polinomio approssimante nella zona centrale dell'intervallo [-1,1] ma si amplificano i valori della distanza agli estremi dell'intervallo stesso.

2( ) ( )nf x p x

Le radici di Tn sono date da: per j= 0…,n-1

e sono tutte reali e semplici ed appartenenti all’intervallo] − 1, 1[;

Tra due radici consecutive del polinomio Tn+1 ne esiste sempre una ed una sola del polinomio Tn, precisamente x(n+1)

k+1 < x(n) k < x(n+1)

k per ogni k = 1, . . . , n.

Due polinomi di Chebyshev consecutivi Tn e Tn+1 non hanno radici in comune.

Cerchiamo n ascisse xj , j=0,…,n-1 tali che Tn(xj)=0 cioè

Dunque

Ritornando alla variabile x otteniamo j= 0,..,n-1

che sono gli zeri distinti di Tn(x)

I polinomi di Chebyshev sono ortogonali rispetto al peso , e rispetto al

seguente prodotto scalare :

cioè verificano la seguente relazione:

Sia W(x) = ∏i=0:n(x-xi)∊ Pn+1.

Tra le possibili scelte dei nodi {xi} i=0:n , Xi ∊[-1,1], inoltre ||W|| = max |W(x)| è minima se: W(x) = Tn+1 (x)/2n cioè gli xi sono gli zeri di Tn+1 (x).

DIMOSTRAZIONE.

Tn+1(x) ha il coefficiente di xn+1 dato da 2n.

Allora, tra tutti i polinomi del tipo xn+1+…, (noti come polinomi monici), è un

candidato per il minimo di . Poniamo quindi: con:

Si ha: poiché se x Є [-1,1].

Teorema

Se poniamo

i =0, …, n+1 si ha

e pertanto . Supponiamo ora che non esiste V Є Pn+1 monico e tale che . Si avrà:

◦ Per i pari ◦ Per i dispari

Pertanto , Definendo H(x) = V(x) – W(x) si ha che : H(x) Є Pn poiché V e W hanno lo

stesso xn+1 . Ma H(x) ha n+1 zeri, il che è assurdo e da ciò la tesi.

function x=cheb(n)

n=20;

ab=-1:1;

if nargin==1

a=-1; b=1;

else

a=ab(1); b=ab(2);

end

for i=0:n

x(i+1)= (a+b)/2 -(b-a)/2*cos(pi*(2*i+1)/(2*(n+1)));

end

plot(i,x);

f=inline('exp(x).* sin(2*x)');

a=0;b=2;

n=5;

for i=0:n

x(i+1)= (a+b)/2 -(b-a)/2*cos(pi*(2*i+1)/(2*(n+1)));

end ;

fx=f(x(i)); % Calcola f sui nodi di griglia

p=polyfit(x(i),fx,n); % Costruisce il polinomio di grado 5

xx=0:0.01:2; % Costruisce una griglia grafica

pxx=polyval(p,xx); % Valuta il polinomio sulla griglia xx

plot(xx,f(xx));

hold;

plot(xx,pxx,'g'); % Disegna il grafico del polinomio

plot(x(i),fx,'r*'); % Disegna i punti di interpolazione

Nodi di Chebishev Nodi equispaziati

Ponendo la funzione peso w(x)=1 otteniamo i polinomi di Legendre su [-1,1] definiti dalla relazione ricorsiva:

(n + 1) Pn+1 (x) = (2n + 1)xPn(x) − nPn−1(x).

Alcuni polinomi di Legendre con il relativo grafico:

Grado – Pn (x)

0 -> 1

1 -> x

2 -> 3x2 /2 – ½

3 -> 5x3/2 – 3/2x

…

n=1,2,3,4

Introduzione

Sia f una funzione integrabile sull’intervallo [a, b].

Il suo integrale può essere difficile da calcolare (può anche non essere

valutabile in forma esplicita).

Una formula esplicita che permetta di approssimare I (f ) viene detta formula di quadratura o formula d’integrazione numerica:

Gli n+1 punti distinti xi ed i coefficienti ai sono detti, rispettivamente, nodi e pesi della quadratura.

Il problema consiste nel determinare xi ed ai in modo che:

per una ampia classe di funzioni.

Se è un polinomio interpolante la f (x) nei punti xi, avremo:

I nodi e i pesi sono scelti in modo da minimizzare l’errore: Una misura di tale errore è data dal grado di precisione o ordine polinomiale.Ogni formula di quadratura interpolatoria che usi n + 1 nodi distinti ha grado di esattezza >=n.

Un modo generale per costruire formule di quadratura con grado di precisionefissato è il metodo dei coefficienti indeterminati, che consiste nel determinare inodi e i pesi imponendo che la formula sia esatta per polinomi del grado datodall’ordine polinomiale.

Vi sono quindi due diverse strategie: a) fissare i nodi e determinare i pesi oppureb) lasciare entrambe le quantità incognite.

Caso a)I pesi si trovano risolvendo il sistema lineare:

Caso b)Il sistema è non lineare. Ciò darà luogo alle formule col più alto grado di precisionepossibile. 

Per aumentare la precisione si hanno due alternative:1) aumentare il numero di nodi, in modo che Qn( f ) sia integrale di un polinomio interpolante di alto grado (quadrature gaussiane);2) dividere [a,b] in sottointervalli utilizzando in essi formule di bassa precisione, quindi sommare i risultati (regole di quadratura composte).

Una formula di quadratura gaussiana consiste in una formula di tipo interpolatorio

che massimizza l'ordine di precisione con un dato numero di nodi. In particolare, scelti n + 1 nodi in modo che siano gli zeri del polinomio di grado n + 1, ortogonale a tutti i polinomi di grado <= n, la formula di quadratura gaussiana ha grado di precisione 2n + 1.

Una caratteristica delle formule di quadratura gaussiane è di avere i pesi tutti positivi, il che contribuisce a irrobustire la stabilità della formula.

Una quadratura di tipo gaussiano si ottiene risolvendo il sistema non lineare:

in cui sia ai che xi sono indeterminati ,imponiamo che la formula abbia precisione 2n+1, se n+1 sono i nodi della quadratura.

Il sistema risultante avrà 2n+2 incognite.

Se n=0 e [a,b]=[-1,1]

Per cui si potrà scrivereImponendo che l’errore sia uguale a 0 possiamo scrivere cioè

Per f(x)=1, x si ottiene, rispettivamente:

Sostituendo i valori appena trovati, otteniamo: Q0 (f) = 2 f(x0) Estendendo questo risultato ad un intervallo [a,b] generico, si ha:

Per n=1, e [a,b]=[-1,1], imponendo che l’errore e considerando f(x)=1,x,x2 ,x3

otteniamo :

Quindi, in generale, si deve risolvere il sistema non lineare:

nelle 2n+2 incognite a0… an , x0… xn .

Nell’ambito delle formule di quadratura interpolatorie, però, si può trovare un’opportuna formula con grado di precisione 2n+1 (che per n+1 nodi è il massimo possibile) senza dover risolvere il sistema non lineare.

A tale scopo consideriamo il seguente:

Teorema

Se è una formula di quadratura di tipo interpolatorio, ovvero

dove pn (x)Є Pn è un polinomio interpolante la funzione f (x) negli n+1 nodi x0… xn ,

ali nodi sono gli zeri di un polinomio pn+1 (x)Є ∏n+1 , insieme dei polinomi ortogonali su [a,b], allora il grado di precisione della formula è 2n+1.

 

Sia

Possiamo scrivere f(x) = pn+1(x) q(x) + r (x) con q(x),r (x) Є Pn.

quindi

Pertanto:

Per il calcolo dei nodi di una quadratura gaussiana si generano dapprima i polinomi ortogonali, usando le formule di ricorrenza.

Dal momento che gli zeri di tali polinomi sono dei valori reali semplici ed interni all’intervallo di ortogonalità, per determinarli si può utilizzare il metodo di Newton.

 

Per il calcolo dei pesi, invece, si può utilizzare il metodo dei coefficienti

indeterminati, oppure possono essere ricavati da:

dove l sono i polinomi fondamentali di Lagrange di grado n.

Se l’integrale da calcolare è del tipo: allora la quadratura

(cioè i nodi ed i pesi) dipende da w(x) .

In tal caso si scelgono i polinomi ortonormali in [a,b] rispetto a w(x) .

a)Polinomi di Jacobi W(x)= (1-x)-p (1+x)-q

b)Polinomi di Chebishev W(x) = 1/√ (1-x) 2

c)Polinomi di Legendre W(x) = 1