אנליזה וקטורית – מציאת ערכי קיצון

חלק ראשון, שבו אנו מוצאים ערכי קיצון מקומיים

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

מה שמתעסקים איתו בחדו"א הוא סיטואציה פשוטה יחסית, שבה המערכת מתוארת על ידי פונקציה $latex f:\mathbb{R}\to\mathbb{R}$ שהיא "נחמדה", במובן זה שהיא גזירה. הרעיון הוא שאפשר להשתמש בנגזרת של $latex f$ כדי לאתר מייד את כל נקודות המקסימום ומינימום הנקודתיות של הפונקציה; ובתקווה, אם אין הרבה כאלו, בדיקה קצרה תעלה מה מהן היא המבוקשת שלנו (שעבורה הערך הוא הטוב ביותר אבסולוטית עבור בחירת פרמטרים חוקית). זה לא עובד תמיד טוב, אבל זה עובד טוב מספיק כדי שזה יהיה שימושי ביותר. הטכניקה עצמה מאוד פשוטה – בכל נקודת קיצון מקומית של הפונקציה, הנגזרת שלה חייבת להתאפס (ההפך לאו דווקא נכון). הסיבה פשוטה: ניקח למשל נקודת מקסימום מקומית. כל עוד הפונקציה "עדיין לא הגיעה" אל נקודת המקסימום אבל היא קרובה אליה, היא עולה אליה; ומייד אחרי נקודת המקסימום היא יורדת ממנה. זה אומר שממש לפני ההגעה לנקודת הקיצון הנגזרת היא חיובית ומייד אחרי היא שלילית. זה מכריח את הנגזרת באותה נקודה להיות "בו זמנית חיובית ושלילית", כלומר בהכרח 0.

בסדרת הפוסטים הנוכחית אנחנו מתעסקים באנליזה וקטורית, כלומר בפונקציות ממשיות מרובות משתנים. אז יש לנו פונקציה $latex f:\mathbb{R}^{n}\to\mathbb{R}$ ואנחנו רוצים לפתור את אותה בעיה – למצוא נקודות קיצון. קל לחשוב על הנקודות הללו בצורה ציורית כאשר $latex n=2$ – אפשר לחשוב על $latex f$ כאילו היא מתארת מפה טופוגרפית, במובן זה שלכל נקודה $latex \left(x,y\right)$ במפה הדו-ממדית נתון לנו גם הגובה של אותה נקודה, $latex f\left(x,y\right)$. נקודת מקסימום היא "פסגת הר" ונקודת מינימום היא "תחתית עמק". וזה מה שאנחנו רוצים למצוא.

הניחוש הנאיבי ביותר הוא שאותה אינדיקציה שעבדה במימד אחד תעבוד גם ב-$latex n$ ממדים: אם יש לפונקציה נקודת קיצון ב-$latex a\in\mathbb{R}^{n}$, אז $latex Df\left(a\right)=0$ (כאשר כאן $latex 0$ מציין את טרנספורמציית האפס, טרנספורמציה לינארית שמחזירה 0 עבור הכל). למרבה השמחה, הניחוש הנאיבי הזה עובד, ואוכיח זאת עוד רגע; למרבה הצער, בכל זאת יש חלק קשה יותר, והוא הסיווג של נקודות הקיצון הפוטנציאליות, שמטרתו להכריע מי הן נקודות הקיצון האמיתיות ומי הן אנומליות לא קשורות.

בואו ניתן כמה הגדרות פורמליות. כרגיל, כל מה שאנחנו מניחים על $latex f$ הוא שהיא מוגדרת על קבוצה פתוחה $latex U\subseteq\mathbb{R}^{n}$; אין צורך להניח שהיא מוגדרת בכל מקום. עבור $latex f$ כזו, אנחנו אומרים ש-$latex a\in U$ היא נקודת מקסימום מקומית אם קיימת סביבה $latex V$ של $latex a$ ב-$latex U$ ("סביבה" היא קבוצה פתוחה שמכילה את $latex a$) כך ש-$latex f\left(a\right)\ge f\left(x\right)$ לכל $latex x\in V$. באופן דומה מגדירים גם נקודות מינימום.

עכשיו, בואו נגדיר נקודה קריטית של $latex f$ בתור נקודה $latex a$ שבה $latex f$ אינה גזירה, או שהיא גזירה אבל $latex Df\left(a\right)=0$. המשפט הראשון שלנו אומר שאם $latex a$ היא נקודת קיצון אז היא נקודה קריטית; אבל יכולות להיות נקודות קריטיות שאינן נקודות קיצון, וקוראים להן נקודות אוכף (כי נקודה שנמצאת על מושב האוכף היא דוגמה יפה לנקודה שבה הנגזרת מתאפסת אבל היא אינה נקודת קיצון). האתגר יהיה לזהות, בהינתן נקודה קריטית, האם היא נקודת קיצון או לא.

ההוכחה שנקודת קיצון היא קריטית מתבססת על רדוקציה למקרה החד ממדי. אם הפונקציה לא גזירה בנקודה, אז על פי הגדרה הנקודה היא נקודת קיצון; לכן אני מניח ש-$latex Df\left(a\right)$ מוגדרת. כדי להראות ש-$latex Df\left(a\right)=0$ אני צריך להוכיח שהטרנספורמציה הזו מחזירה 0, לא משנה על איזה וקטור היא מופעלת. ומה זו "הפעלה" של הנגזרת על וקטור $latex u$? אם תזכרו, כי דיברנו על זה מזמן מזמן, זה מה שנותן לנו את הנגזרת המכוונת של $latex f$ בכיוון $latex h$, שהוגדרה כך: $latex \lim_{h\to0}\frac{f\left(a+hu\right)-f\left(a\right)}{h}$. עכשיו, בואו נגדיר פונקציה $latex \phi:\mathbb{R}\to\mathbb{R}$ על ידי $latex \phi\left(h\right)=f\left(a+hu\right)$. אז קיבלנו ש-

