การแก้ไขเส้นโค้ง

จากวิกิพีเดีย สารานุกรมเสรี
ข้ามไปที่การนำทาง ข้ามไปที่การค้นหา

ใน สาขา คณิตศาสตร์ของการวิเคราะห์เชิงตัวเลข การประมาณ ค่า splineเป็นรูปแบบหนึ่งของการ ประมาณค่า โดยที่ interpolantเป็นพหุนาม แบบ แยกส่วนแบบ พิเศษ ที่เรียกว่าspline นั่นคือ แทนที่จะใช้พหุนามระดับสูงเดี่ยวๆ กับค่าทั้งหมดพร้อมกัน การแทรกสอดแบบ spline จะปรับพหุนามระดับต่ำกับชุดย่อยเล็กๆ ของค่า เช่น การใส่พหุนามลูกบาศก์เก้าคู่ระหว่างแต่ละคู่ที่มีจุดสิบจุด , แทนที่จะใส่พหุนามสิบดีกรีเดียวให้เข้ากับพหุนามทั้งหมด การ ประมาณค่าแบบ Spline มักจะดีกว่า การประมาณค่า พหุนามเนื่องจากข้อผิดพลาด ในการประมาณค่าสามารถทำให้มีขนาดเล็กได้แม้ว่าจะใช้พหุนามดีกรีต่ำสำหรับเส้นโค้ง [1]การแก้ไข Spline ยังหลีกเลี่ยงปัญหาของปรากฏการณ์ Rungeซึ่งการสั่นอาจเกิดขึ้นระหว่างจุดต่างๆ เมื่อทำการประมาณค่าโดยใช้พหุนามระดับสูง

บทนำ

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

เดิมsplineเป็นคำที่ใช้เรียกไม้บรรทัดแบบยืดหยุ่น ที่โค้งงอเพื่อผ่านจุดที่กำหนดไว้ล่วงหน้าจำนวนหนึ่งหรือนอต สิ่งเหล่านี้ถูกใช้เพื่อสร้างภาพวาดทางเทคนิคสำหรับการต่อเรือและการก่อสร้างด้วยมือดังแสดงในภาพ

เราต้องการจำลองเส้นโค้งประเภทเดียวกันโดยใช้ชุดสมการทางคณิตศาสตร์ที่มีพหุนามหนึ่งตัวสำหรับนอตแต่ละคู่และ, ที่ไหน. จึงจะมีพหุนามและนอต: พหุนามแรกเริ่มต้นที่และพหุนามสุดท้ายสิ้นสุดที่.

ความโค้งของเส้นโค้งใด ๆถูกกำหนดเป็น

เพื่อให้ spline มีรูปร่างที่ลดการโค้งงอ (ภายใต้ข้อจำกัดของผ่านนอตทั้งหมด) เราจะกำหนดทั้งสองและให้ต่อเนื่องทุกที่ รวมทั้งที่ปม ดังนั้นอนุพันธ์อันดับหนึ่งและอันดับสองของพหุนามต่อเนื่องกันแต่ละตัวจึงต้องมีค่าเท่ากันที่นอต กล่าวคือ

สิ่งนี้สามารถทำได้ก็ต่อเมื่อมีการใช้พหุนามระดับ 3 หรือสูงกว่า - พหุนามลูกบาศก์หรือสูงกว่า - วิธีการแบบคลาสสิกคือการใช้พหุนามที่มีดีกรี 3 — เส้นโค้งลูกบาศก์

อัลกอริธึมเพื่อค้นหาเส้นโค้งลูกบาศก์ที่สอดแทรก

เราต้องการที่จะหาแต่ละพหุนามได้รับคะแนนผ่าน. ในการทำเช่นนี้ เราจะพิจารณาเพียงส่วนโค้งเดียวซึ่งจะสอดแทรกจากถึง. ชิ้นนี้จะมีความลาดชันและที่จุดสิ้นสุดของมัน หรืออย่างแม่นยำยิ่งขึ้น

สมการเต็มสามารถเขียนในรูปแบบสมมาตรได้

 

 

 

 

( 1 )

ที่ไหน

 

 

 

 

( 2 )

 

 

 

 

( 3 )

 

 

 

 

( 4 )

แต่อะไรคือและ? ในการได้มาซึ่งค่าวิกฤตเหล่านี้ เราต้องพิจารณาว่า

แล้วตามนั้น

 

 

 

 

( 5 )

 

 

 

 

( 6 )

การตั้งค่าt = 0และt = 1ตามลำดับในสมการ ( 5 ) และ ( 6 ) ได้มาจาก ( 2 ) ซึ่งเป็นอนุพันธ์อันดับแรกq′ ( x 1 ) = k 1และq′ ( x 2 ) = k 2และ อนุพันธ์อันดับสอง

 

 

 

 

