การแก้ไขเชิงเส้น

จากวิกิพีเดีย สารานุกรมเสรี
ข้ามไปที่การนำทาง ข้ามไปที่การค้นหา
จากจุดสีแดงสองจุด เส้นสีน้ำเงินคืออินเทอร์โพแลนต์เชิงเส้นระหว่างจุด และอาจหาค่าyที่xได้โดยการแก้ไขเชิงเส้น

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

การประมาณค่าเชิงเส้นระหว่างจุดสองจุดที่รู้จัก

ในการแสดงภาพทางเรขาคณิตนี้ ค่าที่วงกลมสีเขียวคูณด้วยระยะห่างแนวนอนระหว่างวงกลมสีแดงและสีน้ำเงินจะเท่ากับผลรวมของค่าที่วงกลมสีแดงคูณด้วยระยะห่างแนวนอนระหว่างวงกลมสีเขียวและสีน้ำเงิน และค่าที่ วงกลมสีน้ำเงินคูณด้วยระยะห่างแนวนอนระหว่างวงกลมสีเขียวและสีแดง

หากพิกัดที่ทราบทั้งสองจุดนั้นกำหนดไว้ และ , อินเทอร์โพแลนต์เชิงเส้นคือเส้นตรงระหว่างจุดเหล่านี้ สำหรับค่าxในช่วงค่าyตามแนวเส้นตรงหาได้จากสมการความชัน

ซึ่งสามารถหาได้ทางเรขาคณิตจากรูปด้านขวา เป็นกรณีพิเศษของการประมาณค่าพหุนามด้วยn  = 1

การแก้สมการนี้สำหรับyซึ่งเป็นค่าที่ไม่รู้จักที่xให้

ซึ่งเป็นสูตรการประมาณค่าเชิงเส้นในช่วงเวลา . นอกช่วงเวลานี้สูตรเป็นเหมือนการคาดการณ์เชิงเส้น

สูตรนี้ยังสามารถเข้าใจได้ว่าเป็นค่าเฉลี่ยถ่วงน้ำหนัก น้ำหนักมีความสัมพันธ์ผกผันกับระยะทางจากจุดสิ้นสุดไปยังจุดที่ไม่รู้จัก จุดที่ใกล้กว่ามีอิทธิพลมากกว่าจุดที่ไกลออกไป น้ำหนักจึงเท่ากับ และ ซึ่งเป็นระยะห่างมาตรฐานระหว่างจุดที่ไม่รู้จักกับจุดสิ้นสุดแต่ละจุด เพราะสิ่งเหล่านี้รวมเป็น 1,

ซึ่งให้สูตรสำหรับการแก้ไขเชิงเส้นที่ให้ไว้ข้างต้น

การแก้ไขชุดข้อมูล

การประมาณค่าเชิงเส้นบนชุดข้อมูล (จุดสีแดง) ประกอบด้วยชิ้นส่วนของตัวแทรกเชิงเส้น (เส้นสีน้ำเงิน)

การประมาณค่าเชิงเส้นบนชุดของจุดข้อมูล ( x 0y 0 ), ( x 1y 1 ), …, ( x ny n ) ถูกกำหนดให้เป็นการต่อกันของค่า interpolants เชิงเส้นระหว่างจุดข้อมูลแต่ละคู่ ซึ่งส่งผลให้เกิดเส้นโค้งต่อเนื่องโดยมีอนุพันธ์ที่ไม่ต่อเนื่อง (โดยทั่วไป) ดังนั้นระดับความแตกต่างได้ .

การแก้ไขเชิงเส้นเป็นการประมาณ

การประมาณค่าเชิงเส้นมักใช้เพื่อประมาณค่าของฟังก์ชัน บางอย่างfโดยใช้ค่าที่รู้จักสองค่าของฟังก์ชันนั้นที่จุดอื่น ข้อผิดพลาดของการประมาณนี้ถูกกำหนดให้เป็น

โดยที่pหมายถึงพหุนามการแก้ไขเชิงเส้นที่กำหนดไว้ด้านบน:

สามารถพิสูจน์ได้โดยใช้ทฤษฎีบทของโรลว่าถ้าfมีอนุพันธ์อันดับสองต่อเนื่อง ข้อผิดพลาดนั้นจะถูกจำกัดด้วย

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

ประวัติและการใช้งาน

มีการใช้การประมาณค่าเชิงเส้นตั้งแต่สมัยโบราณเพื่อเติมช่องว่างในตาราง สมมติว่ามีตารางที่แสดงรายการประชากรของบางประเทศในปี 1970, 1980, 1990 และ 2000 และตารางนั้นต้องการประมาณจำนวนประชากรในปี 1994 การประมาณค่าเชิงเส้นเป็นวิธีที่ง่ายในการทำเช่นนี้ เชื่อกันว่าถูกใช้ในอาณาจักร Seleucid (สามศตวรรษก่อนคริสตกาล) และโดยนักดาราศาสตร์และนักคณิตศาสตร์ชาวกรีกHipparchus (ศตวรรษที่สองก่อนคริสต์ศักราช) คำอธิบายของการแก้ไขเชิงเส้นสามารถพบได้ในข้อความคณิตศาสตร์จีนโบราณที่เรียกว่าThe Nine Chapters on the Mathematical Art (九章算術) [1]ลงวันที่ 200 BC ถึง AD 100 และAlmagest (ศตวรรษที่ 2) โดยPtolemy.

การดำเนินการขั้นพื้นฐานของการสอดแทรกเชิงเส้นระหว่างสองค่าเป็นที่นิยมใช้ในคอมพิวเตอร์กราฟิกในศัพท์แสงของฟิลด์ว่ามันบางครั้งเรียกว่าlerpคำนี้สามารถใช้เป็นคำกริยาหรือคำนามสำหรับการดำเนินการ เช่น " อัลกอริธึมของ Bresenham lerps เพิ่มขึ้นระหว่างจุดปลายทั้งสองของบรรทัด"