$latex Df\left(a\right)\cdot u=\lim_{h\to0}\frac{f\left(a+hu\right)-f\left(a\right)}{h}=\lim_{h\to0}\frac{\phi\left(h\right)-\phi\left(0\right)}{h}=\phi^{\prime}\left(0\right)$

עכשיו, אם $latex a$ היא נקודת קיצון של $latex f$, אז $latex 0$ היא נקודת קיצון של $latex \phi$, ולכן $latex \phi^{\prime}\left(0\right)=0$ (מהמשפט על נקודת קיצון במקרה החד ממדי), וסיימנו: ראינו ש-$latex Df\left(a\right)\cdot u=0$ לכל $latex u$ ולכן $latex Df\left(a\right)=0$. אז זה היה קל, כמובטח. מה הלאה?

בואו נראה שתי דוגמאות פשוטות כדי לקבל תחושה של נקודת קיצון אל מול נקודת אוכף. נתחיל מ-$latex f\left(x,y\right)=x^{2}+y^{2}$ – גרף של הפונקציה הזו נראה כמו מין קערית שכזו. הגרדיאנט קל לחישוב: $latex \nabla f=\left(2x,2y\right)$. הוא מתאפס בדיוק בנקודה אחת: $latex x=y=0$. לכן זו הנקודה היחידה שעשויה להיות נקודת קיצון, וקל לראות במקרה הזה שמדובר על נקודת מינימום. מסקנה: אין נקודות מקסימום בכלל, אחרת היינו מקבלים עוד נקודות קריטיות.

עכשיו בואו נעבור לדבר על האוכף. נתבונן ב-$latex f\left(x,y\right)=x^{2}y+y^{2}x$. הגרדיאנט שלה הוא $latex \nabla f=\left(2xy+y^{2},2yx+x^{2}\right)$. אז קיבלנו מערכת של שתי משוואות בשני נעלמים עבור $latex \nabla f=0$. אם $latex y=0$ אז $latex 2yx+x^{2}=0$ גורר ש-$latex x=0$ ולכן פרט לנקודת הקיצון הברורה ב-$latex x=y=0$ אנחנו יכולים להניח בהמשך הניתוח ש-$latex x\ne0$ וגם $latex y\ne0$ ולכן אפשר לחלק בהם. כעת, אם $latex 2xy+y^{2}=0$ נחלק ב-$latex y$ ונקבל $latex y=-2x$, ובאופן סימטרי $latex x=-2y$ מתקבל מהמשוואה השניה. קיבלנו $latex x=-2y=4x$, מה שגורר $latex x=0$, וזו סתירה להנחה שלנו שהוא שונה; לכן הנקודה הקריטית היחידה היא $latex x=y=0$. קל לראות שזו לא נקודת קיצון על ידי הסתכלות בישר $latex x=y$: עליו, הפונקציה היא $latex \phi\left(x\right)=f\left(x,x\right)=2x^{3}$ ולכן עבור $latex x>0$ נקבל ערך חיובי ועבור $latex x<0$ נקבל ערך שלילי, ומכאן ש-$latex \left(0,0\right)$ היא לא נקודת קיצון. זו סיטואציה דומה למה שקורה במימד אחד עם, למשל, $latex \tan x$.

אז איך מבדילים בין נקודת קיצון ובין "סתם" נקודה קריטית? בחדו"א של משתנה יחיד היה מבחן שעבד טוב במקרה שבו הפונקציה היא "נחמדה מספיק" – אם היא הייתה גזירה פעמיים, אז הנגזרת השניה שלה נתנה לנו את המידע הדרוש. אם הנגזרת השניה בנקודה הקריטית הייתה חיובית, הנקודה הייתה נקודת מינימום; אם היא הייתה שלילית, זו הייתה נקודת מקסימום; ואם היא הייתה 0 אז זו הייתה נקודה קריטית שאינה נקודת קיצון.

האינטואיציה כאן היתה פשוטה. בנקודת מינימום, רגע לפני הנקודה הפונקציה יורדת, כלומר בעלת נגזרת שלילית; רגע אחרי הנקודה הפונקציה עולה, כלומר בעלת נגזרת חיובית; זה אומר שבסביבות הנקודה, הנגזרת היא פונקציה עולה (בהתחלה שלילית, אחר כך 0, לבסוף חיובית). אם היא פונקציה עולה, אז הנגזרת שלה היא חיובית. שיקול דומה מטפל גם בנקודת מקסימום. ומה קרה ב-$latex \tan x$, למשל? הפונקציה היא עולה כל הזמן, כלומר הנגזרת היא חיובית כל הזמן (למעט בנקודה הקריטית עצמה, שם היא 0). אבל בהתחלה הנגזרת היא פונקציה יורדת (מתחילה מאוד גדולה ולאט לאט קטנה עד שהיא מגיעה ל-0) ואחרי הנקודה הקריטית היא מתחילה לעלות מחדש. כלומר, בנקודה הקריטית הנגזרת היא חיובית קודם וחיובית אחר כך, כלומר הנקודה הקריטית היא נקודת מינימום של הנגזרת, ולכן הנגזרת השניה היא 0.

היינו שמחים להכליל את הטיעון הזה ל-$latex n$ ממדים, וזה אכן מה שנעשה; אפשר להסיק את הקריטריון החד ממדי מהתוצאה שנראה. אבל למרבה הצער, הקריטריון שלנו יהיה מסובך משמעותית יותר מאשר במקרה החד משמעי, ודורש היכרות עם אלגברה לינארית. הקושי הוא בכך שאנחנו צריכים למצוא הכללה כלשהי ל"נגזרת השניה" של מימד אחד. הרי אצלנו "נגזרת" היא כבר לא פונקציה $latex f:\mathbb{R}^{n}\to\mathbb{R}$ כמו הפונקציה שאותה גזרנו; היא אופרטור שלכל נקודה במרחב מתאים טרנספורמציה לינארית (או מטריצה, איך שתעדיפו להסתכל על זה), ואי אפשר לגזור את זה. אז אנחנו משתמשים במשהו אחר – מטריצה $latex n\times n$ שכוללת את כל הנגזרות החלקיות המעורבות מסדר שני. המטריצה הזו נקראת הסיאן.

