Një shembull i thjeshtë i interpolimit të vijës kubike në C. Teoria e gërshetimit shembuj zgjidhjesh

Kthesa dhe sipërfaqet e gjetura në probleme praktike, shpesh kanë mjaft formë komplekse, e cila nuk lejon një detyrë analitike universale në tërësi duke përdorur funksionet elementare. Prandaj, ato janë mbledhur nga fragmente relativisht të thjeshta të lëmuara - segmente (lakore) ose prerje (sipërfaqe), secila prej të cilave mund të përshkruhet në mënyrë mjaft të kënaqshme duke përdorur funksionet elementare të një ose dy ndryshoreve. Në këtë rast, është krejt e natyrshme të kërkohet që funksionet e lëmuara që përdoren për të ndërtuar kthesa ose sipërfaqe të pjesshme duhet të jenë të një natyre të ngjashme, për shembull, ato duhet të jenë polinome në të njëjtën shkallë. Dhe në mënyrë që kurba ose sipërfaqja që rezulton të jetë mjaft e lëmuar, duhet të jeni veçanërisht të kujdesshëm ku bashkohen fragmentet përkatëse. Shkalla e polinomeve zgjidhet nga konsiderata të thjeshta gjeometrike dhe, si rregull, është e vogël. Për të ndryshuar pa probleme tangjenten përgjatë gjithë kurbës së përbërë, mjafton të përshkruani kthesat e bashkuara duke përdorur polinomet e shkallës së tretë, polinomet kubike. Koeficientët e polinomeve të tillë mund të zgjidhen gjithmonë në mënyrë që kurbatura e lakores së përbërë përkatëse të jetë e vazhdueshme. Vizat kubike, të cilat lindin gjatë zgjidhjes së problemeve njëdimensionale, mund të përshtaten në ndërtimin e fragmenteve të sipërfaqeve të përbëra. Dhe këtu vijat bikubike shfaqen mjaft natyrshëm, të përshkruara duke përdorur polinome të shkallës së tretë në secilën prej dy variablave. Puna me splina të tilla kërkon një sasi shumë më të madhe llogaritjesh. Por e drejtë proces i organizuar do të na lejojë të marrim parasysh mundësitë në rritje të vazhdueshme teknologji kompjuterike V shkallë maksimale. Funksionet spline Lëreni në segment, që është, Vërejtje. Indeksi (t) i numrave a^ tregon këtë. se bashkësia e koeficientëve që përcakton funksionin 5(x) në çdo segment të pjesshëm D është i ndryshëm. Në secilin prej segmenteve D1, spline 5(x) është një polinom i shkallës p dhe përcaktohet në këtë segment nga koeficienti p + 1. Segmente totale të pjesshme - atëherë. Kjo do të thotë që për të përcaktuar plotësisht spline-in, është e nevojshme të gjejmë (p + 1)pastaj numrat) do të thotë vazhdimësia e funksionit 5(x) dhe derivateve të tij në të gjitha nyjet e brendshme të rrjetit w. Numri i nyjeve të tilla është m - 1. Kështu, për të gjetur koeficientët e të gjithë polinomeve, fitohen p(m - 1) kushtet (ekuacionet). Për përcaktim i plotë mungon spline (kushtet (ekuacionet). Zgjedhja e kushteve shtesë përcaktohet nga natyra e problemit në shqyrtim dhe ndonjëherë thjesht nga dëshira e përdoruesit. TEORIA SPLINE shembuj të zgjidhjeve Problemet e interpolimit dhe zbutjes më së shpeshti konsiderohen kur është e nevojshme për të ndërtuar një ose një tjetër splin nga një grup i caktuar pikash në problemet e interpolimit në rrafshin B, kërkojnë që grafiku i vijës të kalojë nëpër pika, gjë që imponon m + 1 kushte (ekuacione) shtesë në koeficientët e tij, kushtet e mbetura p - 1 (ekuacionet). për ndërtimin e paqartë të vijës, më së shpeshti përcaktohen në formën e vlerave të derivateve më të ulëta të vijës në skajet e segmentit në shqyrtim [a, 6] - kushtet kufitare (kufitare). Kushtet e ndryshme kufitare ju lejojnë të ndërtoni spina me një sërë veçorish Në problemet e zbutjes, splineja është ndërtuar në mënyrë që grafiku i tij të kalojë pranë pikave (i" "Y"), * = 0, 1,..., t. dhe jo nëpërmjet tyre, masa e kësaj afërsie mund të përcaktohet në mënyra të ndryshme, gjë që çon në një larmi të konsiderueshme të zbutjes. Opsionet e përshkruara për zgjedhjen kur ndërtohen funksionet spline nuk shterojnë të gjithë diversitetin e tyre. Dhe nëse fillimisht u morën parasysh vetëm funksionet e splinave polinomiale pjesë-pjesë, atëherë me zgjerimin e fushës së zbatimit të tyre, filluan të shfaqen splinat, "të ngjitura së bashku" nga funksionet e tjera elementare. Splinjat kub të interpolimit Paraqitja e problemit të interpolimit Le të jepet një rrjet w në segmentin [a, 6). Ndërtoni një funksion të qetë në segmentin (a, 6] që merr o në nyjet e rrjetit vendos vlerat , domethënë Shënim. Problemi i formuluar i interpolimit është rindërtimi funksion të qetë , dhënë në një tabelë (Fig. 2). Është e qartë se një problem i tillë ka shumë zgjidhje të ndryshme kushte shtesë, mund të arrihet paqartësia e nevojshme. Në aplikacione, shpesh ka nevojë për të përafruar një funksion të dhënë në mënyrë analitike duke përdorur një funksion me mjaftueshëm të përshkruar veti të mira. Për shembull, në rastet kur llogaritja e vlerave të një funksioni të caktuar /(x) në pikat e segmentit [a, 6] shoqërohet me vështirësi të konsiderueshme dhe/ose funksioni i dhënë /(x) nuk ka butësinë e kërkuar. , është i përshtatshëm për të përdorur një funksion tjetër që përafrohet mjaft mirë do të kishte një funksion të caktuar dhe do të ishte i lirë nga disavantazhet e tij të theksuara. Problemi i interpolimit të funksionit. Ndërtoni në intervalin [a, 6] një funksion të qetë a(x), që përkon në nyjet e rrjetit w me funksioni i dhënë/(X). Përkufizimi i një spline kub interpolues Një splin kub ndërpolues S(x) në një rrjetë w është një funksion që 1) në secilin segment është një polinom i shkallës së tretë, 2) është dy herë i diferencueshëm vazhdimisht në segmentin [a, b ], domethënë i përket klasës C2[a, 6] dhe 3) plotëson kushtet Në secilin prej segmenteve, splineja S(x) është një polinom i shkallës së tretë dhe përcaktohet në këtë segment me katër koeficientë. . Numri i përgjithshëm i segmenteve është m Kjo do të thotë se për të përcaktuar plotësisht vijën, është e nevojshme të gjenden 4 m numra. (x) në të gjitha nyjet e brendshme të rrjetit w. Numri i nyjeve të tilla është m - 1. Kështu, për të gjetur koeficientët e të gjithë polinomeve, fitohen edhe 3(m - 1) kushte (ekuacione). Së bashku me kushtet (2), fitohen kushtet (ekuacionet). Kushtet kufitare (kufitare) Dy kushte që mungojnë janë specifikuar në formën e kufizimeve në vlerat e vijës dhe/ose derivateve të saj në skajet e intervalit [a, 6]. Kur ndërtohet një vijë kub interpoluese, më shpesh përdoren katër llojet e mëposhtme të kushteve kufitare. A. Kushtet kufitare të tipit 1. - në skajet e intervalit [a, b] përcaktohen vlerat e derivatit të parë të funksionit të dëshiruar. B. Kushtet kufitare të tipit 2. - në skajet e intervalit (a, 6) përcaktohen vlerat e derivatit të dytë të funksionit të dëshiruar. B. Kushtet kufitare të tipit 3. quhen periodike. Është e natyrshme të kërkohet plotësimi i këtyre kushteve në rastet kur funksioni i interpoluar është periodik me periudhën T = b-a. D. Kushtet kufitare të tipit 4. kërkojnë komente të veçanta. Komentoni. Në nyjet e brendshme sepsi, derivati ​​i tretë i funksionit S(x), në përgjithësi, është i ndërprerë. Sidoqoftë, numri i ndërprerjeve të derivatit të tretë mund të reduktohet duke përdorur kushte të tipit të 4-të. Në këtë rast, splineja e ndërtuar do të jetë vazhdimisht e diferencueshme tre herë në intervale Ndërtimi i një spline kub interpolues Le të përshkruajmë një metodë për llogaritjen e koeficientëve të një spline kub, në të cilën numri i sasive që do të përcaktohen është i barabartë. Në secilin nga intervalet, funksioni spline i interpolimit kërkohet në formën e mëposhtme. Këtu TEORIA SPLINE shembuj të zgjidhjeve dhe numrave janë zgjidhja e një sistemi linear, forma e së cilës varet nga lloji i kushteve kufitare. Për kushtet kufitare të tipeve 1 dhe 2, ky sistem ka formën e mëposhtme ku Koeficientët varen nga zgjedhja e kushteve kufitare. Kushtet kufitare të tipit 1: Kushtet kufitare të tipit të dytë: Në rastin e kushteve kufitare të tipit të tretë, sistemi për përcaktimin e numrave shkruhet si më poshtë: Numri i të panjohurave në sistemi i funditështë e barabartë me mn, pasi nga kushtet e periodicitetit rrjedh se po = nm. Për kushtet kufitare të tipit 4, sistemi për përcaktimin e numrave ka formën ku Bazuar në zgjidhjen e gjetur të sistemit, numrat po dhe n mund të përcaktohen duke përdorur formula. Matricat e të trijave lineare sistemet algjebrike janë matrica dominuese diagonalisht. Matricat Tamiya nuk janë njëjës, dhe për këtë arsye secili prej këtyre sistemeve ka e vetmja zgjidhje. Teorema. Ekziston dhe është unik një vijë kubike interpoluese që plotëson kushtet (2) dhe një kusht kufitar i një prej katër llojeve të listuara më sipër. Kështu, të ndërtosh një spline kubike interpoluese do të thotë të gjesh koeficientët e saj Kur gjenden koeficientët e vijës, vlera e spline S(x). pikë arbitrare segmenti [a, b] mund të gjendet në formulën (3). Sidoqoftë, për llogaritjet praktike është më i përshtatshëm algoritmi i ardhshëm duke gjetur vlerën 5(g). Le të x 6 [x", Fillimisht, vlerat e A dhe B llogariten duke përdorur formulat dhe më pas gjendet vlera 5(x): Përdorimi i këtij algoritmi redukton ndjeshëm kostot llogaritëse të përcaktimit të vlerës. Këshilla për përdoruesi Zgjedhja e kushteve kufitare (të skajit) dhe nyjeve të interpolimit lejon në një masë të caktuar kontrollojnë vetitë e splinave të interpolimit. kur interpolojnë funksionet. Bëhet veçanërisht i rëndësishëm në rastin kur është e nevojshme të sigurohet saktësi e lartë e përafrimit të funksionit f(x) me spine 5(g) pranë skajeve të segmentit [a, 6). Vlerat kufitare kanë një efekt të dukshëm në sjelljen e vijës 5(g) pranë pikave a dhe b, dhe ky ndikim dobësohet shpejt ndërsa largohet prej tyre. Zgjedhja e kushteve kufitare shpesh përcaktohet nga disponueshmëria e informacionit shtesë në lidhje me sjelljen e funksionit të përafërt f(x). Nëse vlerat e derivatit të parë f"(x) janë të njohura në skajet e segmentit (a, 6), atëherë është e natyrshme të përdoren kushtet kufitare të tipit 1. Nëse vlerat e derivatit të dytë f"(x) njihen në skajet e segmentit [a, 6], atëherë janë kushtet kufitare të përdorimit natyror të tipit 2. Nëse ka një zgjedhje midis kushteve kufitare të llojeve 1 dhe 2, atëherë përparësi duhet t'i jepet kushteve të tipit 1. Nëse f(x) - funksion periodik, atëherë duhet të ndalemi në kushtet kufitare të tipit të 3-të. Nëse nuk ka informacion shtesë për sjelljen e funksionit të përafërt, shpesh përdoren të ashtuquajturat kushte kufitare natyrore, megjithatë, duhet të kihet parasysh se me një zgjedhje të tillë të kushteve kufitare, saktësia e përafrimit të funksionit f(. x) nga vija S(x) pranë skajeve të segmentit (a, ft] zvogëlohet ndjeshëm. Ndonjëherë përdoren kushte kufitare të tipit 1 ose 2, por jo me vlerat e sakta derivatet përkatëse, dhe me përafrimin e diferencës së tyre. Saktësia e kësaj qasjeje është e ulët. Përvoja praktike e llogaritjeve tregon se në situatën në shqyrtim, më e përshtatshme është zgjedhja e kushteve kufitare të tipit të 4-të. B. Përzgjedhja e nyjeve të interpolimit. Nëse derivati ​​i tretë f""(x) i funksionit ka një ndërprerje në disa pika të segmentit [a, b], atëherë për të përmirësuar cilësinë e përafrimit, këto pika duhet të përfshihen në numrin e nyjeve të interpolimit. Nëse derivati ​​i dytë /"(x) është i ndërprerë, atëherë për të shmangur lëkundjen e splinës pranë pikave të ndërprerjes, është e nevojshme të merren masa të veçanta. Në mënyrë tipike, nyjet e interpolimit zgjidhen në mënyrë që pikat e ndërprerjes së derivatit të dytë të bien. brenda intervalit \xif), e tillë që vlera a mund të zgjidhet përmes një eksperimenti numerik (shpesh mjafton të vendoset a = 0.01 Ka një grup recetash për tejkalimin e vështirësive që lindin kur derivati ​​i parë f". (x) është i ndërprerë. Si një nga më të thjeshtat, ne mund të sugjerojmë këtë: ndani segmentin e përafrimit në intervale ku derivati ​​është i vazhdueshëm dhe ndërtoni një spline në secilin prej këtyre intervaleve. Zgjedhja e një funksioni interpolimi (pro dhe kundër) Qasja 1. Polinom i interpolimit të Lagranzhit Për një varg të caktuar TEORIA SPLINE shembuj zgjidhjesh (Fig. 3) polinomi i interpolimit Lagranzhi përcaktohet nga formula. Këshillohet që të merren parasysh vetitë e polinomit të interpolimit të Lagranzhit nga dy pozicione të kundërta, duke diskutuar avantazhet kryesore veçmas nga disavantazhet. Përparësitë kryesore të qasjes së parë: 1) grafiku i polinomit të interpolimit të Lagranzhit kalon në secilën pikë të grupit, 2) funksioni i ndërtuar përshkruhet lehtësisht (numri i koeficientëve të polinomit të interpolimit të Lagranzhit në rrjet që do të përcaktohet është e barabartë me m + 1), 3) funksioni i ndërtuar ka derivate të vazhdueshëm të çdo rendi, 4) polinomi i interpolimit përcaktohet në mënyrë unike nga vargu i dhënë. Disavantazhet kryesore të qasjes së parë: 1) shkalla e polinomit të interpolimit të Lagranzhit varet nga numri i nyjeve të rrjetit, dhe sa më i madh ky numër, aq më e lartë është shkalla e polinomit të interpolimit dhe, për rrjedhojë, aq më shumë llogaritje kërkohen, 2 ) ndryshimi i të paktën një pike në grup kërkon një rillogaritje të plotë të koeficientëve të polinomit të interpolimit të Lagranzhit, 3) shtimi në grup rrit shkallën e polinomit të interpolimit të Lagranzhit me një dhe gjithashtu çon në një rillogaritje të plotë të koeficientëve të tij, 4) me rafinim të pakufizuar të rrjetës, shkalla e polinomit të interpolimit të Lagranzhit rritet pafundësisht. Sjellja e polinomit të interpolimit të Lagranzhit me rafinim të pakufizuar të rrjetës në përgjithësi kërkon vëmendje të veçantë. Komente A. Mbi përafrimin e një funksioni të vazhdueshëm me një polinom. Dihet (Weierstrass, 1885) se çdo funksion i vazhdueshëm (dhe aq më tepër i qetë) në një interval mund të përafrohet dhe të dëshirohet në këtë interval nga një polinom. Le ta përshkruajmë këtë fakt në gjuhën e formulave. Le të jetë f(x) një funksion i vazhdueshëm në intervalin [a, 6]. Atëherë për çdo e > 0 ekziston një polinom Є(x) i tillë që për çdo x nga intervali [a, 6] pabarazia do të plotësohet (Fig. 4) Vini re se polinomet madje të së njëjtës shkallë që përafrojnë funksionin f(x) me saktësinë e specifikuar , ka pafundësisht shumë. Le të ndërtojmë një rrjet w në segmentin [a, 6]. Është e qartë se nyjet e saj, në përgjithësi, nuk përkojnë me pikat e kryqëzimit të grafikëve të polinomit Pn(x) dhe funksionit f(x) (Fig. 5). Prandaj, për rrjetën e dhënë, polinomi Pn(x) nuk është interpolim. pikë e re në grup kërkon llogaritjen e katër koeficientëve. Vetitë e një spline kubike të interpolimit A. Vetitë e përafrimit të një spline kubike. Vetitë e përafrimit të vijës së interpolimit varen nga butësia e funksionit f(x) - sa më e lartë të jetë butësia e funksionit të interpoluar, aq më i lartë është rendi i përafrimit dhe, kur rafinohet rrjeta, aq më e lartë është shpejtësia e konvergjencës. Nëse funksioni i interpoluar f(x) është i vazhdueshëm në interval Nëse funksioni i interpoluar f(x) ka një derivat të parë të vazhdueshëm në intervalin [a, 6], d.m.th. pikë shtesë, duke plotësuar kushtet kufitare të tipit 1 ose 3, atëherë për h O kemi Në këtë rast, jo vetëm spline konvergjon në funksionin e interpoluar, por edhe derivati ​​i spline konvergon në derivatin e këtij funksioni. Nëse splineja S(x) i përafrohet funksionit f(x) në segmentin [a, b], dhe derivatet e tij të parë dhe të dytë i përafrojnë funksionet B, respektivisht. Viza kubike e ndërthurur ka një tjetër pronë e dobishme . Merrni parasysh shembullin e mëposhtëm. Problemi i zbutjes i formuluar është restaurimi funksioni i qetë i specifikuar në një tabelë. Është e qartë se një problem i tillë ka shumë zgjidhje të ndryshme. Duke i vendosur kushte shtesë funksionit të ndërtuar, mund të arrihet paqartësia e nevojshme. Përkufizimi i një spline kub zbutës Një splin kub zbutës S(x) në një rrjet w është një funksion që 1) në secilin prej segmenteve është një polinom i shkallës së tretë, 2) është dy herë i diferencueshëm vazhdimisht në segmentin [a, 6 ], domethënë i përket klasës C2 [a , b], 3) siguron një minimum për funksionalin ku - numrat e dhënë, 4) plotëson kushtet kufitare të njërit prej tre llojeve të treguara më poshtë. Kushtet kufitare (kufi) Kushtet kufitare përcaktohen në formën e kufizimeve në vlerat e vijës dhe derivateve të saj në nyjet kufitare të rrjetit w. A. Kushtet kufitare të tipit 1. - në skajet e intervalit [a, b) specifikohen vlerat e derivatit të parë të funksionit të dëshiruar. Kushtet kufitare të tipit 2. - derivatet e dyta të funksionit të dëshiruar në skajet e intervalit (a, b] janë të barabarta me zero. B. Kushtet kufitare të tipit të 3-të quhen periodike. Teorema. Viza kubike S(x), duke minimizuar funksionin (4) dhe plotësimi i kushteve kufitare të njërit prej tre llojeve të mësipërme, përkufizohet në mënyrë unike. Vërejtje, ky segment me katër koeficientë është m derivatet në të gjitha nyjet e brendshme të rrjetit o". Kështu, për të llogaritur koeficientët e të gjithë polinomeve, fitojmë 3(m - 1) kushte (ekuacione). funksioni kërkohet në formën e mëposhtme. Këtu, dhe numrat dhe janë zgjidhja e një sistemi ekuacionesh algjebrike lineare, forma e të cilit varet nga lloji i kushteve kufitare. Le të përshkruajmë fillimisht se si gjenden vlerat n*. Për kushtet kufitare të tipeve 1 dhe 2, sistemi ekuacionet lineare për të përcaktuar vlerat Hi shkruhet në formën e mëposhtme ku). Koeficientët varen nga zgjedhja e kushteve kufitare. Kushtet kufitare të tipit 1: Kushtet kufitare të tipit të dytë: Në rastin e kushteve kufitare të tipit të tretë, sistemi për përcaktimin e numrave shkruhet si më poshtë: dhe të gjithë koeficientët llogariten sipas formulave (5) (vlerat me indekset k dhe m + k konsiderohen të barabarta : Shënim i rëndësishëm*: Matricat e sistemeve nuk janë të degjeneruara dhe për këtë arsye secili prej këtyre sistemeve ka një zgjidhje unike Nëse gjenden numrat n, - atëherë madhësitë përcaktohen me lehtësi formulat ku Në rastin e kushteve kufitare periodike, zgjedhja e koeficientëve është zgjedhja e koeficientëve të peshimit p, -, të përfshira në funksional (4), ju mund të kontrolloni vetitë e vijave zbutëse në një masë të caktuar pika (x^, Vk), atëherë faktori i peshimit p\ që korrespondon me të duhet të vendoset i barabartë me zero, në llogaritjet praktike, gjëja më e rëndësishme është zgjedhja e vlerave pi - Le të jetë D, gabimi në matje. vlera y. Atëherë është e natyrshme të kërkohet që vija zbutëse të plotësojë kushtin ose, e cila është e njëjtë Në rastin më të thjeshtë, koeficientët e peshimit pi mund të specifikohen, për shembull, në formën - ku c është një konstante mjaft e vogël. Sidoqoftë, kjo zgjedhje e peshave p nuk lejon përdorimin e një "korridori" për shkak të gabimeve në vlerat y, -. Një algoritëm më racional, por edhe më intensiv i punës për përcaktimin e vlerave p mund të duket kështu. Nëse vlerat gjenden në përsëritjen e fc-të, atëherë supozohet se ku e është një numër i vogël që zgjidhet eksperimentalisht duke marrë parasysh rrjetin e biteve të kompjuterit, vlerat e D dhe saktësinë e zgjidhja e sistemit të ekuacioneve algjebrike lineare. Nëse në përsëritjen fc-të në pikën i, kushti (6) është shkelur, atëherë formula e fundit do të sigurojë një ulje të koeficientit përkatës të peshës p,. Nëse atëherë në përsëritjen tjetër një rritje në p çon në më shumë "korridori" (6) dhe, në fund të fundit, një spine që ndryshon më mirë. Pak teori A. Arsyetimi i formulave për llogaritjen e koeficientëve të një spline kub interpolimi. Le të prezantojmë shënimin ku m, janë madhësi aktualisht të panjohura. Numri i tyre është i barabartë me m + 1. Një vijë e shkruar në formën ku plotëson kushtet e interpolimit dhe është e vazhdueshme në të gjithë intervalin [a, b\: duke e vendosur në formulë, fitojmë, përkatësisht, ajo ka a derivati ​​i parë i vazhdueshëm në intervalin [a, 6]: Duke diferencuar relacionin (7) dhe duke e vendosur atë, marrim relacionin përkatës. në fakt. Le të tregojmë se numrat m mund të zgjidhen në mënyrë që funksioni spline (7) të ketë një derivat të dytë të vazhdueshëm në intervalin [a, 6]. Llogaritni derivatin e dytë të spline në intervalin: Në pikën x, - 0 (në t = 1) kemi Le të llogarisim derivatin e dytë të spline në intervalin Në pikën që kemi Nga kushti i vazhdimësisë së derivati ​​i dytë në nyjet e brendshme të rrjetit a; marrim relacion m - 1 ku duke u shtuar këtyre ekuacioneve m - 1 edhe dy të tjera, që rrjedhin nga kushtet kufitare, fitojmë një sistem m + 1 ekuacionesh algjebrike lineare me m + I të panjohur miy i = 0, 1... , m. Sistemi i ekuacioneve për llogaritjen e vlerave të rsh në rastin e kushteve kufitare të tipit 1 dhe 2 ka formën ku (kushtet kufitare të tipit 1), (kushtet kufitare të tipit të dytë). Për kushtet kufitare periodike (kushtet kufitare të tipit 3), rrjeta o; zgjerohet me një nyje më shumë dhe supozojmë Pastaj sistemi për përcaktimin e vlerave të σ* do të ketë kontinuitetin e formës në nyjet e rrjetit të dytë dhe (të - !)-të. Kemi Nga dy relacionet e fundit marrim dy ekuacionet që mungojnë që i përgjigjen kushteve kufitare të tipit të 4-të: Eliminimi i goo-së së panjohur nga ekuacionet, dhe pc-ja e panjohur nga ekuacionet, si rezultat fitojmë një sistem ekuacionesh. Vini re se numri i të panjohurave në këtë sistem është th - I. 6. Arsyetimi i formulave për llogaritjen e efikasitetit të një spline subichess zbutëse. Le të prezantojmë shënimin ku Zi dhe nj janë aktualisht sasi të panjohura. Numri i tyre është 2m + 2. Funksioni spline, i shkruar në formë, është i vazhdueshëm gjatë gjithë intervalit (a, 6]: duke vënë në këtë formulë, marrim përkatësisht. Le të tregojmë se numrat z, dhe n, mund të të zgjidhet në mënyrë që splinei, i shkruar në formën ( 8), të ketë një derivat të parë të vazhdueshëm në intervalin [a, 6] Le të llogarisim derivatin e parë të spline S(x) në intervalin: Në pikën x ^ - 0 (në t = 1) kemi Le të llogarisim derivatin e parë të splinës 5(x) në intervalin: Në pikën që kemi Nga kushti i vazhdimësisë së derivatit të parë të vijës në nyjet e brendshme të rrjetë dhe --> marrim relacionin m - 1 Është i përshtatshëm për të shkruar këtë relacion përdorim të plotë Shënimi i mëposhtëm është përdorur këtu. Përveç kësaj, një spline në intervalin [a, 6) ka një derivat të dytë të vazhdueshëm: duke diferencuar relacionin (8) dhe duke e vendosur atë, fitojmë, përkatësisht, relacionin e matricës gjendja minimale e funksionalit (4). Kemi Dy barazitë e fundit të matricës mund të konsiderohen si një sistem linear prej 2m + 2 ekuacione algjebrike lineare për 2m + 2 të panjohura. Duke zëvendësuar kolonën r në barazinë e parë me shprehjen e saj të marrë nga relacioni (9), arrijmë në ekuacionin e matricës SPLINE TEORIA shembuj të zgjidhjeve për përcaktimin e kolonës M. Ky ekuacion ka një zgjidhje unike për faktin se matrica A + 6HRH7 është gjithmonë jo të degjeneruar. Pasi e kemi gjetur atë, ne mund ta identifikojmë lehtësisht qytetin e Emsshine. Elementet e matricave threadmagolale A dhe H përcaktohen vetëm nga parametrat e rrjetit dhe (me hapat hi) dhe nuk varen nga vlerat e y^. Hapësira lineare e funksioneve të splinave kubike Kompleti i splinave kubike të ndërtuara në segmentin [a, 6) përgjatë nyjës rrjetë wcra+l është hapësirë ​​lineare dimensionet m + 3: 1) shuma e dy vijave kubike të ndërtuara në rrjetë u>, dhe produkti i një brezi kub të ndërtuar në rrjetë u>, nga numër arbitrar në mënyrë më të fshehtë, ato janë splina kubike të ndërtuara në këtë rrjetë, 2) çdo shpinë kubike e ndërtuar në rrjetë dhe nga një nyje përcaktohet plotësisht nga vlera m + 1 e vlerave y" në këto nyje dhe dy- vetëm + 3 parametra. Duke zgjedhur një bazë në këtë hapësirë ​​të përbërë nga m + 3 vija lineare të pavarura, ne mund të shkruajmë një vijë kub arbitrare a(x) si një kombinim linear i tyre në një mënyrë unike. Komentoni. Ky lloj caktimi i spline është i përhapur në praktikën informatike. Veçanërisht e përshtatshme është një bazë të dhënash e përbërë nga të ashtuquajturat vija kubike B (bazike ose themelore). Përdorimi i D-splines mund të zvogëlojë ndjeshëm kërkesat për kujtesën e kompjuterit. L-vijza. Një spline B me shkallë zero, e ndërtuar në vijën numerike përgjatë rrjetit w, quhet një funksion fork i shkallës k ^ I, i ndërtuar në vijën numerike në rrjetë u, përcaktohet me anë të rekurrentit. formula Grafikët e vijave B të shkallëve të para B, -1 "(g) dhe të dytë në\7\x) janë paraqitur në Fig. 11 dhe 12, përkatësisht. zero vetëm në një segment të caktuar (përcaktuar nga k + 2 nyje B, -3* (i) ishte i ndryshëm nga zeroja në segmentin z,-+2] rasti i një rrjete uniforme (me hapin A, në Fig. 13 është paraqitur një grafik tipik i një kubjejejeje). , domethënë i përket klasës C2[a, "), dhe b) është i ndryshëm nga zero vetëm në katër intervale të njëpasnjëshme (Le ta plotësojmë rrjetin w me nyje ndihmëse të marra plotësisht në mënyrë arbitrare. Me rrjetë të zgjeruar w*, mund të ndërtojmë një familje prej m + 3 kub vijash B: Kjo familje formon bazën në hapësirën e vijave kubike në segmentin (a, b]. Kështu, një vijë kub arbitrare S(z), e ndërtuar në segmentin |b, 6] rrjet o; Nyja izm+1, mund të paraqitet në këtë segment në formën e një kombinimi linear nga kushtet e problemit, koeficientët ft të këtij zgjerimi përcaktohen në mënyrë unike. ... Në rastin kur jepen vlerat y* të funksionit në nyjet e rrjetës dhe vlerat y o dhe V të derivatit të parë të funksionit në skajet e rrjetës (problemi i interpolimit me kufirin kushtet e llojit të parë), këta koeficientë llogariten nga sistemi i formës së mëposhtme Pas përjashtimit sasitë b-i dhe &m+i, marrim një sistem linear me të panjohura 5q, ..., bm dhe një matricë tredimensionale. Gjendja siguron dominimin diagonal dhe, për rrjedhojë, mundësinë e përdorimit të metodës së fshirjes për ta zgjidhur atë. 3 MMCHMY 1. Sistemet lineare Lloje të ngjashme lindin kur merren parasysh probleme të tjera të interpolimit. Zmmchnm* 2. Në krahasim me algoritmet e përshkruara në seksionin 1.1, përdorimi i R-spline në problemet e interpolimit * na lejon të zvogëlojmë* sasinë e informacionit të ruajtur, domethënë të reduktojmë ndjeshëm kërkesat për memorien e kompjuterit, megjithëse kjo çon për rritjen e numrit të operacioneve. Ndërtimi i kthesave spline duke përdorur funksionet spline Më sipër, ne kemi konsideruar vargje, pikat e të cilave janë numëruar në mënyrë që abshisat e tyre të formojnë një sekuencë rreptësisht në rritje. Për shembull, rasti i paraqitur në Fig. 14 kur pika të ndryshme grupi i abshisave identike nuk u lejua. Kjo rrethanë përcaktoi si zgjedhjen e klasës së kthesave të përafërta (funksionet e trafikut) ashtu edhe mënyrën e ndërtimit të tyre. Megjithatë, metoda e propozuar më sipër bën të mundur ndërtimin mjaft të suksesshëm të një kurbë interpolimi në më shumë rast i përgjithshëm, kur numërimi i pikave të grupit dhe vendndodhja e tyre në rrafsh, si rregull, nuk janë të lidhura (Fig. 15). Për më tepër, kur vendosim detyrën e ndërtimit të një kurbë interpolimi, mund ta konsiderojmë grupin e dhënë si jo planar, domethënë është e qartë se për të zgjidhur këtë problem të përgjithshëm është e nevojshme të zgjerohet ndjeshëm klasa e kurbave të pranueshme, duke përfshirë të mbyllura. kthesat, kthesat me pika të vetëkryqëzimit dhe kthesat hapësinore. Është e përshtatshme të përshkruhen kthesa të tilla duke përdorur ekuacione parametrike. përveç kësaj, në mënyrë që funksionet të kenë butësi të mjaftueshme, për shembull, ata i përkasin klasës C1 [a, /0] ose klasës Për të gjetur ekuacionet parametrike të një lakore që kalon në mënyrë sekuenciale nëpër të gjitha pikat e grupit, veproni si më poshtë. . hapi 1. Në një segment arbitrar .Df; ) set ( _points[_points.Length - 1].Df = value; ) ) public double Ddfn (get ( return _points[_points.Length - 1].Ddf; ) set ( _points[_points.Length - 1].Ddf = vlera; BuildSplines(x2); _pikë.Ddf = -y1 * (x2 - x1) / (y2 - y1. Gjatësia - 1].X ) private double BuildSplines(double ddf1) ( double df = _points.Df, ddf = ddf1; for (var i = 0; i< _splines.Length; i++) { _splines[i] = new CSplineSubinterval(_points[i], _points, df, ddf); df = _splines[i].Df(_points.X); ddf = _splines[i].Ddf(_points.X); if (i < _splines.Length - 1) { _points.Df = df; _points.Ddf = ddf; } } return df - Dfn; } }

Segmentet blu janë derivatet e parë të vijës në pikat e saj përkatëse. E shtova këtë element grafik për qartësi më të madhe.

Avantazhet dhe disavantazhet e algoritmit

Në mënyrë të padrejtë, mund të themi se kompleksiteti i algoritmit është O(N), pasi, siç thashë tashmë, pavarësisht nga numri i pikëve, mjaftojnë dy drejtime të llogaritjeve për të marrë vlerën e saktë derivati ​​i dytë në skajin e majtë të intervalit, dhe një tjetër për të ndërtuar spline.

Sidoqoftë, nëse dikush dëshiron të gërmojë në kod dhe të bëjë një analizë më të detajuar të këtij algoritmi, do të jem shumë i lumtur. Thjesht më shkruani për rezultatet, do të isha i interesuar.

Pra, çfarë nuk shkon me testet e IQ?

Le të shqyrtojmë së pari serinë "2, 4, 6, 8, ?"
Le ta imagjinojmë këtë seri numrash si një grup çiftesh vlerash:

Ku e marrim vetë numrin si cilësi, dhe numri serial këtë numër. Çfarë vlere duhet të ketë në vend?

Ideja që unë po përpiqem të çoj pa probleme është se ne mund të zëvendësojmë absolutisht çdo vlerë. Në fund të fundit, çfarë kontrollojnë në të vërtetë detyra të tilla? Aftësia e një personi për të gjetur një rregull të caktuar që lidh të gjithë numrat e disponueshëm, dhe sipas këtij rregulli, të nxjerrë numrin tjetër në sekuencë. Duke folur gjuha shkencore, detyra e ekstrapolimit është këtu (detyra e interpolimit është të gjejë një kurbë që kalon nëpër të gjitha pikat brenda një intervali të caktuar, dhe detyra e ekstrapolimit është të zgjasë këtë kurbë përtej intervalit, duke "parashikuar" sjelljen e kurbës në e ardhmja). Pra, ekstrapolimi nuk ka një zgjidhje të qartë. fare. kurrë. Nëse do të ishte ndryshe, njerëzit do të kishin parashikuar shumë kohë më parë parashikimin e motit për të gjithë historinë e njerëzimit përpara, dhe kërcimet në kursin e këmbimit të rublës nuk do të kishin qenë kurrë një surprizë.

Sigurisht, supozohet se ka ende një përgjigje të saktë për këtë problem dhe është e barabartë me 10, dhe atëherë "ligji" që lidh të gjithë këta numra është

Në prodhimin industrial, të tilla si ndërtimi i anijeve, prodhimi i automobilave dhe prodhimi i avionëve, forma përfundimtare në shkallë ose afër përcaktohet përmes procesit të përfundimit.

Automatizimi i këtij procesi ka qenë me interes të madh për grafikën kompjuterike. Forma e rruzullit matematikor ndjek konturën e vijës fizike (Fig. 5-4), d.m.th. një vizore fleksibël prej druri ose plastike që kalon nëpër pika të caktuara. Peshat e plumbit përdoren për të ndryshuar formën e shiritit. Duke ndryshuar numrin dhe vendndodhjen e tyre, ata përpiqen ta bëjnë kthesën që rezulton më e lëmuar, më e bukur dhe "të këndshme për syrin".

Nëse marrim një shirit fizik si një shirit të hollë fleksibël, forma e tij (devijim) përcaktohet nga ekuacioni i Euler (5-2) për momentin e përkuljes përgjatë shiritit:

ku është moduli i Young, i cili varet nga vetitë e materialit të raftit, është momenti i inercisë, i përcaktuar nga forma e kurbës dhe është rrezja e lakimit.

Për devijime të vogla rrezja është afërsisht e barabartë me

,

ku numri i thjeshtë tregon derivatin në lidhje me distancën përgjatë shkop, dhe është devijimi i shkop. Ekuacioni i Euler-it merr formën

Lërini peshat të veprojnë si mbështetëse të thjeshta, atëherë momenti i përkuljes midis tyre ndryshon në mënyrë lineare. Zëvendësimi në ekuacionin e Euler-it, marrim

dhe pas integrimit të dyfishtë

Kështu, forma e spline jepet nga një polinom kub.

Në përgjithësi, një spline matematikor është një polinom pjesë-pjesë i shkallës me një derivat të vazhdueshëm të shkallës në pikat lidhëse të segmenteve. Për shembull, një spline kub ka vazhdimësi të rendit të dytë në pikat e tij të lidhjes. Vijat pjesërisht nga polinomet e rendit të ulët janë shumë të përshtatshme për interpolimin e kthesave, pasi ato nuk kërkojnë kosto të mëdha llogaritëse dhe nuk shkaktojnë devijime numerike karakteristike të polinomeve rendit të lartë. Ngjashëm me vijat fizike, zakonisht përdoren një seri segmentesh kub, ku secili segment kalon nëpër dy pika. Një splin kub është gjithashtu i përshtatshëm sepse është një kurbë e rendit më të vogël, duke lejuar pikat e përkuljes dhe përkuljen në hapësirë.

Ekuacioni i një segmenti të vijës parametrike është:

, , (5-1)

ku dhe janë vlerat e parametrave në fillim dhe në fund të segmentit. - vektor në çdo pikë të segmentit. është një funksion me vlerë vektoriale, ku janë tre komponentët Koordinatat karteziane vektoriale.

Oriz. 5-5 Një segment i vijës kubike.

Çdo komponent ka një formë të ngjashme me , d.m.th.

, ,

, ,

, .

Koeficientët konstante llogariten në bazë të katër kushteve kufitare për segmentin spline. Le të shkruajmë ekuacionin (5-1) në formë

Le të jenë dhe vektorët e skajeve të segmentit (shih Fig. 5-5). Le të jenë gjithashtu dhe , derivatet në lidhje me , vektorë tangjentë në skajet e segmentit. Duke diferencuar ekuacionin (5-1), marrim

, . (5-3)

Le të shkruajmë rezultatin

, . (5-4)

Le të supozojmë, pa humbur përgjithësinë, se , dhe të zbatojmë kushtet kufitare

Marrim katër ekuacione për të panjohurat:

, (5-6b)

, (5-6c)

. (5-6 ditë)

Zgjidhjet për dhe kanë formën:

(5-7a)

. (5-7b)

Sasitë , , dhe specifikoni segmentin e vijës kubike. Natyrisht, forma e një segmenti varet nga pozicioni dhe vektorët tangjentë në skajet e segmentit. Më pas, vini re se rezultatet përmbajnë vlerën e parametrit në fund të segmentit. Meqenëse çdo vektor i pikës fundore dhe tangjences ka tre komponentë, ekuacioni parametrik kurba hapësinore kubike varet nga dymbëdhjetë komponentë vektoriale dhe vlera e parametrit në fund të segmentit.

Duke zëvendësuar ekuacionet (5-6) dhe (5-7) në (5-1), ne marrim ekuacionin për një segment të një spine kub:

. (5-8)

Ky është një ekuacion për një segment. Për të marrë të gjithë kurbën, duhet të lidhni shumë segmente. Në Fig. 5-6 tregojnë dy segmente ngjitur. Nëse dihen vektorët , , , vektorët tangjentë , , dhe vlerat e parametrave , , atëherë forma e secilit segment përcaktohet nga ekuacioni (5-8). Megjithatë, nuk ka gjasa që vektori tangjent në pikën e lidhjes të jetë i njohur. Për fat të mirë, mund të rrjedhë nga kushti i vazhdimësisë.

Kujtoni që një spline shkallë-pjesë ka vazhdimësi shkallë në pikat e saj të bashkimit; vazhdimësia e një spline kubike është dy. Për ta bërë këtë, derivati ​​i dytë ose lakimi i vijës duhet të jetë i vazhdueshëm. Duke diferencuar ekuacionin (5-1) dy herë, marrim

, . (5-9)

Oriz. 5-6 Dy segmente kubike të ndara pjesë-pjesë.

Për pjesën e parë të spline, parametri ndryshon brenda . Le të zëvendësojmë me ekuacionin (5-9):

.

Për seksionin e dytë të spline, parametri ndryshon në interval. Le të zëvendësojmë në ekuacionin (5-9) vlerën në fillim të seksionit të dytë

Duke barazuar rezultatet e marra dhe duke përdorur ekuacionet (5-6a,b) dhe (5-7a), marrim

.

Ana e majtë e këtij ekuacioni përfaqëson lakimin në fund të segmentit të parë, dhe ana e djathtë përfaqëson lakimin në fillim të segmentit të dytë. Shumëzoni me dhe gruponi termat:

Kjo përcakton , vektorin e panjohur tangjente në pikën e lidhjes. Vini re se ekuacioni përfundimtar përsëri përmban vlerat e parametrave në skajet e segmenteve dhe .

Formula që rezulton mund të përgjithësohet për pikat, dhe për segmentet e një spline kub, vazhdimësia e rendit të dytë mund të merret në pikat e lidhjes.

Oriz. 5-7 Emërtimet për grupin e segmenteve të vijës kub pjesë-pjesë.

Ekuacioni i përgjithësuar për çdo dy segmente të vijës ngjitur dhe në shënimin e Fig. 5-7 duket si kjo:

(5-11)

për segmentin e parë dhe

(5-12)

për të dytën, pasi për çdo segment parametri fillon të ndryshojë nga zero, për të parën dhe për të dytin - .

Barazimi i derivateve të dytë në pikat e bashkimit për çdo segment ngjitur, , jep rezultat i përgjithshëm, ekuivalente me ekuacionin (5-10),

nga i cili përcaktohet vektori tangjent në pikat e lidhjes së çdo dy segmenti dhe .

Përdorimi rekurziv i ekuacionit (5-13) për të gjitha segmentet e spline gjeneron ekuacione vektoriale tangjente, . Në formën e matricës:

(5-14)

Matrica është jo katrore, pasi ka vetëm ekuacione për vektorët dhe nuk mund të përmbyset për të marrë një zgjidhje për . Nëse supozojmë se vektorët tangjentë në skajet e lakores dhe janë të njohur, problemi zgjidhet. Tani matrica duket si

(5-15)

ku matrica është katrore dhe e kthyeshme. Vini re gjithashtu se është tridiagonal, gjë që redukton kostot llogaritëse të përmbysjes së saj. Më tej, matrica është diagonalisht dominuese. Nga kjo rezulton se ka vetëm një zgjidhje:

. (5-16)

Nëse e dimë , atëherë është e lehtë të përcaktohen koeficientët për çdo segment spline. Duke përgjithësuar ekuacionet (5-6)-(5-11), marrim

,

.

Që dhe është sasive vektoriale, atëherë janë edhe vektoriale; nëse kanë komponentë, atëherë i kanë edhe këta komponentë.

Në formën e matricës, ekuacioni i çdo segmenti spline është:

. (5-17)

Le të kërkohet për të specifikuar një spline kub që kalon nëpër pikat , me vektorë tangjente në skajet dhe . Nga ekuacioni (5-16) gjejmë vektorët tangjentë të brendshëm , . Pastaj, nga ekuacioni (5-17) me koordinatat e njohura të skajeve të çdo segmenti dhe vektorët tangjentë, , , për çdo segment përcaktohen. Përgjithësimi përfundimtar i ekuacionit (5-1)

, , , (5-18)

përdoret për të llogaritur një segment spline.

Në formën e matricës, ekuacioni (5-18) duket si ky:

, . (5-19)

Duke zëvendësuar ekuacionin (5-17) dhe duke riorganizuar termat, marrim

, , , (5-20)

, (5-21a)

, (5-21b)

, (5-21s)

, (5-21 ditë)

quhen funksione peshe.

Oriz. 5-8 Funksionet e peshimit të vijës kubike për

Duke përdorur këto përkufizime, ne shkruajmë ekuacionin (5-20) në formë matrice

ku është matrica e funksionit të peshës

përmban informacion gjeometrik. Siç do të shihet nga sa vijon, ekuacionet si (5-22), d.m.th. një matricë e funksionit peshues e shumëzuar me një matricë të kushteve gjeometrike përdoren shpesh për të përshkruar kthesat dhe sipërfaqet.

Nga ekuacioni (5-21) është e qartë se çdo funksion peshe është i rendit të tretë. Çdo pikë në një segment të vijës kub është një shumë e ponderuar pikat fundore dhe vektorët tangjentë. Koeficientët veprojnë si funksione peshuese. Në Fig. 5-8 tregohen për . Nga figura është e qartë se dhe , d.m.th. kurba kalon nëpër vektorin e pikës. Në mënyrë të ngjashme dhe, d.m.th. lakorja kalon edhe nëpër vektorin e pikës. Më pas, vërejmë simetrinë e dhe , dhe dhe . Në fakt . Së fundi, le t'i kushtojmë vëmendje renditjes relative të , , dhe . Dallimi domethënës në madhësi sugjeron që, në përgjithësi, pozicioni i pikave fundore ka një ndikim më të madh se vektorët tangjentë.

Kujtoni që një vijë kub pjesë-pjesë përcaktohet nga pikat, vektorët tangjentë dhe vlerat e parametrave, d.m.th., në skajet e të gjithë segmenteve. Zgjedhja ndikon në butësinë e kurbës.

Vazhdimësia e derivatit të dytë në pikat e lidhjes së brendshme nuk siguron në vetvete butësinë e kurbës në kuptimin e lakimit minimal përgjatë saj. Duke zgjedhur vlerat e duhura, është e mundur të minimizohen koeficientët për secilin segment dhe të arrihet lëmimi më i madh i kurbës. Zakonisht këto llogaritje shtesë nuk kërkohen. Për qëllime praktike, më shumë se metoda të thjeshta, si ato të diskutuara këtu.

Një metodë llogaritjeje është vendosja e vlerave të parametrave gjatësi të barabarta akorde midis pikave fqinje. Në të njëjtën kohë, cilësia e kurbës plotëson kërkesat e shumicës problemet e aplikuara. Një metodë tjetër është normalizimi i variacionit duke marrë e barabartë me një për çdo segment spline. Kjo zgjedhje thjeshton llogaritjet (shih seksionin 5-4). Siç mund të shihet nga ekuacionet e mësipërme, çdo zgjedhje rezulton në koeficientë të ndryshëm dhe kështu fitohen kurba të ndryshme që kalojnë nëpër pikat e dhëna.

Le të shohim një shembull.

Lëreni dhënë funksion të vazhdueshëm f(x). Le të prezantojmë një rrjet

dhe shënojnë f i=f(x i), i=0,1,N .

Spline që korrespondon me këtë funksion f(x) dhe nyjet e dhëna, thirret funksioni S(x), të kënaqshme kushtet e mëposhtme:

1. Në çdo segment , i=1,2,N , funksion S(x) është një polinom i shkallës së tretë;

2. Funksioni S(x), si dhe derivatet e tij të parë dhe të dytë
të vazhdueshme për ;

Kushti i fundit quhet gjendja e interpolimit, dhe spline i përcaktuar nga kushtet 1)-3) quhet gjithashtu spline kubike interpoluese.

