Calcolo numerico - parte 2

EIR

a rispetto Minimi

Questo

dobbiamo minimizzare di

ad problema

è

ovvero a un

.

La X MATRICE

matrice è

QUADRATI detta VANDERMONDE

DI

. I

j xyn - ..... S

M

XI potenze di

2

X2 - XI

1

Xch Xqn X21 - dalla

potenze potenza alla

- potenza

n-esima

di x

:

: 2

n -

Xm Xm Xm1-Dpotenze di Xm

Supponiamo il che

volere approssimante punti

2

di

di polinomio nei

grado assume

Xi ,

Questo del

forma

valore tipo

avrà

yi una

.

a2x

P(x) a0

azx

+ +

=

Sostituendo i incognite

/Xi yi) individuare

dati da

abbiamo le

che

note per

, ,

,

il di

miglior polinomio i

approssimante coeff

grado 2 sono

avere ac do

as :

, ,

,

↑ azxi2

(xi) azXi +

+ 00

=

La sull'insimo

funzione i

errore modo :

1)T

P(xi)(x 2

aT(x

yi xi

yi

- ,

- , ,

L'errore dato

è da

completo :

1)T)2

I (yi aT(xi2 xi

- ,

,

In matriciale

forma abbiamo che :

2

-[

1 tutti infatti

,

Così

9 componente

gli ,

abbiamo ad

agni

errori

la

sottratta attenuta

viene

di dal

quantità prodotto

y ,

in tra matrici .

↳ abbiamo aT(xi2 1)

il

invertito la

viene

prodotto stessa

Xi ma cosa

.

, , trovare

quindi la

vado

Calcolata la minimizzare

vado

al quadrato su

au

norma a

a

, ,

matrice l'errore

che minimo

rende

a .

Potrei funzione

la

minimizzare )

+

[ aT(xi)

Bi(yi 1)

xi

- , , l'attendibilità dato

fattore che

Bi

dae indica del

è ovvero

un ,

inattendibile

n dato

Se Bi o =

=

Se dato

1 attendibile

Bi D

=

=

In affidabili

importanza

dare quelli

modo

questo i date pesate si maggior

va

vengono e a a

importanza affidabili

minor quelli

e a non .

Questo risolto regressione

stato

problema la POLINO

è Mace

con :

possibile

funzione il

che dai punti garantito

sposte

cerchiamo si è

, non

una meno

i si

che la punti

funzione li

meglio

quella che approssima

passi per cerca

ma .

,

NOTA

- facilmente

Vandezmonde elevate

condizionamente

La matrice anche

di raggiunge con

,

sulla

piccole variazioni .

Xi l'interpolazione

Per visto

l'approccio si

la

questo regressione

per usa per

non .

,

,

LEZIONE 8104

12 POLINOMIALE

INTERPOLAZIONE

PROBLEMA Pn(x)

(x0 (Xn trovi

dati polinomio tale

yo) grado

di

yn) si

punte che

na

: un :

n

, ....., ,

Pr(xi) i o

,...,

con

gi n

= =

Esiste il gli

che

polinomio grado punti

è unico

ed passa

di n+1

per

n .

Vediamo problema

di

metodi questo

alcuni di risoluzione :

FUNZIONE

PROBLEMA DELLA INTERPOLANTE il

si trovi

funzione

Assegnate fixi) polinomio

ascisse di

ed

1

N Xn

X1

+ Xo una ,

....,

,

Pn(x) tale che

grado n :

Pr(xi) f(xi) i

con o

, n

=

= ...,

Il azx

P(x) anx

polinomio cercato la forma

avrà azx

do + +... +

+

: =

Imponendo si

condizioni

le flxi)

P(xi) il risolve

Interpolazione problema

di yi

=

= ,

il sistema

seguente :

attraverso ....

. j

I 1

Xon

n -

Xo . . . .

1

n Xyn -

XI

In n 1 1

(n

-

Xn 1 -

.

- .

.

X

n 8 (Xn)

Xn Xn

. . . . .

Le Quando

incognite prodotti

calcoliamo

coefficiente i

i i

ai 0

sono per

con n

= ...., .

nell'i-esimo

il deve

colonna dicendo nodo

che

stamo polinomio uguale

essere a

,

il

flxi) polinomio

prodotto

primo

Ovvero dal attengo nel nodo Xo

, :

. I antXol"an-1

Jad

1)

