Kihagyás

6. gyakorlat

Meta

Témák

  • Nagyságrendőrző becslések
  • Kijelentések, kvantorok, logikai állítások

Órai feladatok

Nagyságrendőrző becslések

A lényege a nagyságrendőrző becsléseknek az, hogy nagy x értékekre az aritmetikai kifejezés értékét a legnagyobb hatványkitevőjű tag határozza meg, tehát az érték becsülhető egy jóval egyszerűbb polinommal

NRF (Nagyságrendőrző felső becslés)

Legyen P(x) egy valós polinom

\[ P(x)=\sum_{i=0}^n a_i \cdot x^{i}= a_{n} \cdot x^{n}+ a_{n-1} \cdot x^{n-1} + \cdot\cdot\cdot \ a_{1} \cdot x + a_{0} \]

Ekkor egy NRF-becslés meghatározása a következő lépésekből áll:

  1. lépés: Hagyjuk el a negatív együtthatós tagokat
  2. lépés: Ekkor már tudjuk, hogy \(P\) minden tagja pozitív, vagy 0. Most az összes tag fokát változtassuk meg n-re

NRA (Nagyságrendőrző alsó becslés)

Legyen P(x) egy valós polinom

\[ P(x)=\sum_{i=0}^n a_i \cdot x^{i}= a_{n} \cdot x^{n}+ a_{n-1} \cdot x^{n-1} + \cdot\cdot\cdot \ a_{1} \cdot x + a_{0} \]

Ekkor egy NRA-becslés meghatározása a következő lépésekből áll:

  1. lépés: Hagyjuk el a n/n;l kissebb fokszámú pozitív együtthatós tagokat
  2. lépés: Ekkor már tudjuk, hogy \(P\) minden tagja negatív, vagy 0. Tehát a következő formában néz ki:
\[ a_{n} \cdot x^{n} - a_{n-1} \cdot x^{n-1} - \cdot\cdot\cdot \ a_{1} \cdot x - a_{0} \]

Ezután a negatív tagokból kiemeljük a -1-et

\[ a_{n} \cdot x^{n} - a_{n-1} \cdot x^{n-1} - \cdot\cdot\cdot \ a_{1} \cdot x - a_{0} = a_{n}\cdot x^{n} - (a_{n-1} \cdot x^{n-1} + \cdot\cdot\cdot + a_{1} \cdot x + a_{0}) \]

Már láttuk, hogy kell egy polinomot felülről becsülni, ezért a zárójeles részt felülről megbecsüljük, tehát megkeressük a \(\(a_{n-1}\)\)-ed fokú részpolinomnak a felső becslését. Ezt itt \(\(M_{1}\)\)-nek neveztük, a küszöböt pedig \(\(R_{1}\)\)-nek. Tehát tudjuk

\[ P(x) \geq a_{n}\cdot x^{n} - (a_{n-1} \cdot x^{n-1} + \cdot\cdot\cdot + a_{1} \cdot x + a_{0}) \geq a_{n} \cdot x^{n}-M_{1}\cdot x^{n-1} \]

Itt pedig a \(a_{n}\)-ot szétválasztjuk hogy legjobb esetben csak egyet kelljen kiemelni, vagy elosztjuk 2-vel és utána emelünk ki

\[ \frac{a_{n}}{2}\cdot x^{n} + \frac{a_{n}}{2}\cdot x^{n} -M_{1}\cdot x^{n-1} = \frac{a_{n}}{2}\cdot x^{n}+x^{n-1}(\frac{a_{n}}{2}\cdot x-M_{1}) \]

Ekkor ha az x-et, ha olyan nagyra választjuk, hogy,

\[ \frac{a_{n}}{2}\cdot x-M_{1} \geq 0 \]
\[ x \geq \frac{2M_{1}}{a_{n}} \]

akkor elhagyható, és amit kapunk:

\[ P(x) \geq \frac{a_n}{2}\cdot x^n \]

to be continued...