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

เมื่อกำหนดฟังก์ชันให้พิจารณาปัญหาการหาจุดคงที่ของซึ่งเป็นคำตอบของสมการแนวทางคลาสสิกในการแก้ปัญหานี้คือการใช้แผนการวนซ้ำจุดคง ที่ ^{[ 2 ]}กล่าวคือ เมื่อกำหนดค่าเริ่มต้นสำหรับการคาดเดาคำตอบแล้ว ให้คำนวณลำดับจนกว่าจะตรงตามเกณฑ์การลู่เข้าบางอย่าง อย่างไรก็ตาม การลู่เข้าของแผนการดังกล่าวไม่ได้รับการรับประกันโดยทั่วไป ยิ่งไปกว่านั้นอัตราการลู่เข้ามักจะเป็นเชิงเส้น ซึ่งอาจช้าเกินไปหากการประเมินฟังก์ชันมีค่าใช้จ่ายในการคำนวณสูง^{[ 2 ]}การเร่งความเร็วของ Anderson เป็นวิธีการเร่งความเร็วการลู่เข้าของลำดับจุดคงที่^{[ 2 ]}${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} ^{n}}$${\displaystyle f}$${\displaystyle f(x)=x}$${\displaystyle x_{0}}$${\displaystyle x_{k+1}=f(x_{k})}$${\displaystyle f}$

กำหนดส่วนที่เหลือและกำหนดและ(โดยที่สอดคล้องกับลำดับของการวนซ้ำจากย่อหน้าก่อนหน้า) เมื่อกำหนดค่าเดาเริ่มต้นและพารามิเตอร์จำนวนเต็มวิธีการนี้สามารถกำหนดได้ดังนี้: ^{[ 3 ] [หมายเหตุ 1 ]}${\displaystyle g(x)=f(x)-x}$${\displaystyle f_{k}=f(x_{k})}$${\displaystyle g_{k}=g(x_{k})}$${\displaystyle x_{k}}$${\displaystyle x_{0}}$${\displaystyle m\geq 1}$

${\displaystyle x_{1}=f(x_{0})}$

${\displaystyle \forall k=1,2,\dots }$

${\displaystyle m_{k}=\min\{m,k\}}$

${\displaystyle G_{k}={\begin{bmatrix}g_{k-m_{k}}&\dots &g_{k}\end{bmatrix}}}$

${\displaystyle \alpha _{k}=\operatorname {argmin} _{\alpha \in A_{k}}\|G_{k}\alpha \|_{2},\quad {\text{where}}\;A_{k}=\{\alpha =(\alpha _{0},\dots ,\alpha _{m_{k}})\in \mathbb {R} ^{m_{k}+1}:\sum _{i=0}^{m_{k}}\alpha _{i}=1\}}$

${\displaystyle x_{k+1}=\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f_{k-m_{k}+i}}$

โดยที่การคูณเมทริกซ์-เวกเตอร์และเป็นองค์ประกอบที่ th ของเกณฑ์การหยุดตามปกติสามารถใช้เพื่อยุติการวนซ้ำของวิธีการได้ ตัวอย่างเช่น การวนซ้ำสามารถหยุดได้เมื่อตกอยู่ภายใต้ค่าความคลาดเคลื่อนที่กำหนด หรือเมื่อค่าตกค้างตกอยู่ภายใต้ค่าความคลาดเคลื่อนที่กำหนด^{[ 2 ]}${\displaystyle G_{k}\alpha =\sum _{i=0}^{m_{k}}(\alpha )_{i}g_{k-m_{k}+i}}$${\displaystyle (\alpha )_{i}}$${\displaystyle i}$${\displaystyle \alpha }$${\displaystyle \|x_{k+1}-x_{k}\|}$${\displaystyle g(x_{k})}$

เมื่อเปรียบเทียบกับการวนซ้ำจุดคงที่มาตรฐาน พบว่าวิธีนี้สามารถลู่เข้าได้เร็วกว่าและมีความแข็งแกร่งกว่า และในบางกรณีสามารถหลีกเลี่ยงการล divergence ของลำดับจุดคงที่ได้^{[ 3 ] [ 4 ]}

