กลับไปหน้าบทความ

อ่าน 15 นาที

พหุนามลากรางจ์

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

พหุนามลากรางจ์

ภาพนี้แสดงพหุนามการประมาณค่าแบบลูกบาศก์L ( x ) (เส้นประสีดำ) สำหรับจุดข้อมูลสี่จุด ( (−9, 5) , (−4, 2) , (−1, −2) , (7, 9) ) ซึ่งเป็นผลรวมของพหุนามฐานที่ปรับขนาดแล้ว y₀ℓ₀(x) , y₁ℓ₁( x ) , y₂ℓ₂ ( x ) และ y₃ℓ₃ ( x ) พหุนามการประมาณค่านี้ผ่านจุดควบคุมทั้งสี่จุดและพหุนามฐานที่ปรับขนาดแล้วแต่ละตัวจะผ่านจุดควบคุมที่เกี่ยวข้องและมีค่าเป็น0 เมื่อxสอดคล้องกับจุดควบคุมอีกสามจุด

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

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

แม้ว่าจะตั้งชื่อตามโจเซฟ-หลุยส์ ลากรองจ์ผู้ตีพิมพ์ในปี 1795 [ 1 ] แต่ วิธีการนี้ถูกค้นพบครั้งแรกในปี 1779 โดยเอ็ดเวิร์ด วอริ่ง [ 2 ] นอกจากนี้ยังเป็นผลลัพธ์ที่ง่ายจากสูตรที่ตีพิมพ์ในปี 1783 โดยเลออนฮาร์ด ออยเลอร์[ 3 ]

การประยุกต์ใช้พหุนามลากรางจ์ ได้แก่ วิธีการอินทิเก รตเชิงตัวเลขของนิวตัน-โคทส์แผนการแบ่งปันความลับของชามีร์ในด้านการเข้ารหัสและการแก้ไขข้อผิดพลาดของรีด-โซโลมอนใน ทฤษฎี การ เข้ารหัส

สำหรับจุดที่มีระยะห่างเท่ากัน การประมาณค่าแบบลากรางจ์มีความเสี่ยงที่จะเกิดปรากฏการณ์การแกว่งตัวขนาดใหญ่แบบ รันจ์

คำนิยาม

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

โปรดสังเกตว่าตัวเศษมีรากอยู่ที่จุดโหนดในขณะที่ตัวส่วนปรับขนาดพหุ นามที่ได้เพื่อให้

พหุนามการประมาณค่าแบบลากรางจ์สำหรับจุดต่างๆ ผ่านค่า ที่สอดคล้องกัน คือการรวมเชิงเส้น :

พหุนามฐานแต่ละตัวมีดีกรี⁠ ⁠ดังนั้นผลรวม⁠ ⁠จึง มีดีกรี⁠ ⁠และเป็นการประมาณค่าในช่วงข้อมูลเนื่องจาก⁠ ⁠

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

รูปแบบศูนย์กลางมวล

พหุนามฐาน Lagrange แต่ละตัวสามารถเขียนใหม่ได้เป็นผลคูณของสามส่วน ได้แก่ ฟังก์ชันที่ใช้ ร่วมกันในพหุนามฐานทุก ตัวค่าคงที่เฉพาะโหนด(เรียกว่าน้ำหนักแบรีเซนทริก ) และส่วนที่แสดงถึงการกระจัดจากถึง : [ 4 ]

โดยการดึงตัวประกอบออกจากผลรวม เราสามารถเขียนพหุนามลากรางจ์ในรูปแบบที่เรียกว่ารูปแบบแบรีเซนทริกแรก ได้ :

หาก ได้คำนวณน้ำหนักไว้ ล่วงหน้า แล้ว ขั้น ตอน นี้จะใช้การคำนวณเพียง ไม่กี่ครั้งเมื่อเทียบกับการคำนวณพหุนามฐานลากรางจ์แต่ละตัวแยกกัน (ดูสัญลักษณ์ Big O )

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

