Polinomi ortogonali

Alvise Sommariva

Università degli Studi di Padova

Dipartimento di Matematica

Il problema ai minimi quadrati

22 marzo 2016 Definizione (Spazio di Hilbert) Uno spazio di Hilbert è uno spazio euclideo che è

completo, separabile, infinito dimensionale (cf. [6, p.155]).

Nota. Al variare del testo la definizione di spazio di Hilbert può essere leggermente diversa, ad esempio uno spazio di Hilbert è uno spazio euclideo completo (cf. [2]).

Esempio

Consideriamo lo spazio normato delle funzioni reali misurabili (cf. [6, p.284]) quadrato integrabili (L^{2}(a, b), ∥ · ∥_{2}) dove (a, b) è un intervallo della retta reale, non necessariamente limitato (cf. [6, p.386], ricordando [6, p.308]), e

∥g∥_{2} = (g, g), (f , g)_{2} = ∫_{a}^{b} f (x) · g(x)dx.

Si dimostra (non facile!) che questo spazio euclideo è un esempio di spazio di Hilbert (cf. [6, p.388]).

Il problema ai minimi quadrati

Esempio Più in generale se w : (a, b) → ℝ è una funzione misurabile positiva allora lo spazio (L_{w}^{2}(a, b), ∥ · ∥_{2,w}) definito come

L_{w}^{2}(a, b) = {f misurabili t.c. ∫_{a}^{b} |f (x)|^{2}w(x) dx < ∞} è uno spazio di Hilbert dotato del prodotto scalare

(f , g)_{2,w} = ∫_{a}^{b} f (x) · g(x)w(x) dx

(cf. [2, p.23]).

Alvise Sommariva  Polinomi ortogonali  4/ 32

Definizione (Funzione peso) Supponiamo sia w : (a, b) → ℝ una funzione tale che

w è nonnegativa, con (a, b) non necessariamente limitato, ∫_{a}^{b} |x|^{n} w(x) dx < +∞ per tutti gli n ∈ ℕ; ∫_{a}^{b} g(x) w(x) dx = 0 per qualche funzione continua e non negativa g implica g ≡ 0 in (a, b).

Una tal w si dice funzione peso.

Polinomi ortogonali

Esempio Le funzioni peso più comuni sono (cf. [1, p.206])

1 w(x) = 1 con x ∈ [−1, 1] (peso di Legendre); 2 w(x) = \frac{1}{\sqrt{1−x^{2}}} con x ∈ (−1, 1) (peso di Chebyshev)); 3 w(x) = (1 − x^{2})^{γ−(1/2)} con x ∈ (−1, 1), γ > (−1/2) (peso di

Gegenbauer)); 4 w(x) = (1 − x)^{α} · (1 + x)^{β} con x ∈ (−1, 1), α > −1, β > −1

(peso di Jacobi)); 5 w(x) = exp (−x) con x ∈ (0, +∞) (peso di Laguerre)); 6 w(x) = exp (−x^{2}) con x ∈ (−∞, +∞) (peso di Hermite); Teorema Lo spazio vettoriale L_{w}^{2}(a, b) contiene lo spazio dei polinomi P_{n} di grado n (con n ∈ ℕ arbitrario).

Dimostrazione. Infatti, se p_{n}(x) = ∑_{k=0}^{n} a_{k}x^{k} allora per la disuguaglianza triangolare e il fatto che per ogni k si ha

∥x^{k}∥_{2,w}^{2} = ∫_{a}^{b} |x|^{2k} w(x) dx < +∞

necessariamente

∥p_{n}∥_{2,w} = ∥∑_{k=0}^{n}a_{k}x^{k} ∥_{2,w} ≤ ∑_{k=0}^{n}|a_{k}|∥x^{k}∥_{2,w} < +∞,

e quindi p_{n} ∈ L_{w}^{2}(a, b). △

Alvise Sommariva  Polinomi ortogonali  7/ 32

Il problema ai minimi quadrati

