מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/מתמטיקה/תרגילים

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

קפיצה אל: ניווט, חיפוש


[עריכה] חסמי אינטגרלים

[עריכה] שאלה

אנא הוכח אחד מחסמי האינטגרלים הבאים (שתי ההוכחות דומות מאד זו לזו):

  1. אם \displaystyle f(n) מונוטונית לא יורדת, אז \displaystyle \int_{m -1}^n f(x) dx \le \sum_{i = m}^n [f(i)] \le \int _m^{n + 1} f(x) dx
  2. אם \displaystyle f(n) מונוטונית לא עולה, אז \displaystyle \int_m^{n + 1} f(x) dx \le \sum_{i = m}^n [f(i)] \le \int _{m - 1}^n f(x) dx

[עריכה] תשובה

זו למעשה שאלה מחדו"א:

  1. היות ש\displaystyle f(n) מונוטונית לא יורדת, אז:
    • \displaystyle \int_{m-1}^n f(x) dx = \sum_{i=m-1}^{n-1}\int_i^{i+1}f(x) dx \le \sum_{i=m-1}^{n-1}\int_i^{i+1}f(i+1) dx = \sum_{i = m}^n[f(i)]
    • \displaystyle \int_m^{n+1} f(x) dx = \sum_{i=m}^n\int_i^{i+1}f(x) dx \ge \sum_{i=m}^n\int_i^{i+1}f(i) dx = \sum_{i = m}^n[f(i)]
  2. כפי שנכתב בשאלה, המקרה שבו \displaystyle f(n) מונוטונית יורדת דומה מאד.

מקור: http://he.wikibooks.org/wiki/%D7%9E%D7%91%D7%A0%D7%99_%D7%A0%D7%AA%D7%95%D7%A0%D7%99%D7%9D_%D7%95%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9E%D7%99%D7%9D_-_%D7%9E%D7%97%D7%91%D7%A8%D7%AA_%D7%A7%D7%95%D7%A8%D7%A1/%D7%A0%D7%A1%D7%A4%D7%97%D7%99%D7%9D/%D7%9E%D7%AA%D7%9E%D7%98%D7%99%D7%A7%D7%94/%D7%AA%D7%A8%D7%92%D7%99%D7%9C%D7%99%D7%9D
כלים אישיים