איטעראַציע מעטאָד אין געפֿינען וואָרצלען
אין אנגעווענדטע מאטעמאטיק, פיזיק, אינזשעניריע, און קאמפיוטער וויסנשאפט, קומט זייער אָפט ארויף די פראבלעם פון "וואָרצל געפינען". א וואָרצל איז דער ווערט פון \(x\) וואָס מאַכט אַ פונקציע נול, דאָס הייסט, די לייזונג צו דער גלייכונג:
\[
f(x)=0
\]
נישט אַלע גלייכונגען האָבן לייזונגען וואָס קענען אויסגעדריקט ווערן אין פארמאכטע פאָרמולעס, ווי קוואַדראַטישע גלייכונגען. פֿאַר פילע רעאַלע פֿאַלן - ווי קאָמפּלעקסע נישט-לינעאַרע גלייכונגען - דאַרפֿן מיר נומערישע צוגאַנגען. איינער פֿון די וויכטיקסטע צוגאַנגען איז די איטעראַטיווע מעטאָדע, אַ פּראָצעדור וואָס פּראָדוצירט אַ סעריע פֿון אַפּראָקסימאַטיווע לייזונגען וואָס קומען נענטער צום וואָרצל דורך איטעראַציע.
דיזער אַרטיקל דיסקוטירט די גרונטלעכע קאָנצעפּטן פון איטעראַציע מעטאָדן, זייערע קאָנווערגענץ באַדינגונגען, און עטלעכע אָפט גענוצטע איטעראַטיווע מעטאָדן פֿאַר געפֿינען וואָרצלען.
-
1. גרונט־אידעע פון איטעראַציע־מעטאָדע
די איטעראַציע מעטאָדע אַרבעט דורך מאַכן אַן ערשטע שאַצונג \(x_0\), און דערנאָך ביסלעכווייַז פֿאַרבעסערן עס צו באַקומען די סיקוואַנס:
\[
x_0, x_1, x_2, פּונקטן, x_n
\]
מיט ערוואַרטונגען:
\[
x_n צו α
\]
וואו α איז דער ריכטיגער וואָרצל פֿון דער גלייכונג f(x)=0.
בכלל, די איטעראציע מעטאד טראנספארמירט די פראבלעם \(f(x)=0\) אין אן עקוויוואלענטע פארעם:
\[
x = g(x)
\]
דערנאך ווערט איטעראציע דורכגעפירט:
\[
x_{n+1} = g(x_n)
\]
אויב דער פּראָצעס קאָנווערגירט, דעמאָלט איז דער פֿיקסירטער פּונקט פֿון \(g(x)\) אַ וואָרצל־לייזונג פֿון דער אָריגינעלער גלייכונג.
-
2. קאָנווערגענץ: ווען איז איטעראַציע געראָטן?
נישט אלע פונקציעס \(g(x)\) פראדוצירן סטאבעלע איטעראציעס. כּדי די איטעראציע \(x_{n+1}=g(x_n)\) זאָל קאָנווערדזשירן צום וואָרצל \(\alpha\), די אַלגעמיינע באַדינגונגען וואָס ווערן אָפט גענוצט זענען:
1. \(g(\α)=\α\) (וואָרצל איז אַ פֿיקסירטער פּונקט)
2. \(|g'(\alpha)| < 1\) (לאקאלע קאנטראקציע) די אינטואיציע פון \(|g'(\alpha)| < 1\) איז: אין דער געגנט פון דער לייזונג, איז די פונקציע \(g\) "נישט צו שטייל", אזוי יעדע איטעראציע ברענגט דעם ווערט פון \(x_n\) נענטער, נישט ווייטער. קאנווערגענץ ווערט אויך באאיינפלוסט דורך דער ערשטער שאצונג. די זעלבע צוויי מעטאדן קענען מצליח זיין אדער דורכפאלן דעפענדינג אויף \(x_0\). --- 3. די בייסעקציע מעטאד אלס א פשוטע איטעראציע כאטש אפט קלאסיפיצירט באזונדער, קען די בייסעקציע מעטאד געזען ווערן אלס א זייער שטארקע איטעראטיווע מעטאד. די באדינגונגען זענען: די פונקציע \(f(x)\) איז קאנטינעווערליך אויפן אינטערוואל \([a,b]\) און עס איז דא א ענדערונג פון סימן: \[ f(a)\cdot f(b) < 0 \] דאס הייסט, עס איז דא א ווארצל צווישן \(a\) און \(b\). דער אַלגעריטם: 1. רעכנט אויס דעם מיטלפונקט \(c=\frac{a+b}{2}\) 2. באַשטימט דעם סובאינטערוואַל וואָס נאָך אַרומנעמט די וואָרצל (באַזירט אויף דער צייכן ענדערונג) 3. איבערחזרט ביז די טאָלעראַנץ ווערט דערגרייכט דער מייַלע פון דעם מעטאָד: עס וועט באַשטימט קאָנווערדזשירן אויב די צייכן ענדערונג באַדינגונג איז דערפילט. דער חסרון: די קאָנווערגענץ איז לעפיערעך פּאַמעלעך ווייַל דער טעות פאַרקלענערט זיך אַפּראָקסימאַטלי מיט האַלב מיט יעדער איטעראַציע (לינעאַר קאָנווערגענץ). --- 4. פיקסט-פונקט איטעראַציע מעטאָד דאָס איז די מערסט דירעקטע פאָרעם פון איטעראַציע: \[ x_{n+1} = g(x_n) \] די טריט: 1. ענדערן \(f(x)=0\) צו \(x=g(x)\) 2. קלייבט אַן ערשטיקע שאַץ \(x_0\) 3. איטערירט ביז \(|x_{n+1}-x_n|\) אָדער \(|f(x_n)|\) איז קלענער ווי די טאָלעראַנץ דער מייַלע איז פּשוטקייט. אָבער, דעם מעטאָד איז זייער סענסיטיוו צו דער ברירה פון \(g(x)\). פֿאַר דער זעלבער גלייכונג, זענען דאָ פֿיל וועגן צו שרײַבן \(x=g(x)\), אָבער בלויז עטלעכע פֿון זיי קאָנווערדזשירן.
למשל, אויב מיר ווילן געפֿינען די וואָרצלען פֿון \(f(x)=x^3-2x-5\), קענען מיר שרײַבן: - \(x = \sqrt[3]{2x+5}\) אַזוי אַז \(g(x)=\sqrt[3]{2x+5}\) דערנאָך איטערירן מיר \(x_{n+1}=\sqrt[3]{2x_n+5}\). דער הצלחה פֿון דער איטעראַציע הענגט אָפּ צי \(|g'(x)|<1\) אַרום דעם וואָרצל. --- 5. ניוטאָן-ראַפֿסאָן מעטאָדע: שנעלע דעריוואַטיוו-באַזירטע איטעראַציע די ניוטאָן-ראַפֿסאָן מעטאָדע איז איינע פֿון די מערסט פּאָפּולערע מעטאָדן ווײַל איר קאָנווערגענץ איז געוויינטלעך זייער שנעל. די איטעראַציע פֿאָרמולע איז: \[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \] אינטערפּרעטאַציע: בײַ \(x_n\), קאָנסטרויִרן מיר אַ טאַנגענט צו דער פֿונקציע \(f(x)\). די דורכשניט פון דעם טאנגענט מיט דער \(x\)-אַקס ווערט גענוצט ווי די נעקסטע שאצונג. מעלות: - קוואַדראַטישע קאָנווערגענץ (זייער שנעל) אויב עס איז נאָענט גענוג צום וואָרצל און \(f'(\alpha)\neq 0\). חסרונות: - פארלאנגט די דעריוואַטיוו פון \(f'(x)\). - קען דורכפאַלן אויב די ערשטע שאַצונג איז שלעכט, אָדער אויב \(f'(x_n)\) איז נאָענט צו נול, מאַכנדיג דעם איטעראַציע שריט נישט סטאַביל. די מעטאָדע ווערט ברייט גענוצט אין אָפּטימיזאַציע, פיזיק מאָדעלירן, און אינזשעניריע קאַמפּיוטינג צוליב איר עפעקטיווקייט ווען די באַדינגונגען זענען גינציק. --- 6. סעקאַנט מעטאָדע: ניוטאָן'ס אַלטערנאַטיוו אָן דעריוואַטיוון אויב דעריוואַטיוון זענען שווער צו רעכענען, אָפפערט די סעקאַנט מעטאָדע אַ קאָמפּראָמיס. די הויפּט געדאַנק איז צו אַפּראָקסימירן די דעריוואַטיוו מיט ענדלעכע דיפערענצן: \[ f'(x_n)\approx \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}} \] אַזוי די איטעראַציע פאָרמולע איז: \[ x_{n+1}=x_n - f(x_n)\,\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} \] די מעטאָדע ריקווייערז צוויי ערשט שאַצונגען: \(x_0\) און \(x_1\). איר קאָנווערגענץ גיכקייט איז בכלל בעסער ווי פּשוט בייסעקשאַן און פיקסט-פונקט, כאָטש געוויינטלעך אַ ביסל שטייטער ווי ניוטאָן. אָבער, ווייַל עס ריקווייערז נישט דעריוואַטיוון, איז דער סעקאַנט אָפט מער פּראַקטיש.
--- 7. אפשטעל קריטעריע אין נומערישער קאמפיוטאציע, זאל מען אפשטעלן איטעראציע ווען זי איז גענוג גענוי אדער אויב מען פארדעכטיגט אז זי קאנווערדזשירט נישט. אלגעמיינע קריטעריע: 1. קליינער אינטער-איטעראציע טעות: \[ |x_{n+1}-x_n|<\varepsilon \] 2. פונקציע ווערט נאנט צו נול: \[ |f(x_n)|<\varepsilon \] 3. מאקסימום איטעראציע לימיט צו פארמיידן אומענדליכע שלייפן: \[ n \le n_{\max} \] די אויסוואל פון טאלעראנץ \(\varepsilon\) ווענדט זיך אין די באדערפענישן: אינזשעניריע סימולאציעס קענען פארלאנגען ענגע טאלעראנצן, בשעת גראָבע חשבונות זענען גאנץ פריי. --- 8. א קורצע פארגלייך פון איטעראציע מעטאדן אין קורצן: - בייסעקשאן: מערסט סטאביל, קאנווערדזשירט באשטימט (מיטן צייכן ענדערונג), אבער שטייט. - פיקס-פונקט: זייער פשוט, אבער קאנווערדזשענס איז נישט שטענדיג גאראנטירט. - ניוטאן-ראפסאן: זייער שנעל, אבער פארלאנגט דעריוואטיוון און איז סענסיטיוו צו ערשטע געזאגן. - סעקאנט: קיין דעריוואטיוון נישט נויטיג, גאנץ שנעל, אבער קען זיין ווייניגער סטאביל ווי בייסעקשאן. אין פּראַקטיק, די אויסוואַל פון מעטאָדע דעפּענדס אויף דער נאַטור פון דער פונקציע, די פאַרפֿיגבאַרקייט פון דעריוואַטיוון, די נויט פֿאַר גיכקייט, און סטאַביליטעט. --- מסקנא איטעראַטיווע מעטאָדן זענען די רוקן-ביין פון נומעריש וואָרצל-געפֿינען פֿאַר ניט-לינעאַרע גלייכונגען. דורך קאַנסטרויִרן אַ סיקוואַנס פון איטעראַטיוולי דערהייַנטיקט אַפּראָקסימאַציעס, קענען מיר צוגיין צו דער לייזונג ווען אַנאַליטישע מעטאָדן זענען נישט פאַרפֿיגבאַר. פֿאַרשטיין קאָנווערגענץ, די אויסוואַל פון ערשט טרעף, און די סטאָפּינג קריטעריאָן זענען קריטיש פֿאַר איטעראַציע צו פּראָדוצירן ריכטיקע און עפֿעקטיווע וואָרצלען. אין פאַקטישע אַפּליקאַציעס, אַ קאָמבינירטע סטראַטעגיע איז אָפט געניצט: אָנהייבן מיט אַ סטאַביל מעטאָדע ווי בייסעקשאַן צו "פאַרשפּאַרן" די וואָרצל אינטערוואַל, און דאַן סוויטשינג צו ניוטאָן אָדער סעקאַנט צו פאַרגיכערן קאָנווערגענץ. דאָס דערגרייכט אַ וואָג צווישן פאַרלאָזלעכקייט און גיכקייט - צוויי זייער ווערטפול אַספּעקטן אין נומעריש קאַמפּיוטינג. --- אויב איר ווילט, קען איך לייגן אַ שריט-פֿאַר-שריט (נומעריש) בייַשפּיל פון יעדער פון די אויבן מעטאָדן צו מאַכן דעם אַרטיקל מער קאָנקרעט.
