วิธีของนิวตัน: หาเฉพาะคำตอบอย่างรวดเร็วด้วยการประมาณเชิงทำซ้ำ

สมการบางอย่างไม่มีวิธีแก้เชิงพีชคณิตที่เป็นระเบียบสวยงาม

จะลองแยกตัวประกอบหรือแทนค่าก็ได้ตามใจ แต่บางสมการไม่มีรูปแบบคำตอบปิด เช่น พหุนามดีกรีตั้งแต่ห้าขึ้นไปไม่มีวิธีแก้เชิงพีชคณิตทั่วไป ฟังก์ชันที่ผสมเอ็กซ์โพเนนเชียลกับพหุนามอย่าง e^x = 3x ก็อยู่ในกลุ่มเดียวกัน กรณีแบบนี้ต้องใช้วิธีคิดอีกแบบ

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

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

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

วิธีของนิวตันคืออะไร

วิธีของนิวตันเป็นเทคนิคเชิงทำซ้ำเพื่อหาเฉพาะคำตอบของฟังก์ชัน เฉพาะคำตอบคือค่าอินพุตที่ทำให้ค่าฟังก์ชันเท่ากับศูนย์

เริ่มจากการเดาครั้งแรก จากนั้นใช้เรขาคณิตของฟังก์ชัน ณ จุดนั้นเพื่อเดาให้ดีขึ้น ทำซ้ำขั้นตอนนี้ และแต่ละรอบจะพาเข้าใกล้เฉพาะคำตอบจริง

แนวคิดมีเท่านี้ ต้องมีเพียงกฎอัปเดตที่ฉลาด ทำซ้ำได้ และลู่เข้าคำตอบ

สูตรของวิธีนิวตัน

แก่นของวิธีนิวตันคือกฎอัปเดตเพียงข้อเดียวที่ใช้ซ้ำจนเข้าใกล้เฉพาะคำตอบพอ

สูตรมีดังนี้:

สูตรวิธีของนิวตัน

แต่ละรอบจะนำค่าประมาณปัจจุบัน x_n ไปสร้างค่าที่ดีกว่า x_{n+1} ทำซ้ำจนผลลัพธ์ใกล้ศูนย์พอ

สูตรประกอบด้วยสามองค์ประกอบ:

• x_n - ค่าประมาณเฉพาะคำตอบในปัจจุบัน

• f(x_n) - ค่าฟังก์ชันที่ค่าประมาณนั้น

• f'(x_n) - อนุพันธ์ของฟังก์ชันที่ค่าประมาณนั้น บอกความชันของเส้นสัมผัส

ถ้า f(x_n) มีค่าสูง แสดงว่ายังห่างจากเฉพาะคำตอบ ถ้า f'(x_n) ชัน ฟังก์ชันกำลังเปลี่ยนแปลงเร็ว จึงก้าวได้ไกลขึ้น อัตราส่วน f(x_n) / f'(x_n) บอกระยะที่ควรขยับพอดี แล้วนำไปลบจากค่าที่เดาปัจจุบันเพื่อเข้าใกล้ขึ้น

ถ้า f'(x_n) เป็นศูนย์หรือใกล้ศูนย์ สูตรจะใช้ไม่ได้ เพราะต้องหารด้วยศูนย์ ทำให้ไม่สามารถสร้างค่าประมาณถัดไปได้ จะอธิบายรายละเอียดในส่วนข้อจำกัด

วิธีการทำงานของวิธีนิวตัน

วิธีนิวตันทำซ้ำสี่ขั้นตอนเดิมทุกครั้ง

1. เลือกการเดาเริ่มต้น: เลือกค่าเริ่ม x_0 ใกล้ ๆ กับเฉพาะคำตอบ ไม่ต้องเป๊ะ เพียงพอให้ฟังก์ชันมีพฤติกรรมคาดเดาได้รอบจุดนั้น จะอธิบายว่า “ใกล้พอ” หมายถึงอะไรในส่วนการลู่เข้า

2. คำนวณค่าฟังก์ชัน: ประเมินค่า f(x_0) เพื่อบอกว่าที่ค่าประมาณปัจจุบัน ฟังก์ชันห่างจากศูนย์แค่ไหน ถ้า f(x_0) = 0 ก็เสร็จสิ้น พบเฉพาะคำตอบแล้ว

