ในการวิเคราะห์เชิงตัวเลขกระบวนการเดลต้ากำลังสองของ Aitkenหรือการประมาณค่าแบบ Aitkenเป็น วิธี การเร่งความเร็วอนุกรมที่ใช้เพื่อเร่งอัตราการลู่เข้าของลำดับ วิธีนี้ตั้งชื่อตามAlexander Aitkenผู้ซึ่งแนะนำวิธีนี้ในปี 1926 ซึ่งเป็นส่วนหนึ่งของการขยาย วิธีการ ของBernoulli ^{[ 1 ]}วิธีนี้มีประโยชน์มากที่สุดสำหรับการเร่งการลู่เข้าของลำดับที่ลู่เข้าเชิงเส้น รูปแบบเบื้องต้นเป็นที่รู้จักของSeki Kōwa (1642 – 1708) และนำไปใช้กับการหาค่าที่ถูกต้องของวงกลม กล่าวคือ การคำนวณค่า π

เมื่อกำหนดลำดับที่มีกระบวนการเดลต้ากำลังสองของ Aitken แล้ว ลำดับใหม่จะเชื่อมโยงกับลำดับนี้${\displaystyle X={(x_{n})}}$${\displaystyle n=0,1,2,3,\ldots ,}$

$${\displaystyle A[X]=(a_{n})={\left({\frac {x_{n}\,x_{n+2}-x_{n+1}^{2}}{x_{n}+x_{n+2}-2\,x_{n+1}}}\right)},}$$

ซึ่งสามารถเขียนได้อีกแบบว่า

$${\displaystyle A[X]=\left(x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}}\right),}$$

ทั้งสองแบบเป็นลำดับเดียวกันทางพีชคณิต แต่แบบหลังมีเสถียรภาพเชิงตัวเลข ที่ดีกว่า ในการนำไปใช้ในการคำนวณ${\textstyle \Delta x_{n}=x_{n+1}-x_{n}}$${\textstyle \Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n}.}$

${\textstyle A[X]}$จะไม่สามารถนิยามได้อย่างชัดเจนหากลำดับนั้นมีองค์ประกอบที่เป็นศูนย์ ซึ่งเกิดขึ้นหากลำดับของผลต่างไปข้างหน้ามีพจน์ที่ซ้ำกัน จากมุมมองทางทฤษฎี หากสิ่งนั้นเกิดขึ้นเฉพาะกับดัชนีจำนวนจำกัดเท่านั้น เราสามารถใช้กระบวนการ Aitken กับส่วนของลำดับที่มีดัชนี ที่ทำให้เป็นดัชนีสุดท้ายที่ลำดับ ซ้ำกันได้ ในทางปฏิบัติ พจน์แรกๆ ของลำดับมักให้ความแม่นยำที่ต้องการ นอกจากนี้ เมื่อคำนวณลำดับด้วยวิธีเชิงตัวเลข เราต้องระมัดระวังในการหยุดการคำนวณก่อนที่ข้อผิดพลาดในการปัดเศษในตัวส่วนจะมากเกินไป เนื่องจากการแปลงลำดับอาจทำให้ตัวเลขสำคัญ หายไป ได้${\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_{n})}$${\textstyle \Delta [X]=(\Delta x_{n}),}$${\displaystyle X}$${\displaystyle n>n_{0}}$${\displaystyle n_{0}}$${\textstyle \Delta [X]}$${\textstyle \Delta ^{2}}$

กระบวนการเดลต้ากำลังสองของ Aitken เป็น วิธี การเร่งการล convergenceและเป็นกรณีพิเศษของการแปลงลำดับที่ไม่เป็นเชิงเส้น

ลำดับที่ลู่เข้าสู่ค่าจำกัดเรียกว่าลู่เข้าเชิงเส้นหรือในทางเทคนิคเรียกว่าลู่เข้าเชิงเส้นแบบ Q ถ้ามีจำนวนบางจำนวนซึ่ง${\textstyle X=(x_{n})}$${\textstyle \ell }$${\textstyle \mu \in (0,1)}$

