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

การนำไปใช้งานเฉพาะเจาะจงพร้อม เกณฑ์ การยุติสำหรับวิธีการวนซ้ำที่กำหนด เช่นการไล่ระดับความชัน (gradient descent ), การปีนเขา (hill climbing) , วิธีของนิวตัน (Newton's method)หรือ วิธีคล้ายนิว ตัน (quasi-Newton methods)เช่นBFGSนั้น คืออัลกอริธึมของวิธีการวนซ้ำหรือวิธีการประมาณค่าต่อเนื่องวิธีการวนซ้ำจะเรียกว่าลู่เข้า (convergent)หากลำดับที่สอดคล้องกันลู่เข้าสำหรับค่าประมาณเริ่มต้นที่กำหนด โดยปกติแล้วจะมีการวิเคราะห์การลู่เข้าของวิธีการวนซ้ำอย่างเข้มงวดทางคณิตศาสตร์ อย่างไรก็ตามวิธีการวนซ้ำแบบใช้ หลักการเชิง อนุมาน ก็เป็นที่นิยมเช่นกัน

ในทางตรงกันข้ามวิธีการโดยตรงพยายามแก้ปัญหาโดยใช้ลำดับการดำเนินการที่จำกัด ในกรณีที่ไม่มีข้อผิดพลาดจากการปัดเศษวิธีการโดยตรงจะให้คำตอบที่แม่นยำ (ตัวอย่างเช่น การแก้ระบบสมการเชิงเส้นโดยการกำจัดแบบเกาส์เซียน ) วิธีการวนซ้ำมักเป็นทางเลือกเดียวสำหรับสมการที่ไม่เป็นเชิงเส้นอย่างไรก็ตาม วิธีการวนซ้ำมักมีประโยชน์แม้กระทั่งสำหรับปัญหาเชิงเส้นที่เกี่ยวข้องกับตัวแปรจำนวนมาก (บางครั้งอาจมีจำนวนนับล้าน) ซึ่งวิธีการโดยตรงจะมีค่าใช้จ่ายสูงมาก (และในบางกรณีเป็นไปไม่ได้) แม้จะมีพลังการคำนวณที่ดีที่สุดก็ตาม^{[ 1 ]}${\displaystyle A\mathbf {x} =\mathbf {b} }$

ถ้าสมการสามารถเขียนให้อยู่ในรูปf ( x ) = xและคำตอบxเป็นจุดคงที่_ที่ ดึงดูด ของฟังก์ชันfแล้ว เราอาจเริ่มต้นด้วยจุดx₁ในแอ่งดึงดูดของxและให้xₙ⁺₁ = f ( xₙ ₎สำหรับn _≥  1 และลำดับ { xₙ _} n  _{≥ 1}จะลู่เข้าสู่คำตอบxโดยที่xₙ⁺₁คือค่าประมาณหรือการวนซ้ำครั้งที่ n ของ x และ xₙ⁺₁ คือค่า_{ประมาณ}หรือ_การวนซ้ำครั้งที่_{n + 1}ถัดไปของ x หรืออีกทางหนึ่ง มักใช้ตัวยกในวงเล็บในวิธีการเชิงตัวเลข เพื่อไม่ให้รบกวนตัวห้อยที่มีความหมายอื่น (ตัวอย่างเช่นx ^{( n +1)} = f ( x ^{( n )} )) ถ้าฟังก์ชันfสามารถหาอนุพันธ์ได้อย่างต่อเนื่องเงื่อนไขที่เพียงพอสำหรับการลู่เข้าคือรัศมีสเปกตรัมของอนุพันธ์มีขอบเขตจำกัดอย่างเคร่งครัดด้วยหนึ่งในบริเวณใกล้เคียงจุดคงที่ ถ้าเงื่อนไขนี้เป็นจริงที่จุดคงที่ แสดงว่าต้องมีบริเวณใกล้เคียงที่เล็กพอ (แอ่งดึงดูด) อยู่^{[ 2 ]}

ในกรณีของระบบสมการเชิงเส้นวิธีการวนซ้ำหลักสองประเภท ได้แก่วิธีการวนซ้ำแบบอยู่กับที่ และ วิธีการ วนซ้ำแบบ Krylov ซึ่ง เป็นวิธีการ ทั่วไปมากกว่า

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

วิธีการวนซ้ำถูกกำหนดโดย และสำหรับระบบเชิงเส้นที่กำหนดซึ่งมีคำตอบที่แน่นอนข้อผิดพลาดโดย วิธีการวนซ้ำเรียกว่าเชิงเส้นถ้ามีเมทริกซ์ อยู่เช่นนั้น และเมทริกซ์นี้เรียกว่าเมทริกซ์การวนซ้ำวิธีการวนซ้ำที่มีเมทริกซ์การวนซ้ำที่กำหนดเรียกว่าลู่เข้าถ้าเงื่อนไขต่อไปนี้เป็นจริง $${\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k}),\quad k\geq 0}$$${\displaystyle A\mathbf {x} =\mathbf {b} }$${\displaystyle \mathbf {x} ^{*}}$$${\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*},\quad k\geq 0.}$$${\displaystyle C\in \mathbb {R} ^{n\times n}}$$${\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall k\geq 0}$$${\displaystyle C}$$${\displaystyle \lim _{k\to \infty }C^{k}=0.}$$