Le të vërtetojmë ekzistencën dhe veçantinë e një spline të përcaktuar nga kushtet e mësipërme. Prova më poshtë përmban gjithashtu një metodë për ndërtimin e një spline.

Në intervalin midis një çifti nyjesh fqinje, funksioni i interpolimit është një polinom i shkallës së 3-të, i cili mund të shkruhet lehtësisht si:

Koeficientët e polinomit përcaktohen nga kushtet në nyje. Ai duhet të pranojë vlerat e tabelës:

(1)

Numri i ekuacioneve u dyfishua më pak numër koeficientë të panjohur, ndaj nevojiten kushte shtesë për mbyllje. Le të gjejmë derivatet e parë dhe të dytë të polinomit kub:

(2)

Le të kërkojmë vazhdimësinë e këtyre derivateve (d.m.th., butësinë e vizores fleksibël) në të gjitha pikat, duke përfshirë nyjet. Duke barazuar kufijtë e djathtë dhe të majtë të derivateve në nyjen e brendshme x i marrim:

3)

Dy kushtet që mungojnë zakonisht përftohen nga supozimi natyror që grafiku ka lakimin zero në skajet:

që korrespondon me skajet e ulura lirisht të vizores. Por nëse ka informacion shtesë për sjelljen asimptotike të funksionit, atëherë mund të shkruajmë kushte të tjera kufitare.

