ผลต่างระหว่างรุ่นของ "204512/บรรยาย 2"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 34 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 1: แถว 1:
 +
{{หัวคำบรรยาย|204512}}
 +
'''จดบันทึกคำบรรยายโดย:''' ''(กรุณาใส่ด้วย)''
 
== เกริ่นนำ ==
 
== เกริ่นนำ ==
 
 
หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้
 
หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้
 
:1.แตกย่อยปัญหาเป็นชิ้นเล็ก หลายชิ้น
 
:1.แตกย่อยปัญหาเป็นชิ้นเล็ก หลายชิ้น
แถว 27: แถว 28:
 
<math>\ 3n^2 + 2n \le 3n^2 + n^2</math>
 
<math>\ 3n^2 + 2n \le 3n^2 + n^2</math>
  
โดยทั่วไปแล้ว Big-Oh คือการแสดง Upper Bound ของฟังก์ขั่น ขณะที่ Big-Omega (<math>Ω</math>) เป็นการแสดงถึง Lower Bound ของฟังก์ชั่น
+
โดยทั่วไปแล้ว Big-Oh คือการแสดง Upper Bound ของฟังก์ขั่น ขณะที่ Big-Omega (<math>\Omega</math>) เป็นการแสดงถึง Lower Bound ของฟังก์ชั่น
 
----
 
----
  
แถว 43: แถว 44:
 
*สามารถสังเกตได้ว่า ประกอบไปด้วยพจน์ที่คูณกัน 4 ชุด
 
*สามารถสังเกตได้ว่า ประกอบไปด้วยพจน์ที่คูณกัน 4 ชุด
  
นิยาม Function ของเวลาที่ใช้ในการคำนวณตัวเลข n-bit
+
นิยาม Function ของเวลาที่ใช้ในการคำนวณตัวเลข n-bit เป็น <math>T(n) = 2T(\frac{n}{2}) + O(n)</math>
 +
 
 +
[[ภาพ:Tree.png|ภาพตัวอย่างการแตกปัญหาออกเป็นส่วนๆ ตามการคำนวณตามวิธีปรกติ]]
 +
 
 +
 
 +
จากภาพ Tree มีความสูง <math>\log{n} \, </math> ทำให้ได้ว่า
 +
 
 +
<math>T(n) =  cn [1 + 2 + 4 + ... + 2^{n}] =  cn \cdot 2^{\log{n}} [ \frac{1}{2^{\log{n}}} + ... + \frac{1}{4} + \frac{1}{2} + 1] = \mathcal{O}(n^2) </math>
 +
 
 +
Gauss ได้เสนอวิธีการคูณในอีกรูปแบบหนึ่งที่ใช้การคูณเพียงสามครั้งจาก <math>x_L y_R + x_R y_L = (x_L + x_R)(y_L + y_R) - x_L y_L - x_R y_R \,</math> ทำให้อัลกอลิธึ่มได้รับการปรับปรุงเป็น <math>T(n) = 3 T(\frac{n}{2}) + \mathcal{O}(n)</math> ซึ่งเมื่อคำนวณในรูปแบบเดียวกับ Tree ด้านบนโดยถือว่าแต่ละ node จะมีลูกอยู่ 3 ชุดแทนที่จะเป็น 4 ชุด เราจะได้ว่า
 +
 
 +
<math>T(n) = cn (\frac{3}{2})^{\log{n}} = n^{log_2{3}} = n^{1.59}</math>
  
 
=== Merge Sort ===
 
=== Merge Sort ===
 +
 +
Merge Sort เป็นอัลกอลิธึ่มแบบ Devide-and-Conquer อีกอันหนึ่งที่ อาศัยการแบ่งข้อมูลออกเป็นส่วนเล็กๆ แล้วเรียงลำดับให้ถูกต้อง แล้วจึงนำข้อมูลที่เรียงแล้วกลับมาต่อกัน
 +
 +