( 7 )

 

 

 

 

( 8 )

ถ้าตอนนี้( x i , y i ), i = 0, 1, ..., nคือn + 1 points และ

 

 

 

 

( 9 )

โดยที่i = 1, 2, ..., n , และเป็นพหุนามดีกรีสามระดับn ตัวที่สอดแทรก yในช่วงเวลาx i -1xx iสำหรับi = 1, ..., nเช่นนั้นq′ i ( x i ) = q′ i +1 ( x i )สำหรับi = 1, ..., n  − 1 จากนั้น พหุนาม nร่วมกันกำหนดฟังก์ชันดิฟเฟอเรนติเอเบิลในช่วงเวลาx 0xx nและ

 

 

 

 

( 10 )

 

 

 

 

( 11 )

สำหรับi = 1, ..., n , โดยที่

 

 

 

 

( 12 )

 

 

 

 

( 13 )

 

 

 

 

( 14 )

ถ้าลำดับk 0 , k 1 , ..., k nเป็นลำดับนั้น นอกจากนี้q′′ i ( x i ) = q′′ i +1 ( x i )ถือไว้สำหรับi = 1, ... , n  − 1 จากนั้นฟังก์ชันผลลัพธ์จะมีอนุพันธ์อันดับสองที่ต่อเนื่องกันด้วยซ้ำ

จาก ( 7 ), ( 8 ), ( 10 ) และ ( 11 ) จะเป็นเช่นนี้ก็ต่อเมื่อ

 

 

 

 

( 15 )

สำหรับi = 1, ..., n  − 1 ความสัมพันธ์ ( 15 ) คือn − 1สมการเชิงเส้นสำหรับค่าn + 1 k 0 , k 1 , ... , k n

สำหรับไม้บรรทัดแบบยืดหยุ่นที่เป็นต้นแบบของการแก้ไข spline แบบหนึ่งมีปุ่มที่ด้านซ้ายของ "ปม" ด้านซ้ายสุด และด้านขวาของ "นอต" ด้านขวาสุด ไม้บรรทัดสามารถเคลื่อนที่ได้อย่างอิสระและจะอยู่ในรูปแบบของ เส้นตรงที่มีq′ = 0 . เนื่องจากq′ควรเป็นฟังก์ชันต่อเนื่องของx จึงควรมี "เส้นโค้งธรรมชาติ" นอกเหนือจากสมการเชิงเส้นn -1 ( 15 )

นั่นคือ

 

 

 

 

( 16 )

 

 

 

 

( 17 )

ในที่สุด ( 15 ) ร่วมกับ ( 16 ) และ ( 17 ) จะเป็นสมการเชิงเส้นn + 1 ที่กำหนด พารามิเตอร์n + 1อย่าง เฉพาะเจาะจง k 0 , k 1 , ... , k n

มีเงื่อนไขอื่น ๆ ที่สิ้นสุดคือ "clamped spline" ซึ่งระบุความชันที่ปลาย spline และ "not-a-knot spline" ที่เป็นที่นิยมซึ่งต้องการให้อนุพันธ์อันดับสามต่อเนื่องกันที่x 1และx n -1คะแนน สำหรับ spline "not-a-knot" สมการเพิ่มเติมจะอ่านได้ว่า:

ที่ไหน.

ตัวอย่าง

การแก้ไขด้วยเส้นโค้ง "ธรรมชาติ" ลูกบาศก์ระหว่างสามจุด

ในกรณีของสามจุดค่าสำหรับหาได้จากการแก้ระบบสมการเชิงเส้นสามเหลี่ยม

กับ

สำหรับสามแต้ม

หนึ่งได้รับที่

และจาก ( 10 ) และ ( 11 ) ว่า

ในรูป ฟังก์ชัน spline ประกอบด้วยพหุนามลูกบาศก์ 2 ตัวและกำหนดโดย ( 9 ) จะปรากฏขึ้น

ดูเพิ่มเติม

รหัสคอมพิวเตอร์

TinySpline: โอเพ่นซอร์ส C-library สำหรับ splines ที่ใช้การประมาณการ cubic spline

SciPy Spline Interpolation: แพ็คเกจ Python ที่ใช้การแก้ไข

การประมาณค่าลูกบาศก์: โอเพ่นซอร์ส C#-ไลบรารี่สำหรับการประมาณค่าเส้นโค้งลูกบาศก์

อ้างอิง

  1. ฮอลล์ ชาร์ลส์ เอ.; เมเยอร์, ​​เวสตัน ดับเบิลยู. (1976) "ขอบเขตข้อผิดพลาดที่เหมาะสมที่สุดสำหรับการประมาณค่า Cubic Spline " วารสารทฤษฎีการประมาณ . 16 (2): 105–122. ดอย : 10.1016/0021-9045(76)90040-X .

ลิงค์ภายนอก