สำหรับคำตอบนั้นเรารู้ว่าซึ่งเทียบเท่ากับการกล่าวว่าดังนั้นเราจึงสามารถกำหนดปัญหาใหม่ให้เป็นปัญหาการหาค่าเหมาะสมที่สุด โดยที่เราต้องการลดค่า ให้เหลือน้อยที่สุด ${\displaystyle x^{*}}$${\displaystyle f(x^{*})=x^{*}}$${\displaystyle g(x^{*})={\vec {0}}}$${\displaystyle \|g(x)\|_{2}}$

แทนที่จะไปโดยตรงจากไปยังโดยเลือกเหมือนในวิธีการวนซ้ำแบบจุดคงที่ ลองพิจารณาจุดกลางที่เราเลือกให้เป็นการรวมเชิงเส้นโดยที่เวกเตอร์สัมประสิทธิ์และคือเมทริกซ์ที่ประกอบด้วยจุดสุดท้าย และเลือกที่ทำให้ มีค่าน้อยที่สุดเนื่องจากผลรวมขององค์ประกอบในเท่ากับหนึ่ง เราจึงสามารถทำการประมาณอันดับแรกได้ ${\displaystyle x_{k}}$${\displaystyle x_{k+1}}$${\displaystyle x_{k+1}=f(x_{k})}$${\displaystyle x'_{k+1}}$${\displaystyle x'_{k+1}=X_{k}\alpha _{k}}$${\displaystyle \alpha _{k}\in A_{k}}$${\displaystyle X_{k}={\begin{bmatrix}x_{k-m_{k}}&\dots &x_{k}\end{bmatrix}}}$${\displaystyle m_{k}+1}$${\displaystyle x'_{k+1}}$${\displaystyle \|g(x'_{k+1})\|_{2}}$${\displaystyle \alpha _{k}}$

$${\displaystyle {\begin{aligned}g(X_{k}\alpha _{k})&=g\!\left(\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}x_{k-m_{k}+i}\right)\\&\approx \sum _{i=0}^{m_{k}}(\alpha _{k})_{i}g(x_{k-m_{k}+i})\\&=\;G_{k}\alpha _{k}\end{aligned}}}$$