Nota. Si osservi che se ”a” e ”b” sono finiti, dal teorema di Weierstrass

∥x^{n}∥_{∞} = max_{x∈[a,b]}|x|^{n} < +∞

ricordando che w ≥ 0,

∫_{a}^{b} |x|^{n} w(x) dx ≤ ∥x^{n}∥_{∞} ∫_{a}^{b} w(x) dx

da cui se

∫_{a}^{b} w(x) dx < +∞

automaticamente, per tutti gli n ∈ ℕ, ∫_{a}^{b} |x|^{n} w(x) dx < +∞.

Alvise Sommariva  Polinomi ortogonali  8/ 32

Problema. Fissati

f ∈ L_{w}^{2}([a, b]),
n ∈ ℕ,

il problema ai minimi quadrati (nel continuo) consiste nel determinare il polinomio p_{n} di grado n tale che sia minima la quantità (cf. [1, p.204-207])

∥f − p_{n}∥_{2,w} = ∫_{a}^{b} |f (x) − p_{n}(x)|^{2} w(x) dx.

Essendo L_{w}^{2}([a, b]) uno spazio euclideo, e (ϕ_{k})_{k=0,...,n} una base di P_{n}, abbiamo visto che la soluzione del problema

∥f − f^{∗}∥_{2,w} = min_{g∈span{ϕ_{0},...,ϕ_{n}}}∥f − g∥_{2,w}

è f^{∗} = ∑_{j=0}^{n} γ_{j}^{∗}ϕ_{j} dove i coefficienti γ_{j}^{∗} verificano le cosidette equazioni normali

∑_{k=0}^{n}(ϕ_{j}, ϕ_{k})_{2,w}γ_{k}^{∗} = (ϕ_{j}, f )_{2,w}, j = 0, …, n.

La soluzione è caratterizzata dalla proprietà di ortogonalità cioè che f^{∗} − f è ortogonale a tutti gli ϕ_{k}, con k = 1, …, n, ovvero

(f , ϕ_{k})_{2,w} = (f^{∗}, ϕ_{k})_{2,w}, k = 0, …, n
Alvise Sommariva  Polinomi ortogonali  10/ 32

Il problema ai minimi quadrati

Nel caso ϕ_{k}(x) = x^{k} per k = 0, …, n, le equazioni normali si riscrivono quindi come

∑_{k=0}^{n}γ_{k}^{∗} (∫_{a}^{b} x^{j+k}w(x)dx) = ∫_{a}^{b} x^{j}f (x)w(x)dx, j = 0, …, n. o in forma matriciale, posto per j, k = 0, …, n

A_{j,k} := ∫_{a}^{b} x^{j+k}w(x)dx, β_{j} = ∫_{a}^{b} x^{j}f (x)w(x)dx, come Aγ = β.

Alvise Sommariva  Polinomi ortogonali  11/ 32

Vediamo quale caso particolare w(x) ≡ 1, (a, b) = (0, 1). Poichè

A_{j,k} = ∫_{0}^{1} x^{j+k} dx = \frac{1}{j + k + 1}

si nota che la matrice A coincide con la matrice di Hilbert (cf. [7])

H_{s,t} = \frac{1}{(s − 1) + (t − 1) + 1}, , s, t = 1, …, n + 1

La matrice di Hilbert H è estremamente sensibile a piccoli cambiamenti nei coefficienti o dei valori del termine noto (si dice malcondizionata).

Facoltativo. Per vederlo (cf. [1, p.530-535]), sia A una matrice non singolare di ordine N, ∥ · ∥ una norma indotta di matrice [8] cioè tale che

∥Ax∥ ≤ ∥A|∥x∥, ∀x ∈ ℝ^{N}

e indichiamo con

κ(A) = ∥A∥∥A^{−1}∥

il condizionamento della matrice rispetto alla norma ∥ · ∥. Si dimostra [3, p.137] che se

(A + δA)(x + δx) = b + δb,