$${\displaystyle \lim _{n\to \infty }{\frac {|x_{n+1}-\ell |}{|x_{n}-\ell |}}=\mu .}$$

นี่หมายความว่าในทางอนุกรมอนันต์ ระยะห่างระหว่างลำดับและลิมิตของมันจะลดลงในสัดส่วนที่เกือบเท่ากันในทุกขั้นตอน และอัตราส่วนของการลดลงจะเข้าใกล้สัดส่วนนั้นมากขึ้นเรื่อยๆ บางครั้งเรียกสิ่งนี้ว่า "การลู่เข้าเชิงเรขาคณิต" เนื่องจากเป็นคุณสมบัติเฉพาะของอนุกรมเรขาคณิตหรือ "การลู่เข้าแบบเอกซ์ponential" เนื่องจากเป็นการลู่เข้าในลักษณะเดียวกัน${\displaystyle \mu ,}$${\displaystyle \mu ^{n}=\exp(n\ln \mu ).}$

วิธีของ Aitken จะช่วยเร่งการลู่เข้าของลำดับหากลำดับนั้นสอดคล้องกับเงื่อนไขที่กำหนดไว้ข้างต้น${\displaystyle X}$${\displaystyle A[X]=(a_{n}),}$${\textstyle \lim _{n\to \infty }{\frac {a_{n}-\ell }{x_{n}-\ell }}=0.}$

${\displaystyle A}$ไม่ใช่ตัวดำเนินการเชิงเส้นบนลำดับ แต่เป็นตัวดำเนินการเชิงเส้นเมื่อเทียบกับการบวกของลำดับคงที่: ถ้า เป็นลำดับคงที่ใดๆจะเป็นค่าคงที่สำหรับทุกซึ่งเห็นได้ชัดจากการแสดงออกของในรูปของตัวดำเนินการผลต่างจำกัด${\textstyle A[X-C]=A[X]-C,}$${\displaystyle C}$${\displaystyle C=(c)}$${\displaystyle n.}$${\displaystyle A[X]}$${\displaystyle \Delta .}$

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

จากประสบการณ์ การดำเนินการ Aช่วยขจัด "พจน์ความคลาดเคลื่อนที่สำคัญที่สุด" สามารถตรวจสอบได้โดยพิจารณาลำดับในรูปแบบโดยที่: ลำดับนี้จะเข้าใกล้ลิมิตเมื่อเข้าใกล้ศูนย์${\displaystyle x_{n}=\ell +a^{n}+b^{n}}$${\displaystyle 0<b<a<1}$${\displaystyle A[X]}$${\textstyle \ell }$${\displaystyle b^{n}}$

ในทางเรขาคณิต กราฟของฟังก์ชันเลขชี้กำลังที่สอดคล้องกับเงื่อนไขและจะมีเส้นกำกับแนวนอนที่(ถ้า)${\displaystyle f(t)}$${\displaystyle f(n)=x_{n}}$${\displaystyle f(n+1)=x_{n+1}}$${\displaystyle f(n+2)=x_{n+2}}$${\displaystyle {\frac {x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}}}$${\displaystyle x_{n}-2x_{n+1}+x_{n+2}\neq 0}$

นอกจากนี้ยังสามารถแสดงได้ว่า หากลำดับลู่เข้าสู่ค่าลิมิตด้วยอัตราที่มากกว่า 1 อย่างชัดเจนก็ไม่ได้หมายความว่าจะมีอัตราการลู่เข้าที่ดีกว่า (ในทางปฏิบัติ การลู่เข้าแบบกำลังสองนั้นเกิดขึ้นได้ยาก ซึ่งหมายความว่าจะได้ค่าทศนิยมที่ถูกต้องมากกว่า 30 (หรือ 100) ตำแหน่งหลังจาก 5 (หรือ 7) รอบการคำนวณ (โดยเริ่มจากค่าที่ถูกต้อง 1 ตำแหน่ง) โดยปกติแล้วในกรณีนั้นไม่จำเป็นต้องเร่งความเร็ว)${\displaystyle X}$${\displaystyle \ell }$${\displaystyle A[X]}$