ทฤษฎีบทสำคัญกล่าวว่า สำหรับวิธีการวนซ้ำที่กำหนดและเมทริกซ์การวนซ้ำนั้น วิธีการนั้นจะลู่เข้าก็ต่อเมื่อรัศมีสเปกตรัม มีค่าน้อยกว่าหนึ่ง นั่นคือ ${\displaystyle C}$${\displaystyle \rho (C)}$$${\displaystyle \rho (C)<1.}$$

วิธีการวนซ้ำพื้นฐานทำงานโดยการแบ่งเมทริกซ์ออกเป็นส่วนๆ และในที่นี้เมทริกซ์ควรสามารถหา เมทริกซ์ผกผันได้ง่าย วิธีการวนซ้ำถูกกำหนดดังนี้ หรือเทียบเท่ากับ จากนี้จึงสรุปได้ว่าเมทริกซ์การวนซ้ำกำหนดโดย ${\displaystyle A}$$${\displaystyle A=MN}$$${\displaystyle M}$$${\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+\mathbf {b} ,\quad k\geq 0,}$$$${\displaystyle \mathbf {x} ^{k+1}=\mathbf {x} ^{k}+M^{-1}\left(\mathbf {b} -A\mathbf {x} ^{k}\right),\quad k\geq 0.}$$$${\displaystyle C=IM^{-1}A=M^{-1}N.}$$

ตัวอย่างพื้นฐานของวิธีการวนซ้ำแบบอยู่กับที่ใช้การแบ่งเมทริกซ์เช่น โดย ที่เป็นเพียงส่วนแนวทแยงของและเป็นส่วนสามเหลี่ยม ล่างที่แท้จริง ของและ เป็นส่วนสามเหลี่ยมบนที่แท้จริงของตาม ลำดับ${\displaystyle A}$$${\displaystyle A=D+L+U\,,\quad D:=\operatorname {diag} ((a_{ii})_{i})}$$${\displaystyle D}$${\displaystyle A}$${\displaystyle L}$${\displaystyle A}$${\displaystyle U}$${\displaystyle A}$

• วิธีริชาร์ดสัน :$${\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}$$
• วิธีจาโคบี :$${\displaystyle M:=D}$$
• วิธี Jacobi แบบหน่วง :$${\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}$$
• วิธีเกาส์-ไซเดล :$${\displaystyle M:=D+L}$$
• วิธีการผ่อนคลายเกินปกติแบบต่อเนื่อง (SOR):$${\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}$$
• การผ่อนคลายเกินพิกัดแบบต่อเนื่องสมมาตร (SSOR):$${\displaystyle M:={\frac {1}{\omega \left(2-\omega \right)}}\left(D+\omega L\right)D^{-1}\left(D+\omega U\right)\quad (\omega \not \in \{0,2\})}$$

วิธีการวนซ้ำแบบคง ที่ เชิงเส้นเรียกอีกอย่างว่าวิธีการผ่อนคลาย