מה זו נגזרת חלקית אנחנו כבר יודעים – פשוט גוזרים את הפונקציה רק על פי משתנה בודד ומתייחסים ליתר בתור פרמטרים. ראינו כבר שאם $latex f$ גזירה אז הנגזרת שלה ניתנת לתיאור בתור וקטור הנגזרות החלקיות של $latex f$. נגזרת חלקית "מסדר שני" היא מה שמתקבל כשגוזרים נגזרת חלקית שוב, ו"מעורבת" אומר שאפשר לגזור שוב על פי כל אחד מהמשתנים. אני מסמן $latex \frac{\partial^{2}f}{\partial x\partial y}$ את מה שמתקבל כשאני גוזר את $latex f$ קודם כל לפי המשתנה $latex x$ ואז לפי המשתנה $latex y$. למשל, עבור פונקציית נקודת האוכף $latex f\left(x,y\right)=x^{2}y+y^{2}x$ אנחנו יודעים ש-$latex \frac{\partial f}{\partial x}=2xy+y^{2}$, ולכן אם נגזור שוב לפי $latex y$, נקבל ש-$latex \frac{\partial^{2}f}{\partial x\partial y}=2x+2y$.

מטריצת הסיאן מתקבלת באופן דומה – הכניסה בשורה ה-$latex i$ ובעמודה ה-$latex j$ שווה לנגזרת החלקית קודם לפי המשתנה $latex x_{i}$ ואחר כך לפי המשתנה $latex x_{j}$, כלומר $latex \left[H\right]_{ij}=\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}}$. אם נכתוב את ההסיאן של $latex f\left(x,y\right)=x^{2}+y^{2}$ נקבל $latex \left[\begin{array}{cc}2 & 0\\0 & 2\end{array}\right]$. אם נכתוב את ההסיאן של $latex f$ של נקודת האוכף, נקבל $latex \left[\begin{array}{cc}2y & 2x+2y\\2x+2y & 2x\end{array}\right]$. שימו לב שזו מטריצה סימטרית, כלומר יוצא שהנגזרת המעורבת קודם לפי $latex x$ ואז על פי $latex y$ שווה לנגזרת המעורבת קודם על פי $latex y$ ואז על פי $latex x$; זה לא מקרי וזה תמיד מתקיים אם שתי הנגזרות המעורבות הללו הן רציפות; אנחנו נניח מעכשיו ש-$latex f$ היא ב-$latex C^{2}$, אחרת המשפט שאני מתאר לא יהיה נכון.

עכשיו אפשר לנסח את הקריטריון שלנו בלשון שאותה יבינו מי שמכירים אלגברה לינארית: אם בנקודה הקריטית ההסיאן הוא מטריצה חיובית לחלוטין (Positive Definite Matrix), אז הנקודה הקריטית היא נקודת מינימום; ואם ההסיאן הוא מטריצה שלילית לחלוטין (Negative Definite Matrix) אז הנקודה הקריטית היא נקודת מקסימום; ואחרת אין לנו מושג מהי הנקודה הקריטית. מן הסתם המושג המרכזי פה הוא "חיובית/שלילית לחלוטין" שתכף אסביר, אבל למי שרוצים את התכל'ס, תנאי שקול לכך שמטריצה תהיה חיובית לחלוטין הוא שכל הערכים העצמיים שלה יהיו חיוביים, ואילו עבור שלילית לחלוטין, שכולם יהיו שליליים. זה מסביר את התוצאה בשתי הדוגמאות שראינו; במקרה הראשון קיבלנו מטריצה שהערך העצמי היחיד שלה הוא 2 החיובי, ולכן הנקודה הקריטית היא נקודת מינימום; ובמקרה השני ההסיאן ב-$latex x=y=0$ הוא מטריצת האפס, שהערך העצמי היחיד שלה הוא 0 שאינו חיובי או שלילי.

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

אנחנו יודעים שכל מטריצה $latex A$ מסדר $latex n\times n$ מעל שדה $latex \mathbb{F}$ מגדירה טרנספורמציה לינארית $latex T_{A}:\mathbb{F}^{n}\to\mathbb{F}^{n}$. אבל יש עוד סוג מעניין של העתקה בערך-לינארית שהמטריצה מגדירה: תבנית בילינארית, שהיא פונקציה $latex B_{A}:\mathbb{F}^{n}\times\mathbb{F}^{n}\to\mathbb{F}$ שלינארית בכל אחד משני הרכיבים שלה בנפרד, ומוגדרת על ידי $latex B\left(v,u\right)=v^{t}Au$ (כלומר, כופלים את המטריצה $latex A$ בוקטור העמודה $latex u$ כרגיל ומקבלים וקטור ב-$latex \mathbb{F}^{n}$, אבל אחר כך כופלים את התוצאה הזו גם בוקטור השורה $latex v^{t}$, דהיינו מבצעים מכפלה סקלרית של $latex v$ ושל $latex Au$). כל תבנית בילינארית מגדירה, בתורה, גם פונקציה $latex g:\mathbb{F}^{n}\to\mathbb{F}$ על ידי $latex g_{A}\left(v\right)=B_{A}\left(v,v\right)=v^{t}Av$ (במילים, כופלים סקלרית את $latex v$ בתמונה של $latex v$ על ידי הטרנספורמציה הלינארית שמוגדרת על ידי $latex A$). לפונקציה כזו קוראים תבנית ריבועית והיא מה שמעניין אותנו כאן. דוגמה פשוטה לתבנית בילינארית היא מכפלה פנימית, ודוגמה פשוטה לתבנית ריבועית שמוגדרת על ידה היא נורמה (כמעט; כזכור, נורמה היא השורש של מכפלה פנימית של וקטור עם עצמו). תבניות בילינאריות וריבועיות מופיעות באינספור מקומות במתמטיקה, הגם שהן קצת פחות נפוצות מטרנספורמציות לינאריות, ולרוב מגיעים אליהן רק בקורס שני באלגברה לינארית.

