פיתון/חישוב נומרי בשפת פייתון/שבוע 1

הרצאה 1:

שורשים מרובעים באמצעות שיטת ניוטון

ניתן להבחין בין שיטות מספריות מענפים אחרים של ניתוח ומדעי המחשב על ידי שלושה מאפיינים:  

• הן עובדות עם מספרים ממשיים שרירותיים (ומרחבים וקטוריים/הרחבות שלהם): התוצאות הרצויות אינן מוגבלות למספרים שלמים או רציונלים מדויקים (למרות שבפועל אנו מחשבים רק קירובים רציונליים של תוצאות אי-רציונליות).  

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

• אנחנו גם מודאגים מהדיוק של התוצאות, מכיוון שבפועל יש לנו רק תשובות משוערות:  

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

– אריתמטיקה עם מספרים ממשיים משוערת במחשב, מכיוון שאנו מקרובים את קבוצת R של מספרים ממשיים לפי קבוצת F של מספרי נקודה צפה, והתוצאה של כל פעולה יסודית (+,−,×,÷) מעוגלת ל- האלמנט הקרוב ביותר של F. עלינו להבין את F וכיצד הצטברות של שגיאות עיגול אלו משפיעה על אלגוריתמים שונים.  

2 שורשים מרובעים

אלגוריתם קלאסי הממחיש הרבה מהחששות הללו הוא השיטה של ​​"ניוטון" לחישוב ריבוע  √ 2 שורשים x = a עבור a > 0, כלומר לפתור x = a. האלגוריתם מתחיל בניחוש כלשהו x1 > 0  ומחשב את רצף הניחושים המשופרים     1 a

הפונקציה המקורית:

$f(x)=x^{2}-a$

√ √ האינטואיציה פשוטה מאוד: אם xn גדול מדי (>√a), אז a/xn יהיה קטן מדי (< a), ולכן הממוצע האריתמטי שלהם xn+1 יהיה קרוב יותר ל- a. מסתבר שהאלגוריתם הזה ישן מאוד, מתוארך לפחות לבבלים הקדמונים בסביבות 1000 לפני הספירה.1 בעת המודרנית, זה היה ראה  

1ראה√למשל Boyer, A History of Mathematics, ch. 3; הבבלים השתמשו בבסיס 60

שווה ערך לשיטת ניוטון למצוא שורש של $f(x)=x^{2}-a$ נזכיר שהשיטה של ​​ניוטון מוצאת שורש משוער של f(x) = 0 מתוך ניחוש xn על ידי קירוב של f(x) כישר המשיק שלו  f(xn) + f0(xn) (x − xn), המוביל לניחוש משופר xn+1 משורש המשיק:  

$f'(1)=2$  

$y-(a+1)=2(x-1)$

$y=2x-(a+1)$

$f'(1.5)=3$

$y=3x-4.25$

$4.25=3x$

$f'(17/12)=17/6$

${\dfrac {17}{6}}x-{\dfrac {577}{144}}=0$

$x={\dfrac {577}{408}}$

from scipy import misc

def NewtonsMethod(f, x, tolerance=0.000001):
    while True:
        x1 = x - f(x) / misc.derivative(f, x) 
        t = abs(x1 - x)
        if t < tolerance:
            break
        x = x1
    return x

def f(x):
    return x**2-2

x = 4

x0 = NewtonsMethod(f, x)

print('x: ', x)
print('x0: ', x0)

דוגמה נוספת (פונקציית ARCTAN,כולל חישוב הנגזרת):

from scipy import misc
import numpy
def NewtonsMethod(f, x, tolerance=0.000001):
    while True:
        x1 = x - f(x) / misc.derivative(f, x) 
        t = abs(x1 - x)
        if t < tolerance:
            break
        x = x1
    return x

def f(x):
    return (6.0*numpy.arctan(x)-numpy.pi)

x = 0.5

x0 = NewtonsMethod(f, x)

print('x: ', x)
print('x0: ', x0)

$g(x)=\arctan(x)$

$6*g(x_{1})-\pi =0$

$g'(x)={\dfrac {1}{(x^{2}+1)}}$

$x_{3}={\dfrac {12}{5}}$

$169*g(x_{3})=198.7448799990719$

$169*g'(x_{3})=25$

$g_{0}(x_{3})={\dfrac {25x_{3}}{169}}-1.22399$

$x_{4}=-0.3453664$

$x_{5}={\dfrac {-0.49962}{0.893433}}=-0.559124$

הרצאה 2:

פורמט IEEE 754

הבעיה

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