Ekuacionet (1-4) formojnë një sistem ekuacionesh lineare për përcaktimin e koeficientëve të panjohur 4N. Ky sistem mund të zgjidhet me metodën e eliminimit Gaussian, por është më fitimprurëse ta reduktoni atë në një formë të veçantë.

Ekuacioni (1) jep të gjithë koeficientët menjëherë dhe i. Nga ekuacionet (3) dhe (4)

(5)

Le të zëvendësojmë (5) në (1), duke eleminuar njëkohësisht Ai = fi -1 , marrim:

(6)

Duke përjashtuar tani nga (3) b unë dhe b i +1 nga (6) dhe d i sipas (5), marrim një sistem ekuacionesh për me une:

Matrica e këtij sistemi është 3-diagonale. Sisteme të tilla zgjidhen ekonomikisht me metodën e fshirjes.

Për shkak të dominimit diagonal, sistemi ka një zgjidhje unike.

Pas gjetjes me i janë përcaktuar a i, b i Dhe d i dhe përcaktohet lloji i polinomeve kubike (vija) në secilin segment.

Kështu, është vërtetuar se ekziston një vijë kubike unike e përcaktuar nga kushtet 1)-3) dhe kushtet kufitare

Vini re se mund të merren parasysh kushte të tjera kufitare.