עכשיו בואו נעזוב את האלגברה הלינארית הכללית ונזכור שאנחנו מדברים על המקרה שבו $latex \mathbb{F}=\mathbb{R}$. בממשיים יש יחס סדר – אפשר להגיד "חיובי" ו"שלילי" (אפילו ב-$latex \mathbb{C}$ אי אפשר להגיד דברים כאלו). זה מוביל אותנו להגדרה שאנחנו רוצים – $latex A$ היא מטריצה חיובית לחלוטין אם התבנית הריבועית שהיא מגדירה מקיימת ש-$latex g_{A}\left(x\right)>0$ לכל $latex x\ne0$ (עבור $latex x=0$ תמיד נקבל $latex g_{A}\left(x\right)=0$, כמובן). בדומה $latex A$ היא שלילית לחלוטין אם $latex g_{A}\left(x\right)<0$ לכל $latex x\ne0$. עבור מטריצה מסדר $latex 1\times1$ הקריטריון הזה שקול לכך שהכניסה היחידה של המטריצה תהיה חיובית/שלילית (כי אם $latex A=\left[a\right]$ אז נקבל ש-$latex g_{A}\left(x\right)=a\cdot x^{2}$) ולכן קיבלנו פה הכללה של התוצאה עבור $latex n=1$.

כדי להבין למה זה עובד ומאיפה $latex H$ הגיעה בכלל אני צריך לשלוף מהכובע שפן שלפחות לעת עתה בחרתי לא לתת לו פוסט, אבל אולי בעתיד כן – פולינומי טיילור. תיארתי אותם פעם בבלוג במקרה החד ממדי, וכנראה שכדאי לתאר אותם בפירוט גם במקרה הרב ממדי, אבל לבינתיים אסתפק בהסבר קצר. כזכור, פולינום טיילור "רגיל" מאפשר לנו לקרב פונקציות מסובכות על ידי פולינומים שמחושבים מתוך כל הנגזרות של הפונקציה בנקודה מסויימת ש"סביבה" מפתחים אותה. פורמלית, $latex f\left(x_{0}+h\right)=\sum_{k=0}^{n}\frac{f^{\left(k\right)}\left(x_{0}\right)}{k!}h^{k}+R_{n+1}\left(x_{0},h\right)$, כאשר $latex \sum_{k=0}^{n}\frac{f^{\left(k\right)}\left(x_{0}\right)}{k!}h^{k}$ הוא הפולינום, ואילו $latex R_{n+1}\left(x_{0},h\right)$ היא פונקציית ה"שארית" שמתארת את הטעות של הפולינום (ומן הסתם לב העניין הוא לחסום את הגודל שלה, מה שיוצא שונה עבור פונקציות שונות ונקודות פיתוח שונות). לפעמים פשוט כותבים טור חזקות אינסופי, $latex \sum_{n=0}^{\infty}\frac{f^{\left(n\right)}\left(x_{0}\right)}{n!}h^{n}$, אבל עם הכתיב הזה צריך להיזהר כי לא בהכרח ברור עבור אילו ערכים של $latex h$ הטור הזה מתכנס בכלל (עבור $latex h=0$ הוא מתכנס תמיד, אבל פרט לכך? הדיון על רדיוס ההתכנסות של טורי חזקות הוא מעניין בפני עצמו וצריך להציג אותו בבלוג מתישהו) וגם לא ברור שאפילו אם הטור מתכנס, אז $latex f\left(x_{0}+h\right)$ שווה לסכום שלו.

פולינומי טיילור של פונקציות $latex f:\mathbb{R}^{n}\to\mathbb{R}$ עובדים בצורה דומה, אבל כפי שאתם מנחשים, צריך לזרוק פנימה את כל הנגזרות החלקיות וזה יוצא מתוסבך למדי לכתיבה בלי שמסכימים מראש על כל מני קיצורים. בכל זאת אני לא יכול להתאפק ואציג את הטור המלא של פיתוח סביב $latex \left(a_{1},\dots,a_{n}\right)$:

$latex \sum_{k_{1}=0}^{\infty}\cdots\sum_{k_{n}=0}^{\infty}\frac{\partial^{k_{1}}}{\partial x_{1}^{k_{1}}}\cdots\frac{\partial^{k_{n}}}{\partial x_{n}^{k_{n}}}f\left(a_{1},\dots,a_{n}\right)\frac{h_{1}^{k1}\cdots h_{n}^{k_{n}}}{k_{1}!\cdots k_{n}!}$

או במילים: כל איבר בטור הזה מתקבל על ידי כך שגוזרים את $latex f$ מספר מסויים של פעמים על פי כל משתנה, כופלים את התוצאה בחזקות מתאימות של כניסות $latex \left(h_{1},\dots,h_{n}\right)$ ומחלקים בעצרת מתאימה. בואו נראה דוגמה פשוטה עבור פונקציה $latex f\left(x,y\right)$ שהיא ב-$latex C^{2}$ ולכן $latex \frac{\partial^{2}f}{\partial x\partial y}=\frac{\partial^{2}f}{\partial y\partial x}$; נפתח את הטור עד סדר שני, כלומר עד וכולל ערכי ה-$latex k$ שמקיימים $latex k_{1}+k_{2}=2$:

$latex f\left(x+h_{1},y+h_{2}\right)=f\left(x,y\right)+\frac{\partial f}{\partial x}\left(x,y\right)h_{1}+\frac{\partial f}{\partial y}\left(x,y\right)h_{2}+\frac{\partial^{2}f}{\partial x^{2}}\left(x,y\right)\frac{h_{1}^{2}}{2}+\frac{\partial^{2}f}{\partial y^{2}}\left(x,y\right)\frac{h_{2}^{2}}{2}+\frac{\partial^{2}f}{\partial x\partial y}\left(x,y\right)h_{1}h_{2}+R_{3}\left(h_{1},h_{2}\right)$

ואם יש לנו $latex n$ משתנים, הכתיב נשאר דומה:

$latex f\left(x_{1}+h_{1},\dots,x_{n}+h_{n}\right)=f\left(x_{1},\dots,x_{n}\right)+\sum_{i=1}^{n}\frac{\partial f}{\partial x_{i}}\left(x_{1},\dots,x_{n}\right)h_{i}+\frac{1}{2}\sum_{i,j=1}^{n}\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}}\left(x_{1},\dots,x_{n}\right)h_{i}h_{j}+R_{3}\left(h_{1},\dots,h_{n}\right)$

כאן אנחנו קצת מרמים בסימון אבל מתקנים את זה בו זמנית: למשל, בסכום מופיעים גם $latex \frac{\partial^{2}f}{\partial x_{1}\partial x_{2}}$ וגם $latex \frac{\partial^{2}f}{\partial x_{2}\partial x_{1}}$ למרות שהאיבר הזה (אלו שתי הצגות שונות לאותו איבר, כי אמרתי שבמקרה שלנו הנגזרות המעורבות שוות) אמור להופיע רק פעם אחת. אז יש לי ספירה כפולה, אבל זה מתקזז עם הכפל ב-$latex \frac{1}{2}$ שהוספתי שם (אם תשימו לב, בנוסחה המקורית אם גזרנו פעמיים לפי אותו משתנה צריך לכפול ב-$latex \frac{1}{2!}$ ואם גזרנו לפי שני משתנים שונים לא עושים את זה).

את כל זה אפשר לכתוב אפילו עוד יותר בקיצור:

$latex f\left(x+h\right)=f\left(x\right)+\nabla f\left(x\right)\cdot h+\frac{1}{2}H_{x}\left(h\right)+R_{3}\left(h\right)$

במילים אחרות, הגרדיאנט של $latex f$ הוא "האיבר הראשון" בפיתוח טיילור של $latex f$, וההסיאן $latex H$ הוא "האיבר השני". האנלוגיה למקרה החד ממדי (שבו האיבר הראשון בפיתוח הוא הנגזרת הראשונה, והאיבר השני הוא הנגזרת השניה) מובהקת כאן.

איך כל זה רלוונטי לענייננו? כזכור, אנחנו מניחים שב-$latex x$ יש ל-$latex f$ נקודה קריטית ורוצים לסווג אותה. נקודה קריטית פירושו של דבר ש-$latex \nabla f\left(x\right)=0$, כך שאפשר לכתוב את פיתוח הטיילור גם בתור

$latex f\left(x+h\right)-f\left(x\right)=\frac{1}{2}H_{x}\left(h\right)+R_{3}\left(h\right)$

נניח שההסיאן ב-$latex x$ הוא חיובי לחלוטין, ולכן על פי המשפט אמור לנבוע מכך ש-$latex x$ היא נקודת מינימום. אם $latex x$ היא נקודת מינימום של $latex f$, אנחנו מצפים שאגף שמאל יהיה חיובי עבור כל ה-$latex h$-ים בסביבה קרובה מספיק של $latex x$. ומה קורה באגף ימין? יש לנו קרב ענקים בין ההסיאן ובין $latex R_{3}\left(h\right)$, השארית. כאן מגיע טיעון אינפי סטנדרטי – אם ניקח $latex h$ "מספיק קטן" אז מצד אחד השארית תהיה קטנה מאוד, ומצד שני ההסיאן יחזיר לנו ערך שהוא יחסית גדול וחיובי, והערך הזה "ינצח" בתחרות. אני אדלג על המשך ההוכחה כי הוא טכני באופן סטנדרטי ואומר בדיוק את זה; הפואנטה המרכזית היא שבגלל שההסיאן הוא פונקציה "נחמדה" (בילינארית) מקבלים שקיים קבוע $latex M$ כלשהי כך ש-$latex H\left(h\right)\ge M\|h\|^{2}$ לכל $latex h$, וזה נותן לנו את ה"יחסית גדול וחיובי" שלנו. הפרטים הטכניים פחות קריטיים פה – מה שמעניין בסיפור הזה, לטעמי, הוא מאיפה ההסיאן הזה צץ בכלל; כשברור שזה הרכיב השני בפיתוח הטיילור של הפונקציה, ושהרכיב הראשון איננו עמנו עוד כי אנחנו בנקודה קריטית, העניין נהיה מאוד ברור.

חלק שני, שבו כל העסק נהיה מאולץ

בתחילת הפוסט אמרתי שבבעיות אופטימיזציה יש לנו לעתים קרובות אילוצים על המערכת, כלומר לא כל פרמטר הוא חוקי. זה מגדיל מייד את רמת הקושי של הבעיה שלנו ועל פניו הופך את כל הטכניקה שראינו עד כה לחסרת תועלת. אתן דוגמה פשוטה. נסתכל על הפונקציה $latex f:\mathbb{R}^{2}\to\mathbb{R}$ המוגדרת על ידי $latex f\left(x,y\right)=x$. בבירור אין לה לא נקודת מינימום ולא נקודת מקסימום בשום מקום ולכן הטכניקה שראינו קודם לא תסייע לנו עם העיסוק בה בכלל. מצד שני, אם נוסיף למערכת את האילוץ שהקלטים ל-$latex f$ חייבים להילקח רק ממעגל היחידה, אז ברור שפתאום יש ל-$latex f$ מקסימום ב-$latex \left(1,0\right)$ ומינימום ב-$latex \left(-1,0\right)$. אבל איך מוצאים את זה?