3. คำนวณอนุพันธ์: ประเมินค่า f'(x_0) ซึ่งเป็นความชันของฟังก์ชันที่ x_0 นั่นคือความชันของเส้นสัมผัสที่จุดนั้น

4. อัปเดตค่าประมาณ: ใช้กฎอัปเดตตามสูตรในส่วนก่อนหน้า

แค่นี้ก็เรียบร้อย

ค่าใหม่ x_1 คือจุดที่เส้นสัมผัสตัดแกน x ในเชิงเรขาคณิต คือการลากเส้นตรงที่สัมผัสโค้งที่ x_0 แล้วตามลงมาจนถึงศูนย์ จุดตัดนั้นคือการเดาครั้งถัดไปที่ดีกว่า

จากนั้นทำซ้ำ นำ x_1 ไปทำขั้นตอนที่ 2 ถึง 4 เพื่อได้ x_2 แล้ว x_3 ต่อไป แต่ละรอบจะวาดเส้นสัมผัสใหม่ที่จุดอัปเดตแล้วหาจุดตัดแกน x

หยุดเมื่อ f(x_n) ใกล้ศูนย์พอ โดยทั่วไปคือเมื่อค่าต่ำกว่าค่ากำหนดเล็ก ๆ ที่ตั้งไว้ล่วงหน้า

มุมมองเรขาคณิตของวิธีนิวตัน

นึกภาพเส้นโค้งบนกราฟ นั่นคือฟังก์ชัน f(x) เฉพาะคำตอบคือจุดที่โค้งตัดแกน x ยังไม่รู้ว่าจุดตัดอยู่ไหน จึงเริ่มเดา x_0 บนแกน x ก่อน

ในแต่ละขั้น ให้วางจุด (x_0, f(x_0)) บนโค้ง แล้ววาดเส้นสัมผัสที่จุดนั้น เส้นตรงที่สัมผัสโค้งและมีความชันเดียวกัน เส้นสัมผัสนั้นจะเอียง และถ้าตามลงไปจะตัดแกน x ที่จุดหนึ่ง จุดตัดนั้นคือค่าประมาณถัดไป x_1

จากนั้นทำซ้ำ ที่ x_1 วาดเส้นสัมผัสใหม่แล้วหาจุดตัดแกน x ได้ x_2 แต่ละเส้นสัมผัสเป็นการประมาณเชิงเส้นเฉพาะที่ของโค้ง และแต่ละจุดตัดจะลงใกล้เฉพาะคำตอบจริงมากขึ้น

แผนภูมิด้านล่างแสดงสองรอบของวิธีนิวตันที่ใช้กับ f(x) = x^2 - 2 โดยเริ่มจาก x_0 = 2.5:

แผนภูมิการตีความเชิงเรขาคณิต

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

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

ตัวอย่างทีละขั้นของวิธีนิวตัน

ลองใช้วิธีนิวตันกับ f(x) = x^2 - 2 เฉพาะคำตอบของฟังก์ชันนี้คือ x = sqrt(2) ≈ 1.4142 กล่าวคือกำลังคำนวณรากที่สองของ 2

อนุพันธ์คือ f'(x) = 2x ดังนั้นกฎอัปเดตกลายเป็น:

ตัวอย่าง (กฎอัปเดต)

เริ่มจากการเดาแรก x_0 = 2.5

รอบที่ 1:

ตัวอย่าง (รอบที่ 1)

รอบที่ 2:

ตัวอย่าง (รอบที่ 2)

รอบที่ 3:

ตัวอย่าง (รอบที่ 3)

แค่สามรอบก็ได้ความแม่นยำถึงสี่ตำแหน่งทศนิยมแล้ว ค่าคลาดเคลื่อนลดจาก 1.086 ที่ x_0 เหลือ 0.0001 ที่ x_3 และลดลงต่อในแต่ละขั้น

ภาพต่อไปนี้แสดงการทำงานของค่าประมาณและค่าคลาดเคลื่อนแบบมองเห็น:

ภาพรวมเชิงภาพของค่าประมาณและค่าคลาดเคลื่อน

แผงซ้ายแสดงว่าค่าประมาณแต่ละครั้งเข้าใกล้ sqrt(2) ≈ 1.4142 อย่างไร ส่วนแผงขวาแสดงค่าคลาดเคลื่อนที่เล็กลงในสเกลลอการิทึม โดยแต่ละรอบเพิ่มความละเอียดโดยประมาณเป็นกำลังสองของรอบก่อน

