204512/บรรยาย 2 - ประวัติรุ่นแก้ไข

Jittat เมื่อ 05:09, 9 สิงหาคม 2550

2007-08-09T05:09:53Z

Jittat เมื่อ 14:51, 19 กรกฎาคม 2550

2007-07-19T14:51:05Z

LewCPE: /* Proof of Interpolation */

2007-06-20T09:45:59Z

Proof of Interpolation

LewCPE: /* Proof of Interpolation */

2007-06-20T09:37:33Z

Proof of Interpolation

LewCPE: /* Proof of Interpolation */

2007-06-20T09:33:47Z

Proof of Interpolation

LewCPE: /* Proof of Interpolation */

2007-06-20T09:24:58Z

Proof of Interpolation

LewCPE: /* Proof of Interpolation */

2007-06-20T09:15:27Z

Proof of Interpolation

LewCPE: /* Proof of Interpolation */

2007-06-20T09:14:14Z

Proof of Interpolation

LewCPE: /* Proof of Interpolation */

2007-06-20T09:13:48Z

Proof of Interpolation

LewCPE: /* Fast Furier Transform */

2007-06-20T09:02:48Z

Fast Furier Transform

@@ แถว 1: / แถว 1: @@
 {{หัวคำบรรยาย|204512}}
 == เกริ่นนำ ==
 หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้

@@ แถว 1: / แถว 1: @@
 == เกริ่นนำ ==
 หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้
 :1.แตกย่อยปัญหาเป็นชิ้นเล็ก หลายชิ้น

@@ แถว 144: / แถว 144: @@
 ในกรณีของ M ที่กล่าวถึงข้างต้น เมื่อเราเลือกคอลัมน์ i และ j ใดๆ มาหามุมระหว่างกันแล้วจะได้ inner product ว่า
-<center><math>M_n(\omega)^{-1} = \frac{1}{n} M_n(\omega^{-1})</math></center>
+<center><math>1+\omega^{i-j}+\omega^{2(i-j)}+\cdots+\omega^{(n-1)(i-j)}</math></center>
 ----

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:37, 20 มิถุนายน 2550
แถว 139:		แถว 139:

	<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>		<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>M_n(\omega)^{-1} = \frac{1}{n} M_n(\omega^{-1})</math></center>
	----		----

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

@@ แถว 127: / แถว 127: @@
 \end{bmatrix}
 </math></center>
 ----

@@ แถว 115: / แถว 115: @@
+=
 \begin{bmatrix}
 & \omega & \omega^2 & \cdots & \omega^{n-1} \\
 \vdots & \vdots & \vdots & \ddots& \vdots \\
 & \omega^{n-1} & \omega^{2(n-1)} & \cdots &  \omega^{(n-1)(n-1)}

@@ แถว 106: / แถว 106: @@
 ==== Proof of Interpolation ====
 การที่เราสามารถพิจารณาค่าจำนวน n จุดของสมการ Polynomial ได้นั้น เราสามารถมองว่าเป็นการคูณกันระหว่าง Matrix ของ Coeffient และ Matrix ของตัวแปร ดังสมการต่อไปนี้
+<center>
 <math>\begin{bmatrix}
 f(x_0)\\
@@ แถว 126: / แถว 126: @@
 a_{n-1}
 \end{bmatrix}
-</math>
+</math></center>
 ----

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:13, 20 มิถุนายน 2550
แถว 105:		แถว 105:

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

		+	<math>\begin{bmatrix}
		+	f(x_0)\\
		+	f(x_1)\\
		+	\vdots \\
		+	f(x_{n-1})
		+	\end{bmatrix}
		+	=
		+	\begin{bmatrix}
		+	1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\
		+	1 & \omega^2 & \omega^4 & \cdots & \omega^{2(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>
	----		----

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:02, 20 มิถุนายน 2550
แถว 103:		แถว 103:

	จาก <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> เสมอ		จาก <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 ====

	----		----