allora

\frac{∥δx∥}{∥x∥} ≤ \frac{κ(A)}{1 − κ(A)\frac{∥δA∥}{∥A∥}} · (\frac{∥δb∥}{∥b∥} + \frac{∥δA∥}{∥A∥}) .

Alvise Sommariva  Polinomi ortogonali  13/ 32

Facoltativo. Per capirne il significato, si supponga per semplicità δA = 0, Allora

\frac{∥δx∥}{∥x∥} ≤ \frac{κ(A)}{1 − κ(A)\frac{∥δA∥}{∥A∥}} · (\frac{∥δb∥}{∥b∥} + \frac{∥δA∥}{∥A∥}) = κ(A)\frac{∥δb∥}{∥b∥}

per cui più grande è κ(A) più grande è il rischio che piccole perturbazioni sul termini noto b provochino grandi effetti sul calcolo della soluzione x.

Si noti che questa stima è solo una maggiorazione.

In molti casi risulta un buon indicatore di quanto un sistema lineare sia difficile da risolvere al calcolatore, indipendentemente dal metodo utilizzato.

Facoltativo. Tornando alla matrice di Hilbert H, vediamo in Matlab valori del numero di condizionamento in norma 2. Se λ_{k} sono gli autovalori di A ordinati in modulo, cioè

|λ_{1}| ≤ … ≤ |λ_{l}| ≤ … ≤ |λ_{n}|

si dimostra che essendo la matrice H simmetrica e definita positiva (cf. [3, p.140])

K_{2}(A) = \frac{|λ_{n}|}{|λ_{1}|}.

Curiosamente, quest’ultima uguaglianza lega due grandi nomi dell’informatica moderna, essendo la corrente definizione di condizionamento introdotta da Turing mentre il rapporto degli autovalori a secondo membro da Von Neumann [3, p.226].

Alvise Sommariva  Polinomi ortogonali  15/ 32

Facoltativo. Per quanto anticipato, calcoliamo il condizionamento della matrice di Hilbert e i corrispettivi autovalori massimi e minimi in modulo. Notiamo che Matlab, non approssimando gli autovalori di una matrice per ottenere il numero di condizionamento (cf. [3, p.139]), per valori grandi dello stesso offre solo un’approssimazione.

D’altra parte si può dimostrare che il condizionamento (in norma 2) della matrice di Hilbert di ordine n è approssimativamente exp (3.5 n) (cf. [3, p.139]).

Il problema ai minimi quadrati

Facoltativo.

>> h e l p cond

COND    Condition  number  with  respect  to  inversion .
COND (X) returns  the 2−norm condition  number (the  ratio  of  the
largest  singular  value  of X to  the  smallest ) . Large  condition
numbers  indicate  a  nearly  singular  matrix .
COND (X , P) returns  the  condition  number  of X in P−norm :
    NORM (X , P) ∗ NORM (INV(X) ,P) .

where  P = 1 , 2 , inf , or ’ f r o . ’

See  also  RCOND , CONDEST , CONDEIG , NORM , NORMEST .

Alvise Sommariva  Polinomi ortogonali  17/ 32

Il problema ai minimi quadrati

Facoltativo.

>> f o r n=5:5:40
f p r i n t f ( ’\n \t [ n ] : %2.0 f [ cond (norma 2) ] : %2.2e [ det ] : %2.2e ’ , n , cond (
h i l b (n) ) , …
det ( h i l b (n) ) ) ; end
[ n ] : 5 [ cond ( norma 2) ] : 4 . 7 7 e+005 [ det ] : 3 . 7 5 e−012
[ n ] : 1 0 [ cond ( norma 2) ] : 1 . 6 0 e+013 [ det ] : 2 . 1 6 e−053
[ n ] : 1 5 [ cond ( norma 2) ] : 8 . 4 9 e+017 [ det ]: −2.19e−120
[ n ] : 2 0 [ cond ( norma 2) ] : 1 . 9 1 e+018 [ det ]: −1.12e−195
[ n ] : 2 5 [ cond ( norma 2) ] : 1 . 4 6 e+019 [ det ] : 8 . 1 4 e−275
[ n ] : 3 0 [ cond ( norma 2) ] : 6 . 1 9 e+018 [ det ] : 0 . 0 0 e+000
[ n ] : 3 5 [ cond ( norma 2) ] : 1 . 0 3 e+019 [ det ] : 0 . 0 0 e+000
[ n ] : 4 0 [ cond ( norma 2) ] : 4 . 5 5 e+019 [ det ] : 0 . 0 0 e+000
Alvise Sommariva  Polinomi ortogonali  18/ 32