การลู่เข้าของวิธีนิวตัน

วิธีนิวตันลู่เข้าได้เร็ว แต่ต้องอยู่ในเงื่อนไขที่เหมาะสม

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

มีสองเงื่อนไขที่ต้องเป็นจริง:

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

โหมดล้มเหลวที่พบบ่อยที่สุดคืออนุพันธ์ใกล้ศูนย์ 

ถ้า f'(x_n) ใกล้ศูนย์ จะต้องหารด้วยจำนวนเล็กมากในกฎอัปเดต ทำให้ค่าประมาณถัดไปกระเด็นไกลจากเฉพาะคำตอบ ในกรณีแย่สุดเมื่อ f'(x_n) = 0 การคำนวณจะใช้งานไม่ได้เพราะหารด้วยศูนย์ไม่ได้

จุดเริ่มที่ไม่ดีอาจทำให้วิธีสลับไปมา (oscillate) หรือดิฟเวิร์จ แทนที่จะเข้าใกล้เฉพาะคำตอบ ค่าประมาณกลับเด้งไปมาหรือไกลออกเรื่อย ๆ ในแต่ละรอบ

วิธีนิวตันได้ผลดีเมื่อเตรียมพร้อมดี เดาเริ่มต้นที่เหมาะสมและฟังก์ชันที่เรียบก็เพียงพอสำหรับการลู่เข้า และลู่เข้าอย่างรวดเร็ว

ข้อดีของวิธีนิวตัน

เมื่อเงื่อนไขเหมาะสม วิธีนิวตันยากจะถูกแซง

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

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

ข้อจำกัดของวิธีนิวตัน

วิธีนิวตันแลกความเร็วมากับข้อกำหนดหลายอย่าง ต่อไปนี้คือข้อจำกัดที่ควรคำนึงถึง:

• ต้องมีอนุพันธ์: ต้องมีนิพจน์วิเคราะห์ของ f'(x) ก่อนจะเริ่มทำรอบแรก สำหรับฟังก์ชันที่อนุพันธ์คำนวณยาก (หรือไม่มี) ควรใช้วิธีอื่น

• อ่อนไหวต่อการเดาเริ่มต้น: หากเริ่มไกลจากเฉพาะคำตอบ วิธีอาจพาไปผิดทาง

• อาจไม่ลู่เข้า: หากฟังก์ชันมีบริเวณแบนหรือโค้งหัก การประมาณด้วยเส้นสัมผัสอาจใช้ไม่ได้ผล

• อาจดิฟเวิร์จหรือสั่นไปมา: ในกรณีแย่ ค่าประมาณไม่ลู่เข้าและออกห่างจากเฉพาะคำตอบ หรือเด้งไปมาไม่สิ้นสุด

ดังนั้นก่อนหยิบใช้วิธีนิวตัน ควรทำความเข้าใจฟังก์ชันของตนเองก่อน

วิธีนิวตันเทียบกับวิธีหาเฉพาะคำตอบอื่น

วิธีนิวตันไม่ใช่วิธีเดียวในการหาเฉพาะคำตอบ และไม่ใช่วิธีที่เหมาะเสมอไป

อีกสองวิธีที่พบได้บ่อยคือ วิธีแบ่งครึ่งช่วง (bisection) และวิธีซีแคนต์ (secant) ขอสรุปสั้น ๆ

วิธีแบ่งครึ่งช่วง (Bisection)

วิธีแบ่งครึ่งช่วงง่ายที่สุดในทั้งสาม เริ่มจากช่วง [a, b] ที่ฟังก์ชันเปลี่ยนเครื่องหมาย หมายความว่าต้องมีเฉพาะคำตอบอยู่ในช่วงนั้น จากนั้นแบ่งช่วงครึ่งหนึ่งซ้ำ ๆ แล้วคงไว้ซึ่งครึ่งที่ยังมีการเปลี่ยนเครื่องหมาย

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

วิธีซีแคนต์ (Secant)

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

สูตรวิธีซีแคนต์

เป็นแนวทางที่ดีเมื่ออนุพันธ์คำนวณยาก ต้องแลกด้วยความเร็วในการลู่เข้า วิธีซีแคนต์เร็วกว่าแบ่งครึ่งช่วงแต่ช้ากว่าวิธีนิวตัน

การประยุกต์วิธีนิวตัน