สำหรับx ใด ๆเนื่องจากฟังก์ชันคงที่คือพหุนามดีกรีเดียวที่แทรกข้อมูลดังนั้นเราจึงสามารถลดรูปสูตร barycentric ให้ง่ายขึ้นได้อีกโดยการหาร { :

นี่เรียกว่ารูปแบบที่สองหรือรูปแบบที่แท้จริงของสูตรการประมาณค่าแบบแบรีเซนทริก

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

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

พหุนามฐานลากรางจ์แต่ละตัวสามารถเขียนในรูปแบบแบรีเซนทริกได้เช่นกัน:

มุมมองจากพีชคณิตเชิงเส้น

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

โครงสร้างนี้คล้ายคลึงกับทฤษฎีบทเศษเหลือของจีนแทนที่จะตรวจสอบเศษเหลือของการหารจำนวนเต็มด้วยจำนวนเฉพาะ เราจะตรวจสอบเศษเหลือของการหารพหุนามด้วยตัวหารเชิงเส้น

นอกจากนี้ เมื่อลำดับมีขนาดใหญ่การแปลงฟูริเยร์แบบเร็ว (Fast Fourier Transformation)สามารถนำมาใช้เพื่อหาค่าสัมประสิทธิ์ของพหุนามที่แทรกเข้าไปได้

ตัวอย่าง

เราต้องการทำการประมาณค่าในช่วงโดเมนณ จุดทั้งสามจุด:

พหุนามโหนดคือ

น้ำหนักบารีเซนทริกคือ

พหุนามฐานลากรางจ์คือ

พหุนามการประมาณค่าแบบลากรางจ์คือ:

ในรูปแบบแบรีเซนทริก (แบบที่สอง)

หมายเหตุ

ตัวอย่างของการล divergence ในการประมาณค่าในช่วงสำหรับชุดพหุนามลากรางจ์

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

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

การแทรกสอดแบบ Lagrange และการแทรกสอดอื่นๆ ที่จุดเว้นระยะห่างเท่ากัน ดังตัวอย่างข้างต้น จะให้พหุนามที่แกว่งไปมาเหนือและใต้ฟังก์ชันจริง พฤติกรรมนี้มีแนวโน้มที่จะเพิ่มขึ้นตามจำนวนจุด ทำให้เกิดความแตกต่างที่เรียกว่าปรากฏการณ์ Rungeปัญหานี้สามารถกำจัดได้โดยการเลือกจุดแทรกสอดที่โหนด Chebyshev [ 5 ]

สามารถใช้พหุนามฐานลากรางจ์ในการอินทิเกรตเชิงตัวเลขเพื่อหาอนุพันธ์ของสูตรนิวตัน-โคเตสได้

เศษเหลือในสูตรการแทรกสอดแบบลากรางจ์

เมื่อทำการประมาณค่าฟังก์ชันf ที่กำหนด โดยใช้พหุนามดีกรีkที่จุดโหนดเราจะได้ส่วนที่เหลือซึ่งสามารถแสดงได้ดังนี้[ 6 ]

สัญลักษณ์ที่ใช้แทนผลต่างหาร คือ หรืออีกทางหนึ่ง เศษเหลือสามารถแสดงได้ในรูปอินทิกรัลเส้นโค้งในโดเมนเชิงซ้อนดังนี้

ส่วนที่เหลือสามารถผูกมัดได้ดังนี้

อนุพันธ์

เห็นได้ชัดว่าเป็นศูนย์ที่จุดโหนด ในการหาที่จุดให้กำหนดฟังก์ชันใหม่และเลือกโดยที่เป็นค่าคงที่ที่เราต้องหาค่าสำหรับ ที่กำหนดเราเลือกเพื่อให้มีศูนย์ (ที่ทุกโหนด และ) ระหว่างและ(รวมถึงจุดปลาย) สมมติว่าสามารถหาอนุพันธ์ได้ ครั้ง เนื่องจากและเป็นพหุนาม ดังนั้น จึงสามารถหาอนุพันธ์ได้ไม่จำกัดครั้ง ดังนั้นจะสามารถหาอนุพันธ์ได้ ครั้ง ตามทฤษฎีบทของโรลล์มีศูนย์มีศูนย์... มีศูนย์ 1 จุด สมมติว่า โดยที่เขียนอย่างชัดเจนว่า :

(เพราะกำลังสูงสุดของin คือ)

สมการสามารถจัดเรียงใหม่ได้ดังนี้[ 7 ]

เนื่องจากเรามี

อนุพันธ์

อนุพันธ์อันดับที่dของพหุนามประมาณค่าแบบลากรางจ์สามารถเขียนได้ในรูปของอนุพันธ์ของพหุนามพื้นฐาน

โปรดจำไว้ (ดูหัวข้อ § คำจำกัดความด้านบน) ว่าพหุนามฐานลากรางจ์แต่ละตัวคือ

สามารถหาอนุพันธ์อันดับแรกได้โดยใช้กฎการคูณ :

อนุพันธ์อันดับสองคือ

อนุพันธ์อันดับสามคือ

และเช่นเดียวกันสำหรับอนุพันธ์อันดับสูงกว่า

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

ฟิลด์จำกัด

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

ดูเพิ่มเติม

  • "สูตรการแทรกสอดของลากรางจ์" , สารานุกรมคณิตศาสตร์ , EMS Press , 2001 [1994]
  • ALGLIBมีการใช้งานในภาษา C++ / C# / VBA / Pascal
  • GSLมีโค้ดการประมาณค่าแบบพหุนามในภาษาซี
  • SOมีตัวอย่าง MATLAB ที่สาธิตอัลกอริธึมและสร้างภาพแรกในบทความนี้ขึ้นมาใหม่
  • วิธีการประมาณค่าแบบลากรางจ์ — บันทึกย่อ, สไลด์นำเสนอ, Mathcad, Mathematica, MATLAB, Maple
  • พหุนามการประมาณค่าแบบลากรางจ์บนเว็บไซต์ www.math-linux.com
  • ไวส์สไตน์, เอริค ดับเบิลยู. "พหุนามแทรกสอดลากรางจ์" . MathWorld .
  • ฟังก์ชันในเวิร์กชีต Excel สำหรับการประมาณค่าแบบ Bicubic Lagrange
  • พหุนามลากรางจ์ใน Python
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Lagrange_polynomial&oldid=1351468117 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ พหุนามลากรางจ์

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

คำนิยาม

กำหนดให้เซตของโหนด ⁠ ⁠ k + 1 {\displaystyle k+1} ซึ่ง ต้องแตกต่างกันทั้งหมดสำหรับดัชนี ⁠ ⁠ ฐาน ลากรางจ์ สำหรับพหุนามดีกรี ⁠ ⁠ สำหรับโหนดเหล่านั้นคือเซตของพหุนามแต่ละตัวดีกรี ⁠ ⁠ ซึ่งมีค่า ⁠ ⁠ ถ้า ⁠ ⁠ และ ⁠ ⁠ โดย ใช้ เดลต้าโครเนกเกอร์ สามารถเขียนได้ดังนี้ ⁠ ⁠...

รูปแบบศูนย์กลางมวล

พหุนามฐาน Lagrange แต่ละตัว สามารถเขียน ℓ j ( x ) {\displaystyle \textstyle \ell _{j}(x)} ใหม่ได้เป็นผลคูณของสามส่วน ได้แก่ ฟังก์ชัน ที่ ใช้ ร่วมกันในพหุนามฐานทุก ℓ ( x ) = ∏ m ( x − x m ) {\displaystyle \textstyle \ell (x)=\prod _{m}(x-x_{m})} ตัว ค่า คง w j...

มุมมองจากพีชคณิตเชิงเส้น

การแก้ ปัญหาการประมาณค่าในช่วง นำไปสู่ปัญหาใน พีชคณิตเชิงเส้น ซึ่งเทียบเท่ากับการหาเมทริกซ์ผกผัน หากใช้ ฐานเอกนาม มาตรฐาน สำหรับพหุนามการประมาณค่าในช่วงเราต้องหา เมทริกซ์ผกผันของ Vandermonde เพื่อหาค่าสัมประสิทธิ์ของโดยการเลือกฐานที่ดีกว่า คือ ฐาน Lagrange...