Il problema ai minimi quadrati

Facoltativo.

>> f o r n=5:5:40
f p r i n t f ( ’\n \t [ n ] : %2.0 f [ min autov . ] : %2.2e [max autov . ] : %2.2e ’ , …
n , min( abs ( e i g ( h i l b (n) ) ) ) ,max( abs ( e i g ( h i l b (n) ) ) ) ) ;

end

[ n ] : 5 [ min autov . ] : 3 . 2 9 e−006 [max autov . ] : 1 . 5 7 e+000
[ n ] : 1 0 [ min autov . ] : 1 . 0 9 e−013 [max autov . ] : 1 . 7 5 e+000
[ n ] : 1 5 [ min autov . ] : 7 . 5 8 e−018 [max autov . ] : 1 . 8 5 e+000
[ n ] : 2 0 [ min autov . ] : 3 . 0 5 e−018 [max autov . ] : 1 . 9 1 e+000
[ n ] : 2 5 [ min autov . ] : 1 . 7 0 e−018 [max autov . ] : 1 . 9 5 e+000
[ n ] : 3 0 [ min autov . ] : 9 . 4 9 e−019 [max autov . ] : 1 . 9 9 e+000
[ n ] : 3 5 [ min autov . ] : 1 . 6 8 e−017 [max autov . ] : 2 . 0 1 e+000
[ n ] : 4 0 [ min autov . ] : 2 . 2 2 e−017 [max autov . ] : 2 . 0 4 e+000

>>

Alvise Sommariva  Polinomi ortogonali  19/ 32

Ricapitolando

1 il problema ai minimi quadrati continui ha un’unica soluzione se e solo se un certo sistema lineare Aγ = β ha una e una sola soluzione;

2 nel caso w ≡ 1, (a, b) = (−1, 1) la matrice A coincide con la matrice di Hilbert che ha un numero di condizionamento estremamente grande, il che comporta che il sistema lineare Aγ = β sarà estremamente sensibile a piccole perturbazioni (cioè malcondizionato);

3 la matrice di Hilbert sembra essere singolare, cioè avente determinante nullo, per n ≥ 0; in realtà, come già detto, si dimostra che è simmetrica e definita positiva, e quindi tutti gli autovalori sono positivi da cui il determinante è non nullo essendo il prodotto degli autovalori.

Alvise Sommariva  Polinomi ortogonali  20/ 32

Notiamo subito che il sistema è difficile da risolvere poichè abbiamo rappresentato il polinomio p_{n}^{∗} nella base 1, x, …, x^{n}. Cosa succede se lo scriviamo come combinazione lineare di elementi di un’altra base {ϕ_{n}}? Se ad esempio scegliessimo la base {ϕ_{n}} cosicchè

(ϕ_{k}, ϕ_{m}) = a_{k}δ_{k,m}, a_{k} > 0, k, m ∈ 0, 1, …, n

con δ_{k,m} delta di Kronecker, finiremmo per risolvere un problema Aγ = β dove A è una matrice diagonale e quindi senza alcuna difficoltà troveremmo

γ_{k} = \frac{β_{k}}{a_{k}}

con a_{k} > 0.

Risulta quindi di importanza fondamentale cercare basi di polinomi {ϕ_{j}} per cui

