Alkalmazott matematika 2

Az interpoláció egy közelítő módszer, amely a függvény ismert értékei alapján ad közelítést a nem ismert értékeire.

A Lagrange-féle interpolációs polinom megadja azt a polinomot, amely $x_1$-ben $y_1$-et, $x_2$-ben $y_2$-t és így tovább $x_n$-ben $y_n$ értéket vesz föl.

A Newton interpoláció első lépése, hogy elkészítjűk az úgynevezett Newton-együtthatókat. Ezt követően ezek segítségével állítjuk elő a polinomot.

A Hermite interpoláció abban különbözőik a Lagrange és Newton féle interpolációktól, hogy az $x_1, x_2, \dots , x_n$ helyeken nem csak az eredeti polinom-függvény értékeit, hanem a deriváltjait is nézzük.

Az interpoláció egy közelítő módszer, amely a függvény ismert értékei alapján ad közelítést a nem ismert értékeire. Ennek hibájának a megbecsléséhez van egy remek képlet.

Egy gráf feszítőfája a gráf minden csúcsát tartalmazó fa részgráf.

A minimális feszítőfa egy gráfban a legkisebb élsúlyú feszítőfa.

A Kruskal algoritmus segítségével minimális feszítőfát lehet megtalálni.

Gráfok egy adott pontjából való feltérképezésére alkalmas módszer a szélességi keresés (BFS = Breadth-first search).

A DFS algoritmus lényege, hogy elindulunk egy úton, és megyünk, amíg csak tudunk.

A BFS és DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk. Ezeket nevezzük BFS és DFS fának.

Egy gráf csúcsainak bejárására van egy nagyon speciális módszer, amit Hamilton körnek nevezünk, és az a lényege, hogy egy olyan körön haladunk végig a gráfban, amely a gráf összes pontját tartalmazza.

A Hamilton út egy olyan út, amely a gráf minden csúcsát tartalmazza.

A Dirac-tétel azt mondja ki, hogy ha egy $G$ egyszerű, $n \geq 3$ csúcsú gráfban minden csúcs foka legalább $\frac{n}{2}$, akkor a gráfban van Hamilton kör.

Az Ore-tétel egy feltétel Hamilton kör létezésére.

Egy mátrix LU felbontása azt jelenti, hogy a mátrixot felbontjuk egy alsó és egy felső háromszögmátrix szorzatára.

Egy nxn-es mátrixnak akkor létezik LU-felbontása, ha az első n-1 főminora nem nulla.

Hogyha egy olyan mátrix LU felbontására van szükségünk, amelynek valamelyik (nem utolsó) főminora 0, akkor megtehetjük azt, hogy egy premutációs mátrix segítségével felcseréljük a sorait.

Az LU-felbontás módszere nem négyzetes mátrixokra ugyanolyan, mint eddig, a Gauss elimináció segítségével történik.

Ez tulajdonképpen egy olyan LU-felbontás, ahol az U mátrix az L-nek a transzponáltja.

A QR-felbontás azt jelenti, hogy egy mátrixot egy ortogonális és egy felsőháromszögmátrix szorzatára bontjuk.

QR-felbontást kaphatunk akkor is, ha az $A$ mátrixot addig-addig szorozgatjuk Givens forgatások mátrixaival, amíg felső háromszögmátrixot nem kapunk.

Az $A$ mátrixból először készítünk egy felső háromszögmátrixot a Householder-tükrözések segítségével.

Legyen $X$ egy részhalmaza a gráfnak, ami tartalmazza $S$-t. Ekkor az $X$ és a többi csúcs alkotta részgráf (amik nincsenek benne az $X$-ben) közötti éleket vágásnak nevezzük.

Egy vágás kapacitása a vágásban szereplő élek kapacitásainak összege.

A Ford-Fulkerson algoritmus egy olyan algoritmus, amit a maximális folyam megkeresésére használunk.

Irányított gráfban egy él kapacitása az a nem negatív valós szám, amit hozzá rendelünk az élhez.

A $(G, S, T, c)$ egy hálózat.

A hálózatban folyamnak nevezünk egy olyan függvényt, amely az élekhez rendel hozzá pozitív valós számokat és amire teljesül, hogy az egy csúcsba befolyó mennyiség megegyezik a csúcsból kifolyóval.

A folyam értékén az S-ből kifolyó és S-be befolyó mennyiségek különbségét értjük.

A Ford-Fulkerson tétel azt mondja ki, hogy egy hálózatban a maximális folyam mindig megegyezik a minimális vágással.

Mindig létezik egy olyan út, ami csak azokon a pontokon halad át, ahol a tartalékidő nulla, és az út hossza megegyezik a teljes folyamat hosszával. Ezt az utat kritikus útnak nevezzük.