תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר
תאריך עדכון אחרון: 29 ביוני 2013
תוכנה 1: MATLAB
הערה: ב־MATLAB בסוף כך שורת הוראה יש להוסיף ; על מנת שלא תתבצע הדפסה, אך אם רוצים הדפסה אין להוסיף ; בסוף השורה.
עבודה בסיסית ב־MATLAB
משתנים
משתנה הוא סמל המסמן כמות, איבר של קבוצה, או ערך לוגי, העשויים להשתנות (מתוך ויקיפדיה).
השמה למשתנה - הכנסת ערך אליו. ב־MATLAB (דוגמות):
x=3
z=pi
w=4+5*i
פעולות בסיסיות עם משתנים (a,b מציינים מספרים):
| הפעולה | הסימן ב־MATLAB |
|---|---|
| חיבור | a+b |
| חיסור | a-b |
| כפל | a*b |
| חילוק | / |
| חזקה | a^b |
| לוגריתם טבעי (ln) | (log(a |
| שורש ריבועי | (sqrt(a |
| ערך שלם / רצפה | (floor(a |
| שארית חלוקה (רק עבור שלמים) | (mod(a,b |
להוספת הערה בסוף שורה כותבים את הסימן % ולאחריו את ההערה.
בחילוק שני מספרים שלמים, המנה היא (floor(x,y והשארית היא (mod(x,y.
משתנים קבועים: i,j - ה־i המרוכב, [math]\displaystyle{ \sqrt{-1} }[/math], pi - פאי.
הדפסת ערך משתנה:
(disp(value
מטריצות
פעולות בסיסיות עם משתנים (A,B מציינים מטריצות):
| הפעולה | ההוראה ב־MATLAB |
|---|---|
| הגדרת מטריצת אפסים בגודל [math]\displaystyle{ m\times n }[/math] | (A=zeros(m,n |
| איבר בשורה x ובעמודה y | (A(x,y |
| חיבור מטריצות | A+B |
| חיסור מטריצות | A-B |
| כפל במובן מטריצות | A*B |
| כפל איבר־איבר | A.*B |
| חילוק (כפל בהופכית) | A/B |
| חילוק איבר־איבר | A./B |
| מימדי מטריצה (וקטור) | (size(A |
| שחלוף (transpose) | 'A |
ועוד...
הערה 1: האינדקסים במטריצה מתחילים מ־1.
הערה 2: אם נעשתה פנייה לאיבר שאינו במערך והושם בו ערך, MATLAB ירחיב באופן אוטומטי את המערך, ובמקומות שנוספו יושמו אפסים.
מערכים: מטריצה מגודל nx1
פעולות בסיסיות עם מערכים (v מייצג וקטור, m,n,p מייצגים מספר כלשהו):
| הפעולה | ההוראה ב־MATLAB |
|---|---|
| אתחול (הצבת אפסים) | (v=zeros(n,1 |
| האיבר ה־n-י | (v(n |
| אורך הוקטור | (length(v |
| וקטור המכיל את המספרים הטבעיים עד n | v=1:n |
| וקטור המכיל את כל המספרים מ־m עד n בקפיצות p | v=m:p:n |
דוגמה: בכתיבה 1:5 יווצר הווקטור [5 4 3 2 1]. בכתיבה 1:2:5 יווצר הוקטור [5 3 1].
ניתן להגדיר וקטור גם באופן הבא: [w=[3 9 10 11 4 (במקום רווחים ניתן להשתמש בפסיקים). על מנת להגדיר מטריצה באופן דומה מוסיפים ; כדי לרדת שורה.
ניתן לקבל וקטור מאינדקסים מסוימים. למשל, עבור w שהוגדר,
[w(1:2:5)=w([1 3 5])=[3 10 4
פעולות בוליאניות
פעולות בוליאניות מחזירות 0 (שקר) או 1 (אמת). דוגמות (a,b מספרים):
| הפעולה | הסימון ב־MATLAB |
|---|---|
| האם שני ערכים שווים | a==b |
| קטן | ab |
| קטן שווה | a<=b |
| גדול שווה | a>=b |
| אינו שווה | =~ |
&& - וגם, || - או
תנאים
תנאי פשוט:
(תנאי) if
הוראות לביצוע
end
תנאי מורכב:
(תנאי) if
(הוראות לביצוע)
else
(הוראות לביצוע)
end
תנאי יותר מורכב:
(תנאי) if
(הוראות לביצוע)
elseif
(הוראות לביצוע)
else
(הוראות לביצוע)
end
לולאת for
לולאת for - ביצוע אותו רצף הוראות מספר ידוע מראש של פעמים.
תכנות:
(וקטור המכיל את ערכי i הדרושים)=for i
(הוראות לביצוע)
end
הערה: אמנם i הוא קבוע, אך ניתן להציב בו ערך. על מנת להחזירו להיות ה־i המרוכב, נכתוב את ההוראה clear i.
לולאת while
לולאת while - ביצוע אותו רצף הוראות מספר שאינו ידוע מראש של פעמים אך עם תנאי לעצירה.
תכנות:
(תנאי לעצירה, תנאי בוליאני) while
(הוראות לביצוע)
end
תרגילים
תרגיל 1 - עצרת
חשבו את [math]\displaystyle{ 1000! }[/math].
פתרון 1 - לולאת for:
;n=1 for i=2:1000 ;n=n*i end ;(disp(n
פתרון 2 - לולאת while:
;n=1 ;i=1 while i<=1000 ;n=n*i ;i=i+1 end ;(disp(n
תרגיל 2 - מספרים ראשוניים
צרו וקטור המכיל את כל המספרים הראשוניים מ־1 עד 1000
;כמה ראשוניים מצאנו % found=0
;וקטור עם המספרים הראשוניים % []=primes
for p=1:1000
;yesno=1
;k=2
while k<=sqrt(p) && yesno==1
if mod(p,k)==0
;yesno=0
end
;k=k+1
end
if yesno==1
;found=found+1
;primes(found)=p
end
end
תרגיל 3 - פירוק מספר שלם לגורמים ראשוניים
פרקו מספר שלם [math]\displaystyle{ k\leq 1000 }[/math] לגורמים ראשוניים (אפשר להשתמש בוקטור primes מהתרגיל הקודם).
;k=252
while k>1
;i=2
while mod(k,primes(i))!~=0
;i=i+1
end
;((disp(primes(i
;(k=k/primes(i
end
יישומים מתמטיים
מחלק משותף גדול ביותר gcd
עבור [math]\displaystyle{ m,n }[/math] שלמים, המספר השלם הגדול ביותר המחלק גם את [math]\displaystyle{ m }[/math] וגם את [math]\displaystyle{ n }[/math] ייקרא המחלק המשותף הגדול ביותר ויסומן [math]\displaystyle{ gcd(m,n) }[/math].
;m=12
;n=30
if n<m
;t=m
;m=n
;n=t
end
for i=1:m
if mod(m,i)==0 && mod(n,i)=0
;gcd=i
end
end
;(disp(gcd
קבלת מינימום
ישנן שלוש דרכים לקבל את המספר המינימלי מבין [math]\displaystyle{ m,n }[/math].
דרך ראשונה - ([min([m,n
דרך שנייה - תנאי
דרך שלישית - [math]\displaystyle{ min=\frac{m+n}{2}-\frac{m-n}{2} }[/math]
אלגוריתם אוקלידס
אלגוריתם אוקלידס נועד למציאת מחלק משותף מקסימלי בין שני מספרים שלמים [math]\displaystyle{ m,n }[/math].
האלגוריתם
נניח [math]\displaystyle{ m\lt n }[/math]. נגדיר:
[math]\displaystyle{ r_0=n }[/math]
[math]\displaystyle{ r_1=m }[/math]
[math]\displaystyle{ r_0=q_1 r_1+r_2 }[/math] כאשר [math]\displaystyle{ 1\leq q_1 \leq r_0 }[/math], [math]\displaystyle{ 0\leq r_2 \lt r_1 }[/math]
ובאינדוקציה [math]\displaystyle{ r_k=q_{k+1} r_{k+1}+r_{k+2} }[/math]
עד שנגיע ל־[math]\displaystyle{ r_N=0 }[/math].
בהכרח נעצור כי [math]\displaystyle{ r_{k+1}\lt r_k }[/math].
לפי אלגוריתם זה, ה־gcd הינו [math]\displaystyle{ r_{N-1} }[/math].
דוגמה
נבחר [math]\displaystyle{ r_0=30, r_1=12 }[/math].
[math]\displaystyle{ 30=2\cdot 12+\underset{r_2}{\underbrace{6}} }[/math]
[math]\displaystyle{ 12=2\cdot 6+\underset{r_3}{\underbrace{0}} }[/math]
ולכן [math]\displaystyle{ gcd(30,12)=6 }[/math]
הוכחת האלגוריתם
[math]\displaystyle{ r_{N-2}=q_{N-1} r_{N-1}+r_N=q_{N-1} r_{N-1} }[/math] [math]\displaystyle{ \Leftarrow }[/math] [math]\displaystyle{ r_{N-1}|r_{N-2} }[/math].
[math]\displaystyle{ r_{N-3}=q_{N-2} r_{N-2}+r_{N-1} }[/math].
[math]\displaystyle{ r_{N-1}|r_{N-2} }[/math] וגם [math]\displaystyle{ r_{N-1}|r_{N-1} }[/math] [math]\displaystyle{ \Leftarrow }[/math][math]\displaystyle{ r_{N-1}|r_{N-3} }[/math]
[math]\displaystyle{ r_{N-4}=q_{N-3} r_{N-3}+r_{N-2} }[/math].
[math]\displaystyle{ r_{N-1}|r_{N-2} }[/math] וגם [math]\displaystyle{ r_{N-1}|r_{N-3} }[/math] [math]\displaystyle{ \Leftarrow }[/math][math]\displaystyle{ r_{N-1}|r_{N-4} }[/math]
<BR
באינדוקציה, נקבל [math]\displaystyle{ r_{N-1}|r_1 }[/math] וגם [math]\displaystyle{ r_{N-1}|r_0 }[/math].
מדוע [math]\displaystyle{ r_{N-1} }[/math] הוא המחלק המשותף הגדול ביותר? נניח [math]\displaystyle{ r_k=gcd(m,n) }[/math], אזי [math]\displaystyle{ r_{k-1}=q_{k} r_{k}+0 }[/math].
בהכרח נגיע למחלק המשותף המקסימלי מפני שבשלב ה־k־י, [math]\displaystyle{ r_{k-1}|gcd(m,n) }[/math] וגם [math]\displaystyle{ r_k|gcd(m,n) }[/math], לכן [math]\displaystyle{ r_{k+1}|gcd(m,n) }[/math].
תכנות
;m=12 ;n=30 if n<m ;r1=n ;r0=m else ;r1=m ;r0=n end while r1>0 ;(r2=mod(r0,r1 ;r0=r1 ;r1=r2 end ;gcd=r0
דוגמה
עבור [math]\displaystyle{ m=169, n=1482 }[/math]
| [math]\displaystyle{ r_2 }[/math] | [math]\displaystyle{ r_1 }[/math] | [math]\displaystyle{ r_0 }[/math] |
|---|---|---|
| 169 | 1482 | |
| 130 | 130 | 169 |
| 39 | 39 | 130 |
| 13 | 13 | 39 |
| 0 | 0 | 13 |
gcd(169,1482)=13
עבור [math]\displaystyle{ m=441, n=42 }[/math]
| [math]\displaystyle{ r_2 }[/math] | [math]\displaystyle{ r_1 }[/math] | [math]\displaystyle{ r_0 }[/math] |
|---|---|---|
| 42 | 441 | |
| 21 | 21 | 42 |
| 0 | 0 | 21 |
gcd(42,441)=21
פתרון מערכת משוואות - ניוטון-רפסון
תהי [math]\displaystyle{ f(x) }[/math] פונקציה, צריך למצוא [math]\displaystyle{ x }[/math] כך ש־[math]\displaystyle{ f(x)=0 }[/math].
האלגוריתם והוכחתו
נתחיל מנקודה כלשהי, ובכל פעם נעביר דרכה משיק ונקבל נקודה חדשה - ששיעור ה־x שלה זהה לשיעור ה־x של החיתוך עם ציר x של המשיק. המחשת האלגוריתם
נתון [math]\displaystyle{ x_0 }[/math]. נחשב את משוואת הישר [math]\displaystyle{ y=ax+b }[/math], [math]\displaystyle{ a=f'(x_0) }[/math], עובר בנקודה [math]\displaystyle{ (x_0,f(x_0)) }[/math] (משוואת המשיק):
[math]\displaystyle{ f(x_0)=f'(x_0)x_0+b }[/math] [math]\displaystyle{ \Leftarrow }[/math] [math]\displaystyle{ b=f(x_0)-x_0 f'(x_0) }[/math]
כלומר, הישר המשיק ל־[math]\displaystyle{ f(x) }[/math] הינו [math]\displaystyle{ y=f'(x_0)x+f(x_0)-x_0 f(x_0) }[/math]. נמצא את [math]\displaystyle{ x_1 }[/math]. חיתוך עם ציר [math]\displaystyle{ x }[/math]:
[math]\displaystyle{ x_1=-\frac{f(x_0)-f'(x_0)x_0}{f'(x_0)}=x_0-\frac{f(x_0)}{f'(x_0)} }[/math].
לכן, [math]\displaystyle{ x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)} }[/math]. נמשיך באיטרציות עד ש־[math]\displaystyle{ |x_k-x_{k-1}|\lt \Delta=10^{-12} }[/math]
טענה: [math]\displaystyle{ |x_{k+1}-\tilde{x}|\leq c|x_k-\tilde{x}|^2 }[/math] עבור [math]\displaystyle{ c\ge 0 }[/math], כאשר [math]\displaystyle{ \tilde{x} }[/math] הינו השורש האמיתי.
תכנות
נתונה פונקציה f ופונקציה 'g=f. השגיאה הרצויה delta.
;x0=1 ;x1=x0+2*delta while abs(x0-x1)>delta ;(x1=x0-f(x0)/g(x0 ;t=x1 ;x1=x0 ;x0=t end
פונקציות
פונקציה הינה רצף הוראות שנועד להתבצע עם נתונים מסוימים. למשל, פונקציה יכולה לקבל מספר ולהדפיס האם הוא ראשוני. פונקציה יכולה להחזיר ערך (או מערך עם כמה ערכים) או לא להחזיר ערך.
תכנות ב־MATLAB:
(קלט) שם הפונקציה = [פלט] function (הוראות לביצוע) end
תרגילים
תרגיל 1 - האם ראשוני
כתבו פונקציה שתקבל מספר טבעי [math]\displaystyle{ p }[/math]. הפונקציה תחזיר 1 אם הוא ראשוני ו־0 אחרת.
(function [yn]=isprime(p
;yn=1
;k=2
while k<=sqrt(p) && yn==1
if mod(p,k)==0
;yn=0
end
;k=k+1
end
end
בהסתמך על הפונקציה הנ"ל, כתבו תוכנית שתיצור וקטור של המספרים הראשוניים עד למספר טבעי נתון [math]\displaystyle{ n }[/math].
;[]=primes
;0=found
for k=1:n
1==(if isprime(k
;found=found+1
;primes(found)=k
end
end
תרגיל 2 - האם וקטור הוא פרמוטציה (תמורה)
כתבו פונקציה המקבלת וקטור ובודקת אם הוא פרמוטציה של [math]\displaystyle{ 1,...,n }[/math].
(function [yn] = ispermut (v
;(n=length(v
;(found=zeros(n,1
for i=1:n
;yn=1
if v(i)<1 || v(i)>n
;yn=0
else
;found(v(i))=1
end
end
;sum=0
for i=1:n
;(sum=sum+found(i
end
;(yn=(sum==n
end
מבני נתונים
המטרה: לכתוב פונקציות להוספה, למחיקה, לחיפוש ולמיון במערך. נחלק את הפעולות לשני מקרים: המערך אינו ממוין והמערך ממוין.
מערך שאינו ממוין
נגדיר איזשהו מערך:
;[v=[79,100,31,5,84
ונבצע עליו את הפעולות הבאות:
הוספה
(function [u] = add2array (v,k הפונקציה מוסיפה איבר k למערך v ומחזירה u % ;u=v ;u(end+1)=k end
מחיקה
אפשרות 1:
(function [u] = deleteFromArray (v,p הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u % ;(u=zeros(length(v)-1,1 ;(u(1:p-1)=v(1:p-1 ;(u(p:length(v)-1)=v(p+1:end end
אפשרות 2:
(function [u] = deleteFromArray2 (v,p הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u % ;(u=zeros(length(v)-1,1 for i=1:p-1 ;(u(i)=v(i end (for i=p+1:length(v ;(u(i-1)=v(i end end
חיפוש
(function [p] = findInArray (v,x
הפונקציה מחזירה את המקום במערך שבו x נמצא או אפס אם x אינו במערך %
;k=1
;p=0
;(n=length(v
while p==0 && k<=n
if v(k)==x
;p=k
else
;k=k+1
end
end
end
מערך ממוין
כעת נניח שיש לנו מערך ממוין v, למשל מהקטן לגדול.
מחיקה
בדיוק כמו במערך שאינו ממוין.
חיפוש
ישנן שתי שיטות חיפוש: חיפוש בינארי ואריה במדבר.
חיפוש בינארי:
(function [p] = binarySearch (v,x
;(n=length(v
;L=1
;H=n
while L<H-1
;(M=floor((L+H)/2
(if x<v(M
;H=M
else
;L=M
end
end
(if x==v(H
;p=H
else
;p=L
end
end
מספר הפעולות בחיפוש בינארי: [math]\displaystyle{ \log_2 n }[/math]
הוספה
אם x קטן מ־(v(1, נכניס אותו בהתחלה. אחרת נחפש את x ונכניס אותו אחרי L.
מיון פשוט
ראשית, נכתוב פונקציית עזר:
(function [m,p] = findSmallest (v,k
הפונקציה מוצאת את המקום p ואת הערך m הנמצא במערך v והמינימלי מהמקום ה־k־י והלאה %
;p=k
;(m=v(k
;(n=length(v
for i=k+1:n
if v(i)<m
;p=i
;(m=v(i
end
end
end
כעת, נכתוב את התוכנית למיון:
for i=1:n-1 ;(m,p]=findSmallest(v,i] ;(v(p)=v(i ;v(i)=m end
יעילות
אם אנו חושדים שזמן הריצה [math]\displaystyle{ t }[/math] כתלות ב־[math]\displaystyle{ n }[/math] פרופורציוני ל־[math]\displaystyle{ n^r }[/math]:
[math]\displaystyle{ t\propto n^r }[/math]
[math]\displaystyle{ \Downarrow }[/math]
[math]\displaystyle{ t=cn^r }[/math]
[math]\displaystyle{ \ln t=\ln c+r\ln n }[/math]
לכן [math]\displaystyle{ \ln t }[/math] כתלות ב־[math]\displaystyle{ \ln n }[/math] הינו קו ישר ששיפועו [math]\displaystyle{ r }[/math], וכך ניתן למצוא את [math]\displaystyle{ \ln c }[/math] כחיתוך עם ציר y.
מספר הגדרות ודוגמות
[math]\displaystyle{ f\left ( n \right )=\Theta\left ( g\left ( n \right ) \right ) }[/math] אם [math]\displaystyle{ \forall n, A\cdot g\left ( n \right )\leq f\left ( n \right )\leq B\cdot g\left ( n \right ) }[/math].
[math]\displaystyle{ f\left ( n \right )=O \left ( g\left ( n \right ) \right ) }[/math] אם [math]\displaystyle{ \forall n, f\left ( n \right )\leq B\cdot g\left ( n \right ) }[/math].
דוגמה:
[math]\displaystyle{ e^x=1+x+\frac{x^2}{2}+...=\sum_{n=0}^\infty\frac{x^n}{n!} }[/math], לכן [math]\displaystyle{ e^x=1+x+\frac{x^2}{2}+O(x^3) }[/math].
באופן מדויק: [math]\displaystyle{ e^x=1+x+\frac{x^2}{2}+\frac{(x^*)^3}{6} }[/math] כאשר [math]\displaystyle{ |x^*|\lt |x| }[/math], ולכן [math]\displaystyle{ \frac{(x^*)^3}{6}\leq\frac{1}{6} x^3 }[/math].
דוגמה נוספת:
בחיפוש בינארי מבוצעות [math]\displaystyle{ \left \lceil \log_2 n\right \rceil }[/math] פעולות, ולכן היעילות הינה [math]\displaystyle{ \left \lceil \log_2 n\right \rceil=O(\log_2 n)=O(\ln n) }[/math].
[math]\displaystyle{ f\left ( n \right )=o\left ( g\left ( n \right ) \right ) }[/math] אם [math]\displaystyle{ \lim_{n\rightarrow\infty}\frac{f\left ( n \right )}{g\left ( n \right )}=0 }[/math].
דוגמה:
[math]\displaystyle{ e^{-x}=o\left ( x^n \right ) }[/math] כי [math]\displaystyle{ \lim_{x\rightarrow\infty}\frac{e^{-x}}{x^n}=0 }[/math]
דוגמה נוספת:
[math]\displaystyle{ \ln x=o\left ( x \right ) }[/math] וגם [math]\displaystyle{ \ln x=O\left ( x \right ) }[/math].
רקורסיה
מתוך פונקציה שאנו מגדירים ניתן לקרוא לעצמה.
ברקורסיה חשוב לזכור:
- תנאי עצירה
- "צעד" הרקורסיה - זימון הפעולה בתוך עצמה
תרגיל 1 - חישוב עצרת
נזכור כי:
[math]\displaystyle{ \left\{\begin{matrix}n!=\left ( n-1 \right )!\cdot n
\\
0!=1 \ \ \ \ \ \ \ \ \ \ \ \
\end{matrix}\right. }[/math]
ונכתוב פונקציה מתאימה:
(function [f] = fact (n if n==0 ;f=1 else ;(f=n*fact(n-1 end end
תרגיל 2 - מקדמים בינומיים
המקדם הבינומי [math]\displaystyle{ \binom{n}{k} }[/math] מונה כמה אפשרויות יש לנו לבחירת [math]\displaystyle{ k }[/math] איברים מתוך [math]\displaystyle{ k }[/math] ללא בחירת איבר פעמיים וללא חשיבות לסדר.
נוסחה סגורה לחישוב: [math]\displaystyle{ \binom{n}{k}=\frac{n!}{k!\left ( n-k \right )!} }[/math]
ממשולש פסקל אנו מקבלים נוסחת נסיגה לחישובם: [math]\displaystyle{ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} }[/math].
נכתוב פונקציה מתאימה:
(function [b] = binomial (n,k if k==0 || k==n ;b=1 else ;(b=binomial(n-1,k)+binomial(n-1,k-1 end end
תרגיל 3 - איחוד מערכים ממוינים
המטרה: לאחד שני מערכים ממוינים u,v למערך ממוין
הפונקציה המתאימה:
(function [w] = merge (u,v
;(nu=length(u
;(nv=length(v
;nw=nu+nv
;(w=zeros(nw,1
if nu==0
;w=v
elseif nv==0
;w=u
else
;ku=1
;kv=1
for kw=1:nw
((if (ku<=nu) && (kv>nv || u(ku)<v(kv
;(w(kw)=u(ku
;ku=ku+1
else
;(w(kw)=v(kv
;kv=kv+1
end
end
end
end
תרגיל 4 - מיון מערך
המטרה: למיין מערך ביעילות [math]\displaystyle{ O(n\cdot\ln n) }[/math]
הביצוע: כל פעם נחלק לשני תת־מערכים, נמיין אותם ונאחד (באמצעות הפעולה מתרגיל 3)
הפונקציה המתאימה:
(function [w] = mergeSort (v ;(n=length(v if n<=1 ;w=v else ;(m=floor(n/2 ;((w1=mergeSort(v(1:m ;((w2=mergeSort(v(m+1:n ;(w=merge(w1,w2 end end
משוואות לינאריות
תהי מערכת משוואות [math]\displaystyle{ Ax=b }[/math] כאשר [math]\displaystyle{ A\in M_{n\times k}\left ( \mathbb{R} \right ) }[/math], [math]\displaystyle{ x\in\mathbb{R}^k }[/math] ו־[math]\displaystyle{ b\in\mathbb{R}^n }[/math]. אזי:
- למערכת אין פתרון אם [math]\displaystyle{ b\notin C\left ( A \right ) }[/math].
- למערכת יש פתרון יחיד אם [math]\displaystyle{ rank\left ( A \right )=k }[/math], כלומר [math]\displaystyle{ \det\left ( A \right )\neq 0 }[/math].
- למערכת יש אינסוף פתרונות אם [math]\displaystyle{ b\in C\left ( A \right ) }[/math].
במקרים 1 ו־3 מתקיים [math]\displaystyle{ rank\left ( A \right )\lt k }[/math], [math]\displaystyle{ \det\left ( A \right )=0 }[/math].
הערה: [math]\displaystyle{ rank\left ( A \right ) }[/math] - מספר העמודות הבת"ל ב־[math]\displaystyle{ A }[/math].
מקרה 2: פתרון יחיד
שלוש אפשרויות לחישוב הפתרון על ידי MATLAB:
- x=inv(A)*b
- x=A\b
- x=pinv(A)*b
אפשרויות 2 ו־3 מתאימה גם אם [math]\displaystyle{ A }[/math] אינה הפיכה / ריבועית.
מקרה 1: אין פתרון
התאמת קו ישר לאוסף נקודות
עבור סדרת N נקודות, [math]\displaystyle{ \left \{ \left ( x_i,y_i \right ) \right \}_{i=1}^N }[/math], ננסה להתאים ישר [math]\displaystyle{ y=c_1 x+c_2 }[/math] הקרוב להן ביותר (קו מגמה).
נגדיר מטריצה [math]\displaystyle{ A }[/math]: [math]\displaystyle{ A=\begin{pmatrix} x_1 & 1 \\ x_2 & 1 \\ \vdots & \vdots \\ x_N & 1 \end{pmatrix} }[/math]
ו־וקטור [math]\displaystyle{ y }[/math]: [math]\displaystyle{ y=\begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_N \end{pmatrix} }[/math]
ונפתור את מערכת המשוואות [math]\displaystyle{ Ac=y }[/math]. הפתרון [math]\displaystyle{ c }[/math] שנקבל הינו הווקטור [math]\displaystyle{ \begin{pmatrix} c_1 \\ c_2 \end{pmatrix} }[/math]
פתרון המערכת: ניעזר ברגרסיה לינארית
נגדיר פונקציה [math]\displaystyle{ R=\sum_{i=1}^Nd_i^2 }[/math] כאשר [math]\displaystyle{ d_i }[/math] הינו המרחק של הנקודה ה־i־ית מהישר (אנך לציר x), שהוא בעצם הפרשי ה־y. כלומר, [math]\displaystyle{ R\left ( c_1,c_2 \right )=\sum_{i=1}^N \left ( y_i-c_ix_i-c_2 \right )^2 }[/math]. המינימום של הפונקציה הזו ייתן לנו את הפתרון המקורב ביותר לנקודות, כזה שסכום ריבועי המרחקים שלו מהנקודות הנתונות מינימלי - הכי קרוב.
נגזור ונקבל נגזרות חלקיות:
[math]\displaystyle{ \frac{\partial R}{\partial c_1}=\sum_{i=1}^N 2\cdot \left ( y_i-c_ix_i-c_2 \right ) \cdot \left (-x_i \right )=-\sum_{i=1}^{N}2x_i \left ( y_i-c_ix_i-c_2 \right )=0 }[/math]
[math]\displaystyle{ \frac{\partial R}{\partial c_2}=\sum_{i=1}^N 2\cdot \left ( y_i-c_ix_i-c_2 \right ) \cdot \left (-1 \right )=-\sum_{i=1}^{N}2 \left ( y_i-c_ix_i-c_2 \right )=0 }[/math]
נמשיך לפתור:
[math]\displaystyle{ c_1\sum_{i=1}^N x_i^2+c_2 \sum_{i=1}^N x_i=\sum_{i=1}^{N} x_i y_i }[/math]
[math]\displaystyle{ c_1\sum_{i=1}^{N}x_i+Nc_2=\sum_{i=1}^{N}y_i }[/math]
בעצם, קיבלנו מערכת משוואות השקולה למערכת [math]\displaystyle{ A^t A c=A^t y }[/math] (למי שאינו מאמין, ניתן לבדוק).
נחשב את [math]\displaystyle{ \det(A^t A) }[/math] כדי לדעת מתי אין פתרון יחיד למערכת:
[math]\displaystyle{ \det\left ( A^t A \right )=N\sum_{i=1}^{N}x_i^2-\left ( \sum_{i=1}^{N}x_i \right )^2=N^2 \left [ \frac{\sum_{i=1}^{N}x_i^2}{N}-\left ( \frac{\sum_{i=1}^{N}x_i}{N} \right )^2 \right ] }[/math]
למה: [math]\displaystyle{ \frac{\sum_{i=1}^{N}x_i^2}{N}-\left ( \frac{\sum_{i=1}^{N}x_i}{N} \right )^2=\frac{1}{N}\sum_{i=1}^{N}\left ( x_i-\frac{\sum_{i=1}^{N}x_i}{N} \right )^2 }[/math]
הוכחה: נסמן את הממוצע [math]\displaystyle{ \bar{x}=\frac{\sum_{i=1}^{N}x_i}{N} }[/math]. אזי:
[math]\displaystyle{ \frac{1}{N}\sum_{i=1}^{N}\left ( x_i-\bar{x} \right )^2=\frac{1}{N}\sum_{i=1}^{N} \left (x_i^2-2x_i\bar{x} +\bar{x}^2 \right )=\frac{1}{N}\sum_{i=1}^{N} x_i^2-2\bar{x}\underset{\bar{x}}{\underbrace{\frac{1}{N}\sum_{i=1}^{N}x_i}}+\underset{\bar{x}^2}{\underbrace{\frac{1}{N}\sum_{i=1}^{N}\bar{x}^2}}=\frac{1}{N}\sum_{i=1}^{N} x_i^2-\bar{x}^2 }[/math]
מסקנה: [math]\displaystyle{ \det (A^t A)=0 }[/math] אם ורק אם [math]\displaystyle{ x_1=x_2=...=x_N=\bar{x} }[/math]. לכן, קיים פתרון ריבועים מינימליים (Least squares solution).