(ϕ_{k}, ϕ_{m}) = a_{k}δ_{k,m}, a_{k} > 0, k, m ∈ 0, 1, …, n.
Alvise Sommariva  Polinomi ortogonali  21/ 32

Definizione (Polinomi ortogonali)

Una tal famiglia triangolare di polinomi {ϕ_{k}}_{k=0,...,n} (cioè tale che deg(ϕ_{k}) = k) si dice ortogonale rispetto alla funzione peso w nell’intervallo di riferimento se e solo se

(ϕ_{i}, ϕ_{j})_{2,w} = c_{i} δ_{i,j}

con δ_{i,j} il delta di Kronecker, c_{i} > 0, i, j = 0, …, n).

Si può dimostrare usando la procedura di Gram-Schmidt che una tal famiglia triangolare di polinomi esiste e con la stessa procedura costruirla direttamente; inoltre è immediato osservare che ogni polinomio di grado n si può scrivere univocamente come combinazione lineare di ϕ_{0}, …, ϕ_{n}.

Di conseguenza se p_{n} = ∑_{j=0}^{n} a_{k}ϕ_{k}, allora per la bilinearità del prodotto scalare (·, ·)_{2,w}

(ϕ_{n+1}, p_{n})_{2,w} = (ϕ_{n+1}, ∑_{j=0}^{n}a_{k}ϕ_{k})_{2,w} = ∑_{j=0}^{n}a_{k}(ϕ_{n+1}, ϕ_{k})_{2,w} = 0.

Inoltre (cf. [4, p.978], [1, p.213])

Teorema Sia {ϕ_{k}}_{k=0,...,n} una famiglia triangolare di polinomi ortogonali in (a, b) rispetto ad una funzione peso w. Allora il polinomio ϕ_{n} ha esattamente n radici reali e distinte nell’intervallo aperto (a, b).

Dimostrazione. Siano x_{1}, …, x_{m} (con m ≤ n) tutti e soli gli zeri di ϕ_{n} interni ad (a, b) con molteplicità rispettivamente α_{1}, …, α_{m}. Di conseguenza, per qualche numero a_{n} abbiamo

ϕ_{n}(x) = a_{n} (∏_{k=1}^{m}(x − x_{k})^{α_{k}})r(x)

avendo supposto ∏_{k=1}^{m}(x − x_{k})^{α_{k}} ≡ 1 se non ci sono zeri interni ad (a, b).

Il polinomio r per costruzione non ha zeri in (a, b) e quindi non si annulla mai ed essendo una funzione continua ha segno costante.

Dimostrazione. Consideriamo il polinomio

q(x) = (∏_{k=1}^{m}(x − x_{k})^{mod_{2}(α_{k})}).

Se uno zero di ϕ_{n} ha molteplicità dispari ma maggiore di 1 o uno almeno ha molteplicità pari o esiste uno zero complesso non in (a, b), è facile osservare che il grado di q è minore di n. Osserviamo ora che qualsiasi sia un numero naturale, α_{k} + mod_{2}(α_{k}) è un numero pari.

Polinomi ortogonali

Dimostrazione. Di conseguenza avendo (∏_{k=1}^{m}(x − x_{k})^{α_{k}+mod_{2}(α_{k})})r_{n−m}(x) segno costante e non coincidente col polinomio nullo,

0 = (ϕ_{n}, q)
= ∫_{a}^{b} ϕ_{n}(x) q(x) w(x) dx
= ∫_{a}^{b} a_{n} ∏_{k=1}^{m}(x − x_{k})^{α_{k}}r_{n−m}(x) ∏_{k=1}^{m}(x − x_{k})^{mod_{2}(α_{k})} w(x) dx
= ∫_{a}^{b} a_{n} (∏_{k=1}^{m}(x − x_{k})^{α_{k}+mod_{2}(α_{k})})r_{n−m}(x) w(x) dx ≠ 0

(1)

da cui la contraddizione.