Mund të merren parasysh më shumë detyrë e përbashkët interpolimi i një funksioni nga një spline - një polinom i shkallës së n-të

,

koeficientët e të cilit janë pjesë-pjesë konstante, dhe i cili në nyje merr vlera të dhëna dhe është i vazhdueshëm së bashku me derivatet e tij (n-1).

Në praktikë, më të zakonshmet janë 2 raste: një me n=3 ( polinomet kub) tashmë është marrë në konsideratë, e dyta për n-1 (polinomet e Njutonit të shkallës 1) korrespondon me përafrimin e grafikut të një vije të thyer të ndërtuar nga nyjet; përcaktimi i koeficientëve është i dukshëm.

LEKTURA Nr.14

INTEGRIMI NUMERIK

FORMULA E THJESHTA KUADRATURE

Formula e përgjithshme drejtkëndëshat

1. Formula kuadratike e drejtkëndëshave të majtë.

2. Formula drejtkëndëshe djathtas

3. Formula kuadratike për drejtkëndëshat e mesit

Llogaritja e gabimit të formulave të integrimit numerik.

Le h>0 mjaft pak x 0 =0.

Le ta zgjerojmë funksionin në një seri Taylor në lagje x 0 =0. :

Gabim lokal për një segment të vogël h -

, pra