(vor Xoh Xo Xoas+

+... + do

xo =

. . . . ao il

sistema polinomio

imponendo che

Con punto

questo nel

stiamo deve

Xo essere

,

f(xd

uguale uguale

ovvero a yo

a .

il

Questo formalmente

interpolante corretta

è

di polinomio

calcolare

metado ma

,

,

vista

punto efficiente

da è

di pratico

un non

La matrice condizionata

è

MATRICE mal

detta anche

punti

dei Xi DI VANDERMONDE

,

, ,

piccoli

.

n

per ci problemi

Nonostante la ,

matrice quindi nella

pieno

ha sono

rango non

sempre , all'impossibilità

svantaggio di

del altro

sistema dovuto

è

risoluzione un

,

le volesse

attenute

utilizzare soluzioni altro punto

si aggiungere

se

;

già un

(bisogna .

da

ricominciare

Xi capa

1

+

Questa il polinomio interpolante è

costruzione praticamente

dimostra che ha

univocamente le distinte (matrice

determinato siano

perché

, xi determinato

sistema compatibile

=D

pieno

rango e

POLINOMIO INTERPOLANTE LAGRANGE

DI

20(x)yo

P(x) 22(x)yz 2n(x)yn

Ly(x)y

+ +

+ +...

= +

(EDP(x) (2(x)f(x2)

Co(x)f(xo) (n(x)f(xn)

(1(x)f(x) +....

+ +

= +

PoliNoti

P(x)

dove detto

è Interpolatore

si dicono Nodi Interpolazione

di

Xi il

Definiamo polinomio

r-esimo : (x

)(x

(x (X

(r(x) xo(x )

x2) xn)

Xn Xm -

- -

- -

- +

= . . . . ...

(xp (Xk (Xx

Xo(xm 1)(X Xn)

1)

Xk Xr

X2)

- -

- - + -

. . . . - -.

-

=

#(m(x)

Osserviamo che :

Il (perché

tutti

(r(x) interpolazione

in i nodi

1 di Scelgo

polinomio Comunque

nullo

è ,

Xi

. ,

tra stesso)

termini tra

la tranne

i differenza

moltiplicate nel

che

sempre

avrò Xi se

e

,

, (infatti il

si

tra numeratore

R-esimo i prodotti quindi

nodo

k-esimo

nodo salta or

a ,

, ,

tutto .

prodotto)

ho che

sostituendo il

di

differenza prima X annulla

Xka X-Xa

non

,

, (0

(r(x) Xo)

ESEmpio Xo 0

D

se =

X

: = = - =

...

(xn Xo)

- - .

. i

2

. che

Lk(x)

polinomio

il

Nel infatti abbiamo

vuole prodott

K-esimo nado 1 a

, ,

si

numeratore denominatore semplificano

quelli :

e a )

(1) (

xoxa L)

Lk(x) 2

+

= ... . . · =

-Xola) (xX1lXk Exn)

)

+

.... -

.

.

3 il

i interpolante

polinomio

che P(x)

effettivamente

precedenti dimostrano

due è

punti itk

gli LIXil

P(X) tutte

calcolato

perché nel nodo che

K-esimo avremo sono

can

, P(Xr)

l'unico si che

conclude

quindi

è

nulli 1

i

con I

r =

= ,

,

Esempio allora

Se X-X1 c

8

P(xz) 21(x1(y

b) +...

+ +

= .

I

DP(xz)

= yz

= i

4 A precedente questo esplicitamente del

coefficiente

differenza calcola

metodo

del ,

. non

polinomio an

do

, ..., complessità

richieda

(r(x)

5 il

Calcolare polinomio punto certa

in un una

n.

pari

computazionale a

Infatti x)

numeratore (operazione

il ripetuta punto fare

che possiamo

ogni

in

calcolare

, va

per

la operazione

seguente : =

(x "completo"

(X T(x) (x- (X-xi)

xi)

Xo) termini

xn) dei

prodotto

=

- -

. . . . (X-Xi)

= le andiamo

tutte differenze

di

produttoria

numeratore alla

= a

tagliere (x-Xn)

il fattore

complessità computazionale

Questa richiede

operazione una .

n

Invece dai

dai

denominatore) dipende

dipende nodi punti

calcolare che

il ,

X

ma

Xk non

per ,

bisognerà Servirà

nodo)

.

denominatore

calcolare volte

eseguire prodotti 1

n-1

un per n +

,

(quanti termini

i polinomia

del .

sono ?

Questa richiede complessità computazionale

operazione una n

CONFRONTO :

Se n'operazioni calcolare i denominatori

richiede

questo poi

,

metodo inizialmente per e

, numeratori il

calcolare i punto

operazioni in usufruiva

precedente

, che

ogni metado

per ;

n no sistema

il

Vandermonde operazioni

poi

matrice richiedeva risolvere

di operazioni

della n

per

, e

(aix)

eseguire tra

prodott coefficiente

i date

per e vista

Concludo di

il Lagrange computazionale

conviene

di

polinomio da punto

che , un .

,

Inoltre /basterà

aggiungo fatt

sfruttare

possiamo contr già aggiungere

nodo i

se un un

,

prodotto) possibile il .

precedente

che metodo

era

cosa con

non

,

Sei consecutivi

tra

.

6 allora

la

nodi distanza nodi

equispaziate è ,

h

, e :

si sicuramente

il la

Quindi denominatore

h è

caledo del

semplifica che

Xk Xk ,

=

- 1

- lunga

parte più

2h

Xx

Xr .

=

2

- - via

così

e

POLINOMIO NEWTON

DI

INTERPOLANTE

P(x) as(X (X

an(X 1)

Xd)(X Xo)(x Xd(x

a2(x x1) Xz)(X x2)

xo) +

(x xz)

+ Xn

+

+

au a

+

= -

- - -

-

-

, - -

- .... -

.... .

Questa Taylor

generalizzazione

considerare

si

formula può della di dove

formula

una ,

invece Coincidono

punte

i Xn-1

X2

Xo X1 .

=...:

=

=

Ricordiamo formula

la Taylori

di Xd

Pn(x) Pn(xd) X

Pin(xd)(x (d(x

xo) x(x

+

+ +.. +

= - - -

(non form