Numerikus módszerek fizikusoknak (BMETE92MF00/T0)

Kurzus típus: 
Elmélet
Nyelv: 
magyar
Félév: 
2017/18/1
Órarendi információ: 

Sz 12:15-14:00 (KF81)
Cs 12:15-14:00 (KF81)

 Hírek 

  • A megbeszéltek szerint a második röpzhra november 2-án (csütörtökön) az előadás első 20 percében kerül sor. A zh anyaga a konjugált gradiens módszertől a 8. hét előadásanyagáig tart (lásd a lenti táblázatot). (új!)
  • Az első évfolyamzh október 19-én csütörtökön, az előadás keretében lesz. A zh-n egy A4-es oldalnyi (!) saját kézzel írt emlékeztető, íróeszköz és számológép használható. A zh anyaga a QR-felbontásig tart, a túlhatározott egyenletrendszerek már nem fognak szerepelni. 
  • Matlab hírek 
  • HELLÓ MATLAB! – előadás a BME-n
  • BSc és MSc diplomatéma kiírások
  • Az Alkalmazott Analízis Szeminárium honlapja
  • Egyetemünkön mindenki számára elérhető a Matlab program. A telepítési útmutató ezen a belső linken érhető el.

 A hallgatók eredményei 

 Az előadások ill. gyakorlatok anyaga 

Az előadások és gyakorlatok beosztása:

Hét Előadás (SZ12, CS12) Gyakorlat (SZ14 ill. CS14)
1. hét, 09.04. 

Szerda: A félévi követelmények ismertetése. A tantárgy témájának ismertetése. Modellalkotás és annak szükségszerűsége. Példák. Normált terek. Banach-féle fixpont tétel. Vektor- és mátrixnormák. Csütörtök: Speciális mátrixok (sávmátrixok, szimmetrikus mátrixok, permutációs mátrixok, ortogonális mátrixok, diagonális dominancia, definitség, M-mátrixok). Sajátérték és sajátvektor. Gersgorin-tételek. Mátrixok hasonlósági transzformációi, tulajdonságai. Diagonalizálhatóság és feltételei.

  • Bevezetés: csak tájékoztató jelleggel szerepelt. Nem kérjük számon.
  • Normált terek: a definíciókat és a tételeket kell ismerni, de nem kell tudni bizonyítani semmit sem.
  • Lineáris operátorok: nem kell.
  • Vektor és mátrixnormák: minden kell, a 19. tétel ($p=2$ eset igazolása később szerepel a Normák és sajátérték részben) és a 20. tétel bizonyítása is. 
  • Euklideszi terek: egyelőre kimarad, később lesz majd.
  • Mátrixok speciális tulajdonságai: minden kell. 
  • Sajátértékek és sajátvektorok: minden állítást és definíciót ismerni kell, de csak a Gersgorin-tételt kell bizonyítani.
  • Diagonalizálhatóság: minden állíltást és definíciót ismerni kell, de nem kell tudni igazolni semmit.
Vektor- és mátrixnormák kiszámítása. Feladatok a normákkal kapcsolatban. Az 1-es mátrixnorma képletének igazolása. 
2. hét, 09.11.

Szerda: A 2-es mátrixnorma képletének igazolása. Spetrálsugár becslése normával. Az $A^k$ sorozat, ill. $\sum A^k$ sor konvergenciája. Alsó és felső becslés az $\|(E-A)^{-1}\|$ normára. Elégséges feltétel arra, hogy egy mátrix M-mátrix legyen (gyakorlaton). Korrekt kitűzésű feladatok, kondicionáltság és kondíciószám. Gépi számábrázolás. A dupla pontosságú (64 bites) lebegőpontos számrendszer. Csütörtök:  A gépi számábrázolás folytatása. Mátrixok kondíciószáma, lineáris egyenletrendszerek (LER) érzékenysége az együtthatókra. A Gauss-módszer.

  • Normák és sajátérték: Az 50. tétel bizonyításán kívül minden kell. Az 53. tétel bizonyítását lásd gyakorlaton. Ebben a részben szerepel a 2-es mátrixnorma képletének igazolása is (19. tétel). 
  • Lehetséges hibaforrások: nem kell.
  • Korrekt kitűzésű feladatok: a definíciót kell ismerni.
  • Kondicionáltság, kondíciószám: minden kell.
  • Gépi számábrázolás és következményei: minden kell, különös tekintettel a dupla pontosságú lebegőpontos számrendszer konstrukciójára, ill. a kiegyszerűsödés jelenségére. 
  • Lineáris egyenletrendszerek: nem kell, csak emlékeztető volt.
  • Mátrixok kondíciószáma: kell, a kondíciószám tulajdonságainak az igazolása is (az első négy).
  • A megoldás érzékenysége: kell.
  • Lineáris egyenletrendszerek megoldási módszerei: kell.
  • Gauss-módszer: kell. 
Banach-féle fixponttétel. Gersgorin-tételek. Normák és sajátétékek kapcsolata. Nevezetes mátrixtípusok. Lebegőpontos számábrázolás.  
3. hét, 09.18.