לפני שנפתור את הבעיה הזו, צריך להבין מה המשמעות של "אילוץ". עבורנו זה אומר שנתונה פונקציה $latex g:\mathbb{R}^{n}\to\mathbb{R}$ כלשהי ונתון $latex c\in\mathbb{R}$, ואנחנו מגדירים אילוץ על ידי המשוואה $latex g\left(x\right)=c$. כלומר, מותר לחפש את הפתרון רק בקרב ה-$latex x$-ים שמקיימים $latex g\left(x\right)=c$. בדוגמה שלי, $latex g\left(x,y\right)=x^{2}+y^{2}$ ואילו $latex c=1$. כפי שבטח כבר ברור לכם, השיטה הזו להבעת אילוצים היא נוחה מאוד ומאפשרת לתאר שלל יצורים גאומטריים (ראינו כרגע מעגל; קו ישר מתואר על ידי $latex g\left(x,y\right)=ax-by$ עבור $latex a,b$ כלשהם, וכדומה).

כעת, נניח ש-$latex g$ היא פונקציה "נחמדה" – גזירה. נסמן ב-$latex S$ את המרחב שמוגדר על ידי $latex S=\left\{ x\in\mathbb{R}^{n}\ |\ g\left(x\right)=c\right\} $ (מעכשיו אקרא לו "משטח" כי בתלת מימד משוואות כאלו מגדירות משטחים; שם מדויק יותר למקרה הכללי שבו אני עוסק הוא יריעה אבל זה מושג לא טריוויאלי ואני לא רוצה להיכנס להגדרה שלו כרגע), וניקח $latex x_{0}\in S$ כלשהו. הנה אבחנה מיידית שבלבלה אותי בצורה יוצאת דופן כשרק למדתי את הנושא הזה: $latex \nabla g\left(x_{0}\right)$ הוא אורתוגונלי ל-$latex S$ בנקודה $latex x_{0}$. הגרדיאנט של הפונקציה שמגדירה את המשטח ניצב למשטח באותה נקודה. למה זה מבלבל? כי לעתים קרובות נהוג להגדיר את הגרדיאנט של פונקציה בנקודה כלשהי בתור הוקטור שמצביע על הכיוון שבו היא "הכי תלולה". אם הגרדיאנט ניצב למשטח, הוא מצביע על כיוון שבו הפונקציה בכלל לא גדלה, וזה נראה הכי לא נכון שרק אפשר. אז למה זה מסתדר?

זה מסתדר כי עשיתי מיש-מש מכל העסק. הגרדיאנט לא ניצב לפונקציה; הוא ניצב למשטח שהפונקציה מגדירה בצורה מסויימת. מה שבלבל אותי בשעתו הוא שאפשר להגדיר משטחים בשתי דרכים שונות. דרך אחת, כללית פחות, היא לכתוב $latex z=f\left(x,y\right)$ ובכך לתאר את המשטח $latex S=\left\{ \left(x,y,f\left(x,y\right)\right)\ |\ x,y\in\mathbb{R}^{2}\right\} $; הדרך השניה, הכללית יותר, היא לכתוב $latex S=\left\{ \left(x,y,z\right)\ |\ F\left(x,y,z\right)=c\right\} $. שימו לב שבדרך הראשונה אנחנו משתמשים בפונקציה של שני משתנים ובשניה בפונקציה של שלושה משתנים כדי להגדיר את אותו הדבר – משטח ב-$latex \mathbb{R}^{3}$. אם יש לי פונקציה $latex f:\mathbb{R}^{2}\to\mathbb{R}$ ואני רוצה להציג את המשטח שמוגדר על ידה בדרך הראשונה בעזרת דרך ההצגה השניה, אני פשוט אגדיר $latex F\left(x,y,z\right)=z-f\left(x,y\right)$ ו-$latex c=0$; לכן דרך ההצגה השניה כללית יותר. היא כללית יותר ממש (כלומר, יש דברים שאי אפשר לעשות בדרך הראשונה) כי למשל אני יכול לתאר את כדור היחידה על ידי $latex F\left(x,y,z\right)=x^{2}+y^{2}+z^{2}$ ו-$latex c=1$, אבל אין לי דרך לעשות את זה באמצעות הצגת קואורדינטת ה-$latex z$ כפונקציה של שתי האחרות (כי עבור אותם $latex x,y$ עשויים להיות שני ערכי $latex z$ אפשריים שונים על המשטח).

הנה הוכחה זריזה לכך שהגרדיאנט ניצב למשטח שהפונקציה מגדירה. הרעיון הוא לקחת מסלול כלשהו במשטח שעובר דרך $latex x_{0}$ ולהראות שהגרדיאנט ב-$latex x_{0}$ ניצב אליו. בלי להיכנס לעובי ההגדרות, מסלול הוא פונקציה גזירה $latex c:\left[0,1\right]\to\mathbb{R}^{n}$, ומסלול במשטח $latex S\subseteq\mathbb{R}^{n}$ מקיים את הדרישה ש-$latex c\left(\left[0,1\right]\right)\subseteq S$, ונניח ש-$latex c\left(0\right)=x_{0}$. עכשיו, הרעיון במסלול שעובר דרך $latex S$ הוא שכל נקודה בו מקיימת את האילוץ שמגדיר את $latex S$. נניח שהאילוץ הזה הוא $latex F\left(x\right)=c$, אז $latex F\left(c\left(t\right)\right)=c$ לכל $latex t\in\left[0,1\right]$. עכשיו אפשר להשתמש בכלל השרשרת, לגזור ולקבל ש-$latex DF\left(c\left(0\right)\right)\cdot Dc\left(0\right)=0$, או בסימון קצת שונה, ש-$latex \nabla F\left(x_{0}\right)\cdot c^{\prime}\left(0\right)=0$. עכשיו, $latex c^{\prime}\left(0\right)$ הוא בדיוק שיפוע המשיק ל-$latex c$ ב-$latex x_{0}$, ואילו $latex \nabla F\left(x_{0}\right)$ הוא הגרדיאנט של $latex F$, וקיבלנו שהמכפלה הפנימית שלהם היא 0 – כלומר, הם ניצבים.