• טווח: כדי להיות שימושי, השיטה שלך צריכה לאפשר מספרים חיוביים ושליליים גדולים מאוד.
• דיוק: האם אתה יכול להבחין בין 1.7 ל-1.8? מה לגבי בין 1.700001 ל-1.700002? כמה מקומות עשרוניים צריך לזכור?
• יעילות זמן: האם הפתרון שלך עושה השוואות ופעולות אריתמטיות מהירות וקלות?
• שיקולי שטח: ייצוג מדויק ביותר של השורש הריבועי של 3 הוא בדרך כלל דבר נפלא, אלא אם כן אתה צריך מגה-בייט כדי לאחסן אותו.
• יחסים אחד לאחד: הפתרון שלך יהיה הרבה יותר פשוט אם ניתן לכתוב כל מספר נקודה צפה רק בדרך אחת, ולהיפך.

פתרון

השיטה שהמפתחים של IEEE 754 Form תקפו לבסוף משתמשת ברעיון של סימון מדעי. סימון מדעי הוא דרך סטנדרטית לבטא מספרים; זה מקל עליהם לקרוא ולהשוות. אתה בוודאי מכיר את התווים המדעיים עם מספרי בסיס 10. אתה פשוט מחלק את המספר שלך לשני חלקים: ערך שגודלו הוא בטווח של 1≤n<101≤n<10, וחזקת 10. לדוגמה:

3498523 נכתב כ-$3.498523*10^{6}$

−0.0432 נכתב בתור –4.32×10–2–0.0432 נכתב כ–4.32×10–2

אותו רעיון תקף כאן, פרט לכך שאתה צריך להשתמש בחזקות 2 כי המחשב עובד ביעילות עם מספרים בינאריים. רק חלק את המספר שלך לערך שגודלו הוא בטווח 1≤n<21≤n<2, ובחזקה של 2. (שים לב, צריכה להיות רק דרך אחת לעשות זאת - אתה מבין למה? )

−6.84 נכתב בתור –1.71×22–6.84 נכתב כ–1.71×22

0.05 נכתב כ-1.6×2-50.05 נכתב כ-1.6×2-5

כדי ליצור את המיתר, עלינו לעסות את המוצר הזה כך שיקבל את הצורה הבאה:

(−1)סימן סיביות(1+שבר)×2מעריך - הטיה(-1)סיביות סימן(1+שבר)×2מעריך - הטיה

לאחר שהדבר נעשה, יהיו לנו שלוש פיסות מידע מרכזיות (המוצגות בצבע למעלה) אשר, כאשר הן נכללות יחד, מזהות את המספר:

• First Piece - אם ביט הסימן הוא 0, אז המספר חיובי; (−1)0=1(−1)0=1. אם סיביות הסימן היא 1, המספר שלילי; (−1)1=−1(−1)1=−1.
• חתיכה שנייה - אנחנו תמיד מביאים בחשבון כך שהמספר בסוגריים יהיה שווה (1+ שבר כלשהו)(1+ שבר כלשהו). מכיוון שאנו יודעים שה-11 נמצא שם, הדבר החשוב היחיד הוא השבר, אותו נכתוב כבינארי מחרוזת.

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

0.1binary=2−1=0.50.1binary=2−1=0.5

0.01binary=2−2=0.250.01binary=2−2=0.25

0.101binary=2−1+2−3=0.6250.101binary=2−1+2−3=0.625

• חתיכה שלישית - החזקה של 2 שקיבלת בשלב האחרון היא פשוט מספר שלם. שים לב, מספר שלם זה עשוי להיות חיובי או שלילי, תלוי אם הערך המקורי היה גדול או קטן, בהתאמה. נצטרך לאחסן את המעריך הזה -- עם זאת, שימוש בהשלמה של השניים, הייצוג הרגיל של ערכים חתומים, מקשה על השוואות של ערכים אלה. ככזה, אנו מוסיפים ערך קבוע, הנקרא הטיה, למעריך. על ידי הטיית המעריך לפני שהוא מאוחסן, אנו מכניסים אותו לטווח ללא סימן מתאים יותר להשוואה.
  • עבור נקודה צפה בעלת דיוק יחיד, מעריכים בטווח של -126 עד +127 מוטים על ידי הוספת 127 כדי לקבל ערך בטווח 1 עד 254 (ל-0 ול-255 יש משמעויות מיוחדות).
  • עבור דיוק כפול, מעריכים בטווח -1022 עד +1023 מוטים על ידי הוספת 1023 כדי לקבל ערך בטווח 1 עד 2046 (ל-0 ול-2047 יש משמעויות מיוחדות).