חיפוש פתרונות למשוואות

כל עוד מדובר במשוואות מהמעלה הראשונה והשניה – כמוהן אנחנו זוכרים מימי לימודינו בבית הספר – ניתן לפתור אותן באופן אנאליטי: מעבירים אגפים, עושים מכנה משותף, משתמשים בנוסחה למציאת שורשי משוואה ריבועית וכו'.
במשוואות ממעלה גבוהה יותר או שאינן פולינומים – זו כבר עלולה להיות בעייה לא פתירה, ולעיתים יש לחפש פתרון "בכח" בתחום מסויים: קובעים גבול עליון וגבול תחתון, ואט-אט מצמצמים את התחום עד שמגיעים לדיוק הרצוי וכך מקבלים את התוצאה בקירוב די טוב.
יש מספר שיטות לצמצום התחום, והחביבה עלי נעזרת ביחס הזהב (..0.618033):
1. נסמן את הגבול התחתון X1 ואת העליון X4, כאשר עבור אחד מהם הפונקציה חיובית, עבור השני שלילית, ואנחנו מחפשים את הנקודה בינהם בה היא מתאפסת.
2. נחשב את X2 ו-X3 כך שיחלקו את המרחק בין X1 ו-X4 לפי יחס הזהב.
3. נחשב את ערך הפונקציה בכל אחת מארבע הנקודות X1, X2, X3, X4.
4. אם שינוי הסימן הוא בין X1 ו-X2 אזי ניקח את X1, X2, X3 ונחשב בעזרתם את X1..X4 מחדש (כאשר X1 תישאר X1, ו-X3 תהפוך ל-X4; את X2 נהפוך ל-X3, ואת X2 החדש נחשב);
   ואם שינוי הסימן אינו בין X1 ו-X2 אזי ניקח את X2, X3, X4 ונחשב בעזרתם את X1..X4 מחדש (כאשר X4 תישאר X4, ו-X2 תהפוך ל-X1; את X3 נהפוך ל-X2, ואת X3 החדש נחשב).
5. נחזור ל-3 כל עוד ההפרש בין X1 ל-X4 גדול מהדיוק הרצוי.
הפואנטה בשיטה הזו היא שבכל פעם ניקח 3 נקודות מהשלב הקודם ואת ערכי הפונקציה עבורן, ונצטרך לחשב בכל פעם נקודה אחת ולהפעיל את הפונקציה פעם אחת.
לו היינו מחלקים את התחום לשלושה חלקים שווים כפי שהאינטואיציה שלנו אומרת – בשלב הבא נצטרך לחשב מחדש את X2 ואת X3 (וכמובן את ערכי הפונקציה עבורן), מכיוון שנקודות האמצע הקודמות כבר לא יחלקו את התחום המצומצם לשלוש..

דוגמה: נחפש למשוואה 4x³-3x²+2x-1=0 פתרון בין 10- ל-10.
קודם כל ניצור פונקציה מתאימה למשוואה הנ"ל:

Create Function dbo.F(@X Float) Returns Float As

    Begin

    Return (4*Power(@X,3)-3*Power(@X,2)+2*@X-1)

    End;

Go

וכעת נבנה CTE רקורסיבי שיחפש פתרון מקורב לפי הקבועים שנגדיר לו:

Declare    @X1 Float,

        @X4 Float,

        @f Float,

        @d Float;

Select    @X1=-10,

        @X4=10,

        @d=0.0001;

Select    @f=2/(SQRT(5)+1);

With T As

(Select    1 N,

        X1,

        X2,

        X3,

        X4,

        Null I,

        dbo.F(X1) Y1,

        dbo.F(X2) Y2,

        dbo.F(X3) Y3,

        dbo.F(X4) Y4

From    (Select    @X1 X1,

                @X4-@f*(@X4-@X1) X2,

                @X1+@f*(@X4-@X1) X3,

                @X4 X4) T

Union All

Select    N,

        Case When I=0 Then X1 Else X2 End X1,

        Case When I=0 Then X3-@f*(X3-X1) Else X3 End X2,

        Case When I=0 Then X2 Else X2+@f*(X4-X2) End X3,

        Case When I=0 Then X3 Else X4 End X4,

        I,

        Case When I=0 Then Y1 Else Y2 End Y1,

        Case When I=0 Then dbo.F(X3-@f*(X3-X1)) Else Y3 End Y2,

        Case When I=0 Then Y2 Else dbo.F(X2+@f*(X4-X2)) End Y3,

        Case When I=0 Then Y3 Else Y4 End Y4

From    (Select    N+1 N,

                X1,

                X2,

                X3,

                X4,

                Y1,

                Y2,

                Y3,

                Y4,

                Case When Y1*Y2<0 Then 0 Else 1 End I

        From    T

        Where    X4-X1>@d) T)

Select    *

From    T;

X1@ ו-X4@ הוגדרו בתור 10-, 10 בהתאמה והם תוחמים את תחום החיפוש.

f@ הוא יחס הזהב המוגדר,

ו-d@ הוא המרווח בו נעצור את החיפוש.

ניתן לעיין בתוצאות ולראות איך בכל שלב עוברות 3 נקודות ו-3 ערכים של הפונקציה לשלב הבא; ונקודה אחת והפעלה אחת של הפונקציה יש לבצע מחדש.

מי שרוצה לוודא שיחס הזהב מתקיים לאורך כל החיפוש- יכתוב את ה-Select שבשתי השורות האחרונות כך:

...

...

...

Select    *,

        (X3-X1)/(X4-X1) f1,

        (X4-X2)/(X4-X1) f2

From    T;