การทำงานของ Lerp นั้นรวมอยู่ในฮาร์ดแวร์ของโปรเซสเซอร์กราฟิกคอมพิวเตอร์สมัยใหม่ทั้งหมด มักใช้เป็นส่วนประกอบสำคัญสำหรับการดำเนินการที่ซับซ้อนมากขึ้น ตัวอย่างเช่น การแก้ไขแบบ bilinearสามารถทำได้ในสาม lerps เนื่องจากการดำเนินการนี้มีราคาถูก จึงเป็นวิธีที่ดีในการใช้ตารางค้นหาที่แม่นยำด้วยการค้นหาฟังก์ชันที่ราบรื่นอย่างรวดเร็วโดยไม่ต้องมีรายการตารางมากเกินไป

ส่วนขยาย

การเปรียบเทียบการแก้ไขแบบเชิงเส้นและแบบสองมิติ การประมาณค่าแบบ 1 และ 2 มิติบางส่วน
จุดสีดำและสีแดง / เหลือง / เขียว / น้ำเงินสอดคล้องกับจุดที่สอดแทรกและตัวอย่างที่อยู่ใกล้เคียงตามลำดับ
ความสูงเหนือพื้นดินสอดคล้องกับค่านิยมของพวกเขา

ความแม่นยำ

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

หลายตัวแปร

การประมาณค่าเชิงเส้นตามที่อธิบายไว้ในที่นี้ใช้สำหรับจุดข้อมูลในมิติเชิงพื้นที่หนึ่งมิติ สำหรับสองมิติเชิงพื้นที่ส่วนขยายของเชิงเส้นที่เรียกว่าบิลิแนร์การแก้ไขและในสามมิติtrilinear แก้ไขอย่างไรก็ตาม โปรดสังเกตว่า อินเทอร์โพแลนต์เหล่านี้ไม่ใช่ฟังก์ชันเชิงเส้นของพิกัดเชิงพื้นที่อีกต่อไปแต่เป็นผลผลิตของฟังก์ชันเชิงเส้น นี่คือตัวอย่างที่ชัดเจนของการแก้ไขแบบ bilinear interpolationในรูปด้านล่าง นามสกุลอื่น ๆ ของเชิงเส้นสามารถนำไปใช้ชนิดอื่น ๆ ของตาข่ายเช่นรูปสามเหลี่ยมและ tetrahedral ตาข่ายรวมทั้งพื้นผิวเบซิเยร์สิ่งเหล่านี้อาจถูกกำหนดให้เป็นมิติที่สูงกว่าอย่างแท้จริงฟังก์ชันเชิงเส้นแบบทีละชิ้น (ดูรูปที่สองด้านล่าง)

ตัวอย่างของการประมาณค่าแบบ bilinear interpolationบนหน่วยกำลังสองด้วยค่าz 0, 1, 1 และ 0.5 ตามที่ระบุ ค่า Interpolated ระหว่างแสดงด้วยสี
ฟังก์ชันเชิงเส้นแบบทีละชิ้นในสองมิติ (บนสุด) และโพลิโทปนูนซึ่งเป็นเส้นตรง (ด้านล่าง)

รองรับภาษาโปรแกรม

ไลบรารี่และภาษาแรเงาจำนวนมากมีฟังก์ชันตัวช่วย "lerp" (ในGLSL ที่รู้จักกันในชื่อmixแทน) ส่งคืนการแก้ไขระหว่างสองอินพุต (v0, v1) สำหรับพารามิเตอร์ (t) ในช่วงหน่วยปิด [0, 1] ลายเซ็นระหว่างฟังก์ชัน lerp ถูกนำไปใช้อย่างหลากหลายในทั้งสองรูปแบบ (v0, v1, t) และ (t, v0, v1)

// วิธีที่ไม่ถูกต้องซึ่งไม่รับประกัน v = v1 เมื่อ t = 1 เนื่องจากข้อผิดพลาดเลขทศนิยม วิธีนี้เป็นแบบโมโนโทนิก
// แบบฟอร์มนี้อาจใช้เมื่อฮาร์ดแวร์มีคำสั่ง Native fused multiply-add 
float  lerp ( float  v0 ,  float  v1 ,  float  t )  { 
  return  v0  +  t  *  ( v1  -  v0 ); 
}

// วิธีที่แม่นยำซึ่งรับประกัน v = v1 เมื่อ t = 1 วิธีนี้เป็นแบบโมโนโทนิกก็ต่อเมื่อ v0 * v1 < 0 ค่า Lerping ระหว่างค่าเดียวกันอาจไม่สร้างค่าเดียวกัน
float  lerp ( float  v0 ,  float  v1 ,  float  t )  { 
  ผลตอบแทน ( 1  -  t )  *  v0  +  t  *  v1 ; 
}

ฟังก์ชัน lerp นี้มักใช้สำหรับการผสมอัลฟา (พารามิเตอร์ "t" คือ "ค่าอัลฟา") และอาจขยายสูตรเพื่อผสมองค์ประกอบหลายๆ อย่างของเวกเตอร์ (เช่น เชิงพื้นที่x , y , แกนzหรือr , g , ส่วนประกอบสี ) แบบขนาน

ดูเพิ่มเติม

อ้างอิง

  1. โจเซฟ นีดัม (1 มกราคม 2502) วิทยาศาสตร์และอารยธรรมในประเทศจีน: เล่มที่ 3 คณิตศาสตร์และวิทยาศาสตร์แห่งสวรรค์และโลก . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. หน้า 147–. ISBN 978-0-521-05801-8.

ลิงค์ภายนอก