Szerda: Sportnap miatt nincs előadás. Csütörtök: A Gauss-módszer végrehajthatósága, és vizsgálata. $LU$-felbontás. Főelemkiválasztás. Általános $LU$-felbontás, $LDM^T$-felbontás, Cholesky-felbontás (köv. hétre csúcsik).

  • A Gauss-módszer algoritmusa: a módszert végre kell tudni hajtani az előadáson szereplő mintafeladat mintájára.
  • A Gauss-módszer végrehajthatósága: kell, kivéve a 62. tétel első pontjának bizonyítása.
  • A Gauss-módszer műveletigénye: kell.
  • LU-felbontás: kell. A 66. tételt nem kell ismerni pontosan, elég annyi, hogy L elemeinek abszolút értékben való csökkentésével lehet csökkenteni az LU-felbontás hibáját.
  • Főelemkiválasztás: kell.
  • LU-felbontás általános mátrixokra: kell, kivéve a 67. tétel bizonyítása. A 142. oldalról a növekedési faktor fogalma kell, ill. az alsó képlet kvalitatív ismerete.    
  • $LDM^T$-felbontás: kell.
  • Cholesky-felbontás: kell.
A szerdai gyakorlat a sportnap miatt elmarad. Kondíciószám, LER direkt megoldási módszerei.
4. hét, 09.25.

Szerda: $LDM^T$-felbontás, Cholesky-felbontás, mikor melyik módszert használjuk?, a Matlab linsolve parancsának algoritmusa. Iterációs egyenletrendszer-megoldás. A konvergencia szükséges és elégséges feltétele. Hibabecslés a Banach-féle fixponttétellel. Jacobi-, Gauss-Seidel-módszer, és ezek relaxált változatai. Csütörtök: Iterációs módszerek konvergenciája. Gradiens módszerek bevezetése..

  • Lineáris iterációs eljárások: kell.
  • Jacobi-iteráció: kell.
  • Gauss-Seidel-iteráció: kell.
  • Relaxációs módszerek: kell. (Táblázatba foglaltuk az egyes módszerek nevezetes mátrixait.)
  • Konvergencia: kell, kivéve a 75., 79., 80.  tételek.
  • Leállási feltételek: kell.
  • Gradiens módszerek - minimalizáló tulajdonság: kell.
  • Gradiens módszer: kell, kivéve a 83. tételt. (Eddig tart az első röpzh elméleti anyaga.)

Direkt módszerek lineáris egyenletrendszerek megoldására.

5. hét, 10.02.

Szerda: 1. röpzh. Betegség miatt az eheti előadások elmaradnak, később pótoljuk őket. Iterációs módszerek lineáris egyenletrendszerek megoldására. Példatár: 3.34, 3.37, 3.41*, 3.43, 3.45, 3.47, 3.48, 3.50, 3.52* (pcg-vel is), 3.53*
6. hét, 10.09.

Szerda: A konjugált gradiens módszer és tulajdonságai. Householder-tükrözés. Csütörtök:  A Housholder-tükrözés és a Givens forgatás alkalmazása $QR$-felbontásra. Sajátértékfeladatok kondicionáltsága.

  • Konjugált gradiens módszer: kell. (Itt kezdődik a második röpzh elméleti anyaga.)
  • A konjugált gradiens módszer konvergenciája: kell, kivéve a 85. tétel bizonyítását és a 88. tételt.
  • Javított algoritmus: kell.
  • Megjegyzések: csak az első két dia kell.
  • Householder-tükrözés: kell, kivéve a 213. oldalon található levezetés.
  • A QR-felbontás: kell.
  • Givens-forgatás: kell.
  • Túlhatározott rendszerek megoldása: kell.
  • Kondicionáltság (sajátértékfeladatok): kell.
$QR$-felbontás meghatázozása Householder-tükrözéssel és Givens-forgatással. Túlhatározott egyenletrendszerek megoldása.
7. hét, 10.16.

Szerda: Sajátértékfeladatok megoldása: hatványmódszer, inverz- és Rayleigh-hányados iteráció, QR-iteráció. Csütörtök: I. évfolyamzh (a zh anyaga a félév elejétől a QR-felbontásig tart, túlhatározott egyenletrendszer megoldása már nem lesz).

  • Hatványmódszer: kell.
  • A Rayleigh-hányados: kell, kivéve a 96. tétel bizonyítása.
  • Inverz iteráció: kell.
  • Rayleigh-hányados iteráció: kell.
  • Householder-defláció: nem kell.
  • Rangcsökkentés: kell.
  • A Jacobi-módszer: nem kell.
  • QR-iteráció: kell, kivéve a 99. tétel.
Sajátértékfeladatok megoldása.

8. hét, 10.23.