ในทางปฏิบัติ การคำนวณมักจะลู่เข้าสู่ค่าลิมิตได้เร็วกว่า การคำนวณแบบ อื่น ดังที่แสดงให้เห็นในตัวอย่างการคำนวณด้านล่าง โดยปกติแล้ว การคำนวณแบบนี้จะประหยัดกว่ามาก(เกี่ยวข้องกับการคำนวณผลต่าง การคูณ และการหารเพียงครั้งเดียว) มากกว่าการคำนวณจำนวนพจน์ที่มากกว่าของลำดับอย่างไรก็ตาม ต้องระมัดระวังไม่ให้เกิดข้อผิดพลาดเนื่องจากความแม่นยำไม่เพียงพอในการคำนวณผลต่างระหว่างตัวเศษและตัวส่วนของนิพจน์${\displaystyle A[X]}$${\displaystyle X}$${\displaystyle A[X]}$${\displaystyle X}$

ตัวอย่างที่ 1 : ค่าของสามารถประมาณได้โดยการกำหนดค่าเริ่มต้นสำหรับและทำซ้ำตามลำดับต่อไปนี้ ซึ่งเรียกว่าวิธีของเฮรอน : เริ่มต้นด้วย${\displaystyle {\sqrt {2}}\approx 1.4142136}$${\displaystyle x_{0}}$$${\displaystyle x_{n+1}={\frac {x_{n}+{\frac {2}{x_{n}}}}{2}}.}$$${\displaystyle x_{0}=1:}$

เป็นที่น่าสังเกตว่า วิธีของ Aitken ไม่ได้ช่วยประหยัดค่าใช้จ่ายในการคำนวณสองรอบ การคำนวณค่าสามค่าแรกต้องใช้ค่าห้าค่าแรก นอกจากนี้ค่าที่สองมีความแม่นยำน้อยกว่าค่าที่สี่ ซึ่งไม่น่าแปลกใจเนื่องจากกระบวนการของ Aitken เหมาะที่สุดสำหรับลำดับที่ลู่เข้าแบบเชิงเส้นมากกว่าแบบกำลังสอง และวิธีของ Heron ในการคำนวณรากที่สองนั้นลู่เข้าแบบกำลังสอง${\textstyle A[X]}$${\textstyle X}$${\textstyle A[X]}$${\textstyle X}$

ตัวอย่างที่ 2 : ค่าของ π สามารถคำนวณได้โดยใช้ผลรวมอนันต์ผ่านสูตรของไลบ์นิซสำหรับπ :${\displaystyle {\frac {\pi }{4}}}$

$${\displaystyle {\frac {\pi }{4}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}\approx 0.785398}$$

ในตัวอย่างนี้ วิธีของ Aitken ถูกนำมาใช้กับอนุกรมที่ลู่เข้าแบบไม่เป็นเชิงเส้น และช่วยเร่งการลู่เข้าได้อย่างมาก การลู่เข้ายังคงเป็นแบบไม่เป็นเชิงเส้น แต่เร็วกว่าการลู่เข้าแบบเดิมมาก กล่าวคือค่าแรกซึ่งการคำนวณต้องใช้ค่าสามค่าแรกนั้นอยู่ใกล้กับค่าลิมิตมากกว่าค่า ที่แปด${\textstyle A[X]}$${\textstyle X}$${\textstyle X}$