עכשיו בואו נפתור את הבעיה של אופטימיזציה-עם-אילוצים. הפתרון הוא סוג של הכללה של מה שראינו קודם. קודם בדקנו איפה הגרדיאנט של $latex f$ מתאפס. ההכללה שלנו תהיה לבדוק איפה הגרדיאנט של $latex f$ שווה לצירוף לינארי של האילוצים. המקדמים של האילוצים נקראים "כופלי לגראנז'", והשיטה נקראת על שמם – שיטת כופלי לגראנז'.

הנה הניסוח הפורמלי. נניח שיש לנו פונקציה $latex f:\mathbb{R}^{n}\to\mathbb{R}$ שהיא מה שאנחנו רוצים לאפטמז, ופונקציות אילוצים $latex g_{1},\dots,g_{k}:\mathbb{R}^{n}\to\mathbb{R}$ עם קבועים $latex c_{1},\dots,c_{k}$ שמגדירות קבוצה $latex S$ (כלומר, האילוץ הוא $latex g_{i}\left(x\right)=c_{i}$ עבור $latex 1\le i\le k$). נניח ש-$latex x_{0}$ היא נקודה שמקיימת את כל האילוצים ($latex g_{i}\left(x_{0}\right)=c_{i}$) וש-$latex \nabla g_{i}\left(x_{0}\right)\ne0$, ושיש ל-$latex f|_{S}$ מקסימום או מינימום מקומי ב-$latex x_{0}$ (הסימון $latex f|_{S}$ פירושו "$latex f$ מצומצמת ל-$latex S$"), אז קיימים $latex \lambda_{1},\dots,\lambda_{k}\in\mathbb{R}$ כך ש-$latex \nabla f\left(x_{0}\right)=\lambda_{1}\nabla g_{1}\left(x_{0}\right)+\dots+\lambda_{k}\nabla g_{k}\left(x_{0}\right)$. זה אומר שכשאנחנו מחפשים נקודות קיצון, אנחנו מקבלים מערכת של משוואות שנקודות הקיצון חייבות להיכלל בפתרונות שלה.

בואו נראה איך זה עובד במקרה של דוגמת המעגל שנתתי קודם. מכיוון ש-$latex f\left(x,y\right)=x$ אז $latex \nabla f=\left(1,0\right)$, ומכיוון ש-$latex g\left(x,y\right)=x^{2}+y^{2}$, אז $latex \nabla g=\left(2x,2y\right)$. משוואת כופלי לגראנז' נותנת לנו כאן את המשוואה $latex \left(1,0\right)=\lambda\left(2x,2y\right)$ שמתורגמת בתורה לשתי משוואות פשוטות:

$latex 2x\lambda=1$

$latex 2y\lambda=0$

מהמשוואה הראשונה ברור ש-$latex \lambda\ne0$ ולכן מהשניה קיבלנו ש-$latex y=0$ הוא הכרחי. הנקודות היחידות שמקיימות את האילוץ $latex g\left(x,y\right)=1$ ומקיימות $latex y=0$ הן $latex \left(1,0\right)$ ו-$latex \left(-1,0\right)$ ועבור כל אחת מהן יש, כמובן, $latex \lambda$ שפותר את המשוואה. קיבלנו ששתי אלו הן נקודות הקיצון שלנו, וזה אכן מה שהתחלתי ממנו.

חסרים לנו עוד שני דברים – אינטואיציה למה כל זה עובד, והוכחה. את ההוכחה המלאה אני לא אביא כאן, ובמקום זה אתן דגש חזק על הרעיונות הכלליים. הדבר הראשון שצריך להבין הוא שנתתי למעלה את הגרסה ה"שימושית" של המשפט – קחו את הגרדיאנט של $latex f$, אז הוא צירוף לינארי של הגרדיאנטים של האילוצים. זה משהו שקל להשתמש בו פרקטית, אבל זו לאו דווקא הדרך הקלה ביותר לחשוב על המשפט. אז הנה ניסוח כללי יותר של המשפט: אם $latex S$ הוא משטח, $latex x_{0}\in S$ היא נקודה על המשטח ו-$latex f$ היא פונקציה כך של-$latex f|_{S}$ יש נקודת קיצון ב-$latex x_{0}$, אז המישור המשיק ל-$latex S$ בנקודה $latex x_{0}$ מוכל בגרעין של $latex \nabla f\left(x_{0}\right)$. אם אני אסמן את המישור המשיק ל-$latex S$ בנקודה $latex x_{0}$ בתור $latex T_{x_{0}}S$ אז אפשר לכתוב פשוט $latex T_{x_{0}}S\subseteq\ker\left(\nabla f\left(x_{0}\right)\right)$ (אתם אמורים להכיר גרעין כי זה מושג בסיסי באלגברה לינארית; אוסף כל הנקודות שמאפסות את הטרנספורמציה הלינארית $latex \nabla f\left(x_{0}\right)$).

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