และปัญหาของเราก็คือการหาค่าที่ทำให้ค่า น้อยที่สุดหลังจากที่เราหาค่า ได้แล้วในทางทฤษฎีเราก็สามารถคำนวณค่าได้ ${\displaystyle \alpha }$${\displaystyle \|G_{k}\alpha \|_{2}}$${\displaystyle \alpha _{k}}$${\displaystyle x'_{k+1}}$

อย่างไรก็ตาม เนื่องจากถูกออกแบบมาเพื่อให้จุดเข้าใกล้มากขึ้นจึงน่าจะอยู่ใกล้มากกว่าดังนั้นจึงควรเลือกแทนที่จะเป็นนอกจากนี้ เนื่องจากผลรวมขององค์ประกอบในเท่ากับหนึ่ง เราจึงสามารถทำการประมาณค่าอันดับแรก ได้${\displaystyle f}$${\displaystyle x^{*}}$${\displaystyle f(x'_{k+1})}$${\displaystyle x^{*}}$${\displaystyle x'_{k+1}}$${\displaystyle x_{k+1}=f(x'_{k+1})}$${\displaystyle x_{k+1}=x'_{k+1}}$${\displaystyle \alpha _{k}}$

$${\displaystyle {\begin{aligned}f(x'_{k+1})&=f\left(\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}x_{k-m_{k}+i}\right)\\&\approx \sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f(x_{k-m_{k}+i})\\&=\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f_{k-m_{k}+i}\,.\end{aligned}}}$$

ดังนั้นเราจึงเลือก

${\displaystyle x_{k+1}=\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f_{k-m_{k}+i}}$.

ในแต่ละรอบของอัลกอริธึมปัญหาการเพิ่มประสิทธิภาพ แบบมีข้อจำกัด ภายใต้เงื่อนไขจะต้องได้รับการแก้ไข ปัญหาสามารถแปลงเป็นสูตรที่เทียบเท่ากันได้หลายแบบ^{[ 3 ]}ซึ่งให้วิธีการแก้ปัญหาที่แตกต่างกันซึ่งอาจส่งผลให้การใช้งานสะดวกยิ่งขึ้น ${\displaystyle \operatorname {argmin} \|G_{k}\alpha \|_{2}}$${\displaystyle \alpha \in A_{k}}$

• กำหนดเมทริกซ์และแก้และตั้งค่า; ^{[ 3 ] [ 4 ]}${\displaystyle {\mathcal {G}}_{k}={\begin{bmatrix}g_{k-m_{k}+1}-g_{k-m_{k}}&\dots &g_{k}-g_{k-1}\end{bmatrix}}}$${\displaystyle {\mathcal {X}}_{k}={\begin{bmatrix}x_{k-m_{k}+1}-x_{k-m_{k}}&\dots &x_{k}-x_{k-1}\end{bmatrix}}}$${\displaystyle \gamma _{k}=\operatorname {argmin} _{\gamma \in \mathbb {R} ^{m_{k}}}\|g_{k}-{\mathcal {G}}_{k}\gamma \|_{2}}$${\displaystyle x_{k+1}=x_{k}+g_{k}-({\mathcal {X}}_{k}+{\mathcal {G}}_{k})\gamma _{k}}$
• แก้แล้วตั้งค่า^{[ 1 ]}${\displaystyle \theta _{k}=\{(\theta _{k})_{i}\}_{i=1}^{m_{k}}=\operatorname {argmin} _{\theta \in \mathbb {R} ^{m_{k}}}\left\|g_{k}+\sum _{i=1}^{m_{k}}\theta _{i}(g_{k-i}-g_{k})\right\|_{2}}$${\displaystyle x_{k+1}=x_{k}+g_{k}+\sum _{j=1}^{m_{k}}(\theta _{k})_{j}(x_{k-j}-x_{k}+g_{k-j}-g_{k})}$

สำหรับทั้งสองทางเลือก ปัญหาการปรับให้เหมาะสมจะอยู่ในรูปแบบของ ปัญหา กำลังสองน้อยที่สุดเชิงเส้นแบบ ไม่มีข้อจำกัด ซึ่งสามารถแก้ไขได้ด้วยวิธีการมาตรฐาน รวมถึงการแยกส่วน QR ^{[ 3 ]}และการแยกส่วนค่าเอกลักษณ์ [ ^{4 ]}ซึ่งอาจรวมถึงเทคนิคการทำให้เป็นระเบียบเพื่อจัดการกับข้อบกพร่องของอันดับและ ปัญหา เงื่อนไข ในปัญหาการ ^ปรับให้เหมาะสม การแก้ปัญหากำลังสองน้อยที่สุดโดยการแก้สมการปกติโดยทั่วไปไม่แนะนำเนื่องจากความไม่เสถียรเชิงตัวเลข ที่อาจเกิดขึ้น และต้นทุนการคำนวณที่สูงโดยทั่วไป^{[ 4 ]}

ความหยุดนิ่งในวิธีการ (เช่น การวนซ้ำครั้งถัดไปที่มีค่าเดียวกัน) ทำให้วิธีการล้มเหลวเนื่องจากความไม่ต่อเนื่องของปัญหากำลังสองน้อยที่สุด ในทำนองเดียวกัน ความใกล้หยุดนิ่ง ( ) ส่งผลให้สภาพของปัญหากำลังสองน้อยที่สุดไม่ดี ยิ่งไปกว่านั้น การเลือกพารามิเตอร์อาจมีความเกี่ยวข้องในการกำหนดสภาพของปัญหากำลังสองน้อยที่สุด ดังที่กล่าวไว้ด้านล่าง^{[ 3 ]}${\displaystyle x_{k+1}=x_{k}}$${\displaystyle x_{k+1}\approx x_{k}}$${\displaystyle m}$

อัลกอริทึมสามารถปรับเปลี่ยนได้โดยการแนะนำพารามิเตอร์การผ่อนคลายตัวแปร (หรือพารามิเตอร์การผสม) [ ^{1 ] [ 3 ] [ 4 ] ใน}แต่ละขั้นตอน ให้คำนวณค่าวนซ้ำใหม่เป็นการเลือกค่ามีความสำคัญต่อคุณสมบัติการลู่เข้าของวิธีการ โดยหลักการแล้วอาจแตกต่างกันไปในแต่ละรอบการวนซ้ำ แม้ว่ามักจะเลือกให้เป็นค่าคงที่ก็ตาม^{[ 4 ]}${\displaystyle \beta _{k}>0}$$${\displaystyle x_{k+1}=(1-\beta _{k})\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}x_{k-m_{k}+i}+\beta _{k}\sum _{i=0}^{m_{k}}(\alpha _{k})_{i}f(x_{k-m_{k}+i})\;.}$$${\displaystyle \beta _{k}}$${\displaystyle \beta _{k}}$

พารามิเตอร์นี้กำหนดว่าจะใช้ข้อมูลจากรอบก่อนหน้ามากน้อยเพียงใดในการคำนวณรอบใหม่ในด้านหนึ่ง หากเลือกให้มีค่าเล็กเกินไป จะใช้ข้อมูลน้อยเกินไป และการลู่เข้าอาจช้าเกินไป ในทางกลับกัน หากเลือกให้มีค่ามากเกินไป ข้อมูลจากการวนซ้ำเก่าอาจถูกเก็บไว้สำหรับการวนซ้ำครั้งถัดไปมากเกินไป ทำให้การลู่เข้าอาจช้าเช่นกัน^{[ 3 ]}ยิ่งไปกว่านั้น การเลือกค่าจะส่งผลต่อขนาดของปัญหาการหาค่าเหมาะสมที่สุด ค่าที่มากเกินไปอาจทำให้สภาพของปัญหาการหาค่ากำลังสองน้อยที่สุดแย่ลง และต้นทุนในการแก้ปัญหาก็จะสูงขึ้น^{[ 3 ]}โดยทั่วไป ปัญหาเฉพาะที่จะต้องแก้ไขจะเป็นตัวกำหนดตัวเลือกที่ดีที่สุดของพารามิเตอร์^{[ 3 ]}${\displaystyle m}$${\displaystyle x_{k+1}}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$

เมื่อพิจารณาถึงอัลกอริธึมที่อธิบายไว้ข้างต้น การเลือกในแต่ละรอบการทำซ้ำสามารถปรับเปลี่ยนได้ ความเป็นไปได้ประการหนึ่งคือการเลือกสำหรับแต่ละรอบการทำซ้ำ(บางครั้งเรียกว่าการเร่งความเร็วของ Anderson โดยไม่มีการตัดทอน) ^{[ 3 ]}ด้วยวิธีนี้ ทุกรอบการทำซ้ำใหม่จะถูกคำนวณโดยใช้รอบการทำซ้ำที่คำนวณไว้ก่อนหน้านี้ทั้งหมด เทคนิคที่ซับซ้อนกว่านั้นขึ้นอยู่กับการเลือกเพื่อให้รักษาสภาพที่มีขนาดเล็กพอสำหรับปัญหาของกำลังสองน้อยที่สุด^{[ 3 ]}${\displaystyle m_{k}}$${\displaystyle m_{k}=k}$${\displaystyle k}$${\displaystyle x_{k+1}}$${\displaystyle m_{k}}$

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

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

• Eyert ^{[ 6 ]}และ Fang และ Saad ^{[ 4 ]}ตีความอัลกอริทึมภายในคลาสของ วิธีการ กึ่งนิวตันและวิธีการหลายเซแคนต์ ซึ่งเป็นการขยายวิธีการเซแคนต์ ที่รู้จักกันดี สำหรับการแก้สมการไม่เชิงเส้นพวกเขายังแสดงให้เห็นว่าสามารถมองแผนการนี้เป็นวิธีการในคลาส Broyden ^ได้ อย่างไร [ ^{7 ]}${\displaystyle g(x)=0}$
• Walker และ Ni ^{[ 3 ] [ 8 ]}แสดงให้เห็นว่าแผนการเร่งความเร็วของ Anderson เทียบเท่ากับ วิธีการ GMRESในกรณีของปัญหาเชิงเส้น (เช่น ปัญหาของการหาคำตอบสำหรับเมทริกซ์จัตุรัสบางตัว) และจึงสามารถมองได้ว่าเป็นการขยาย GMRES ไปสู่กรณีที่ไม่เป็นเชิงเส้น ผลลัพธ์ที่คล้ายกันนี้พบโดย Washio และ Oosterlee ^{[ 9 ]}${\displaystyle A\mathbf {x} =\mathbf {x} }$${\displaystyle A}$

นอกจากนี้ ผู้เขียนคนอื่นๆ ได้พัฒนาวิธีการที่เทียบเท่าหรือเกือบเทียบเท่ากันหลายวิธีโดยอิสระ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ]}แม้ว่าส่วนใหญ่จะอยู่ในบริบทของการประยุกต์ใช้งานเฉพาะที่น่าสนใจมากกว่าที่จะเป็นวิธีการทั่วไปสำหรับสมการจุดคงที่

ต่อไปนี้เป็นตัวอย่างการใช้งานใน ภาษา MATLABของวิธีการเร่งความเร็วแบบแอนเดอร์สัน (Anderson acceleration scheme) สำหรับการค้นหาจุดตรึง (fixed-point) ของฟังก์ชันโปรดสังเกตว่า: ${\displaystyle f(x)=\sin(x)+\arctan(x)}$

• ปัญหาการหาค่าเหมาะสมที่สุดได้รับการแก้ไขในรูปแบบโดยใช้การแยกส่วน QR${\displaystyle \gamma _{k}=\operatorname {argmin} _{\gamma \in \mathbb {R} ^{m_{k}}}\|g_{k}-{\mathcal {G}}_{k}\gamma \|_{2}}$
• การคำนวณการแยกส่วน QR นั้นไม่เหมาะสม: จริงๆ แล้วในแต่ละรอบ จะมีการเพิ่มคอลัมน์เดียวลงในเมทริกซ์และอาจมีการลบคอลัมน์เดียวออกไป ข้อเท็จจริงนี้สามารถนำมาใช้เพื่ออัปเดตการแยกส่วน QR ได้อย่างมีประสิทธิภาพด้วยความพยายามในการคำนวณที่น้อยลง^{[ 14 ]}${\displaystyle {\mathcal {G}}_{k}}$
• สามารถทำให้ขั้นตอนวิธีมีประสิทธิภาพในการใช้หน่วยความจำมากขึ้นได้โดยการจัดเก็บเฉพาะการวนซ้ำและค่าความคลาดเคลื่อนล่าสุดไม่กี่รายการ หากไม่จำเป็นต้องใช้ เวกเตอร์ของการวนซ้ำทั้งหมด${\displaystyle x_{k}}$
• โค้ดนี้สามารถขยายไปใช้กับกรณีของค่าเวกเตอร์ได้โดยตรง${\displaystyle f(x)}$

f = @( x ) sin ( x ) + atan ( x ); % ฟังก์ชันที่ต้องการคำนวณจุดคงที่x0 = 1 ; % ค่าเริ่มต้นที่คาดเดาk_max = 100 ; % จำนวนรอบการทำซ้ำสูงสุดtol_res = 1e-6 ; % ค่าความคลาดเคลื่อนของค่าตกค้างm = 3 ; % พารามิเตอร์ mx = [ x0 , f ( x0 )]; % เวกเตอร์ของค่าที่ได้จากการวนซ้ำ x g = f ( x ) - x ; % เวกเตอร์ของค่าความคลาดเคลื่อนG_k = g ( 2 ) - g ( 1 ); % เมทริกซ์ของส่วนเพิ่มในค่าตกค้างX_k = x ( 2 ) - x ( 1 ); % เมทริกซ์ของส่วนเพิ่มใน xk = 2 ; ในขณะที่k < k_max และabs ( g ( k )) > tol_res m_k = min ( k , m ); % แก้ปัญหาการหาค่าเหมาะสมที่สุดโดยใช้การแยกส่วน QR [ Q , R ] = qr ( G_k ); gamma_k = R \ ( Q ' * g ( k )); % คำนวณค่าวนซ้ำใหม่และค่าตกค้างใหม่x ( k + 1 ) = x ( k ) + g ( k ) - ( X_k + G_k ) * gamma_k ; g ( k + 1 ) = f ( x ( k + 1 )) - x ( k + 1 ); % อัปเดตเมทริกซ์การเพิ่มขึ้นด้วยองค์ประกอบใหม่X_k = [ X_k , x ( k + 1 ) - x ( k )]; G_k = [ G_k , g ( k + 1 ) - g ( k )]; n = size ( X_k , 2 ); ถ้าn > m_k X_k = X_k (:, n - m_k + 1 : end ); G_k = G_k (:, n - m_k + 1 : end ); end k = k + 1 ; end% พิมพ์ผลลัพธ์: คำนวณจุดคงที่ได้ 2.013444 หลังจาก 9 รอบfprintf ( "คำนวณจุดคงที่ได้ %f หลังจาก %d รอบ\n" , x ( end ), k );

• จุดคงที่
• การวนซ้ำจุดคงที่
• อัลกอริทึมค้นหาราก