ต่อไปนี้เป็นตัวอย่างของการใช้การประมาณค่าแบบ Aitken เพื่อช่วยหาลิมิตของลำดับเมื่อกำหนดค่าเริ่มต้นบางค่าโดยที่ลิมิตของลำดับนี้ถือว่าเป็นจุดคงที่(เช่น) ตัวอย่างเช่น ถ้าลำดับกำหนดโดย โดยมีจุดเริ่มต้นที่ ฟังก์ชันจะเป็นซึ่งมีเป็นจุดคงที่ (ดูวิธีการคำนวณรากที่สอง ) ค่าของจุดคงที่นี้จะถูกประมาณค่า${\displaystyle x_{n+1}=f(x_{n})}$${\displaystyle x_{0},}$${\displaystyle f}$${\displaystyle \alpha =f(\alpha )}$${\textstyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {2}{x_{n}}}\right)}$${\displaystyle x_{0}=1,}$${\textstyle f(x):={\frac {1}{2}}\left(x+{\frac {2}{x}}\right),}$${\displaystyle \alpha$ :={\sqrt {2}}}

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

%ตัวเลือกเหล่านี้ขึ้นอยู่กับปัญหาที่กำลังแก้ไขx0 = 1 %ค่าเริ่มต้นf ( x ) = ( 1 / 2 ) * ( x + 2 / x ) %ฟังก์ชันที่หาองค์ประกอบถัดไปในลำดับtolerance = 10 ^- 10 %ต้องการความแม่นยำ 10 หลักepsilon = 10 ^- 16 %ห้ามหารด้วยจำนวนที่น้อยกว่าค่านี้maxIterations = 20 %ห้ามทำการวนซ้ำไปเรื่อยๆhaveWeFoundSolution = false %เราสามารถหาคำตอบได้ภายในค่าความคลาดเคลื่อนที่ต้องการหรือไม่? ยังไม่สำหรับi = 1 : จำนวนการวนซ้ำสูงสุดx1 = f ( x0 ) x2 = f ( x1 )ถ้า( x1 ~= x0 ) lambda = absoluteValue (( x2 - x1 ) / ( x1 - x0 )) %ตัวเลือกเสริม: คำนวณค่าประมาณของ |f'(fixedPoint)| ซึ่งแสดงด้วย lambda endตัวหาร= ( x2 - x1 ) - ( x1 - x0 );ถ้า( ค่าสัมบูรณ์ของตัวหาร< เอปซิลอน) %เพื่อหลีกเลี่ยงข้อผิดพลาดที่เพิ่มขึ้นอย่างมาก อย่าหารด้วยตัวเลขที่เล็กเกินไปพิมพ์( 'คำเตือน: ตัวหารเล็กเกินไป' ) หยุด%ออกจากลูปสิ้นสุดaitkenX = x2 - ( ( x2 - x1 ) ^ 2 ) / ตัวหารถ้า( ค่าสัมบูรณ์( aitkenX - x2 ) < ค่าความคลาดเคลื่อน) %ถ้าค่าอยู่ในช่วงความคลาดเคลื่อนพิมพ์( "จุดคงที่คือ " , aitkenX )) %แสดงผลลัพธ์ของการประมาณค่าแบบ Aitken haveWeFoundSolution = true break %เสร็จแล้ว ออกจากลูปendx0 = aitkenX %อัปเดต x0 เพื่อเริ่มต้นใหม่endถ้า( haveWeFoundSolution == false ) %ถ้าเราไม่สามารถหาคำตอบได้ภายในค่าความคลาดเคลื่อนที่ต้องการพิมพ์( "คำเตือน: ไม่สามารถหาคำตอบได้ภายในค่าความคลาดเคลื่อนที่ต้องการ" , tolerance ) พิมพ์( "ค่าประมาณที่คำนวณได้ครั้งล่าสุดคือ " , aitkenX ) end

• อัตราการบรรจบกัน
• ขีดจำกัดของลำดับ
• การวนซ้ำจุดคงที่
• การคาดการณ์ของริชาร์ดสัน
• การแปลงลำดับ
• การแปลงแชงค์
• วิธีการของสเตฟเฟนเซ่น