Vetia e aditivitetit

- gabim në segment.

Formulat e kuadratit Newton-Cotes

Nëse një polinom n - gradë, atëherë

Këto janë formula kuadratike të llojit të interpolimit. Këtu Nga deri në – Koeficientët e Cotes

Formula pa dimensione.

Ky është një funksion që:

Kalon nëpër të gjitha pikat e dhëna
,
;

Në çdo segment midis pikave ngjitur ka një parabolë kub;

E vazhdueshme së bashku me derivatet e saj të parë dhe të dytë në të gjitha pikat.).

interpolimi
lokale			globale
lineare	parabolike	kub parabolë	polinom gradë ( N-1)	kub spline
Oriz. 1.5.

Është e qartë se me interpolim lokal, në kryqëzimet e pjesëve të polinomeve, fitohen ndërprerje në derivate, të cilat në një numër problemesh mund të jenë të padëshirueshme, për shembull, kur llogaritet shpejtësia nga koordinatat e pikave. Me interpolim global nga një polinom, gjithçka
derivatet e një shkalle polinomiale janë të vazhdueshme, por për shkak të përdorimit shkallë të lartë polinomet në
një funksion i vazhdueshëm mund të ketë shumë maksimum dhe minima, d.m.th. Në kurbë mund të shfaqen shenja të rëndësishme të jashtme që nuk janë në funksionin origjinal. Për shkak të këtyre dallimeve, polinomet e shkallës më të lartë se e pesta ose e gjashta nuk përdoren për interpolim. Vizat kubike përdoren aktualisht për interpolim global.