Szerda: Nemlineáris egyenletek megoldása (bevezetés, kondicionáltság, konvergenciarend, intervallumfelezés, Newton-módszer, fixpont iterációk, nemlineáris egyenletek megoldása a Newton-módszerrel, minimalizációs feladatok megoldása a gradiens- és a Newton-módszerekkel). Csütörtök: Polinominterpoláció (az interpoláció alapfeladata, interpolációs polinom egyértelműsége, Lagrange-féle és Newton-féle előállítás).

  • Nemlineáris egyenletek megoldása - nemlineáris egyenletek: kell.
  • Polinomok: nem kell.
  • Kondicionáltság: kell.
  • Konvergenciasebesség: csak az első dia kell a definícióval.
  • Geometriai módszerek: csak az intervallumfelezési és a Newton-módszer kell (ez utóbbinál a tételek is kellenek bizonyítással együtt).
  • Fixpont iterációk: kell.
  • Aitken-gyorsítás: nem kell, viszont ezen rész végén szerepel külön cím nélkül a nemlineáris egyenletrendszerek megoldása, ami kell. Ráadásul ez előadáson általánosabban szerepelt, továbbá volt szó a lokális minimumhelyek megkeresésének módszereiről is (Newton-módszer, gradiens-módszer).
  • Interpoláció alapfeladata: kell.
  • Lagrange-polinom: kell.
  • Kondicionáltság: nem kell. (Eddig tart a második röpzh elméleti anyaga.)
Nemlineáris egyenletek megoldása.
9. hét, 10.30.

Szerda: Mindenszentek ünnepe miatt nincs előadás. Csütörtök: Az interpolációs polinom Newton-féle előállítása. Interpoláció hibabecslése.

  • Interpolációs hiba: kell.
  • Newton-féle előállítás: kell. (Ez a két témakör előadáson fordított sorrendben szerepelt, és egy kicsit máshogy, mint ahogy a diákon található. A két témakör közti Csebisev-polinomos interpoláció a következő előadás anyaga lesz.)
A szerdai gyakorlat Mindenszentek ünnepe miatt elmarad. Nemlineáris egyenletrendszerek megoldása, minimalizálás. Polinominterpoláció.

10.hét, 11.06.

Szerda: Interpoláció Csebisev-alappontokon. Hermite- és spline-interpoláció. Csütörtök: Trigonometrikus interpoláció, gyors Fourier-transzformáció.

  • Csebisev-polinomok: kell (sőt a hibabecslést megadtuk tetszőleges [a,b] intervallumra is). 
  • Hermite-interpoláció: kell, kivéve a Lagrange-alappolinomos előállítás.
  • Spline-interpoláció: kell, kivéve a 123. tétel.
  • Trigonometrikus interpoláció: kell. 
Polinominterpoláció hibabecslése. Hermite-Fejér-interpoláció. Spline-interpoláció.
11.hét, 11.13.

Szerda: Gyors Fourier-transzformáció, numerikus deriválás, numerikus integrálás a Newton-Cotes-formulákkal. Csütörtök: TDK konferencia

  • Gyors Fourier-transzformáció: kell.
  • Közelítés legkisebb négyzetek értelemben: nem kell.
  • Numerikus differenciálás: kell.
A csütörtöki gyakorlat a TDK-konferencia miatt elmarad. A szerdai gyakorlaton behozzuk a lemaradást a másik gyakorlathoz képest.
12.hét, 11.20.

Szerda: Numerikus integrálás folytatása: Newton-Cotes-formulák, pontossági rend, összetett formulák, konvergenciarend. Gauss-kvadratúra. Csütörtök: Kezdetiértékfeladatok megoldása.

  • Numerikus integrálás - motiváció: kell
  • Kvadratúraformula: kell.
  • Newton-Cotes-formulák: kell, kivéve a 136. és 137. tételek bizonyításai.
  • Romberg-módszer: nem kell.
  • Gauss-kvadratúra: kell, kivéve a 131. tétel.
  • ...
Trigonometrikus interpoláció. Numerikus deriválás. Numerikus integrálás bevezetés.
  • gauss_meth.m - Gauss-módszer és $LU$-felbontás
  • jor.m - Relaxált Jacobi-iteráció vagy JOR
  • sor.m - Relaxált Gauss-Seidel vagy SOR
  • grad.m - Gradiens-módszer
  • konjgrad.m - Konjugált gradiens-módszer
  • nemlin_polint.mnemlin_polint.mlx - Nemlineáris egyenletek ill. polinomintepoláció. A labormunkát segítő Matlab m-fájl ill. live script fájl. 
  • polint2_trigint.mpolint2_trigint.mlx - Polinomintepoláció hibája, Csebisev- és Hermite-interpoláció, spline-interpoláció, trigonometrikus interpoláció. A labormunkát segítő Matlab m-fájl ill. live script fájl. 
  • trigint_numder_numint.mtrigint_numder_numint.mlx - Trigonometrikus interpoláció, numerikus deriválás és integrálás. A labormunkát segítő Matlab m-fájl ill. live script fájl. 

 Korábbi zárthelyi dolgozatok 

 

 Hasznos linkek