C08-Aproximarea functiilor_1.pdf

37
Cursul 8 Aproximarea funcțiilor

Transcript of C08-Aproximarea functiilor_1.pdf

  • Cursul 8

    Aproximarea funciilor

  • Aproximarea functiilor

    Fie o funcie real f:[a,b]R, cunoscut numai ntr-un numr limitat de puncte numite noduri, (ansamblul acestora constituind suportul interpolrii): x1,x2,,xn prin valorile y1=f(x1), y2=f(x2),, yn=f(xn).

    O multime F de functii reale este

    interpolatoarea de ordin n daca pentru orice

    sistem de n puncte distincte x1,x2,,xn din

    X si oricare ar fi numerele reale y1,y2,,yn

    exista in F o singura functie care in punctele xi ia valorile yi.

  • Interpolare

    Problema de interpolare: Dandu-se multimea

    interpolatoare F de de ordin n in X si perechile

    (xi,yi) XxR cu proprietatea ca ij xixj sa

    se determine aceea functie jF care in

    punctele xi ia valorile yi.

    Se aproximeaza comportarea funciei n afara

    acestor puncte printr-un polinom generalizat de

    interpolare, de forma:

    Pn(x)=a1u1(x)+a2u2(x)++anun(x)

    n care funciile liniar independente

    u1(x),u2(x),,un(x)

    sunt cunoscute i constituie baza interpolrii.

  • Interpolare

    Aceasta poate fi format din funcii simple:

    polinoame, funcii trigonometrice,

    exponeniale, etc.

    Determinarea polinomului generalizat de interpolare (a coeficienilor ai) se face,

    impunnd ca pe suportul interpolrii

    polinomul de interpolare s coincid cu funcia f.

    Pn(xi)=f(xi), i=1:n

    numite condiii de interpolare.

  • Interpolare

    Condiiile de interpolare conduc la sistemul

    de ecuaii liniare

    scris matriceal

    U.a=f

    n:1i,xfxua in

    1k

    ikk

  • Interpolare

    S-au folosit notatiile

    cu uij=uj(xi), fi=f(xi)

    n

    2

    1

    n

    2

    1

    nn2n1n

    n22221

    n11211

    f

    f

    f

    f

    a

    a

    a

    a

    uuu

    uuu

    uuu

    U

  • Interpolare

    Polinomul de interpolare este

    cu

    Introducand conditiile de interpolare se obtine

    xlxlxl

    UxuxuxuUxuxl

    n21

    1

    n21

    1TT

    fxlfUxuaxuxuaxP T1TTn

    1k

    kkn

    k

    n

    1k

    kn xfxlxP

    .1xl

    ,ki,0xl

    kk

    ik

  • Interpolarea polinomiala

    Pentru baza polinomial

    u1(x)=1, u2(x)=x,,u(x)=xn-1

    Funciile lk(x) sunt polinoame de grad n-1, cu rdcinile xi, i=1:n, ik:

    Deci polinoamele lk(x) pot fi scrise

    n1k1k1kk xxxxxxxxCxl

    nk1kk1kk1k

    kxxxxxxxx

    1C

    n

    ki,1i ik

    i

    kxx

    xxxl

  • Interpolare

    Polinomul de interpolare poart n acest caz numele de polinom de interpolare Lagrange i are

    forma

    Sistemul determinat de condiiile de interpolare

    este

    n

    ki,1i ik

    i

    n

    1k

    knxx

    xxxfxP

    n

    1k

    i

    k

    ik n:1i,xfxa

  • Interpolare

    Acesta are determinant Vandermonde, care este nenul dac punctele xi sunt distincte, caz n care sistemul este compatibil determinat, cu soluie unic, ceea ce implic un polinom de interpolare unic.

    n

    2

    1

    n

    2

    1

    1n

    n

    2

    nn

    1n

    2

    2

    22

    1n

    1

    2

    11

    y

    y

    y

    a

    a

    a

    xxx1

    xxx1

    xxx1

  • Interpolare

    Alte forme ale polinomului de interpolare Lagrange

    kk

    kx

    x

    xx

    1xl

    n

    1i

    ixxx

    n

    ki,1i

    ikk

    n

    1k

    n

    ki,1i

    i xxxxxx

    n

    ki,1i

    ik

    n

    1i

    i

    k

    n

    ki,1i ik

    i

    k

    xx

    xx

    xx

    1

    xx

    xxxl

    n

    1k kk

    kn

    1k

    kkxxx

    xfxxlxfxP

  • Interpolare

    Se observ c multiplicatorii Lagrange reprezint raportul produselor pe coloane ale celor dou matrice:

    1xaxa

    xa1xa

    xaxa1

    V

    nn

    22

    11

    1xxxx

    xx1xx

    xxxx1

    U

    n2n1

    2n21

    1n12

    Uprod/VprodlllL n21

  • Interpolare

    Valoarea polinomului Lagrange ntr-un punct de

    abscis a

    U=diag(x)*ones(n)-ones(n)*diag(x)+eye(n)

    y*Uprod/Vprodylbn

    1i

    ii

    n

    n21

    n21

    n21

    nnn

    222

    111

    I

    xxx

    xxx

    xxx

    xxx

    xxx

    xxx

    U

    n

    n

    2

    1

    n

    2

    1

    I

    x00

    0x0

    00x

    111

    111

    111

    111

    111

    111

    x00

    0x0

    00x

    U

  • Interpolare

    V=(a-diag(x))*~eye(n)+eye(n)

    n

    nn

    22

    11

    I

    0xx

    x0x

    xx0

    0aa

    a0a

    aa0

    V

    n

    n

    2

    1

    I

    011

    101

    110

    x00

    0x0

    00x

    011

    101

    110

    *aV

  • Interpolare

    function b = Lagrange(a, x, y)

    % valoare polinom Lagrange in a

    n = length(x);

    V=(a-diag(x))*~eye(n)+eye(n);

    U=diag(x)*ones(n)-ones(n)*diag(x)+eye(n);

    b=prod(V)./prod(U)*y;

    function a = coefLagr(x, y)

    % Intrri:

    % x = tabloul absciselor celor n puncte

    % y = tabloul ordonatelor celor n puncte

    % Ieiri:

    % a = coeficienti polinom Lagrange

  • Interpolare

    a=zeros(n,1);

    z=zeros(n,1);

    % calcul coeficieni c din (x-x(1))...(x-x(n))

    c=poly(x);

    for i = 1 : n

    % calcul coeficieni b ai mpririi

    % polinomului prin x-x(i)

    [b,r]=deconv(c,[1 -x(i)]);

    % calcul p=(x(i)-x(1))...(x(i)-x(i-1))(x(i)-x(i+1))(x(i)-x(n))

    z=x(i)-x;

    z(i)=1;

    p=prod(z);

    a(1:n)=a(1:n)+y(i)*b(1:n)/p;

    end

  • Interpolarea Lagrange-Exemplu

    Sa se calculeze polinomul de interpolare Lagrange corespunzator datelor:

  • Interpolarea Lagrange-Exemplu

    Solutie:

    4 3 2 4 3 2

    4 3 2 2

    1 1 2 2 1 2( ) 6 2

    2 1 2 2 1 2 2 1 2 1 1 1 1 2

    2 1 1 1 12 2 2 4 4

    2 2 2 1 2 2 1 4 3

    12 2

    12

    x x x x x x x xP x

    x x x xx x x x x x x x

    x x x x x x

  • Interpolare

    Polinomul de interpolare de grad poate fi calculat

    prin recuren, folosind polinoame de interpolare de

    grad mai mic.

    Dac se noteaz ={i1,i2,,ip} i

    P - polinomul de interpolare ce trece prin punctele

    (xi1,yi1),(xi2,yi2),,(xip,yip)

    atunci polinomul de interpolare definit pe ansamblul

    extins de puncte +j+k= {j,k}

    jk

    jkkj

    kjxx

    xPxxxPxxxP

  • Interpolare

    Metoda Neville are forma:

    n care s-a notat Qij=Pi-j,,i polinomul de

    interpolare prin punctele (xi-j,yi-j),,(xi,yi) Se pornete cu polinoamele de interpolare de grad 0, reprezentate prin y1,y2,,yn, formndu-se polinoamele de interpolare de grad 1, 2, ..., .a.m.d.

    conform tabloului x1 y1 = Q11 Q12 Q13 Q1n

    x2 y2 = Q21 Q22 Q23 Q2,n-1

    x3 y3 = Q31 Q32 Q3,n-2

    xn yn = Qn1

    , 1 1, 1i j i j i i j

    ij

    i i j

    x x Q x x x Q xQ x

    x x

  • Interpolare

    b = Neville (x, y, a)

    % Intrri:

    % a = abscisa n care se calculeaz polinomul

    % x = tabloul absciselor celor n+1 puncte

    % y = tabloul ordonatelor celor n+1 puncte

    % Ieiri:

    % b = valoare polinom de interpolare

    n = length(x);

    q = y

    for i = 1 : n

    for j = 1 : n

    q(j)=((a-x(j+i))*q(j)-(a-x(j))*

    q(j+i))/(x(j)-x(j+i));

    end

    end

    b = q(n);

  • Metoda Neville-exemplu

    Sa se calculeze polinomul de interpolare Lagrange (folosind metoda Neville de recuren) corespunzator datelor:

  • Interpolarea Lagrange-Exemplu

    (folosind metoda Neville de recuren)

    Solutie:

    2 1,0 1 2,01,1

    1 2

    1 6 2 24 2

    2 1

    x x Q x x Q x xQ x

    x x

    3 2,0 2 3,02,1

    2 3

    0 2 1 02

    1 0

    x x Q x x Q x xQ x

    x x

  • Interpolarea Lagrange-Exemplu

    (folosind metoda Neville de recuren)

    Solutie:

    4 3,0 3 4,03,1

    3 4

    1 0 0 00

    0 1

    x x Q x x Q x xQ

    x x

    5 4,0 4 5,04,1

    4 5

    2 0 1 22 2

    1 2

    x x Q x x Q x xQ x

    x x

    3 1,1 1 2,1 21,2

    1 3

    0 4 2 2 2

    2 0

    x x Q x x Q x x x xQ x x

    x x

    4 2,1 2 3,1 22,2

    2 4

    1 2 1 0

    1 1

    x x Q x x Q x x xQ x x

    x x

  • Interpolarea Lagrange-Exemplu

    (folosind metoda Neville de recuren)

    Solutie:

    5 3,1 3 4,1 23,2

    3 5

    2 0 0 2 2

    0 2

    x x Q x x Q x x xQ x x

    x x

    2 24 1,2 1 2,2 21,3

    1 4

    1 2

    2 1

    x x x x x xx x Q x x QQ x x

    x x

    2 25 2,2 2 3,2 22,3

    2 5

    2 1

    1 2

    x x x x x xx x Q x x QQ x x

    x x

    2 25 1,3 1 2,3 21,4

    1 5

    2 2

    2 2

    x x x x x xx x Q x x QQ x x

    x x

  • Diferene divizate

    111 xfxF

    21

    2111

    212xx

    xFxFx,xF

    p1

    p21p1p11p

    p1pxx

    x,,xFx,,xFx,,xF

    Diferentele divizate ale unei functii f n raport cu xi pot fi introduse prin recuren cu relaiile:

  • Diferene divizate

    p

    1k

    p

    1i

    ik

    k

    p

    1k k

    k

    p1p

    xx

    xf

    x

    xfx,,xF

    ,xfxx

    xfxflimx,xFlimx,xF 1

    10

    10

    xx101

    xx111

    1010

    i

    1p

    p

    ii1p xfx,,xF

    Ele se pot calcula cu relatia:

    Se introduce diferenta divizat de argument repetat:

    pe baza creia se deduce:

  • Diferene divizate

    function a = DifDiv(x, y)

    % Intrri:

    % x = abscisele celor n puncte

    % y = ordonatele celor n puncte

    % Ieiri:

    % y =diferene divizate de ordin

    1:n

    n = length(x);

    for k = 1 : n-1

    y(k+1:n)=(y(k+1:n)-y(k))./

    (x(k+1:n)-x(k));

    end

  • Identitatea lui Newton

    0010 xfxfx,xFxx

    1010110210 x,xFx,xFx,x,xFxxxx

    21021022103210 x,x,xFx,x,xFx,x,x,xFxxxxxx

    n10n1n0n

    n01nn1n0

    x,x,xFx,,x,xF

    x,,x,xFxxxxxx

    Pornind de la relatia de recurenta a diferentelor divizate se va stabili o alta forma a polinomului de interpolare Lagrange care pune in evidenta expresia erorii.

  • Identitatea lui Newton

    n01nn0n0n1n0

    21021010100

    x,,x,xFxxxxx,,xFxxxx

    x,x,xFxxxxx,xFxxxfxf

    xRxPxf nn

    Prin adunarea lor se ajunge la:

    relatie denumita Identitatea lui Newton.

    Aceasta relatie contine atat polinomul de interpolare Lagrange cat si restul interpolarii:

  • Identitatea lui Newton

    are n+1 rdcini

    are n rdcini are o rdcin

    Prin derivarea de n ori a polinomului de interpolare se obtine:

    n01nn0n x,,x,xFxxxxxR

    xRxPxf nn

    xPxf n xPxf nnn

    n10n

    n

    n x,,x,xF!nxP

  • Identitatea lui Newton

    De unde:

    n101nn0n x,,x,x,xFxxxxxR

    0x,,x,xF!nxf n10nn

    !n

    fx,,x,xF

    )n(

    n10n n0 x,x

    !n

    fx,,x,xF

    )n(

    n10n

    !1n

    fMxxxxxR 1nn0n

    ffM 1n1n

  • Identitatea lui Newton

    Dac funcia f este nedefinit derivabil fC atunci

    Mn+1(f) crete foarte repede, deci majorarea este

    grosier. function b = Newton(a, x, y)

    % Intrri:

    % a = abscisa n care se calculeaz polinomul

    % x = tabloul absciselor celor n puncte

    % y = tabloul ordonatelor celor n puncte

    % Ieire:

    % valoarea polinomului de interpolare n a

    n = length(x);

    a = DifDiv(x, y);

    b = a(n);

    for i = n-1:-1:1

    b = (a - x(i-1)).*b + a(i);

    end

  • Diferente divizate-exemplu

    Sa se calculeze polinomul de interpolare Lagrange folosind identitatea lui Newton cu diferente divizate corespunzatoare datelor:

  • Interpolarea Lagrange-Exemplu

    (folosind identitatea lui Newton cu diferente divizate)

    Solutie:

    1 1 1 22 1 2

    1 2

    ( ) ( ) 6 2( , ) 4

    2 1

    F x F xF x x

    x x

    1 2 1 32 2 3

    2 3

    ( ) ( ) 2 0( , ) 2

    1 0

    F x F xF x x

    x x

  • Interpolarea Lagrange-Exemplu (folosind identitatea lui Newton cu diferente

    divizate) Solutie:

    1 3 1 3

    2 3 4

    3 4

    ( ) ( ) 0 0( , ) 0

    0 1

    F x F xF x x

    x x

    1 4 1 52 4 5

    4 5

    ( ) ( ) 0 2( , ) 2

    1 2

    F x F xF x x

    x x

    2 1 2 2 2 33 1 2 3

    1 3

    ( , ) ( , ) 4 2( , , ) 1

    2 0

    F x x F x xF x x x

    x x

    2 2 3 2 3 43 2 3 4

    2 4

    ( , ) ( , ) 2 0( , , ) 1

    1 1

    F x x F x xF x x x

    x x

  • Interpolarea Lagrange-Exemplu (folosind identitatea lui Newton cu diferente

    divizate) Solutie:

    2 3 4 2 4 5

    3 3 4 5

    3 5

    ( , ) ( , ) 0 2( , , ) 1

    0 2

    F x x F x xF x x x

    x x

    3 1 2 3 3 2 3 44 1 2 3 4

    1 4

    ( , , ) ( , , ) 1 1( , , , ) 0

    2 1

    F x x x F x x xF x x x x

    x x

    3 2 3 4 3 3 4 54 2 3 4 5

    2 5

    ( , , ) ( , , ) 1 1( , , , ) 0

    1 2

    F x x x F x x xF x x x x

    x x

    2 2

    ( ) ( 2) 2 ( 4) 2 ( 1) 1

    6 4 8 3 2

    F x f x x x

    x x x x x