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

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

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

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

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

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

นั่นหมายความว่าในทางอนุกรมวิธาน ระยะห่างระหว่างลำดับและลิมิตของมันจะลดลงในสัดส่วนที่เกือบเท่ากัน${\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[XC]=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}$)

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

ในทางปฏิบัติ${\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 ไม่ได้ช่วยประหยัดค่าใช้จ่ายในการคำนวณสองรอบในที่นี้ การคำนวณสามรอบแรกยังคงใช้ต้นทุนเดิม${\textstyle A[X]}$ค่าที่ต้องการห้าค่าแรก${\textstyle X}$ค่าต่างๆ นอกจากนี้ ข้อที่สอง${\textstyle A[X]}$ค่าที่ได้มีความแม่นยำน้อยกว่าค่าที่ 4${\textstyle X}$ค่าดังกล่าวไม่น่าแปลกใจ เนื่องจากกระบวนการของ Aitken เหมาะที่สุดสำหรับลำดับที่ลู่เข้าแบบเชิงเส้น มากกว่าแบบกำลังสอง และวิธีการของ Heron ในการคำนวณรากที่สองนั้นลู่เข้าแบบกำลังสอง

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

%ตัวเลือกเหล่านี้ขึ้นอยู่กับปัญหาที่กำลังแก้ไข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

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