กระบวนการทำ Merge Sort มีสามขั้นคือ
 +
 +
* การแบ่งส่วนข้อมูล ได้ทำได้ทันที
 +
* การเรียงข้อมูล ที่แบ่งไปครึ่งๆ แล้ว ใช้เวลา <math>T(\frac{n}{2}) \,</math>
 +
* การนำข้อมูลที่เรียงแล้วสองชุดมาต่อกันใช้เวลา <math>\mathcal{O}(n)</math>
 +
 +
โดยรวมแล้ว Merge Sort ใช้เวลาในการทำงาน <math>T(n) = T(\frac{n}{2}) + \mathcal{O}(n)</math>
 +
 +
หรือก็คือ <math>\mathcal{O}(n\log{n})</math>
  
 
=== Fast Furier Transform ===
 
=== Fast Furier Transform ===
 +
[[ภาพ:Plot.png|thumb|กราฟแสดงการหาสมการผลลัพธ์จากการคูณค่าในแต่ละจุดของสมการตั้งต้น ภาพจาก[http://www.walterzorn.com/grapher/grapher_e.htm Walterzorn.com]]]
 +
FFT คืออัลกอลิธึ่มที่ใช้ในการหาผลคูณของสมการ Polynomial สองชุดเข้าด้วยกัน เพื่อใช้งานในด้าน Signal บางอย่าง โดยมีแนวคิดคือการหาสมการที่เป็นผลคุณของ Polynomial นั้นไม่จำเป็นที่จะต้องเกิดจากการนำสมการมาคุณกันจริงๆ แต่อาจสร้างได้จากคุณสมบัติของ Polynomial ดังนี้
  
 +
* สมการ Polynomial ที่มี degree เป็น d ใดๆ สามารถสร้างขึ้นจากการหาค่าผลของสมการที่ตำแหน่งต่างๆ จำนวน d+1 ตำแหน่ง
 +
* เมือนำสมการ Polynomial degree d สองสมการมาคูณกัน เราจะได้สมการ Polynomial degree เป็น 2d
 +
* ดังนั้นหากเราหาค่าของสมการตั้งต้นสองสมการจำนวน 2d+1 จุด แล้วนำมาคูณกัน สุดท้ายแล้วเราจะได้ค่า 2d+1 จุดที่สามารถนำไป Interpolate กลับมาเป็นสมการผลคูณของ Polynomial สองสมการได้
 +
 +
==== Devide and Conconquer ====
 +
เริ่มจากพิจารณาสมการ Polynomial degree-n ใดๆ เช่น <math>f(x) = 8 + 5x + 4x^2 + 2x^3 \,</math> เราสามารถหาค่าของจุดต่างๆ จำนวน n จุดได้ โดยหาค่าทั้งในฝั่งบวกและลบไปพร้อมๆ กัน เช่นพิจารณาจุด <math>\pm x_1, \pm x_2, \pm x_3 , ... , \pm x_n</math> เราจะสามารถแยกพิจารณากรณีคู่และคี่ไปพร้อมๆ กันได้โดยการแยกตัวประกอบเพื่อให้ทุกพจน์มี degree เป็นคู่เสมอ ดังเช่นตัวอย่าง
 +
 +
<math>f(x) = 8 + 5x + 4x^2 + 2x^3 = (8 + 4x^2) + x(5 + 2x^2) \,</math>
 +
 +
การแยกเช่นนี้เป็นจริงเสมอสำหรับ Polnomial ใดๆ เราจึงแยกเป็น <math>f(x) = f_e(x^2) + x f_o(x^2) \,</math> เมื่อ <math>f_e(x)\,</math> เป็นพจน์คู่ของ <math>f(x) \,</math> และ <math>f_o(x)\,</math> เป็นพจน์คี่ของ <math>f(x) \,</math> โดยที่เมื่อคำนวณค่าออกมาเพียงครั้งเดียว เราสามารถหาค่าทั้งฝั่งบวกและลบได้ดังสมการ
 +
 +
<math> f(x_n) = f_e(x_n^2) + x f_o(x_n^2)</math>
 +
 +
 +
<math>f(-x_n) = f_e(x_n^2) + x f_o(x_n^2)</math>
 +
 +
จากข้างบนทำให้เราสามารถย่อยป้ญหาให้เล็กลงครึ่งหนึ่งได้ แต่ในระบบจำนวนจริงเราไม่สามารถแบ่งปัญหาให้เล็กลงไปกว่าครึ่งได้อีกเพราะการยกกำลังสองในครั้งแรกก็ทำให้เลขทุกตัวกลายเป็นจำนวนบวกไปหมด แต่เราสามารถใช้จำนวนเชิงซ้อนในรูปแบบ [http://en.wikipedia.org/wiki/Primitive_root_of_unity Root of Unity] เพื่อให้สามารถแบ่งปัญหาลงไปเรื่อยๆ ได้โดยการใช้ Root of Unity มีคุณสมบัติที่น่าสนใจสองประการคือ
 +
 +
* มีคู่ตรงข้ามเสมอ ทำให้สามารถยกกำลังสองเพื่อหาค่าทั้งสองค่าในครั้งเดียวได้
 +
* การยกกำลังสองในแต่ละครั้งจะทำให้ได้ Root of Unity ในอับดับที่ <math>\frac{n}{2}</math> เสมอ
 +
 +
การคำนวณค่าของการคูณสมการ Polynomial ใดๆ จึงสามารถทำได้ โดยพิจารณาว่าสมการผลลัพธ์จะมี degree เป็นเท่าใด แล้วเลือกใช้งาน Root of Unity ในลำดับที่สูงกว่านั้นทำให้สามารถคำนวณหาค่าของทุกจุดได้ในเวลาเพียง <math>n\log{n}\,</math>
 +
 +
==== Interpolation ====
 +
หลังจากที่เราพิจารณาจุดได้มากพอที่จะ Interpolate สมการของผลลัพธ์กลับออกมาได้แล้ว สิ่งที่เราต้องทำต่อไปคือการสร้างสมการที่เป็นผลคูณของสองสมการที่ผ่านมา โดยขณะที่การพิจารณาค่าที่ตำแหน่งต่างๆ ของ <math>f(x) \,</math> นั้นได้ความเร็วเป็น <math>\mathcal{O}(n \log{n})</math> แล้วก็ตาม แต่ความเร็วในการ Interpolate สมการกลับขึ้นมาก็ต้องนำมาพิจารณาด้วย
 +
 +
แต่คุณสมบัติของฟังก์ขั่น FFT ที่เราใช้ในการพิจารณาค่าในส่วนที่แล้ว มีคุณสมบัติที่น่าแปลกคือ
 +
 +
จาก <math>\langle values \rangle = FFT(\langle cofficients \rangle, \omega)</math> เราจะได้ว่า <math>\langle cofficients \rangle = \frac{1}{n}FFT(\langle values \rangle, \omega^{-1})</math> ซึ่งเนื่องจากสมการในการ Interpolate นั้นเป็นสมการเดียวกับที่ใช้ในการพิจารณาค่าทำให้เราได้ว่าอัลกอลิธึ่มนี้มีความเร็ว <math>\mathcal{O}(n \log{n})</math> เสมอ
 +
 +
==== Proof of Interpolation ====
 +
การที่เราสามารถพิจารณาค่าจำนวน n จุดของสมการ Polynomial ได้นั้น เราสามารถมองว่าเป็นการคูณกันระหว่าง Matrix ของ Coeffient และ Matrix ของตัวแปร ดังสมการต่อไปนี้
 +
<center>
 +
<math>\begin{bmatrix}
 +
f(x_0)\\
 +
f(x_1)\\
 +
\vdots \\
 +
f(x_{n-1})
 +
\end{bmatrix}
 +
=
 +
\begin{bmatrix}
 +
1 & 1 & 1 & \cdots & 1 \\
 +
1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\
 +
\vdots & \vdots & \vdots & \ddots& \vdots \\
 +
1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots &  \omega^{(n-1)(n-1)}
 +
\end{bmatrix}
 +
\begin{bmatrix}
 +
a_0\\
 +
a_1\\
 +
\vdots \\
 +
a_{n-1}
 +
\end{bmatrix}
 +
</math></center>
 +
 +
เราให้ Matrix ของ <math>\omega</math> ตรงกลางนั้นชื่อว่า M โดยมันมีรูปแบบที่เรียกว่า Vandermonde Matrix ที่ระบุว่า Matrix ในรูปแบบนี้จะมี Inverse เสมอ
 +
 +
การพิสูจน์สมการการ Interpolate นั้นทำโดยการมอง Matrix M เป็น Matrix ที่ Map เวคเตอร์จาก Space หนึ่งๆ ไปอีก Space หนึ่ง ซึ่งหากทุกแกนของ Space ใหม่นั้นตั้งฉากกันทั้งหมด เราจะสามารถบอกได้ว่าการ Inverse จะทำให้ได้ค่าเดิม คือ Coefficient กลับมาเสมอ และสามารถใช้สูตร
 +
 +
<center><math>M_n(\omega)^{-1} = \frac{1}{n} M_n(\omega^{-1})</math></center>
 +
 +
ซึ่ง <math>\omega^{-1}\,</math> ก็ยังคงเป็น Root of Unity อยู่ ทำให้เราสามารถใช้อัลกอลิธึ่มเดิมทำงานได้ต่อไป
 +
 +
ขั้นตอนต่อไปคือการพิสูจน์ว่าแมทริกซ์ M นั้นทุก Column (ซึ่งเป็นเวคเตอร์) ตั้งฉากกันทั้งหมด โดยสามารถทำได้จากการทำ inner product ตามสมการ
 +
 +
<center><math>u \cdot v^* = u_0 v_0^* + u_1 v_1^* + \cdots + u_{n-1} v_{n-1}^*</math> โดยที่ <math>v^* \,</math> คือ Conjugate ของ <math>v \,</math></center>
 +
 +
โดยที่การทำ inner product จะให้ผลลัพธ์สูงสุดเมื่อเวคเตอร์ขนานกัน และให้ผลลัพธ์เป็นศูนย์เมื่อเวคเตอร์ตั้งฉากกัน
 +
 +
ในกรณีของ M ที่กล่าวถึงข้างต้น เมื่อเราเลือกคอลัมน์ i และ j ใดๆ มาหามุมระหว่างกันแล้วจะได้ inner product ว่า
 +
 +
<center><math>1+\omega^{i-j}+\omega^{2(i-j)}+\cdots+\omega^{(n-1)(i-j)}</math></center>
 +
 +
ซึ่งเป็นอนุกรมเลขาคณิตที่มีอัตราส่วนเป็น <math>\omega^{(i-j)}</math> ทำให้เราได้ผลลัพธ์ของอนุกรมเป็น <math>\frac{1 - \omega^{n(i-j)}}{1-\omega^{i-j}}</math> แต่เนื่องจาก <math>\omega</math> เป็น Root of Unity ทำให้<math>\omega^n = 1</math> เสมอ อนุกรมนี้จึงได้ 0 ทั้งหมดนี้เราจึงได้พิสูจน์ว่าเราสามารถใช้อัลกอลิธึ่ม FFT ในการทำ Interpolate สมการกลับมาได้ และทำให้อัลกอลิธึ่มรวมใช้เวลาการทำงานอยู่ใน <math>\mathcal{O}(n\log{n})</math>
 
----
 
----
  
แถว 54: แถว 153:
  
 
[http://en.wikipedia.org/wiki/Big_O_notation อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia ]
 
[http://en.wikipedia.org/wiki/Big_O_notation อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia ]
 +
 
[[Big_O_notation | อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia ]]
 
[[Big_O_notation | อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia ]]
  
ใช้ยากจังน้อ
+
[http://en.wikipedia.org/wiki/Inner_product Inner Product ใช้ในการพิสูจน์เรื่อง Manipulation]

รุ่นแก้ไขปัจจุบันเมื่อ 05:09, 9 สิงหาคม 2550

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย: (กรุณาใส่ด้วย)

เกริ่นนำ

หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้

1.แตกย่อยปัญหาเป็นชิ้นเล็ก หลายชิ้น
2.ทำการแก้ปัญหาย่อยเหล่านี้ด้วยวิธีการที่คล้ายกัน
3.คำตอบสุดท้ายหาได้จากการสรุปคำตอบทั้งหมดของทุกปัญหาย่อย

ดังจะเห็นได้จากปัญหาทั้งในชีวิตประจำวัน และปัญหาทางทฤษฎีคอมพิวเตอร์ สามารถเปรียบเทียบกรรมวิธี Divide and Conquer Algorithm กับ Lagacy Algorithm ได้ว่ามีประสิทธิ์ภาพต่างกันมากน้อยเพียงใด ซึ่งวิธีที่เปรียบเทียบเป็นที่นิยมโดยทั่วไปคือการหา Big O Notation มาเปรียบเทียบกัน


การวิเคราะห์เปรียบเทียบ Algorithm โดยการหา Big O Notation

Definition 1

 
T of n is in Big-Oh of f of n iff there're constants and such that
for all
กราฟแสดงตัวอย่าง Big-Oh ตามนิยาม
เช่น

จะเห็นได้ว่า definition 1 เป็นจริงได้เมื่อ

โดยทั่วไปแล้ว Big-Oh คือการแสดง Upper Bound ของฟังก์ขั่น ขณะที่ Big-Omega () เป็นการแสดงถึง Lower Bound ของฟังก์ชั่น


ตัวอย่างปัญหา ที่ใช้กรรมวิธีแก้ไขแบบ Divide & Conquer

Multiplication

การคูณกันของ ที่เป็น binary number ขนาด n-bit สามารถแยกออกได้เป็น

  • สามารถสังเกตได้ว่า ประกอบไปด้วยพจน์ที่คูณกัน 4 ชุด

นิยาม Function ของเวลาที่ใช้ในการคำนวณตัวเลข n-bit เป็น

ภาพตัวอย่างการแตกปัญหาออกเป็นส่วนๆ ตามการคำนวณตามวิธีปรกติ


จากภาพ Tree มีความสูง ทำให้ได้ว่า

Gauss ได้เสนอวิธีการคูณในอีกรูปแบบหนึ่งที่ใช้การคูณเพียงสามครั้งจาก ทำให้อัลกอลิธึ่มได้รับการปรับปรุงเป็น ซึ่งเมื่อคำนวณในรูปแบบเดียวกับ Tree ด้านบนโดยถือว่าแต่ละ node จะมีลูกอยู่ 3 ชุดแทนที่จะเป็น 4 ชุด เราจะได้ว่า

Merge Sort

Merge Sort เป็นอัลกอลิธึ่มแบบ Devide-and-Conquer อีกอันหนึ่งที่ อาศัยการแบ่งข้อมูลออกเป็นส่วนเล็กๆ แล้วเรียงลำดับให้ถูกต้อง แล้วจึงนำข้อมูลที่เรียงแล้วกลับมาต่อกัน

กระบวนการทำ Merge Sort มีสามขั้นคือ

  • การแบ่งส่วนข้อมูล ได้ทำได้ทันที
  • การเรียงข้อมูล ที่แบ่งไปครึ่งๆ แล้ว ใช้เวลา
  • การนำข้อมูลที่เรียงแล้วสองชุดมาต่อกันใช้เวลา

โดยรวมแล้ว Merge Sort ใช้เวลาในการทำงาน

หรือก็คือ

Fast Furier Transform

กราฟแสดงการหาสมการผลลัพธ์จากการคูณค่าในแต่ละจุดของสมการตั้งต้น ภาพจากWalterzorn.com

FFT คืออัลกอลิธึ่มที่ใช้ในการหาผลคูณของสมการ Polynomial สองชุดเข้าด้วยกัน เพื่อใช้งานในด้าน Signal บางอย่าง โดยมีแนวคิดคือการหาสมการที่เป็นผลคุณของ Polynomial นั้นไม่จำเป็นที่จะต้องเกิดจากการนำสมการมาคุณกันจริงๆ แต่อาจสร้างได้จากคุณสมบัติของ Polynomial ดังนี้

  • สมการ Polynomial ที่มี degree เป็น d ใดๆ สามารถสร้างขึ้นจากการหาค่าผลของสมการที่ตำแหน่งต่างๆ จำนวน d+1 ตำแหน่ง
  • เมือนำสมการ Polynomial degree d สองสมการมาคูณกัน เราจะได้สมการ Polynomial degree เป็น 2d
  • ดังนั้นหากเราหาค่าของสมการตั้งต้นสองสมการจำนวน 2d+1 จุด แล้วนำมาคูณกัน สุดท้ายแล้วเราจะได้ค่า 2d+1 จุดที่สามารถนำไป Interpolate กลับมาเป็นสมการผลคูณของ Polynomial สองสมการได้

Devide and Conconquer

เริ่มจากพิจารณาสมการ Polynomial degree-n ใดๆ เช่น เราสามารถหาค่าของจุดต่างๆ จำนวน n จุดได้ โดยหาค่าทั้งในฝั่งบวกและลบไปพร้อมๆ กัน เช่นพิจารณาจุด เราจะสามารถแยกพิจารณากรณีคู่และคี่ไปพร้อมๆ กันได้โดยการแยกตัวประกอบเพื่อให้ทุกพจน์มี degree เป็นคู่เสมอ ดังเช่นตัวอย่าง

การแยกเช่นนี้เป็นจริงเสมอสำหรับ Polnomial ใดๆ เราจึงแยกเป็น เมื่อ เป็นพจน์คู่ของ และ เป็นพจน์คี่ของ โดยที่เมื่อคำนวณค่าออกมาเพียงครั้งเดียว เราสามารถหาค่าทั้งฝั่งบวกและลบได้ดังสมการ


จากข้างบนทำให้เราสามารถย่อยป้ญหาให้เล็กลงครึ่งหนึ่งได้ แต่ในระบบจำนวนจริงเราไม่สามารถแบ่งปัญหาให้เล็กลงไปกว่าครึ่งได้อีกเพราะการยกกำลังสองในครั้งแรกก็ทำให้เลขทุกตัวกลายเป็นจำนวนบวกไปหมด แต่เราสามารถใช้จำนวนเชิงซ้อนในรูปแบบ Root of Unity เพื่อให้สามารถแบ่งปัญหาลงไปเรื่อยๆ ได้โดยการใช้ Root of Unity มีคุณสมบัติที่น่าสนใจสองประการคือ

  • มีคู่ตรงข้ามเสมอ ทำให้สามารถยกกำลังสองเพื่อหาค่าทั้งสองค่าในครั้งเดียวได้
  • การยกกำลังสองในแต่ละครั้งจะทำให้ได้ Root of Unity ในอับดับที่ เสมอ

การคำนวณค่าของการคูณสมการ Polynomial ใดๆ จึงสามารถทำได้ โดยพิจารณาว่าสมการผลลัพธ์จะมี degree เป็นเท่าใด แล้วเลือกใช้งาน Root of Unity ในลำดับที่สูงกว่านั้นทำให้สามารถคำนวณหาค่าของทุกจุดได้ในเวลาเพียง

Interpolation

หลังจากที่เราพิจารณาจุดได้มากพอที่จะ Interpolate สมการของผลลัพธ์กลับออกมาได้แล้ว สิ่งที่เราต้องทำต่อไปคือการสร้างสมการที่เป็นผลคูณของสองสมการที่ผ่านมา โดยขณะที่การพิจารณาค่าที่ตำแหน่งต่างๆ ของ นั้นได้ความเร็วเป็น แล้วก็ตาม แต่ความเร็วในการ Interpolate สมการกลับขึ้นมาก็ต้องนำมาพิจารณาด้วย

แต่คุณสมบัติของฟังก์ขั่น FFT ที่เราใช้ในการพิจารณาค่าในส่วนที่แล้ว มีคุณสมบัติที่น่าแปลกคือ

จาก เราจะได้ว่า ซึ่งเนื่องจากสมการในการ Interpolate นั้นเป็นสมการเดียวกับที่ใช้ในการพิจารณาค่าทำให้เราได้ว่าอัลกอลิธึ่มนี้มีความเร็ว เสมอ

Proof of Interpolation

การที่เราสามารถพิจารณาค่าจำนวน n จุดของสมการ Polynomial ได้นั้น เราสามารถมองว่าเป็นการคูณกันระหว่าง Matrix ของ Coeffient และ Matrix ของตัวแปร ดังสมการต่อไปนี้

เราให้ Matrix ของ ตรงกลางนั้นชื่อว่า M โดยมันมีรูปแบบที่เรียกว่า Vandermonde Matrix ที่ระบุว่า Matrix ในรูปแบบนี้จะมี Inverse เสมอ

การพิสูจน์สมการการ Interpolate นั้นทำโดยการมอง Matrix M เป็น Matrix ที่ Map เวคเตอร์จาก Space หนึ่งๆ ไปอีก Space หนึ่ง ซึ่งหากทุกแกนของ Space ใหม่นั้นตั้งฉากกันทั้งหมด เราจะสามารถบอกได้ว่าการ Inverse จะทำให้ได้ค่าเดิม คือ Coefficient กลับมาเสมอ และสามารถใช้สูตร

ซึ่ง ก็ยังคงเป็น Root of Unity อยู่ ทำให้เราสามารถใช้อัลกอลิธึ่มเดิมทำงานได้ต่อไป

ขั้นตอนต่อไปคือการพิสูจน์ว่าแมทริกซ์ M นั้นทุก Column (ซึ่งเป็นเวคเตอร์) ตั้งฉากกันทั้งหมด โดยสามารถทำได้จากการทำ inner product ตามสมการ

โดยที่ คือ Conjugate ของ

โดยที่การทำ inner product จะให้ผลลัพธ์สูงสุดเมื่อเวคเตอร์ขนานกัน และให้ผลลัพธ์เป็นศูนย์เมื่อเวคเตอร์ตั้งฉากกัน

ในกรณีของ M ที่กล่าวถึงข้างต้น เมื่อเราเลือกคอลัมน์ i และ j ใดๆ มาหามุมระหว่างกันแล้วจะได้ inner product ว่า

ซึ่งเป็นอนุกรมเลขาคณิตที่มีอัตราส่วนเป็น ทำให้เราได้ผลลัพธ์ของอนุกรมเป็น แต่เนื่องจาก เป็น Root of Unity ทำให้ เสมอ อนุกรมนี้จึงได้ 0 ทั้งหมดนี้เราจึงได้พิสูจน์ว่าเราสามารถใช้อัลกอลิธึ่ม FFT ในการทำ Interpolate สมการกลับมาได้ และทำให้อัลกอลิธึ่มรวมใช้เวลาการทำงานอยู่ใน


แหล่งข้อมูล​อื่น​

อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia

อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia

Inner Product ใช้ในการพิสูจน์เรื่อง Manipulation