Gjatë interpolimit, vlerat e funksionit duhet të kenë një gabim të vogël, sepse kurbë e vazhdueshme
kryhet pikërisht përmes pikave të përcaktuara.

Nëse një funksion matet ose llogaritet afërsisht dhe gabimet janë të rëndësishme, atëherë nuk ka kuptim të kryhet interpolimi dhe të vazhdohet me përafrim. Në latinisht fjala ap-proximo do të thotë "pothuajse afër". Kur përafrohet, kurba tërhiqet pranë pikave të dhëna në përputhje me disa kritere të afërsisë, për shembull, kriteri katrorët më të vegjël ose kriteri minimal. Ndryshimet ndërmjet interpolimit dhe përafrimit janë ilustruar në Fig. 1.6.

Nëse kemi një të vazhdueshme ose funksion diskret, atëherë zakonisht përdoren 5 lloje të transformimeve të funksioneve:

E vazhdueshme në diskrete (kampionimi),

Diskrete në të vazhdueshme (interpolim),

Diskrete në të vazhdueshme (përafrim),

E vazhdueshme në të vazhdueshme (ndërhyrje),

Diskret në diskrete (zbutje).

Vini re se me zbutjen, e cila përdoret gjerësisht në përpunimin dixhital, nuk ndërtohet një funksion i vazhdueshëm dhe transformohen vetëm ordinatat e pikave.

