ในวิชาแคลคูลัสวิธีของนิวตัน (หรือเรียกว่า วิธีนิวตัน-ราฟสัน ) เป็นวิธีแบบวนซ้ำสำหรับการหาค่ารากของฟังก์ชันที่หาอนุพันธ์ได้${\displaystyle f}$ซึ่งเป็นคำตอบของสมการ${\displaystyle f(x)=0}$อย่างไรก็ตาม เพื่อให้ได้ค่าที่เหมาะสมที่สุดสำหรับอนุพันธ์อันดับสอง${\displaystyle f}$เป้าหมายของเราคือการค้นหารากเหง้าของ...${\displaystyle f'}$ดังนั้นเราจึงสามารถใช้วิธีของนิวตันกับอนุพันธ์ ของมันได้${\displaystyle f'}$เพื่อหาแนวทางแก้ไขปัญหา${\displaystyle f'(x)=0}$หรือที่รู้จักกันในชื่อจุดวิกฤตของ${\displaystyle f}$คำตอบเหล่านี้อาจเป็นค่าต่ำสุด จุดสูงสุด หรือจุดอานม้า ดูส่วน"ตัวแปรหลายตัว"ในหัวข้อ จุดวิกฤต (คณิตศาสตร์)และส่วน"การตีความทางเรขาคณิต"ในบทความนี้ด้วย สิ่งนี้มีความเกี่ยวข้องกับการหาค่าเหมาะสมที่สุดซึ่งมีเป้าหมายเพื่อค้นหาค่าต่ำสุด (ทั่วโลก) ของฟังก์ชัน${\displaystyle f}$.

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

กำหนดให้ฟังก์ชันเป็นฟังก์ชันที่หาอนุพันธ์อันดับสองได้${\displaystyle f:\mathbb {R} \to \mathbb {R} }$เราพยายามแก้ไขปัญหาการหาค่าที่เหมาะสมที่สุด

${\displaystyle \min _{x\in \mathbb {R} }f(x).}$

วิธีการของนิวตันพยายามแก้ปัญหานี้โดยการสร้างลำดับ${\displaystyle \{x_{k}\}}$จากการคาดเดาเบื้องต้น (จุดเริ่มต้น)${\displaystyle x_{0}\in \mathbb {R} }$ที่ลู่เข้าสู่ค่าต่ำสุด${\displaystyle x_{*}}$ของ${\displaystyle f}$โดยใช้ลำดับการประมาณค่าเทย์เลอร์อันดับสองของ${\displaystyle f}$รอบการวนซ้ำ การขยายอนุกรมเทย์เลอร์อันดับสอง ของfรอบ ๆ${\displaystyle x_{k}}$เป็น

${\displaystyle f(x_{k}+t)\approx f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}.}$

รอบถัดไป${\displaystyle x_{k+1}}$ถูกกำหนดขึ้นเพื่อลดค่าประมาณกำลังสองนี้ให้น้อยที่สุดใน ${\displaystyle t}$และการตั้งค่า${\displaystyle x_{k+1}=x_{k}+t}$ถ้าอนุพันธ์อันดับสองเป็นบวก การประมาณค่ากำลังสองจะเป็นฟังก์ชันนูนของ${\displaystyle t}$และสามารถหาค่าต่ำสุดได้โดยการกำหนดให้ค่าอนุพันธ์เท่ากับศูนย์ เนื่องจาก

${\displaystyle \displaystyle 0={\frac {\rm {d}}{{\rm {d}}t}}\left(f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}\right)=f'(x_{k})+f''(x_{k})t,}$

บรรลุขั้นต่ำสำหรับ

