พิสูจน์ Binet’s formula / Matrix Exponentiation / Fast Doubling ในการหาค่าลำดับฟีโบนัชชี

Image from https://stringfixer.com/

วิธีการหาค่าลำดับฟีโบนัชชีด้วยอัลกอริทึมต่าง ๆ สามารถอ่านเพิ่มเติมได้ที่ การหาค่าลำดับ Fibonacci สำหรับในบทความนี้จะทำการแสดงที่มาของสูตร

จะทำการอธิบายสิ่งที่ต้องใช้ 2 เรื่องก่อน คือ
1. Eigen value , Eigen vector
2. การยกกำลังเมทริกซ์
หากเข้าใจอยู่แล้วสามารถข้ามไปอ่านที่ขั้นตอนการพิสูจน์ได้เลย

Eigen value(ค่าเจาะจง) , Eigen vector(เวกเตอร์เจาะจง)
หากมีเมทริกซ์ A เราจะสามารถเขียนให้อยู่ในรูป AV = λV
เมื่อ
V คือ เมทริกซ์ที่มีขนาด nx1 และไม่เป็นเมทริกซ์ศูนย์ เรียกว่า vector
λ คือ ค่าคงที่ค่าหนึ่งที่ ซึ่งจะเปลี่ยนตามเมทริกซ์ A

                        AV = λV
                   (A-λI)V = 0
สมการนี้จะเป็นจริง เมื่อ det(A-λI) = 0

เมื่อ I คือ เมทริกซ์ เอกลักษณ์

ตัวอย่าง

จากนั้นหา Eigen vector จาก Eigen value แต่ละตัว(ตัวอย่างแสดงที่ λ1)

(Eigen vector มักเขียนให้อยู่ในรูปแบบสัดส่วนอย่างต่ำ)

ลองแทนค่าสิ่งที่ได้ใน AV = λV ดู(ใช้กรณี λ1 เป็นตัวอย่าง)

จะพบว่าสมการเป็นจริง

การยกกำลังเมทริกซ์ (Matrix Exponentiation)
โดยทั่วไปการยกกำลังเมทริกซ์ ก็จะนำเอาเมทริกซ์มาคูณกันไปเรื่อย ๆ ตามจำนวนเลขชี้กำลัง ถ้าเมทริกซ์มีขนาดเล็กและยกกำลังไม่มากก็สามารถคำนวณผลออกมาได้ไม่ยาก แต่ถ้าเมทริกซ์มีขนาดใหญ่และเลขชี้กำลังมีค่ามาก การคำนวนก็จำเป็นต้องใช้เวลาและหน่วยความจำในปริมาณมากตามไปด้วย

จากความรู้เรื่อง Eigen value , Eigen vector เราสามารถที่จะเขียนเมทริกซ์ให้อยู่ในรูป

เมื่อ

T คือ เมทริกซ์ของ Eigen Vector
D คือ นำ Eigen value มาเรียงตามแนวเส้นทะแยงมุมหลัก ตำแหน่งอื่นให้เป็น 0

หากต้องการหาค่า Aⁿ สามารถเขียนได้เป็น ดังนี้

จะเห็นว่าเราสามารถหาค่ายกกำลังเมทริกซ์เฉพาะ D ซึ่งเป็น Diagonal matrix ทำให้การยกกำลังเมทริกซ์ ลดขนาดลงไปได้มาก (เพราะว่ามี 0 อยู่ในตำแหน่งที่ไม่ใช่เส้นทะแยงมุมหลัก)

จากสิ่งที่ได้กล่าวมาสามารถนำมาพิสูจน์สูตรได้ ดังนี้
จากนิยามลำดับฟีโบนัชชี

สามารถเขียนให้อยู่ในรูปเมทริกซ์ ได้ดังนี้

แทนค่า n = 1 , 2 , … , n

แทนค่า n = 1

แทนค่า n = 2

แทนค่า n = n (กรณีทั่วไป)

จะเห็นว่าหากต้องการค่าลำดับฟีโบนัชชีที่ตำแหน่ง n คือ Fₙ จะต้องทำการหาค่ายกกำลังเท่ากับ n ดังนั้น จะทำการแปลงเมทริกซ์ยกกำลังให้อยู่ในรูป A = TD(Inv(T))

สำหรับ Fast Doubling Method พิสูจน์ได้ ดังนี้

ในบทความนี้ได้ทำการแสดงวิธีการได้มาของสูตรที่ใช้ในการหาค่าลำดับฟีโบนัชชี สำหรับการนำไปประยุกต์เขียนโปรแกรม สามารถอ่านเพิ่มเติมได้ที่บทความที่ได้ให้ไว้ที่ตอนต้นของบทความนี้