Vizë kubike.
Schoenberg propozoi përdorimin e splinave kubike për interpolim në vitin 1949. Fjala "vijëz" vjen nga emri i pllakave të gjata të holla metalike, të cilat për një kohë të gjatë hartuesit gjermanë i lidhnin me gozhdë në një tabelë vizatimi në vend të modeleve për të vizatuar kthesa komplekse.

Vizë kubikeështë një funksion që:

Kalon nëpër të gjitha pikat e dhëna
,
;

Në çdo segment midis pikave ngjitur është një polinom kub;

E vazhdueshme së bashku me derivatet e saj të parë dhe të dytë në të gjitha pikat.

Vini re se, falë kushtit të tretë, parabolës kubike
përmes dy pikave kryhet pa mëdyshje.

Formula për një vijë kub është shkruar për një segment arbitrar me numrin , skaji i majtë i së cilës ka një abshisë . Në këtë segment për këdo
rezultati i interpolimit llogaritet duke përdorur një spline kub.

Për më tepër, midis pikave të dhëna kemi një segment, pra në këtë formulë
.

Nëse kalon në një segment tjetër, atëherë duhet të ndryshoni numrin e segmentit aktual dhe në të njëjtën kohë të gjithë koeficientët në formulë do të ndryshojnë. Bazuar në tre kushte, mund të tregohet se