${\displaystyle t=-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

เมื่อนำทุกอย่างมารวมกัน วิธีของนิวตันจะทำการวนซ้ำ

${\displaystyle x_{k+1}=x_{k}+t=x_{k}-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

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

แผนการวนซ้ำข้างต้นสามารถนำไปปรับใช้ได้โดยทั่วไปดังนี้${\displaystyle d>1}$มิติโดยการแทนที่อนุพันธ์ด้วยเกรเดียนต์ (ผู้เขียนแต่ละคนใช้สัญลักษณ์ที่แตกต่างกันสำหรับเกรเดียนต์ รวมถึง...)${\displaystyle f'(x)=\nabla f(x)=g_{f}(x)\in \mathbb {R} ^{d}}$) และส่วนกลับของอนุพันธ์อันดับสองกับเมทริกซ์เฮสเซียนผกผัน (ผู้เขียนแต่ละท่านใช้สัญลักษณ์ที่แตกต่างกันสำหรับเมทริกซ์เฮสเซียน รวมถึง${\displaystyle f''(x)=\nabla ^{2}f(x)=H_{f}(x)\in \mathbb {R} ^{d\times d}}$) ดังนั้นจึงได้รูปแบบการวนซ้ำ

${\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k}),\qquad k\geq 0.}$

บ่อยครั้งที่วิธีการของนิวตันถูกดัดแปลงให้รวมถึงขนาดขั้นตอน ที่เล็กลง${\displaystyle 0<\gamma \leq 1}$แทนที่จะ${\displaystyle \gamma =1}$:

${\displaystyle x_{k+1}=x_{k}-\gamma [f''(x_{k})]^{-1}f'(x_{k}).}$

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

ถ้าfเป็นฟังก์ชันนูนอย่างเข้มข้นที่มีเมทริกซ์เฮสเซียนแบบลิปชิตซ์ แล้วโดยมีเงื่อนไขว่า${\displaystyle x_{0}}$อยู่ใกล้พอที่จะ${\displaystyle x_{*}=\arg \min f(x)}$ลำดับ${\displaystyle x_{0},x_{1},x_{2},\dots }$ค่าที่ได้จากวิธีของนิวตันจะลู่เข้าสู่ค่าต่ำสุด (ซึ่งจำเป็นต้องมีเพียงหนึ่งเดียว) ${\displaystyle x_{*}}$ของ${\displaystyle f}$เร็วแบบกำลังสอง^{[ 1 ]} นั่นคือ

${\displaystyle \|x_{k+1}-x_{*}\|\leq {\frac {1}{2}}\|x_{k}-x_{*}\|^{2},\qquad \forall k\geq 0.}$

การหาเมทริกซ์ผกผันของเมทริกซ์เฮสเซียนในมิติสูงเพื่อคำนวณทิศทางของนิวตัน${\displaystyle h=-(f''(x_{k}))^{-1}f'(x_{k})}$อาจเป็นกระบวนการที่สิ้นเปลืองค่าใช้จ่าย ในกรณีเช่นนี้ แทนที่จะหาเมทริกซ์ผกผันของเฮสเซียนโดยตรง การคำนวณเวกเตอร์จะดีกว่า${\displaystyle h}$เนื่องจากเป็นคำตอบของระบบสมการเชิงเส้น

${\displaystyle [f''(x_{k})]h=-f'(x_{k})}$

ซึ่งอาจแก้ได้ด้วยวิธีการแยกตัวประกอบต่างๆ หรือโดยประมาณ (แต่มีความแม่นยำสูง) โดยใช้วิธีการวนซ้ำวิธีการเหล่านี้หลายวิธีใช้ได้กับสมการบางประเภทเท่านั้น ตัวอย่างเช่นการแยกตัวประกอบแบบ Choleskyและวิธีการไล่ระดับเชิงสังยุคจะใช้ได้ก็ต่อเมื่อ${\displaystyle f''(x_{k})}$เป็นเมทริกซ์บวกแน่นอน แม้ว่านี่อาจดูเหมือนเป็นข้อจำกัด แต่บ่อยครั้งมันเป็นตัวบ่งชี้ที่มีประโยชน์ว่ามีบางอย่างผิดพลาดเกิดขึ้น ตัวอย่างเช่น หากกำลังแก้ปัญหาการหาค่าต่ำสุด และ${\displaystyle f''(x_{k})}$ถ้าเมทริกซ์ไม่เป็นเมทริกซ์บวกแน่นอน การวนซ้ำจะลู่เข้าสู่จุดอานม้าไม่ใช่จุดต่ำสุด

ในทางกลับกัน หาก ทำการ หาค่าเหมาะสมที่สุดแบบมีข้อจำกัด (เช่น โดยใช้ตัวคูณลากรางจ์ ) ปัญหาอาจกลายเป็นปัญหาการหาจุดอานม้า ซึ่งในกรณีนี้เมทริกซ์เฮสเซียนจะเป็นเมทริกซ์สมมาตรไม่จำกัด และคำตอบของ${\displaystyle x_{k+1}}$จะต้องทำด้วยวิธีการที่ใช้ได้ผล เช่น วิธีต่อไปนี้${\displaystyle LDL^{\top }}$รูปแบบหนึ่งของการแยกตัวประกอบ Choleskyหรือ วิธี ตกค้างแบบสังยุค

นอกจากนี้ยังมีวิธีการคล้ายนิวตัน หลายวิธี ซึ่งเป็นการสร้างค่าประมาณของเมทริกซ์เฮสเซียน (หรือเมทริกซ์ผกผันโดยตรง) จากการเปลี่ยนแปลงของเกรเดียนต์

หากเมทริกซ์เฮสเซียนอยู่ใกล้กับเมทริกซ์ที่ไม่สามารถผกผัน ได้ เมทริกซ์เฮสเซียนผกผันอาจไม่เสถียรทางตัวเลข และคำตอบอาจล diverge ในกรณีนี้ ในอดีตเคยมีการลองใช้วิธีแก้ไขบางอย่าง ซึ่งได้ผลลัพธ์ที่แตกต่างกันไปในแต่ละปัญหา ตัวอย่างเช่น สามารถปรับเปลี่ยนเมทริกซ์เฮสเซียนโดยการเพิ่มเมทริกซ์แก้ไขเข้าไป${\displaystyle B_{k}}$เพื่อที่จะทำให้${\displaystyle f''(x_{k})+B_{k}}$เมทริกซ์บวกแน่นอน วิธีหนึ่งคือการหาเมทริกซ์ทแยงมุมของเมทริกซ์เฮสเซียนแล้วเลือก${\displaystyle B_{k}}$ ดังนั้น${\displaystyle f''(x_{k})+B_{k}}$มีเวกเตอร์ลักษณะเฉพาะเหมือนกับเมทริกซ์เฮสเซียน แต่ค่าลักษณะเฉพาะที่เป็นลบแต่ละค่าจะถูกแทนที่ด้วย${\displaystyle \epsilon >0}$.

แนวทางหนึ่งที่นำมาใช้ในอัลกอริทึม Levenberg–Marquardt (ซึ่งใช้เมทริกซ์ Hessian โดยประมาณ) คือการเพิ่มเมทริกซ์เอกลักษณ์ที่ปรับขนาดแล้วเข้าไปในเมทริกซ์ Hessian${\displaystyle \mu I}$โดยปรับขนาดในแต่ละรอบตามความจำเป็น สำหรับขนาดใหญ่${\displaystyle \mu }$และหากค่า Hessian มีขนาดเล็ก การวนซ้ำจะทำงานคล้ายกับการลดระดับความชันโดยมีขนาดขั้นตอน${\displaystyle 1/\mu }$วิธีนี้ส่งผลให้การลู่เข้าช้าลงแต่มีความน่าเชื่อถือมากขึ้นในกรณีที่เมทริกซ์เฮสเซียนไม่ได้ให้ข้อมูลที่เป็นประโยชน์

วิธีการของนิวตันในฉบับดั้งเดิมนั้นมีข้อจำกัดอยู่หลายประการ:

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

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

ตัวอย่างเช่น โดยทั่วไปแล้วจำเป็นต้องมีฟังก์ชันต้นทุนที่เป็นนูน (อย่างแข็งแกร่ง) และเมทริกซ์เฮสเซียนที่มีขอบเขตทั่วโลกหรือมีความต่อเนื่องแบบลิปชิตซ์ ตัวอย่างเช่น มีการกล่าวถึงเรื่องนี้ในส่วน "การลู่เข้า" ในบทความนี้ หากพิจารณาเอกสารของ Levenberg และ Marquardt ในเอกสารอ้างอิงสำหรับอัลกอริทึม Levenberg–Marquardtซึ่งเป็นแหล่งที่มาดั้งเดิมของวิธีการที่กล่าวถึง จะเห็นได้ว่าโดยพื้นฐานแล้วไม่มีการวิเคราะห์ทางทฤษฎีในเอกสารของ Levenberg ในขณะที่เอกสารของ Marquardt วิเคราะห์เฉพาะสถานการณ์เฉพาะที่และไม่ได้พิสูจน์ผลลัพธ์การลู่เข้าทั่วโลก สามารถเปรียบเทียบได้กับการค้นหาเส้นแบบย้อนกลับในการลดระดับความชัน ซึ่งมีการรับประกันทางทฤษฎีที่ดีภายใต้สมมติฐานทั่วไปมากกว่า และสามารถนำไปใช้และทำงานได้ดีในปัญหาขนาดใหญ่ในทางปฏิบัติ เช่น โครงข่ายประสาทเทียมเชิงลึก

• วิธีควาซี-นิวตัน
• การลดระดับความชัน
• อัลกอริทึมเกาส์-นิวตัน
• อัลกอริทึมเลเวนเบิร์ก-มาร์ควาร์ด
• ภูมิภาคที่น่าเชื่อถือ
• การเพิ่มประสิทธิภาพ
• วิธีเนลเดอร์-มีด
• ฟังก์ชันที่สอดคล้องกันเอง - ฟังก์ชันที่วิธีของนิวตันมีอัตราการบรรจบกันทั่วโลกที่ดีมาก^{[ 2 ] :มาตรา 6.2}

• โคเรนบลัม, แดเนียล (29 ส.ค. 2558) “การสร้างภาพนิวตัน-ราฟสัน (1D) ” บล๊อก . ffe9653768cb80dfc0da.