הדרך להגיע מהניסוח הזה לניסוח שהצגתי קודם היא דרך תוצאה לא מרתקת במיוחד באלגברה לינארית: נניח ש-$latex f:\mathbb{R}^{n}\to\mathbb{R}$ היא טרנספורמציה לינארית ו-$latex G:\mathbb{R}^{n}\to\mathbb{R}^{m}$ היא טרנספורמציה לינארית, אז $latex \ker G\subseteq\ker f$ אם ורק אם קיימים $latex \lambda_{1},\dots,\lambda_{m}$ כך ש-$latex f=\sum\lambda_{i}G_{i}$, כאשר $latex G_{i}$ הוא ההטלה של $latex G$ לרכיב ה-$latex i$, כלומר $latex G_{i}\left(a\right)=\left[G\left(a\right)\right]_{i}$.

מה שמעניין הוא להבין מה האינטואיציה שמאחורי המשפט הכללי. למה שהוא יהיה נכון? הנקודה הקריטית היא שאם $latex S$ הוא משטח שמוגדר בצורה "נחמדה מספיק" אז בהינתן נקודה $latex x_{0}\in S$ כלשהי, יש סביבה של $latex x_{0}$ שנראית כמו תת-מרחב לינארי של $latex \mathbb{R}^{n}$. ההגדרה של "יריעה", שאני חומק ממנה בפוסט הזה, מפרמלת את הרעיון הזה; בואו נראה דוגמה פשוטה. את המעגל שלנו מתחילת הפוסט אפשר לתאר באמצעות פרמטריזציה: פונקציה גזירה $latex p:\mathbb{R}\to\mathbb{R}^{2}$ שמוגדרת על ידי $latex p\left(t\right)=\left(\sin t,\cos t\right)$. על ה-$latex p$ הזו אפשר להרכיב את $latex f$ שלנו, שהיא הפונקציה שאנחנו מנסים לאפטמז, ולקבל את הפונקציה $latex \varphi\left(t\right)=f\left(p\left(t\right)\right)=\sin t$. קיבלנו פונקציה במשתנה בודד שמוגדרת מעל $latex \mathbb{R}$, כך שאפשר לחפש לה מקסימום ומינימום בדרך הרגילה – גוזרים ומשווים לאפס. תנסו, תראו שזה עובד.

אז גם באופן כללי, אם יש לנו פרמטריזציה של $latex S$ בסביבה של $latex x_{0}$ מצבנו טוב. בואו נניח ש-$latex p:\mathbb{R}^{n}\to\mathbb{R}^{n}$ היא פרמטריזציה שכזו; פירוש הדבר הוא ש-$latex p\left(\mathbb{R}^{n}\right)$ הוא סביבה של $latex x_{0}$ ב-$latex S$. אנחנו מניחים שב-$latex x_{0}$ יש ל-$latex f$ נקודת קיצון מקומית; בואו נסמן ב-$latex a\in\mathbb{R}^{n}$ נקודה שמקיימת $latex p\left(a\right)=x_{0}$. אז לפונקציה $latex f\left(p\left(t\right)\right)$ יש נקודת קיצון מקומית ב-$latex a$, מה שאומר ש-$latex D\left[f\left(p\left(a\right)\right)\right]$ תהיה טרנספורמציית האפס. מכלל השרשרת נובע שזה אומר ש-$latex Df\left(p\left(a\right)\right)\cdot Dp\left(a\right)$ היא טרנספורמציית האפס.

עכשיו, את $latex Df\left(p\left(a\right)\right)$ אנחנו מכירים בסימון קצת שונה. ראשית, $latex p\left(a\right)=x_{0}$. שנית, מכיוון ש-$latex f$ היא פונקציה שמחזירה סקלר, אני מסמן את $latex Df$ ב-$latex \nabla f$. כלומר, $latex Df\left(p\left(a\right)\right)=\nabla f\left(x_{0}\right)$ הישן והטוב.

שנית, מה זה $latex Dp\left(a\right)$? זכרו ש-$latex p$ היא פונקציה שמגדירה לנו משטח; לכן $latex Dp\left(a\right)$ מתארת את המישור המשיק למשטח בנקודה $latex p\left(a\right)=x_{0}$, מה שסימנתי בתור $latex T_{x_{0}}S$ (כן, זה היה נפנוף ידיים). כלומר, לכל קלט שהיא מקבלת, $latex Dp\left(a\right)$ מחזירה לנו נקודה ששייכת ל-$latex T_{x_{0}}S$.

עכשיו, ראינו שההרכבה של $latex \nabla f\left(x_{0}\right)$ על $latex Dp\left(a\right)$ היא זהותית אפס. זה אומר שלכל קלט ש-$latex Dp\left(a\right)$ מקבלת, הפלט שלה (נקודה ב-$latex T_{x_{0}}S$) יגרום ל-$latex \nabla f\left(x_{0}\right)$ להחזיר אפס. מכיוון ש-$latex Dp\left(a\right)$ היא פונקציה על כל $latex T_{x_{0}}S$ נקבל את התוצאה – $latex T_{x_{0}}S\subseteq\ker\nabla f\left(x_{0}\right)$. הפורמליזם פה לא היה מלא אבל אני מקווה שהרעיון ברור עכשיו.

6 תגובות על הפוסט “אנליזה וקטורית – מציאת ערכי קיצון

  1. קודם כל תודה על הפוסט!
    שאלה קטנה ולא קשורה לנושא העיקרי – כתבת שב-R יש יחס סדר ושאפשר להגדיר דבר כזה ב-C. זאת לא סתרה למשפט שקובע שכל שדה סדור ארכימדי ושלם, איזומורפי ל-R (ו-C לא איזומורפי ל-R למשל כי הוא סגור אלגברית)?

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

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

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

  4. איך מוכיחים את הלמה מלינארית? רפרנס יספיק. (הכיוון שאם פונקציה לינארית מתאפסת בכל האפסים המשותפים של פונקציות לינאריות אז היא צירוף לינארי שלהן)

  5. היי גדי,
    כתבת "ואם היא הייתה 0 אז זו הייתה נקודה קריטית שאינה נקודת קיצון."
    זה לא נכון, ראה y=x⁴ .

כתיבת תגובה

האימייל לא יוצג באתר.