פתרון נוסחת נסיגה

[globus1988]

פתרון נוסחת נסיגה

ניסיתי לפתור את הנוסחה הבאה בשיטת האב, לפי המקרה השלישי, אבל הסתבכתי עם תנאי הרגולריות. תוכלו לעזור לי?
צירפתי מטה את הנוסחה, נוסח משפט שיטת האב, ואת הניסיון שלי לפתור נוסחה זו...
תודה לכל העוזרים!

 

[Javali]

רמז

n^4+n^3lg n = BigTheta(n^4)

 

[globus1988]

תודה, אבל

את זה אני יודע... ואיך זה מתקשר לבעיה שיש לי עם תנאי הרגולריות?

 

[Javali]

הקשר

הקשר לבעיה שלך הוא שניסיון הפתרון שלך לא מיישם את מה שאתה טוען שאתה יודע.

 

[globus1988]

ניסיתי ללכת להגדרה של BIG THETA

ולא להצביע על דוגמא ל-c כנ"ל אלא רק להראות שקיים כזה, אבל לא הצלחתי להגיע למסקנה הרצויה. ניסיתי "לשחק" אם אי-השוויונות, אבל לא הלך. האם לכיוון הזה התכוונת? או שהתסבכתי מידי?

 

[Javali]

מה הקשר בין big theta לבין big omega?

 

[globus1988]

big theta (חסם מלעיל ומלרע) בפרט מקיים big omega (חסם מלרע)

 

[Javali]

למה אתה לא משתמש בזה בתשובה הסרוקה שלך?

 

[globus1988]

מצטער שאני שוב לא מבין,

אני שוב מנסה להבין איך זה עוזר לי למצוא קבוע c<1 וחיובי כך שיתקיים האי-שיוויון של תנא הרגולריות
תוכל להסביר לי מה אני לא מבין נכון?

 

[Javali]

הסבר

אתה יודע
n^4+n^3lg n = BigTheta(n^4)
אתה כותב:
n^4+n^3lg n = BigOmega(n^(3+epsilon))
החסם שלך אינו צמוד וזה דופק לך את החישובים.

 

[globus1988]

רגע, אתה מתייחס למה שעשיתי לפני בדיקת תנאי הרגולריות?

שם באמת השתמשתי באומגה, אבל אני מדבר על תנאי הרגולריות... שם אני לא רואה את הבעיה במה שעשיתי (גם, באופן עקרוני, פעלתי לפי איך שהמרצה שלי הראה בכיתה)

צירפתח מטה שוב את נוסח משפט האב. תנאי הרגולריות הוא ב-3.

אם שוב לא הבנתי אותך נכון, אז מצטער...

 

[Javali]

טעות שלי - לא הבנתי אותך

קח c=2/3 ותקבל:
cf-af(n/b) = 2n^4/3 + 2n^3lg/3 - n^4/3 - n^3lg(n/3) > 2n^4/3-n^4/3 + 2n^3lg/3-n^3lg = n^4/3 - n^3log/3
לכן
cf-af(n/b) ==> infinity
וקיבלת את מה שאתה רוצה.

 

[globus1988]

תודה! עכשיו הדברים מתחילים קצת להתסדר... אבל נראה לי

שמשהו בהצבה לא מסתדר... אני חושב שהיית צריך להציב cf-af(n/b) = 2n^4/3 + 2n^3lg/3 - (n/3)^4 - (n/3)^3lg(n/3), לא?

 

[Javali]

לא

אם צריך את כל השלבים אז ההצבה היא:
cf-af(n/b) = 2n^4/3 + 2n^3lg/3-27(n/3)^4 - 27(n/3)^3lg(n/3)=2n^4/3 + 2n^3lg/3 - 27(n^4)/81 - 27(n^3 lg (n/3))/27 =
=2n^4/3 + 2n^3lg/3 - n^4/3 - n^3lg(n/3) ...

 

[globus1988]

תודה רבה!!! אשמח אם תגיד לי אם הבנתי נכון

החלטת להציב בתור C שבר חיובי מסוים הקטן מ-1, והיית יכול לבחור בעצם נראה לי כל שבר כזה ולאו דווקא את 3\2, לא?
בכל מקרה, המטרה היא עתה להראות כי קיים n טבעי (ולא חייבים להצביע על n ספציפי) שהחל ממנו מתקיים cf - af(n/b) >=0. עצם כך שאני מראים כי הגבול הוא אינסוף כאשר n שואף לאינסוף מלמדת אותנו כי קיים בהכרח n0 מסויים שהחל ממנו הביטוי כולו אי-שלילי.
אני צודק?

 

[Javali]

כמעט

לא כל שבר יעבוד. אם c<1/3 זה לא עובד. מעבר לזה, הכל נכון.

 

[globus1988]

כי אז הביטוי ישאף למינוס אינסוף?