Dukuria e Runge

djathtas|parapamje| 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.
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.

## 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, &#x2026;, 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 &#x2212; 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 &#x2264;&nbsp;*n*, interpolimi që rezulton lëkundet drejt fundit të intervalit, pra afër &#x2212; 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  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.

## Referime