Dukuria e Runge

Në fushën e analizës numerike, dukuria e Runge ( German: [ˈʁʊŋə] ) është një problem i lëkundjes në skajet e një intervali që ndodh kur përdoret interpolimi polinomial me polinome të shkallëve të larta mbi një grup pikash interpolimi të baraslarguara. Ajo u zbulua nga Carl David Tolmé Runge (1901) kur hetoi sjelljen e gabimeve kur përdorej interpolim polinomial për të përafruar funksione të caktuara. Zbulimi ishte i rëndësishëm sepse tregon se shkuarja në shkallë më të larta nuk përmirëson gjithmonë saktësinë. Fenomeni është i ngjashëm me fenomenin Gibbs në përafrimet e serive Fourier.

Funksioni Runge (me të kuqe, maja më e lartë qendrore); polinomi interpolues i rendit të 5-të me pika interpoluese të barabarta (blu, maja qendrore më e ulët); dhe polinomi interpolues i rendit të 9-të me pika interpoluese të barabarta (e gjelbër, maja qendrore mesatare). Lëkundjet në kufijtë e intervalit rriten me rritjen e rendit polinomial.

Paraqitja

Teorema e përafrimit të Weierstrassit thotë se për çdo funksion të vazhdueshëm $f(x)$ të përcaktuar në një segment $[a,b]$, ekziston një grup funksionesh polinomiale $P_{n}(x)$ për n =0, 1, 2, …, secili prej shkallës të shumtën n, që i përafrohet $f(x)$ me konvergjencë uniforme mbi [ a, b ] kur n tenton për në pafundësi, d.m.th.

$\lim _{n\rightarrow \infty }\left(\sup _{a\leq x\leq b}\left|f(x)-P_{n}(x)\right|\right)=0.$

Konsideroni rastin kur interpolohet përmes n +1 pikave të barabarta të një funksioni f ( x ) duke përdorur polinomin n -shkallë P _n ( x ) që kalon nëpër ato pika. Natyrisht, mund të pritet nga teorema e Weierstrass se përdorimi i më shumë pikave do të çonte në një rindërtim më të saktë të f ( x ). Megjithatë, ky grup i veçantë i funksioneve polinomiale P _n ( x ) nuk është i garantuar të ketë vetinë e konvergjencës uniforme; teorema thotë vetëm se ekziston një grup funksionesh polinomiale, pa ofruar një metodë të përgjithshme për të gjetur një të tillë .

$P_{n}(x)$ e prodhuar në këtë mënyrë në fakt mund të largohet nga $f(x)$ndërsa n rritet; kjo zakonisht ndodh në një model oscilues që zmadhohet pranë skajeve të pikave të interpolimit. Zbulimi i kësaj dukurie ndodhi nga Runge.

Problem

Marrim në shqyrtim funksionin Runge

$f(x)={\frac {1}{1+25x^{2}}}\,$

(një version i shkallëzuar i Shtrigës së Agnesit ). Runge zbuloi se nëse ky funksion interpolohet në pikat e baraslarguara x_i ndërmjet − 1 dhe 1 në mënyrë të tillë që:

$x_{i}={\frac {2i}{n}}-1,\quad i\in \left\{0,1,\dots ,n\right\}$

me një polinom $P_{n}(x)$ të shkallës ≤ n, interpolimi që rezulton lëkundet drejt fundit të intervalit, pra afër − 1 dhe 1. Madje mund të vërtetohet se gabimi i interpolimit rritet (pa kufi) kur rritet shkalla e polinomit:

$\lim _{n\rightarrow \infty }\left(\sup _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\right)=\infty .$

Kjo tregon se interpolimi polinomial i shkallës së lartë në pika të baraslarguara mund të jetë i mundimshëm.

Arsyeja

Fenomeni i Runge është pasojë e dy vetive të këtij problemi.

• Magnituda e derivateve të rendit n të këtij funksioni të veçantë rritet shpejt kur rritet n .
• Baraslargësia ndërmjet pikave çon në një konstante Lebegu që rritet shpejt kur rritet n .

Dukuria është grafikisht e dukshme sepse të dyja vetitë kombinohen për të rritur magnitudën e lëkundjeve.

Gabimi ndërmjet funksionit gjenerues dhe polinomit interpolues të rendit n jepet nga

$f(x)-P_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i})$

Metoda zbutëse

Ndryshimi i pikave të interpolimit

Lëkundjet mund të minimizohen duke përdorur nyjet që shpërndahen më dendur drejt skajeve të intervalit, konkretisht, me dendësi asimptotike (në segmentin [ -1, 1 ] ) të dhënë nga formula $1/{\sqrt {1-x^{2}}}$ . Një shembull standard i një grupi të tillë nyjesh janë nyjet e Çebishevit, për të cilat gabimi maksimal në përafrimin e funksionit Runge garantohet të zvogëlohet me rritjen e rendit polinom.

Përdorimi i polinomeve pjesë-pjesë

Problemi mund të shmanget duke përdorur kurba spline të cilat janë polinome pjesë-pjesë. Kur përpiqet të zvogëlohet gabimi i interpolimit, mund të rritet numri i pjesëve polinomale që përdoren për të ndërtuar spline në vend të rritjes së shkallës së polinomeve të përdorura.

Nxënia e katrorëve më të vegjël

Një metodë tjetër është nxënia e një polinomi të shkallës më të ulët duke përdorur metodën e katrorëve më të vegjël. Në përgjithësi, kur përdoren $m$ pika të baraslarguara, nëse $N<2{\sqrt {m}}$ atëherë përafrimi i katrorëve më të vegjël $P_{N}(x)$ është i mirëkushtëzuar.

polinomi i Bernshtajnit

Duke përdorur polinomet e Bernshtajnit, mund të përafrohet në mënyrë të njëtrajtshme çdo funksion i vazhdueshëm në një interval të mbyllur, megjithëse kjo metodë është mjaft e kushtueshme nga ana llogaritëse.