วิธีนิวตันพบได้ทั่วทั้งวิทยาศาสตร์ วิศวกรรม และแมชชีนเลิร์นนิง ต่อไปนี้คือรายละเอียด

การแก้สมการเชิงตัวเลข

การประยุกต์โดยตรงที่สุด เมื่อฟังก์ชันไม่มีคำตอบแบบปิด วิธีนิวตันใช้หาเฉพาะคำตอบ เรื่องนี้เจอบ่อยมากในการคำนวณเชิงวิทยาศาสตร์ เช่น หาจุดสมดุลในปฏิกิริยาเคมี หรือแก้สมการทรานเซนเดนทัลในประมวลผลสัญญาณ

การหาค่าเหมาะที่สุด (Optimization)

การหาค่าต่ำสุดหรือค่าสูงสุดของฟังก์ชัน f(x) คือการหาที่ซึ่งอนุพันธ์ f'(x) = 0 ซึ่งเป็นปัญหาการหาเฉพาะคำตอบ จึงใช้วิธีนิวตันได้ เพียงรันอัลกอริทึมกับ f'(x) แทน f(x) โดยใช้อานุพันธ์อันดับสอง f''(x) แทนอนุพันธ์อันดับหนึ่ง

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

แมชชีนเลิร์นนิง

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

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) เป็นตัวปรับเหมาะควอซี-นิวตันที่ประมาณอนุพันธ์อันดับสองเพื่อหลีกเลี่ยงการคำนวณตรง เป็นตัวเลือกมาตรฐานสำหรับโลจิสติกรีเกรสชันและปัญหานูนอื่น ๆ วิธีนิวตันยังเป็นพื้นฐานของการอัปเดตแบบนิวตัน-ราฟสันในงานฟิตโมเดลเชิงสถิติ เช่น โมเดลเชิงเส้นทั่วไป

ฟิสิกส์และวิศวกรรม

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

ข้อผิดพลาดที่พบบ่อยกับวิธีนิวตัน

ข้อผิดพลาดส่วนใหญ่ของวิธีนิวตันมักมาจากสี่เรื่องเดิม ๆ ต่อไปนี้:

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

• คำนวณอนุพันธ์ผิด: กฎอัปเดตขึ้นกับ f'(x) อนุพันธ์ที่ผิด ไม่ว่าจะคำนวณพลาดหรือโค้ดผิด จะทำให้ค่าประมาณผิดตั้งแต่รอบแรก และความผิดพลาดจะทบในแต่ละรอบ

• ไม่ตรวจการหารด้วยศูนย์: หาก f'(x_n) เท่าศูนย์หรือเข้าใกล้มาก ขั้นอัปเดตจะทำงานไม่ได้ ควรใส่เงื่อนไขป้องกันในการเขียนโปรแกรม: ถ้าอนุพันธ์ต่ำกว่าค่ากำหนดเล็ก ๆ ให้หยุดและรายงานความล้มเหลว แทนที่จะให้ผลลัพธ์ที่ไร้ความหมาย

• หยุดเร็วเกินไป: ตัดรอบก่อนค่าประมาณจะลู่เข้าทำให้ได้คำตอบที่ดูใกล้แต่ไม่ใช่ กำหนดเงื่อนไขหยุดบนค่าคลาดเคลื่อนจริง เช่น ให้ |f(x_n)| หรือ |x_{n+1} - x_n| ต่ำกว่าค่ากำหนดที่เลือกรอบคอบ ไม่ใช่หยุดตามจำนวนรอบคงที่

สรุป

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

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

วิธีที่ดีที่สุดในการสร้างสัญชาตญาณคือฝึกกับตัวอย่างง่าย ๆ เริ่มจาก f(x) = x^2 - 2 ลองจุดเริ่มต่างกันแล้วสังเกตสิ่งที่เกิดขึ้น ต่อไปลองฟังก์ชันที่มีหลายเฉพาะคำตอบหรือบริเวณแบน แล้วดูว่าวิธีเริ่มมีปัญหาที่ไหน

ถ้าชอบแนวคิดการหาค่าเหมาะด้วยการทำซ้ำ ควรรู้จักเกรเดียนต์ดิเซนต์ อ่าน Gradient Descent in Machine Learning: A Deep Dive เพื่อเรียนรู้วิธีปรับเหมาะโมเดลสำหรับแมชชีนเลิร์นนิง