, , ,

(2.2)

Për të kryer interpolimin, d.m.th. llogaritjet
për këdo, paraprakisht nga pikët e dhëna Të gjithë koeficientët spline duhet të llogariten, d.m.th. vargjeve , , secila prej të cilave ka një gjatësi në përputhje me numrin e segmenteve ndërmjet pikave.

Paraqitja e problemës: pikat e dhëna , . Përcaktoni të gjithë koeficientët e vijës , , , d.m.th. total
koeficientët,
, sepse segment

Konsideroni çdo dy segmente ngjitur
Dhe
me numra
Dhe . Pika është e përbashkët për ta, shih fig. 2.1.

Për segmentin e djathtë, vija kubike ka formën (2.1), dhe për të majtën, d.m.th. në

NË pikë e përbashkët
le të barazojmë vlerat majtas dhe djathtas
dhe derivatet
Dhe
sipas përkufizimit të një spline kub. Duke përdorur shënimin
për gjatësinë e segmentit të majtë, marrim tre ekuacione për pesë koeficientë të panjohur
,
,
, , .

Të tilla treshe ekuacionesh mund të shkruhen për të gjitha nyjet e brendshme,
, e cila jep
ekuacionet.

Këto dy ekuacione shtesë mund të jenë arbitrare, por përgjithësisht supozohet se funksioni
pranë skajeve të tij është lineare. Pastaj, nga ekuacioni i fundit dhe i parë (2.4) dhe ekuacioni (2.5) kemi:

Shpesh sistemi i ekuacioneve (2.8) shkruhet për derivatet e dyta në nyje, duke i treguar ato
. Pastaj ajo merr formën (Bakhvalov, Metodat numerike, M., 2002):