วิธีการของ Krylov subspace ^{[ 3 ]}ทำงานโดยการสร้างฐานของลำดับกำลังเมทริกซ์ที่ต่อเนื่องกันคูณด้วยค่าตกค้างเริ่มต้น ( ลำดับ Krylov ) จากนั้นการประมาณค่าของคำตอบจะถูกสร้างขึ้นโดยการลดค่าตกค้างให้น้อยที่สุดเหนือ subspace ที่สร้างขึ้น วิธีการต้นแบบในกลุ่มนี้คือวิธีการไล่ระดับแบบสังยุค (CG) ซึ่งสมมติว่าเมทริกซ์ของระบบเป็นเมทริกซ์สมมาตรบวกแน่นอนสำหรับเมทริกซ์สมมาตร (และอาจเป็นเมทริกซ์ไม่แน่นอน) จะใช้วิธีการค่าตกค้างน้อยที่สุด (MINRES) ในกรณีของเมทริกซ์ที่ไม่สมมาตร ได้มีการพัฒนาวิธีการต่างๆ เช่นวิธีการค่าตกค้างน้อยที่สุดแบบทั่วไป (GMRES) และวิธีการไล่ระดับแบบสังยุคคู่ (BiCG) ${\displaystyle A}$${\displaystyle A}$

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

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

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

• วิธีการแบบบาบิโลนสำหรับการหาค่ารากที่สองของตัวเลข^{[ 4 ]}
• การวนซ้ำจุดคงที่^{[ 5 ]}
• วิธีการค้นหาค่าศูนย์ของฟังก์ชัน:
  • วิธีการของแฮลลีย์
  • วิธีของนิวตัน
• สมการเชิงอนุพันธ์มีความสำคัญ:
  • ทฤษฎีบท Picard–Lindelöfว่าด้วยการมีอยู่ของคำตอบของสมการเชิงอนุพันธ์
  • วิธีรันเก-คุตตะสำหรับการแก้สมการเชิงอนุพันธ์ด้วยวิธีเชิงตัวเลข

จัมชีด อัล-กาชีใช้ระเบียบวิธีวนซ้ำในการคำนวณค่าไซน์ของ 1° และπในตำราว่าด้วยคอร์ดและไซน์ด้วยความแม่นยำสูง ระเบียบวิธีวนซ้ำในยุคแรกสำหรับการแก้ระบบสมการเชิงเส้นปรากฏในจดหมายของเกาส์ถึงลูกศิษย์ของเขา เขาเสนอให้แก้ระบบสมการ 4x4 โดยการแก้ส่วนประกอบที่มีค่าตกค้างมากที่สุดซ้ำๆ

ทฤษฎีของวิธีการวนซ้ำแบบอยู่กับที่นั้นได้รับการวางรากฐานอย่างมั่นคงด้วยผลงานของDM Youngตั้งแต่ช่วงทศวรรษ 1950 วิธีการไล่ระดับแบบสังยุค (conjugate gradient method) ก็ถูกคิดค้นขึ้นในช่วงทศวรรษ 1950 เช่นกัน โดยมีการพัฒนาอย่างอิสระโดยCornelius Lanczos , Magnus HestenesและEduard Stiefelแต่ธรรมชาติและการประยุกต์ใช้ของมันยังไม่เป็นที่เข้าใจในขณะนั้น จนกระทั่งในทศวรรษ 1970 จึงได้ตระหนักว่าวิธีการที่ใช้หลักการสังยุคนั้นใช้ได้ผลดีมากสำหรับสมการเชิงอนุพันธ์ย่อย โดยเฉพาะอย่างยิ่งสมการเชิงวงรี

• นิพจน์แบบปิด
• การปรับปรุงแบบวนซ้ำ
• วิธีของ Kaczmarz
• กำลังสองน้อยที่สุดแบบไม่เชิงเส้น
• การวิเคราะห์เชิงตัวเลข
• อัลกอริทึมค้นหาราก

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับวิธีการวนซ้ำ

• แม่แบบสำหรับการแก้ระบบสมการเชิงเส้น
• Y. Saad: วิธีการวนซ้ำสำหรับระบบเชิงเส้นแบบเบาบางฉบับพิมพ์ครั้งที่ 1, PWS 1996