עבודת סמינריון יעילות אלגוריתמים (עבודה אקדמית מספר 9280)
70 עמודים.
עבודה אקדמית מספר 9280שאלת המחקר:
כיצד באה לידי ביטוי יעילות אלגוריתמים?
תוכן עניינים:
מבוא................................................................................................ 5 פרק א' – אלגוריתם ניוטון-רפסון ............................................................................. 8 פרק ב' – פיתוחַ ושכלוּל של אלגוריתם ניוטון-רפסון ................................................... 19 פרק ג' – אלגוריתמים “חריגים” ............................................................................... 29 פרק ד' – כיוון מחקר חדש – אלגוריתם דינאמי ממעלה שלישית ................................. 33 פרק ה' - הוכחת התכנסות האלגוריתם הדינאמי ........................................................ 45 סיכום ......................................................................................................... 60 ביבליוגרפיה .................................................................................. 61 נספחים ................................................................................................ 62
המדע המודרני שואף למצוא מודלים מתמטיים שיתארו את שלל התופעות המוכרות לנו. מודלים אלו הם למעשה מערכות של משוואות ונמדדים על-פי ההתאמה בין פתרונות, לתוצאות המושגות בניסוים אמפיריים. בכל צעד ושעל אין מנוס מהתמודדות עם משוואות – פשוטות ומסובכות כאחד. מעצם הצורך הרב והשימוש הנרחב, תחום האנליזה הנומרית שעוסק בין היתר בחיפוש אחר אלגוריתמים יעילים לפתירת משוואות, החל לצבור תאוצה מאז ייסודו של המדע המודרני עוד בתקופתו של ניוטון. (Isaac Newton) אלגוריתם ניוטון-רפסון שפותח לפני יותר משלוש מאות שנה על-ידי אייזק ניוטון הוא ללא ספק האלגוריתם המשמעותי הראשון בתחום, ועד היום ,(Joseph Raphson) וג'וסף רפסון מנוצל במקרים רבים. במרוצת השנים פותחו אלגוריתמים שונים ויעילים יותר, אך למעשה, מרבית הפיתוחים הנומריים מנסים עד היום לפתור את הבעיה באופן דומה. עבודה זו תחולק לארבעה פרקים עיקריים: הפרק הראשון יעסוק באלגוריתם ניוטון-רפסון ותכונותיו בציר המספרים הממשי והמרוכב כאחד, ויהווה בסיס לכל הפיתוחים שיופיעו בפרק השני – פיתוחים שנמצאים כיום בחזית המחקר המדעי. הפרק השלישי יעסוק באלגוריתמים שיעילותם מוטלת בספק, אך מקוריותם מעוררת השראה. אותם אלגוריתמים, למרות שאינם נפוצים בקהילה המדעית, יעסיקו אותנו בעיקר בפרק הרביעי, ועל-כן, יוצגו בהרחבה תוך הדגשת הבסיס הרעיוני שלהם. בפרק הרביעי אציג אם כן, כיוון חדש להתמודד עם הבעיה שביכולתו לפתור את אחת הבעיות העיקריות באנליזה הנומרית: היכולת לאתר שורש ספציפי בתחום מוגדר ללא צורך בחישוב כל שאר הפתרונות, ועל כך בהמשך. להלן נדון במשמעות של פתרון משוואות.
ביבליוגרפיה לדוגמא (בעבודה האקדמית כ-20 מקורות אקדמיים באנגלית ובעברית)
Acton, F. S., Numerical Methods That Work, Washington DC: Mathematical Association of America,. 2. Pan, V. Y., Univariate Polynomial Root-Finding with a Lower Computational Precision and Higher Convergence Rates, USA: Lehman College of CUNY,. 3. Mekwi, W.R., ‘Iterative Methods for Roots of Polynomials’, In: Eprints Administrator, University of Oxford.