שיטת ניוטון

הביטוי שבחרתי הוא תיאור מתמטי של שיטת ניוטון.

זמן רב לפני ניוטון, השתמשו היוונים בנוסחה דומה לחישוב השורש הריבועי של מספר חיובי. מאז ניוטון, שיטת האיטרציות משמשת באופן כללי יותר למציאת קירובים לפתרון של כל משוואה מהצורה f(x)=0. בשלב מוקדם בקריירה שלי בתחום המתמטיקה, רציתי להבין מדוע השיטה הזאת פועלת מהר והיטב כל כך ומהן המגבלות שלה.

במקרה המיוחד שבו f הוא פולינום, המשפט היסודי של האלגברה קובע שלמשוואה f(x)=0 מוכרח להיות פתרון. הפתרון x עשוי להיות מספר ממשי או מרוכב. גאוס, בראשית המאה ה-19, הוכיח שהפתרון קיים בעזרת אלגוריתם שאפשר לזהות כי היה מבוסס על רעיון של ניוטון (בהוכחה הזאת היה פער). המאמר שלי מ-1981 על "המשפט היסודי של האלגברה ותורת הסיבוכיות" התבסס על שיטת ניוטון והיה קשור לרעיון של גאוס.

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

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

לשאלה על מציאת שורש לפולינום יש הכללה טבעית לפתרון של מערכת משוואות פולינומיות. כדי לטפל בהכללה הזאת, שיתפתי פעולה עם מייק שוב (Shub) בכתיבת סדרה של מאמרים שקראנו להם "הסיבוכיות של משפט בזו". מטרתנו הייתה להפוך את הבעיה הזאת לנגישה על ידי מציאת אלגוריתם שיספק קירובים טובים בזמן פולינומי. בכך נכשלנו, והבעיה הזאת עודנה פתוחה ועומדת. עם זאת, פיטר בורגיסר (Burgisser) ופליפה קוקר (Cucker) התקרבו מאוד לפתרון הבעיה הזאת במאמר שפורסם ב-2011 בכתב העת החשוב Annals of Mathematics. הם השתמשו בפיתוחים של קרלוס בלטראן (Beltran) ולואיס פארדו (Pardo), ושיטת ניוטון מילאה תפקיד מרכזי בעבודתם.

יחד עם לנור בלום (Blum), מייק שוב ואנוכי הכללנו את רעיון מכונת טיורינג ממדעי המחשב כדי לתמוך בתחום של מציאת שורשים לפונקציות. האלגוריתמים במספרים ממשיים של הפרויקט שלנו נחקרו בהיבטים של סיבוכיות, שלמות-NP ונגישות. בסופו של דבר, פליפה קוקר הצטרף אלינו לכתיבת ספר על "סיבוכיות וחישובים במספרים ממשיים".

ג'ון קיטס כתב "יופי הוא אמת, אמת היא יופי". הוא כתב גם "דְּבַר־יֹפִי יְשַׂמַּח לֵבָב לָעַד" [תרגום ראובן אבינועם]. אני מבקש להוסיף שיופי הוא פשוט ועמוק. אני מקווה שמילותיי המעטות ישכנעו אתכם ששיטת ניוטון היא רעיון שיש בו יופי רב.