Alvise Sommariva  Polinomi ortogonali  27/ 32

Nota. Potrebbe venire il dubbio su perchè qualche zero non possa essere ”a” o ”b”. Nella dimostrazione avrebbe quale unico effetto che r_{n−m} si annulla in ”a” o ”b”, rimanendo di segno costante in (a, b). La conclusione è che il polinomio ortogonale p_{n} ha n radici distinte e semplici, interne ad (a, b).

Polinomi ortogonali

Teorema ([1]) Sia {ϕ_{k}}_{k=0,...,n} una famiglia triangolare di polinomi ortogonali in [a, b] rispetto ad una funzione peso w. Allora per n ≥ 1

ϕ_{n+1}(x) = α_{n}(x − β_{n})ϕ_{n}(x) − γ_{n}ϕ_{n−1}(x)

dove, detto a_{n} il coefficiente di grado massimo di ϕ_{n}, si ha

α_{n} = \frac{a_{n+1}}{a_{n}}  (2)
β_{n} = \frac{(xϕ_{n}, ϕ_{n})_{2,w}}{(ϕ_{n}, ϕ_{n})_{2,w}}  (3)
γ_{n} = \frac{α_{n}(xϕ_{n−1}, ϕ_{n})_{2,w}}{(ϕ_{n−1}, ϕ_{n−1})_{2,w}}  (4)

Alvise Sommariva  Polinomi ortogonali  29/ 32

Nota. Notiamo che

scelti i polinomi ortogonali ϕ_{0} e ϕ_{1}, la procedura determina la famiglia triangolare di polinomi ortogonali di grado superiore, non appena sono disponibili i coefficienti α_{k}, β_{k}, γ_{k}. Se ϕ_{n} è tale che (ϕ_{n}, ϕ_{k})= 0 per k = 0, …, n − 1 allora per τ ≠ 0 pure ϕ̃_{n} = τϕ_{n} è tale che

(ϕ̃_{n}, ϕ_{k}) = (τϕ_{n}, ϕ_{k}) = τ(ϕ_{n}, ϕ_{k}) = 0, k = 0, …, n − 1

e quindi potrebbe essere considerato quale polinomio ortogonale di grado n.

Nota. In pratica spesso si sceglie

α_{n} = 1,

i polinomi ϕ_{0}(x) = 1, ϕ_{1}(x) = x − ∫_{a}^{b} xw(x)dx/ ∫_{a}^{b} w(x)dx cosicchè i polinomi ortogonali siano monici cioè con coefficiente di grado massimo uguale a 1.

In molti altri casi, come nelle routines Matlab di W. Gautschi, si pone

p_{−1}(x) = 0,
p_{0}(x) = 1,

e quindi si applica la formula ricorsiva con α_{k} = 1 per k > 0.

K. Atkinson, An Introduction to Numerical Analysis, Wiley, (1989). K. Atkinson e W. Han, Theoretical Numerical Analysis, A Functional Analysis Framework, Springer, (2001). D. Bini, M. Capovani e O. Menchi , Metodi numerici per l’algebra lineare, Zanichelli, (1993). V. Comincioli, Analisi Numerica, metodi modelli applicazioni, McGraw-Hill, (1990). G. Dahlquist e A. Bjorck , Numerical methods, Dover, (2003). A.N. Kolmogorov e S.V. Fomin, Introductory Real Analysis, Dover publications, 1970. Wikipedia, (Hilbert Matrix), http://en.wikipedia.org/wiki/Hilbert matrix. Wikipedia, (Norma matriciale), http://it.wikipedia.org/wiki/Norma matriciale. Wikipedia, (Orthogonal polynomials), http://en.wikipedia.org/wiki/Orthogonal polynomials. Wikipedia, (Polinomi di Chebyshev), http://it.wikipedia.org/wiki/Polinomi di Chebyshev. Wikipedia, (Polinomi Ortogonali), http://it.wikipedia.org/wiki/Polinomi ortogonali.