MEN.pdf

KrzysztofMoszyński

METODY NUMERYCZNE

DLA

INFORMATYKÓW

Rokakademicki2004/2005

Rozdział1

APROKSYMACJA.

Ogólnezagadnienieaproksymacjiwprzestrzeniliniowej

( X,

)-przestrzeńliniowaunormowana, P -podzbiórprzestrzeni X .

•

Dla x

∈

X poszukujemy elementu p

∈

P takiego, że

−

jest

wystarczającomałe : p aproksymuje x .

•

Dla x

∈

X poszukujemyelementu p

∈

P takiego,że

∀

∈

−

≤

−

;

pnazywasięwtedy elementem najlepszej aproksymacji x

∈

X przez

elementy podzbioruP.

Własności elementu aproksymującego (w szczególności elementu

najlepszej aproksymacji) zależą od X , P i

. Dla tego, jeślimó-

wimy o aproksymacji, to musimy być świadomi tego

•

skądbierzemyelementaproksymowany ( x ),

•

gdzieszukamyelementuaproksymującego( p ),

•

wjakisposób mierzymyjakość aproksymacji(

Istnienieelementunajlepszejaproksymacji

Twierdzenie1.1

•

( X,

) -przestrzeńliniowaunormowana,

•

⊂

X -podprzestrzeńskończonego wymiaru.

Wtedy, dla każdego x

∈

X istnieje element p

∈

P, najlepszej aproksymacji

dlax.

Dowód

1. Jeśli x

∈

P ,tobierzemy p = x .

2. Jeśli x

∈

P ,to ρ ( x,P )=inf q∈P

−

= r> 0, gdyż P jest skoń-

czonegowymiaru.Niech Q = P

,gdzie

> 0jestustalonąliczbą.Wtedy Q jestzbiorem zwartym (dlaczego?).

Połóżmy f ( q )=

∩{

∈

−

≤

r +

}

Q ;funkcja f jestciągłaijestokreślona

nazbiorzezwartym Q ,awięcna Q osiągaswójkresdolny.Toznaczy,

żeistnieje p

−

dla q

∈

= f ( p )=inf q∈Q f ( q ).To

oznacza,że p jestelementemnajlepszejaproksymacjidla x .

∈

Q spełniającewarunek

−

W sytuacji, o której mówi Twierdzenie 1.1, element najlepszej

aproksymacji dla x

∈

X może być jedyny lub nie, w zależności

odwłasnościnormy

Przykład

Niech X = R 2 =

{

( ξ 1 ,ξ 2 )

ξ 1 ,ξ 2 ∈

}

; P =

{

( ξ 1 ,ξ 2 )

ξ 2 =0

}

, x =

(0 , 1).

= ( ξ 2 1 + ξ 2 2 )

dla y =( ξ 1 ,ξ 2 ), to jedynym elementemnajlepszejaproksymacjidla x

będzie p =(1 , 0).

1. Jeśliwprzestrzeni X przyjmiemynormę euklidesową ,

2. Jeślizaśnormęokreślimytak:

,tozbioremwszyst-

kich elementów najlepszej aproksymacji dla x w P będzie odcinek

otwarty((

=max

ξ 1 |

ξ 2 |}

−

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

3. Jeśli(naprzykładprzydeﬁnicjinormyzpunktu1.),jakozbiór P przyj-

miemy

to okaże się, że w P nie ma elementu najlepszej aproksymacji

dla x .(Dlaczego?).

P =

{

( ξ 1 ,ξ 2 )

ξ 2 < 1

}

Obiektami, które najczęściejmusimy aproksymować są funkcje . Chodzi

namzwykleoto,abyśmymoglizastąpićfunkcję

bardzo skomplikowaną

lub

taką,októrejwiemyzbytmało

przezinnąfunkcję,zktórąłatwopotraﬁmysobieradzić.Takimistosunkowo

łatwymifunkcjamisą,naprzykład, wielomiany. Ichwartościpotraﬁmyłatwo

obliczać(patrz-ćwiczenia: schematHornera ).

Najczęściej będą nas interesować funkcje ciągłe określone na pewnym

ustalonym zbiorze zwartym Ω

R d , mające wartości rzeczywiste. (Gdy

d =1, najczęściejbędzieΩ=[ a,b ].)Niechwięcnaszym zbiorem X będzie

zbiórwszystkichfunkcjiciągłychokreślonychna Ω.W X łatwookreślimy,w

sposóbnaturalny,operację+-dodawaniaelementów,orazoperacjęmnożenia

ichprzezliczby.Wtensposóbwzbiorze X zbudujemystrukturę przestrzeni

liniowej .Mamyjuż przestrzeńliniowąX .JeśliΩjestzbioremonieskończonej

mocy,towymiar(algebraiczny) X jest nieskończony .

Wnaszej przestrzeniliniowej X możemyteraz określić normę na różne

sposoby. Nasza przestrzeń X stanie się w ten sposób przestrzenią liniową

unormowaną .

Najczęściejw X używasię normy”sup” ;dla f

∈

∞, Ω =sup

t∈ Ω |

f ( t )

Jeśli nie będzie wątpliwości co do zbioru Ω, będziemy pisać krócej

∞ .

Zbieżnośćwsensienormy

· ∞, Ω ,to zbieżnośćjednostajnaw Ω.Innąnormą,

zktórąbędziemymiećdoczynieniato normaL 2 (Ω)

2 =(

| 2 d Ω) 2 .

Ω |

f ( t )

Aproksymacjawsensiekażdejztychnormmainnewłasności.

INTERPOLACJALAGRANGE’A

Niech X będzieprzestrzeniąliniowąwszystkichfunkcjiciągłych,określonych

na skończonym przedzialedomkniętym[ a,b ]

R ;niech P będzie zbiorem

wszystkichwielomianówjednejzminnejrzeczywistej.Szczególnymrodzajem

aproksymacji elementówprzestrzeni X przez elementy jej podprzestrzeniP

jest interpolacjawsensieLagrange’a

⊂

(1.1)Zadanieinterpolacjiwielomianowej,globalnejwsensie

Lagrange’a

Wprzedziale [ a,b ] danyjestukładn +1 różnychpunktówzwanych węzłami :

≤

x 0 <x 1 <x 2 <

···

<x n ≤

Dlaf

∈

X poszukuemywielomianuP n ∈

P,stopnia

≤

n,otejwłasności,że

f ( x j )= P n ( x j ) dlaj =0 , 1 , 2 ,

···

,n.

WielomianP n spełniającypowyższewarunkito wielonianinterpolacyjny

Lagrange’adla funkcji f,iwęzłów x 0 ,x 1 ,

···

,x n .

Tensposób aproksymacjipozwala prybliżać przypomocywielomianu P n

stopnia

n dowolnąfunkcję(nawetniekoniecznieciągłą!),określonąjedy-

niewzadanychwęzłach.Funkcję f ,którejwartościznamyjedyniewwęzłach

wymienionychwsformułowaniuzadania(1 . 1),(mogątobyćnaprzykładwiel-

kościotrzymanezpomiaróweksperymentalnych),zastępujemywielomianem

P n .

≤

WielomianinterpolacyjnyLagrange’a niejestnaogółelementemnaj-

lepszejaproksymacji! .

Twierdzenie1.2

ZadanieinterpolacjiLagrange’a(1.1)majednoznacznerozwiązanie

Dowód

1.Istnienie .Podamykonstrukcjęrozwiązania,używająctakzwanych wielo-

mianówbazowychLagrange’a ,związanychzwęzłami x 0 ,x 1 ,

···

,x n .Każdemu

węzłowiprzyporządkowanyjestwielomianstopnia n :

(1 . 2) l j ( x )= ( x

−

x 0 )( x

−

x 1 )

···

( x

−

x j− 1 )( x

−

x j +1 )

···

( x

−

x n )

x n ) ,

( x j −

x 0 )( x j −

x 1 )

···

( x j −

x j− 1 )( x j −

x j +1 )

···

( x j −

dla j =0 , 1 ,

···

,n .Zauważmy,że

l j ( x k )= δ jk dla j,k =0 , 1 ,

···

,n,

oraz że każda z funkcji l j jest wielomianem stopnia n .Stądnatychmiast

wynika,że

(1 . 3)

P n ( x )=

f ( x j ) l j ( x ) ,

j =0

jestwielomianemstopnia

≤

n ,orazże

P n ( x k )=

δ jk f ( x j )= f ( x k ) ,

j =0

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: